Medium Flashcards
medium probs
Print a binary tree in an m*n 2D string array following these rules:
In every recursive call, we do as follows:
If we’ve reached the end of the tree, i.e. if root==null, return.
Determine the column in which the current element(root) needs to be filled, which is the middle of ll and rr, given by say, j. The row number is same as ii. Put the current element at res[i][j]res[i][j].
Make the recursive call for the left child of the rootroot using fill(res, root.left, i + 1, l, (l + r) / 2).
Make the recursive call for the right child of the rootroot using fill(res, root.right, i + 1, (l + r + 1) / 2, r).
How to find the height of a tree from a root.
public int getHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
fill function usage in java
String[][] res = new String[height][(1 << height) - 1];
for(String[] arr:res)
Arrays.fill(arr,””);
1 << x
2^x
2^x
1 << x
< List < List > > ans
= new ArrayList<>()
Random Pick Index
public int pick(int target) {
int result = -1; int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != target)
continue;
if (rnd.nextInt(++count) == 0)
result = i;
}
return result;
}
< List > ans
= new ArrayList<>()
Exclusive Time of Functions
Time complexity : O(n). We iterate over the entire logslogs array just once. Here, n refers to the number of elements in the logs list.
Space complexity : The stack can grow upto a depth of atmost n/2. Here, nn refers to the number of elements in the given logslogs list.
How to initialize a stack in java
Stack<integer> st = new Stack<>();</integer>
How to split a string with delimiter :
String[] s = log.split(“:”);
How to convert string to integer in java
int curr = Integer.parseInt(s[2]);
or
int curr = Integer.parseInt(“2”);
how to find if stack is empty in java
st.isEmpty()
stack operstions in java
st. peek()
st. push(1); or st.push(Integer.parseInt(s[0]));
st,pop()
create array of size n in java
int [] res = new int[n];
Random Pick with Weight
say we have the numbers 1, 5, 2 easiest solution is to construct the following array
arr[] = {0,1,1,1,1,1,2,2}
then generate a random number between 0 and 7 and return the arr[rnd].
The solution here is similar but instead we construct the following array (accumulated sum)
{1, 6, 8} generate a number between 1-8 and say all numbers generated up to 1 is index 0. all numbers generated greater than 1 and up to 6 are index 1 and all numbers greater than 6 and up to 8 are index 2. After we generate a random number to find which index to return we use binary search.
Container With Most Water
Time complexity : O(n). Single pass.
Space complexity : O(1). Constant space is used.
The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
All other containers are less wide and thus would need a higher water level in order to hold more water.
The smaller one of first and last line doesn’t support a higher water level and can thus be safely removed from further consideration.
Best Time to Buy and Sell Stock II
Time complexity : O(n). Single pass.
Space complexity: O(1). Constant space needed.
Find First and Last Position of Element in Sorted Array
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Time complexity : O(log10(n))
Because binary search cuts the search space roughly in half on each iteration, there can be at most ⌈log10(n)⌉ iterations. Binary search is invoked twice, so the overall complexity is logarithmic.
Space complexity : O(1)
Given a nested list of integers, implement an iterator to flatten it.
Input: [[1,1],2,[1,1]] Output: [1,1,2,1,1]
* // This is the interface for creating nested lists.
* public interface NestedInteger {
*
* @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* @return the single integer that this NestedInteger holds, if it holds a single integer
Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* @return the nested list that this NestedInteger holds, if it holds a nested list
Return null if this NestedInteger holds a single integer
* public List<nestedinteger> getList();</nestedinteger>
Given an array of strings, group anagrams together.
Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output: [[“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ]
is not important
Time Complexity: O(NK), where N is the length of strs, and K is the maximum length of a string in strs. Counting each string is linear in the size of the string, and we count every string.
Space Complexity: O(NK), the total information content stored in ans.
Solve the Equation
Time complexity : O(n). Generating coefficients and findinn lhs and rhs will take O(n)
Space complexity : O(n)
Search in Rotated Sorted Array
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
time complexity - O(log N)
Decode Ways
Input: “226” Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).
public String substring(int startIndex)
public String substring(int startIndex, int endIndex)
startIndex: inclusive
endIndex: exclusive
Valid Sudoku
O(N^2)
Trapping Rain Water
Trapping Rain Water
C++
Time complexity: O(n)
We store the maximum heights upto a point using 2 iterations of O(n) each.
We finally update ans using the stored values in O(n)
Space complexity: O(n)extra space.
Additional O(n) space for left_max and right_max arrays
