Amazon interview prep

B. 2

At index 2 the left sum is 1 + 3 = 4 and the right sum is 2 + 2 = 4. To find it in O(n), take the total once, then walk the array keeping the left sum: the right sum at i is total - left - a[i].

A. cd

Removing "bbb" brings the two a's next to the third, making "aaacd", and removing "aaa" leaves "cd". A stack of (letter, count) pairs does it in one pass: add to the top count when the letter matches, and pop when the count reaches 3.

A. They are at the same depth but have different parents

Same depth, different parents. Nodes with the same parent are siblings. A level-order traversal that records each node's depth and parent checks it in O(n).

C. 20

dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|), giving dp = [0, 10, 20, 20]: jump 0 -> 1 -> 3 for 10 + 10. Each stone needs only the two before it, so O(n) time and O(1) space.

D. Depth-first search with backtracking, starting from every cell that matches the first letter

From a matching cell, try the four neighbours for the next letter. Mark the cell as used on the way in and unmark it on the way out, so another path can still use it. Counting letters ignores where they are.

C. Level-order (breadth-first) traversal

Level order visits each level left to right, so each node's next is just the node visited after it in the same level. For a perfect binary tree it can even be done with O(1) extra space by walking the next pointers of the level above.

D. 3

The longest path is LL - L - root - R, which has 3 edges. In general, for each node take (height of left subtree) + (height of right subtree) and keep the maximum, all in one O(n) traversal.

D. The word's letters sorted, such as "aet", or a count of each letter

Anagrams share the same multiset of letters, so the sorted letters (O(k log k)) or a 26-letter count (O(k)) is identical for all of them. Words with the same key go in the same group.

C. A hash map from key to node, a hash map from frequency to a doubly linked list of keys with that frequency, and the current minimum frequency

A hit moves the key from list f to list f + 1. Each list is in recency order, so evicting takes the oldest key in the min-frequency list, and min resets to 1 when a new key arrives.

D. Traverse with BFS or DFS, keeping a map from each original node to its copy; create a copy the first time a node is seen and reuse it after that

The map is what stops cycles from recursing forever and makes every edge point at the copies. Each node and edge is handled once: O(V + E).

C. 12421

Mirroring the left half gives 12321, which is smaller than 12345, so increase the middle digit and mirror again: 12421. The general method mirrors, then increments the middle with carries if needed.