The interviewer was a principal from Caltech. He talked fast and used a lot of technical jargon, like a college professor would. It was rushed, only 30 minutes.
Explain a sorting algorithm better than O(N^2).
Merge sort — recursively split the array into left and right halves until there are only 2 elements left, then merge by inserting the smaller of the two into a new array and returning it (N log N). Most VMs actually use an improved version of merge sort (JS's V8 uses Timsort).
Explain a sorting algorithm worse than O(N^2). What's the worst algorithm you can think of?
Random sort (no upper bound on time). Generate all permutations (N!).
Given 4 distinct cups of coffee, 2 from coffee shop A and 2 from shop B, with scores that are random and fair, what's the probability that both of A's coffees rank higher than both of B's coffees?
(2×1×2×1) / 4! — there are 2 ways to arrange the first A relative to the remaining A, and 2 ways to arrange the first B relative to the remaining B, so you need Ax2 > Ax1 > Bx2 > Bx1 out of 4P4, i.e. 4! total orderings.
Review a piece of code — what's wrong with it?
This question doesn't really make sense in JavaScript, honestly, because the point of it is to discuss race conditions and parallel threading. Toward the end I was having a bit of trouble following, so I switched to explaining it in C++ terms instead, using a mutex lock for threads.
The basic issue is that a read happening during a set can get a stale value, and it's also missing a GC/cache eviction policy — otherwise you'd need unlimited memory. For JS you'd need a queue scheduler, blocking writes, and parallel reads — there's no real threading since JS is single-threaded. For C++ you'd need a mutex lock for multithreading.
The interviewer said he has versions of this question in 12 different languages, but what's actually being tested is race conditions, mutexes, threading, garbage collection, and eviction policy.
const cache = new Map()
function retrieve(key, val) {
if (cache.has(key)) {
return cache.get(key)
}
const newVal = await longRunningFn(key)
cache.set(key)
return newVal
}
I hadn't talked through sorting algorithms in a long time myself. I only got to the mutex and GC parts because the interviewer hinted at them — this one might be more suited to someone who just finished school as a new grad. From what I've seen in other people's interview reports it's pretty similar to this. The caching question is genuinely hard to review for without seeing actual code.
Discussion
Loading comments…