Coding floyd-warshal importantly shows that you can code, and generally signals at least one of two things:
1. You studied hard for the interview, you're willing to do difficult and unpleasant intellectual work for rewards and do so in a structured enough manner to get results.
2. You have such a deep understanding of graphs and graph algorithms you were able to re-construct floyd-warshal in 45 minutes. This implies time will not be an issue if you see an opportunity for these problems, and you can probably handle much harder problems as well.
Filtering for these two traits might work very well depending on the hiring needs of a particular company.
1. You're fresh out of school or you have a lot of time on your hands.
2. You memorized some interview preparation book.
I do agree that a candidate that has shown some effort preparing for an interview is a positive. Other than that this seems like a silly game.
The flip side is the candidate that memorized the book, prepared like it's a test at school, and is useless on the job, can't operate at all outside that memorized domain, can't write the simplest bit of real world code.
Which is handy because Google et al don't really want employees who look at the in-office perks and wonder why they'd be appealing at all if you're just going to go home at the end of the day.
Consider a world where every L6+ manager candidate has a family and kids. However, only 5% of these can make time to do the LC stuff (revising most likely if they've been managing for a while).
So your company will end up filtering out 95% of candidates immediately, but people in the company will say that there's no problem as all of the successful candidates have a family and kids, so it can't be biased.
Don't get me wrong, I'm a fan of technical screening for managers, but I'm making the point that you can't look at the output of a funnel and conclude that everything's fine, you need to look at the complete funnel to understand this.
I think this leaves out the possibility of high mastery. I think it is instructive think about algorithm skills as similar to those for algebra. If the most advanced algebra you ever solved was linear equations, remembering how to solve a linear equation may be difficult. However if you're skilled at solving advanced calculus problems by hand, your understanding of algebra is so deep that you could re-derive the process as necessary. Many of us with a lot of math experience will never forget how to solve linear or quadratic equations barring steep cognitive decline and this is also so true for certain classes of algorithms. Personally, I've studied graphs and graph algorithms beyond what you might find in just CLRS or other introductory algorithms textbooks and as a result I can re-derive many classic graph algorithms on the fly, no memorization necessary. I have done this interviews as have people I know.
1. Glue together whatever services are available and seem to make sense.
2. Throw increasing amounts of traffic at it and check what fails
3. Try to patch around failure point
4. blame the service provider for "not scaling"
5. Ask for more and more machines
6. Exclaim how great their design is on the basis of the cool class hierarchies and interfaces they wrote. Teach "junior devs" their "OOP design skills and patterns"
7. Go to step 2
They think of themselves as great engineers who scale things. The reality is they are absolute shit engineers who have no clue what they are building, frequently have crazy O(n^2) loops in their code, dont recognize a graph problem if its staring them in their face.
Examples
1. They needed a way to rerun map reduce jobs to regenerate data for previous 30 days. It was a straight forward, graph topological sort problem. Instead they built a crazy solution using multiple instances of Airbnb airflow. One server ran out of memory for these airflow instances, so they allocated a whole damn cluster of machines to run 30 instances of airflow! The job of the cluster? Issuing map reduce jobs to the hadoop cluster. They needed a cluster of machines just to issue commands to hadoop. They gave an elaborate tech talk about "scaling to 30X capacity" to process 30 days of data. Meanwhile, my team was processing 3 years of data. We considered hamake for our data rebuild process. Eventually, I wrote a 70 line scala topological sort routine that would do the job for us, because it gave us more flexibility than hamake and linked to our code libraries.
2. Some guy wrote a data pipeline to summarize a days results that took 24 hours to run, thanks to 40 different joins. I rewrote it to use a single group by. The code ran in 10s of minutes. He didn't know how hadoop worked or external sorting, beyond writing arbitrary sql. So much for looking up algorithms when required.
3. Guys presents beautiful OOP code that has major race conditions in a distributed environment. I point out the race condition. Keeps proposing hacks to "solve the problem". Does not understand transaction processing or locking algorithms or what options are available to him. Hadn't heard if read write locks. What are the pros or cons. Doesn't understand the difference between local locks and distributed fault tolerant locks. I explain it to him. He eventually comes up with a solution using zookeeper that will need zookeeper to process 1000s of updates per second. I give up.
"DSA, what DSA? They are for kids. I will look up an algorithm when I need it".
Sounds you understand locking and distributed locks. Cool. Your next project is a video encoder. Write an arithmetic coder in a 20 minute interview? Motion detection? Your next project is a chess engine. Write minimax with alpha-beta cutoff in an interview? Your next project is public key cryptography ... A distributed k/v database... Can you write a bloom filter for me in an interview? Gradient descent in some machine learning application?
If you're such a great software engineer, which likely you are, you should be able to do all the above (at least somewhat), by doing your research, and writing code.
I'm not saying hire bad engineers. I'm saying the game is silly. Sure, a good engineer (and people that aren't so good) can play the game. Also not arguing with the person that said if your goal is to get paid better and you want that job then play the game. Doesn't make it less silly.
> Having those guys memorize those won't make them better engineers, right?
They can't realistically memorize all the algorithms, they have to develop an understanding of graphs and algorithmic complexity to be able to get through. They should be able to map arbitrary problems to a corresponding graph problem. These are absolutely fundamental. At least I should be able to communicate to them, "use a topological sort" and they should be able to understand what I am talking about.
Sure, some one could set aside their job for 1 year and memorize everything and they might just get through the interview loop. But it is impossible to have a perfect filter, however DSA and complexity analysis is a bare minimum.
> Your next project is a video encoder. Write an arithmetic coder in a 20 minute interview? Motion detection? Your next project is a chess engine. Write minimax with alpha-beta cutoff in an interview? Your next project is public key cryptography ... A distributed k/v database... Can you write a bloom filter for me in an interview? Gradient descent in some machine learning application?
Funnily enough, none of these questions are asked in a FAANG interview at all. So, I don't know why you are constructing a strawman and demolishing it. The questions actually asked are from basic CS201. These are very specialized questions.
FWIW, I have already built a bloom filter, minhash and consistent hash at work and I am a machine learning engineer. So, I can implement an in memory consistent hash store, bloomfilter, minhash, count min sketch and gradient descent in an interview setting comfortably.
For motion detection a 2 dimensional derivative function should work. A simple delta between 2 images is a basic implementation . Huffman coding is not too complex to write. The basic entropy formula is pretty simple. In fact, most ML classifiers minimize cross entropy loss, so I am very familiar with entropy. Minimax - I have partly forgotten. But if the interviewer prompts me with some high level details I should be able to do it.
I have actually been asked to derive gradient descent in a Google staff eng equivalent interview and also demonstrate that gradient descent converges to global minima for the single layer perceptron[1]. Mind you, this was a specialist ML IC6+ position. Not a new college hire loop.
[1] You need to prove that the Hessian is positive semi definite. I did the basic set up but couldn't complete the derivation. However, I got an offer.
Lots of people get good grades in data structure and algorithm courses where the test basically looks like these interviews. You get some problem that "asks" for some algorithm to be used, you implement it, done. Out of those people, maybe 10%-20% are going to be great programmers. IMNSHO. And I'm probably being generous. How do I know? I hire those people. Everyone I hire has great grades in those courses. And some of them, many years from now, are gonna be awesome. And I don't hire everyone that has good grades.
Most of those are exactly the people you're complaining about and they'll ace your interview. Why are you asking them a dynamic programming question and then complaining about their usage of Zookeeper or whatnot? These things have nothing to do with each other.
I didn't say those are the questions asked in FAANG interviews.
I think if ML is your domain, and you present yourself as an expert in this stuff, then technical questions along those lines are fair game. And you're right that you should know your stuff. And you should also have the ability to work in a different domain. I've written Huffman encoders a few times in my life (as far as I can recall never in a work setting) and I could maybe write one in an interview. But I can't write an arithmetic coder in an interview without looking it up. Can you? I mean what exactly is the point here? Sure, the stuff you do day in and day out, you should demonstrate that you're able to do it. The stuff that you don't do, you should demonstrate that you're able to understand this is another domain, research, and then do stuff.
This is a little bit like comparing PhDs to people without PhDs. If you're a machine learning PhD you will know a ton about the domain (and also you're forced to learn a ton about some adjacent domains). Are you a better programmer or software engineer? I don't think so. It's like comparing a mechanical engineer to a Physics PhD.. these guys are not interchangeable. CS PhDs, those guys with the knowledge you seem to think is that important on the top of their mental stack, tend to build those terrible pieces of software you're complaining about. (obviously can't generalize, some are also awesome engineers, just like some Physics PhDs might be great at machine design). Don't get me wrong, I have the utmost respect to PhDs and I worked with some brilliant scientists in different domains. I don't want most of them to write software ;)
Getting back to the point, the FAANG interviews focus on basic graph algorithms etc. Getting hired at a FAANG doesn't imply you are a great engineer. Thats not something you can figure out in 5 interview loops. It means that you have the tools to understand basic CS201 concepts and are not the "I will look up the algorithm when I need it" engineer - which is absolutely a recipe for disaster.
And these algorithms are very relevant, Apart from top sort, bloom filters etc. I have also used dynamic programming on the job, to tokenize product titles to minimize the entropy of the final inferred tokenization of a product, before indexing. I can't even begin to imagine working with an engineer who cant understand that a correct naive tokenization is exponential, that the standard trick to solve such a problem is DP etc. These are basic, it doesn't mean you are a great engineer. It means that you have the basics covered and don't need to be hand held through the implementation details of systems. It's the difference between telling an engineer "we use DP to minimize the tokenization entropy" and sitting with him/her for 1 hour and walking him through every step, like it is some kind of magic. The standard FAANG interview doesn't even cover probability that well, so they have a fairly lenient expectation from the engineers about the concepts that they need to know.
As for why I am complaining about zookeeper. Because zookeeper is an implementation of PAXOS algorithm which has an extremely high penalty for writes. A person who thinks, everything is a black box and he doesn't need to know about algorithms, and will "look them up" when required, is actually never going to looks up any algorithm. Like I said he won't understand something is a graph problem even when it is staring him in his face. I have given several examples of graphs, DP etc being used on the job. And you completely ignore the basic problem with guy implementing lost updates with race conditions.
1. He doesn't realize this is a standard problem, covered in a FAANG system design interview.
2. He doesn't look up standard solutions and cooks up his own hacks, using a central database to record state. His hack has more race conditions.
3. I have to tell him the standard solution to this is locks
4. He ignores my suggestion, and finds out about zookeeper. He thinks it's a key value store like Cassandra. He doesn't realize that zookeeper is an implementation of PAXOS and has very high write cost. Because, he doesn't care about algorithms. Everything is a black box to be glued together.
5. He judges good software engineering on the basis of object hierarchy design, design patterns etc. Algorithms, data structures etc are irrelevant to the job, except for vectors and hash maps. There are API services to do everything else.
This was an engineer at a non FAANG company. Having worked at both FAANG and non FAANG, my observations
1. FAANG engineers are generally higher quality and way faster at execution.
2. Excellent non FAANG engineers are plenty, but at a non FAANG they are fewer to be found. Very often, they end up at a FAANG a few years down the line.
3. FAANG hires don't necessarily have large scale system design skills. The interview cant really pick that up. That's what the promotion and annual reviews are for.
4. The FAANG loop is a classifier, just like any other interview loop - with both type I and type 2 errors. So, it will both reject good candidates and accept bad ones. Any criticism of FAANG interview loops that don't understand the concept of type I and type 2 errors are just emotional hyperventilation. None of the alternative proposals even care to show how it could possibly be better than the FAANG loop.