Salesforce interview prep

A. A stack

Push each opening bracket. Each closing bracket must match the bracket on top, which is popped. The string is balanced if every bracket matched and the stack ends empty.

B. O(n log k); it is the smallest element in the heap, at its top

Each number costs O(log k): push it, and pop the minimum when the heap exceeds k. The heap then holds the k largest numbers, and the smallest of those, at the top, is the k-th largest.

B. A depth-first or breadth-first search from the start over open neighbouring cells, marking each cell visited

Reachability is a graph search: each open cell is a node joined to its open neighbours. Marking cells visited keeps it O(rows x columns). BFS also gives the shortest path length.

A. 6, indices 3 to 6

Keep the best sum ending at each index: extend the previous run if it is positive, otherwise start again. The best run is 4, -1, 2, 1 at indices 3 to 6, summing to 6, in one O(n) pass.

A. Two heaps: a max-heap of the smaller half and a min-heap of the larger half, kept within one element of each other in size

The median is the top of the bigger heap, or the average of both tops when the sizes match. Each new number goes into one heap and at most one top moves across to rebalance, both O(log n). A sorted array needs O(n) shifting per insert.

C. Double a bound (1, 2, 4, 8, ...) until a[bound] >= key, then binary search between bound/2 and bound

This is exponential (galloping) search. Doubling reaches past position p in about log p steps, and the binary search inside that last window takes about log p more. Searching up to the largest int would also work but costs log of that bound, not of p.

D. 12

4 letters give 4! = 24 orders, but swapping the two a's gives the same string, so divide by 2! = 2: 12. In general n! divided by the factorial of each letter's count. Generating them by backtracking takes O(n * n!) time.

A. 4

The valid part is "()()" at positions 1 to 4. A stack of indexes, starting with -1, finds it: push on "(", pop on ")", and after a pop the length is i minus the index now on top. The last ")" has nothing to match, so 6 is impossible.

C. Start at the top-right corner: step left while you see a 1, step down on a 0; O(R + C)

Moving left means this row has more 1s than any before it, so remember it; moving down skips a row that cannot beat the best. Each step leaves a row or a column for good, so at most R + C steps. Binary search per row is O(R log C), better than counting but worse than the staircase.

A. Build behaviour by holding other objects that do part of the work, rather than by extending classes

Inheritance ties a subclass to its parent's internals and is fixed when compiled. Holding a collaborator, such as a Logger or a PricingRule, keeps classes loosely coupled and lets the part be swapped.

B. Inheritance models an is-a relationship (a Car is a Vehicle); composition models a has-a relationship by holding other objects as fields (a Car has an Engine)

Composition keeps classes loosely coupled: the engine can be swapped or mocked, and changes inside it do not ripple into Car. Inheritance ties the child to the parent's implementation, which is why "favour composition over inheritance" is common advice.

D. An app that loads one HTML page and then redraws the view in JavaScript as the user moves around, fetching data rather than whole pages

React, Angular and Vue apps are typically SPAs: the router changes the URL with the History API and swaps components without a full reload. The cost is a heavier first load and extra work for search engines, which server rendering addresses.

C. 3

Each weighing has three outcomes (left lighter, right lighter, balance), so k weighings can tell apart at most 3^k coins. 3^2 = 9 is fewer than 12, and 3^3 = 27 is enough: weigh 4 against 4, keep the group of 4 with the fake, then 1 against 1 twice at most.