3 ms·
> If Dan isn’t passing your algorithms interview, it’s not testing what you think it is. I think it's also much easier to see/solve problems in practice than o
by BeetleB 2y ago
> If Dan isn’t passing your algorithms interview, it’s not testing what you think it is.
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.
- chipdart 2y ago> I quickly realized that the map had a high overhead - all those pointers in a red-black tree consume more RAM than my data! That is true if you use std::map , which should only be used if you have a strong requirement in having sorted keys. If you do not have a requirement to keep sorted keys, you should use std::unordered_map which internally implements a dictionary as a hash table, exactly as std::unordered_set. > 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 you used std::unordered_map instead, you would be doing the same thing with a constant-time computational complexity instead of logarithmic, while retaining linear space complexity.