Facebook LeetCode

Question 1

Diagonal Traversal - given a NxM matrix, iterate it diagonally

Answer 1

1. The sum of indicies i,j for an entry in the NXM matrix is the same for all entries in a diagonal.
2. The direction of the diagonal is dependent on the remainder of the sum, i.e. 0 or 1 when i+j mod 2.
3. The number of diagonals is equal to N+M+1.

Algorithm

1. Use a hashmap where the key is the sum(i,j) and the value is a list of all values whose i,j index sums to i+j.
2. Iterate from 0 to number of diagonals, using the iteration index as a key into the hashmap. Depending on i+j mod 2, append the values from the hashmap in reverse or normal order.

Question 2

Continuous sub-array sum - find a sub-array that sums to a multiple of k

Answer 2

1. use a prefix sum
2. if the remainder of some prefix sum at i is found when computing the remainder of a prefix sum at j where i < j, then a sub-array between (i, j] is a multiple of k.
3. use a hashmap where the key is a remainder and the value is the index of the prefix sum at i mod k

Algorithm

1. define a hashmap and init a prefix sum
2. iterate the array, compute the remainder of the prefix sum, and check the following. if the remainder is 0 but i+1 > 1 then return true (corner case where you found multiple of k near the beginning of the array) or if the remainder is in the hashmap and the distance between the two indicies is greater than 2 then return true else add the remainder and index to the hashmap
3. if the loop ends then return false.

Question 3

Find peak element - return the index where a[i] is strictly greater than its neighbors

Answer 3

1. Use binary search.
2. Modify binary search to look left if the left neighbor > mid else go right.

Algorithm

1. init left and right pointers
2. while left < right, calculate the mid point, and do the following
   i. if mid is > then all neighbor then return the mid
   ii. if mid < then left then binary search on left
   iii. if mid < then right then binary search on right
   iiv. outside while loop just return left or right

Question 4

Shortest Path in a Binary Matrix - distance from (0,0) -> (-1,-1)

Answer 4

Use bfs and a hashmap to keep track of distances. The distance hashmap consist of a key-value pair where the key is the position and the value is the distance that position is from (0,0). Init dist[(0,0)] to be 1.

Corner cases:

1. Check if (0,0) and (-1,-1) are both 0 - 0 is a path, 1 is an obstacle.
2. init dist[(0,0)] to be 1
3. check if popped value is (-1,-1) before looping children - solves input [[0]]

Question 5

Add Strings - add two numbers that are in string representation

Answer 5

Set two points i,j at the ends of the two strings respectively. Set a carry variable to 0. While i,j are greater than 0, extract the string at i and j and use ord() to compute its uni code. Subtract ord("0") from the unicode to get the actual value of the string.
Sum the two values and a carry. If the sum is greater than 10 set carry to 1 else 0. Take value module 10 and append the results to a string builder. Decrement i and j. Outside the while loop, append "1" to result if carry exist. Return results in reverse.

Question 6

Copy List with Random Pointers - Do a deep copy of a linked list. Nodes contain a next and random pointer.

Answer 6

Create a hashmap whose key is the original node and value is a copy of it.
Iterate using a dummy pointer set to the head. In the while loop, hash into the hashmap using the pointer and set the copied node’s next and random.
return the hashmap of the head.

Question 7

Valid Palindrome - change to lowercase and remove all non-alphanumeric characters

Answer 7

Recreate a new string by changing all uppercase to lowercase and remove all non-alphanumeric characters. Then check if the reverse of the string equals itself.

Question 8

Capacity To Ship Packages Within N Days

Answer 8

Do binary search between the max weight and the total weights. In the binary search while loop, determine if the mid value is sufficient. You can determine if if the mid value is sufficient by doing a prefix sum of the weights. If the prefix sum is greater than mid, then increment the days-needed and reset the prefix sum. Once days-needed is greater than N days, return false. If the loop completes, return True. If it is, search the left for, else search the right. When the loop terminates return left or right.

Question 9

Remove All Adjacent Duplicates in String

Answer 9

Use a stack. Iterate through the string and if the stack is not empty, check if top of stack is equal to the character. If it is, the pop the stack else add the char to the stack. Return all values in the stack as a concatenated string.

Question 10

Toeplitz Matrix

Answer 10

To check if the matrix is a toeplitz, we can iterate the matrix using two loops. And check the following in the innermost loop. If the row or column index is 0, continue to the next iteration. If the current value doesn’t equal to its top left neighbor then immediately return False. If the loop completes, return True.

Question 11

Cutting Ribbons - Max ribbon length to achieve K ribbons of the same length.

Answer 11

Do binary search with left set to 1 and right set to max ribbon length. On each iteration compute the number of cuts of length mid by doing ribbon//mid.
If the number of cuts is >= k, then search right else search left.

Question 12

Binary Search Tree Iterator: Inorder Traversal

Answer 12

We utilize a stack to keep track the next value to iterate too. Given a root, keep inserting the root.left nodes into the stack until root is Null. When hasNext() is called return true if the stack is not empty, else false. When next() is called, pop the stack and then keep inserting pop_node.right’s left nodes until null. Then return pop_node.value.