Algorithms Interviews: Theory vs. Practice (2020)

On phone, so will be brief. Will try a longer response later. (Apologies to other responses, not hitting them all.)

Basic point is that many will abstract out data to different locations and ownership lifetimes. So, congrats, you kept us at a lower complexity, but failed to realize you need to first essentially reindex all of the data for that to happen.

Now, I grant that often the problem is more in the data scattered over any number of databases. If there are reasons to keep that spread, though, hard to just sweep it aside.

And then there are those that don't accept, "send it to a solver." Really annoying how often people assume they can easily beat cplex and friends.

I worked at a very large company (over 100K employees) for over a decade. I definitely encountered problems where knowing complexity and graph algorithms helped. Not knowing them would have cost the company almost nothing.

I think you're subject to survivorship bias. Many (most?) large Fortune 500 companies make the bulk of their money by simple business logic and grunt work. Not by scaling. Internet based companies (which are the minority) are outliers.

I think it's also much easier to see/solve problems in practice than on a theoretical whiteboard.

I've rarely had to use Leetcode level algorithms at work. But when I did, it was much easier to solve than if I'd been given the exact same problem without the context of the experience I'd accumulated working on the project.

Example: I wrote a C++ program that stored a large number of 32 bit numbers[1] in a map (both key and value were 32 bits). When I ran the program, it ran out of memory (something like 80GB of RAM). I quickly realized that the map had a high overhead - all those pointers in a red-black tree consume more RAM than my data! As I was storing only once and doing lookups many times, it was simpler to simply sort all the keys, and then store the values. When I needed to do a lookup, I'd do a binary search and find it. Algorithmically same complexity as a map.

If someone gave me this problem as a whiteboard, I'd implement the map based solution, and would really struggle if I started getting questions about memory performance, and it would be silly to ding me for not choosing a binary search. In reality, my screwup was extremely simple to solve - given that I had a good understanding of the problem domain - something lacking in a whiteboard interview.

So in general, people who do poorly in those whiteboard interviews may well solve the exact same problem with ease in an actual work situation.

Another example: I wrote a DAG and needed to check if two (arbitrary) nodes were connected. I chose a fairly inefficient algorithm - recursive backtracking with no memoization. If I've already computed that B is connected to C, and I know A is connected to B, I don't need to run the whole algorithm to know that A is connected to C.

I wrote the simple, inefficient version, knowing it was a poor algorithm. But my reasoning was that I wanted to write all my tests with corner cases working before I fixed the performance.

Once I had all the tests written, I returned to optimize the algorithm. Then I said "Heck, let's see how bad it is with real world data."

The algorithm was fast. Even when I significantly increased N. How come?

Oh, it's because due to real world limitations in the problem I was solving, the maximum distance between any 2 nodes I was comparing was 7. Yes, in the abstract, it seemed very inefficient, but when you apply real world limitations, you realize there is nothing to gain by making it more efficient. Leetcode biased folks would have made the code more complex for little gain.

[1] Maybe it was 64 bit - I forget.

If you're biggest worry about leetcode is does this language need a semi-colon at the end then I doubt you have trouble interviewing.

---

Do you do much interviewing as an interviewer?