An Algorithm for Passing Programming Interviews (2020)

Post by dnpp123 » Mon, Jan 03, 2022, 1:22 AM UTC

malisper wrote: post #52

sk5t wrote: post #22

Earlier quoted context omitted.

The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Tabulating call count by division(s) of time would be less obviously problematic.

> The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Even if n elements are scanned in the the worst case, the expected time it takes to perform such a scan is O(1). This is because we perform a scan on each insertion and O(n) elements are deleted in a sc…

Post by taeric » Mon, Jan 03, 2022, 1:26 AM UTC

sk5t wrote: post #58

taeric wrote: post #39

Earlier quoted context omitted.

I'd assume a linked list was used to be able to drop a lot in a single shot. In particular, seems safe to assume the queue is sorted by time. Such that as soon as you see a time that is outside the window, you can drop all of the rest in one shot. The page wasn't loading for me, so I can't see the proposal. Just don't let a linear scan scare you, for small n.

There are various approaches that might or might not improve the runtime outlook (maybe a priority queue, maybe a list that supports fast random access for binary or exponential search, etc.) but wouldn't the only "fast" path to drop a bunch of entries hinge on moving the head reference and pushing the work onto the GC? One might start to think about something like a ring at the point where this would start to matter…

Post by vanusa » Mon, Jan 03, 2022, 1:30 AM UTC

Rebelgecko wrote: post #45

vanusa wrote: post #34

Earlier quoted context omitted.

Yeah - why not just tell them? You know, like IRL. What this is supposedly about. Again, the question referred to the target performance, not the optimal performance.

When I implement something IRL (unless I'm implementing something from a paper or an algorithm that's well known), I typically can't just ask someone what the algorithmic complexity is. I have to determine if for myself. Ed: to clarify a bit, in some cases the "non-optimal" solution is going to be the best one. And that's even before you start worrying about things like time/memory tradeoffs. When a candidate asks me…

Post by Frost1x » Mon, Jan 03, 2022, 1:31 AM UTC

posharma wrote: post #15

ldjkfkdsjnv wrote: post #10

Before people start complaining about leetcode and how it doesnt exemplify skills: its a proxy for a combination of: intelligence and how hard you are willing to study the computer science knowledge shown is just a bonus EDIT: One last thing to throw in, its pretty clear that theres a correlation between the top software companies and how hard their leetcode interviews are. You can claim all you want it doesnt work,…

You've to be a genius to solve a "hard" unseen leetcode problem in 15 mins correctly. Facebook is notorious at expecting candidates to regurgitate solutions to problems in 15 mins. Intelligence plays a lesser role than exhaustive and painful practice which involves solving the same problem multiple times. It's a full-fledged examination that expects you to excel while being constantly watched and judged.

Post by arduinomancer » Mon, Jan 03, 2022, 1:35 AM UTC

malisper wrote: post #32

avl999 wrote: post #12

I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough. If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Re…

There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time. Of course there are even more niche data stru…