JPMorgan Chase interview prep

A. [6, 7] only

Sort by start; an interval is isolated when it starts after the largest end seen so far and ends before the next interval starts. [1, 3] and [2, 4] overlap, as do [9, 12] and [11, 13]. Sorting makes it O(n log n).

B. 3

Sorted by start, [1, 3] and [2, 6] overlap and become [1, 6]; [8, 10] and [15, 18] stand alone. After sorting, one pass that extends the last merged interval or starts a new one: O(n log n).

D. 3 and 2

Greedy takes 4, then 1 and 1: three coins. Two 3s make 6 with two. Greedy is safe for coin sets like 1, 2, 5, 10 but not for every set, so the general minimum-coins problem is solved with dynamic programming: best[a] = 1 + the smallest best[a - c] over every coin c.

B. 1 4 2 3 5

Scan from the right for the first number smaller than the one after it: 3, since 5 4 2 is falling. Swap it with the smallest larger number to its right, 4, giving 1 4 5 3 2, then reverse that falling tail into rising order: 1 4 2 3 5. All in O(n) time and O(1) extra space.

C. 29

Always combine the two smallest, using a min-heap: 2 + 3 = 5, then 4 + 5 = 9, then 6 + 9 = 15, for 5 + 9 + 15 = 29. Small numbers are added into every later sum, so they should be combined first; this is the same idea as Huffman coding, O(n log n) in all.

D. 6

Group the string into runs: 2 zeros, 2 ones, 2 zeros, 2 ones. Each pair of neighbouring runs gives min(a, b) such substrings, so 2 + 2 + 2 = 6: "0011", "01", "1100", "10", "0011" and "01". One pass over the run lengths is O(n).

C. 4 additions, 4884

87 + 78 = 165, 165 + 561 = 726, 726 + 627 = 1353, 1353 + 3531 = 4884, which reads the same both ways. Reverse a number with a loop of n % 10 and n / 10. Some numbers, such as 196, are not known to ever reach a palindrome, so real code caps the number of steps.

D. When each record is read and written as a whole and its fields vary from record to record

A document keeps a record and its nested details together without one fixed schema, which suits catalogues, profiles and event logs. Relational databases are stronger when data is shared between tables and changes must span them in one transaction.

C. Passes the request on to the next middleware or route handler in the chain

Middleware runs in the order it was added, for jobs like logging, parsing JSON bodies or checking a login. If a middleware neither responds nor calls next(), the request hangs. next(err) skips ahead to the error-handling middleware.

C. Running containers across a cluster of machines: scheduling them, restarting failed ones, scaling and load-balancing them

Docker packages an app into a container image; Kubernetes runs many such containers reliably across servers, declared as desired state (deployments, services) that it keeps true.