Data structures and algorithms I actually used while working at tech companies

I did not get the job at Google.

I do make sure as a more senior engineer at my current company I use what leverage I have to make sure other interviewers don't ask pointless questions like this.

It's OK to ask people general questions (what's algorithmic complexity, what kind of algorithms and data structures they know about, what are the tradeofs, etc).

But expecting people to remember the exact steps of an algorithm they last used 10 years ago at university is just stupid. It's like asking engineers to remember the tensile strength of a material they could use once a decade. That's what the documentation is for. It will take 3 minutes to look it up when I need it (if I need it at all).

1. Tree/graph traversal (certificate validation and a couple other random places)

2. Using, not implementing, hash tables

3. Generators/iterators/streams: minimizing the number of unnecessary list traversals or allocations made when you have to shovel data around

4. Circular buffers: specifically in low latency, high throughput applications

5. Some exotic string search algorithms in a very specific, highly performance sensitive inner loop

6. Database query performance tuning

7. Every now and then something vaguely reminiscent of dynamic programming comes up, but it's never an actual dynamic programming problem, it's just a "cache results of expensive operations" problem.

For my job you need something exotic once in a blue moon, and when that happens you Google for someone else's research. You're not making up algorithms on your own. If you want to test that someone can handle algorithm-heavy situations like case #5, you should be testing their paper reading and ability to implement that paper, not their ability to solve an algorithms puzzle.

Also relevant to my job: if you find yourself implementing cryptographic algorithms, you're almost certainly doing it wrong. You shouldn't be implementing cryptographic algorithms. When I need them, my job is to vet and correctly use an expert implementation.

The programme in question was running into performance problems, and a few smart people had already banged their head against a wall solving them.

After lots of experiments and different approaches, my solution was to remove most of the advanced data structures that were in the code.

In theory, they should have given us logarithmic runtime on some common operations, but the constant factors were too large. I proved (in the mathematical and the practical sense) that a brute force scheme combined with a careful randomization would dramatically improve real world performance with a fraction of the previous line count.

Despite me removing those interesting data structures, I still count it as a great application of my algorithms-and-data-structures knowledge: a big part of expertise is to be able to spot opportunities for simplification.

- General IQ. Can this person understand and apply complex ideas

- Grit. Is this person hard-working enough to learn things that take time and effort

It's the software equivalent of the NFL scouting combine. The goal is not to create a test that is similar to the day-to-day job. But rather, create a test that isolates and evaluates a specific set of skills, which you think are important to the organization.

I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on.

I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries.

I only implement stuff myself when it's faster and simpler to implement AND TEST it than to draw in another dependency, or if there isn't a well-made off-the-shelf component.

So what I've implemented myself at $work is pretty limited:

* depth-first tree traversal

* graph traversal

* parsers for various non-standard file formats

* maybe a topological sort once, not sure

Finally, many classical algorithms have lesser-known variants that optimize for some practical advantages (reduced memory usage, memory cache friendliness, sequential disk reads/writes etc.). So if I were to implement, say, a substring search, it might not be a by-the-book Boyer-Moore algorithm, but some subsequent paper that builds on it to add a few percent practical performance improvement.

It's just an exercise to see "how badly does this guy want it? how much did you cram?" Like hazing.

As an anecdotal story, I once interviewed at a well known HFT in Manhattan, after jumping through the phone screen and timed coding interview (involving four questions), you were invited on site. The first thing you do on-site (10 am in the morning) is take a 2 hour multiple choice exam consisting of 100 questions and get this - it was literally on scantron card, so they can score it right away (exactly how I used to multiple choice exams in high school).

If they didn't like your score, you were sent packing right away, otherwise the real interviews would begin with actual people throughout the afternoon. Allegedly, the way you knew this was, if you they asked you what you wanted to lunch, that meant you passed and could go to the one-on-one interviews.

I didn't get the job in the end, but I did get a ham sandwich and soda out of the deal.

> Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

First, it's not remotely true that 90% of Google engineers use Homebrew, seeing as how almost all development is done on Linux (Max Howell is unjustifiably full of himself here). And secondly, he doesn't know why he wasn't hired, but it may well be because of the entitled attitude on display here rather than any coding shortcomings. No one wants to work with pompous rockstars. They may be fine for developing one-person projects out in the wild but they don't work well on team projects at large companies.

If you go into an interview with the attitude that the problems you're being asked to solve are beneath you and that you just flat-out deserve the job without having to prove yourself, your success rate is gonna be poor. To a big corporation, almost no one is as big of a deal as they might think they are, unless they hold a Turing Award or similar.

The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars and where you divided them (e.g., dividing after a full stop is better than after a comma, which is better than between two works, which is way better than midword).

With a reasonable cost function, this really seems a textbook dynamic programming example (possibly much more credible than the entering-a-treasure-cave-with-a-rucksack story).

I think the problem is being expected to regurgitate* 1-2 hyperoptimal leetcode solutions in 45 minutes while suffering from heavy interview pressure.

*by regurgitate, you can't simply implement the optimal solution either even if you know it. You have to put on a show where it seems like you're arriving at and iterating towards the optimal solution, "explaining your thought processes". But you can't waste time iterating and going down suboptimal paths either because you only have 45 minutes or less. Hence why ideally you know the exact optimal solution beforehand, or at least know the tricks and patterns to quickly get to the optimal solution for the type of problem you are tackling.

Recruiters and official interview guides say that your "thought processes" matter a lot, but reports from in the field tend to imply that the #1 most important factor is that you get the optimal solution. If you can't, your "thought processes" are worth little, barring exceptional circumstances.

I remember a stint in research, about data analytic non the less, where rarely anyone had a good grasp of SQL or any other way to persist data for that matter. It really puzzles me to this day.

Might be me finding most ORMs to be harmful if used without understanding of the underlying technologies.

Mostly that they prepared for an algorithms question.

It may be a good filter for 3rd-wave do-as-you're told programmers who stay in their lanes, produce by the book expected code, and just consistently obediently build things.

They wan better cogs for the corporate software machine.

If people are asking me algo questions, the job probably isn't right for me because my answer is "it depends". Last time I took one I was thinking "there's like 4 answer to this, what the fuck do you want?" it might as well have been "I'm thinking of a color" ... they have something written down and called it the "right" answer.

I gave a parallelizable answer, they wanted single threaded. I gave a single threaded one, they wanted 2 passes. I gave them a 2 pass version, they wanted one that didn't use collections.deque, I mean it was nonsense. "Guess what's on my piece of paper!" Cool beans bro.

Some people would have given them that answer the first time, I'm sure of it. Not me though. Not during the interview, not during the day-to-day.

I don't know how. I really don't. I don't know the right answers, all I see are a bunch of possibilities. That's why I'm first-wave.

The writer of homebrew isn't what Google is looking for anymore. His time to get hired there closed around 15 years ago. After the revolutionaries comes the administrators, a far less interesting but necessary entourage.

The people like me have all already quit. I've actually got nothing to offer them.

So why are firms that are hiring so obsessed with producing more and more arcane barriers to entry?

As I always comment when this topic comes up: this process makes some sense at Google (where I work) where the sheer number of applicants is massive and false-negatives are perfectly fine because the potential applicant pool is so large. But at smaller companies, who can't pay Google compensation and feed you gourmet food, blah blah blah? And where your job will be mainly writing some JavaScript to drive web pages? Really?

I work around embedded stuff and spend a lot of time in low-level code, and I _still_ don't get to spend a lot of time writing algorithm and data structure heavy code. I actually really enjoy doing that kind of work, but on my own time, at my desk, with my headphones on, and some books and resources to reference as I'm doing it. This is how engineering / authoring / writing is classically done, by the way. Calmly, often solitary, and with space to gather thoughts and do trial and error.

Why should I be selected or deselected based on my ability to perform this activity in front of people in a high pressure situation? Often someone 15 years younger than me, fresh out of a CS program, and with a pile of hubris that goes with that?

For what it's worth I'm self-educated, not a CS grad, but got into this because it's what I like to do and spent many years privately studying on my own to get here.

FWIW I just this morning turned down a potential job opportunity because this is the interview process they wanted.

One of the most memorable was when I had to build a graph from sql statements, parse the sql statements, determine the dependencies between the sql statements by traversing the syntax tree and ordering the graph based on the dependencies so sql statements on each level could be evaluated in parallel.

It was one of the most fun and interesting projects I've ever worked on, it took me a few days to come up with a Java implementation and after a few bugs I rewrote it in Scala. I think I ended up with some kind of DFS algorithm if I recall, I might give it a shot at implementing it from memory and putting it on github.

But the general understanding of algorithms and complexity did help even in CRUD apps. It gives the bricks to form mental model of the underlying system. I don't need to code a b-tree but I may need to tweak its params.

Indexes come up a bit. I've seen many junior engineers struggle when performance problems crop up over time. If they don't have a familiarity with data structures and algorithms their "fixes" never seem to work and they get frustrated. I enjoy taking the time to show them how indexes can speed up search and when they don't give you much benefit. At small companies getting off the ground I think it's less important to hire people for their algorithms/data-structures knowledge.

At companies where the teams are working on high-performance or large scale problems it's quite essential. Being able to shave down build times, as in the article, is a big deal. Knowing how to scale a large problem is a big deal when the quality of the service depends on it.

There are also some problems that require it. I'm building a key-value data store as one of my side projects and it definitely requires knowledge of data structures and algorithms. You can't even implement one efficiently without such knowledge!

So I guess it depends on how much your team actually works with these concepts. If your hiring process is keeping the bar high but all you do is schlep JSON from one bucket to another you're missing out on a lot of good candidates for no good reason. If you're building networking products or databases then yeah, keep the bar high.

But within reason. I agree with the OP -- the need for exotic structures and algorithms is so rare that it's not a terribly good indicator of anything to use them in an interview unless you're looking for researchers.

update: spelling.

Most coding problems can be broken apart and the individual components tackled one by one. But that has two problems. One, it doesn't stress-test the programmer. Two, the most beneficial changes to a codebase come from a high-level understanding of the system. Implementation might be segmented, but the more of the system you can simultaneously understand & manipulate in your head, the better placed you are to manipulate the architecture.

Complex algo questions force you to manipulate a fundamentally complex problem. You can break it apart in some ways, but in general you have to be able to think about the entire basic algorithm in your head. Reversing a binary tree? You have to be able to visualise the datastructure you're manipulating and figure out what changes you need to make before you start writing. It's a stress test, it tests horsepower.

Granted, you can game that system by doing practice questions which undermines it to an enormous degree but I'm not sure what else you can do to test that.

Some of the stuff I personally worked on was tries and nested tries for routing/cache purge, LRU & variants for the caching algorithm on a cache node, and I implemented consistent hashing for the distributed cache.

There were some algorithms stuff for load balancing, but I didn't work on that.

I know there was a few other things, but I can't remember them right now.

- Space partitioning such as octrees

- Finite-state machines

- Behaviour trees (I much prefer to state machines)

- Too many machine learning and deep learning algorithms to list

I have also had to come up with boutique solutions to a number of problems. Even though I have never failed to deliver a solution in the real world I doubt I would pass any sort of algorithm interview without significant study. I don't rote memorize things and only (quickly) learn what is relevant when it is required to solve a problem. Unfortunately I also do not know of any quick way to test for that sort of ability that would be suitable for an interview.

In my experience at Amazon and Google we all referred to books and colleagues when working through algorithms.

I'm not sure how people in the comments are saying that the "advanced stuff is never used", when the author used the A* search algorithm at work! I'm especially fond of this passage:

> You should also know about basic data structures that are pretty common, like hashtables, queues, or stacks. But specific algorithms like Dijkstra or A* are not ones you'd need to memorize: you'll have a reference for this, just like I had when implementing crypto.

Everyone complains about the lack of applications for these interviews, but there's not really an expectation to go beyond the fundamentals.

I think having a rough understanding of what's out there does help though. Just reading some books about them, kinda scanning over them thinking hmm that's interesting. And then when you need one you'll remember "wait I think some sort of x algorithm I read about might be able to solve this".

Greedy alogrithms are simple to come up with in an interview, Yes. But they are often wrong and even if they are right there is no way to know that, unless you construct a mathematical proof.

I would highly advice not using greedy in an interview since coming up with a solid proof in 15 mins is not really possible in all but simple cases.

a) A really good problem solver

b) Someone who has ran through all the example interview problems on leetcode or something similar

Then I thought that this might be similar to the Turing test. Once you’re that good at faking it that you can convince someone else - maybe the difference doesn’t matter at that point.

Of course, there are positions where this kind of skill is unnecessary and I cannot know everything about the false negatives. But failure in these areas also correlate with poor coding skills, at least in my experience of a free hundred interviews.

That said, the only algorithm that I'm convinced that every single programmer needs to know by heart is state machines. Because using them can often save you a lot of code and complexity. And because you really have to know them well to recognize spots where they would be useful. And because using an off-the-shelf library to implement them is, for most use cases, more complicated, more time-consuming to implement, and less readable than a little light hard-coding.

Sounds like a terrible case of NIH. Why (re)implement AES when you've got battle tested implementations from OpenSSL, NaCL and practically any OS provided crypto APIs?

That makes sense. I would expect one to implement data structures and algorithms in a new operating system / kernel without the presence of any libraries available, except for libc, so that they can be reused or abstracted elsewhere in the kernel, drivers etc.

> There were cases where we had to build our own encryption / decryption implementations, formally verifying and auditing them, in the absence of the framework supporting it, or audited libraries being available.

I would leave implementing cryptographic protocols to the professional cryptographers.

But overall, I agree with the author to ask about data structures and algorithms that are actually used in the company if I were interviewing a candidate. It gives an honest account of the engineering decisions and reasons made in the team as to how implementing this DS & A helped them solved their problem and to test if the candidate understands these concepts.

However, after asking the candidate to implement a DS or A, if the candidate questions the technical interviewer if they use it in the company / teams and the answer is no, then it seems rather than a dishonest ego trip on the interviewer's side to test the candidate if they know the secret konami code.

I'm surprised this wasn't listed first. I always ask a question or two related to hash tables when I interview candidates and I'm continuously shocked that a good chunk of candidates don't know the basics of hash tables. I expect you to know that looking up whether an item exists in a hash table is _generally_ fast in practice, even if you don't know the specifics of O(1) best case, O(n) worst case. I expect you to know that it doesn't allow duplicate keys. I don't expect you to implement a hash data structure from scratch, but I do expect you to know which data structure implements a hash table in your language of choice (e.g. Object, Dictionary, Map, etc.).

It's the one slightly more complex "data structure" that I use all the time, so it's surprising to me when people don't know the basics.

The only other exotic data structure I've had to use is the union-find data structure. It's a pretty slick data structure, both because it's so easy that you could probably come up with the optimal one just by thinking about it for a few hours, but also because its runtime is O(n * inverse Ackermann(n)), the latter function grows so slowly that it is less than 4 for the number of atoms in the universe. Although, unfortunately, the data structure doesn't do a good job of telling you which union call is the one that merged two sets that should be separate together.

These are both good books that I actually like! They aren't quite as massive or comprehensive as CLRS but are easier to read as a textbook. I also like Steven Skiena's course videos. But I agree completely that they are unlikely to be something you'll use day-to-day unless you work as an algorithms specialist.

> Grokking Algorithms by Aditya Bhargava... I am convinced that you don't need to know more about algorithms than this book covers.

This is a nice and compact book, and I think he's right for most jobs that involve writing software. Won't be enough to get you past the idiotic algorithm puzzle interviews though. ;-(

What people seem to want is big-data or various tech stacks. I look forward to the time I can put even a bloom filter to work.

(edit: typo)

It's probable that I've done some of the other stuff -- graph traversal comes to mind as feeling like something I've done professionally -- I feel like I've done stuff like that maybe once or twice in ~20 years. While it was useful to have that knowledge, probably, it wasn't even remotely representative of regular work on those jobs.

But that raises another question: is it still worthwhile to test for something you'll use 0.1% of the time on the job? Like, say I didn't know anything about graph traversal, and came across a problem that (even though I didn't know it) was perfectly suited to a solution involving a well-known algorithm. I might search around a bit, but ultimately my solution will probably be pretty non-optimal, might involve brute-forcing, and might be difficult to understand and read since I had no idea what I was doing.

On one hand you could say yes, that's important: even if you will barely use this information, it will be absolutely critical that you have it already and understand it when you do run into a problem that needs it, to the point that we don't want to hire you if you don't have it. On the other hand, you could say that picking it up as you go along is fine, or even writing a bad, brute-forced solution is fine, and the likelihood is that someone else on the team would notice during design or review and suggest the correct approach. You could even say that even if that doesn't happen, a bad implementation of part of your stack isn't even that big a deal; we all write so much technical debt for various reasons, this is just another thing that someone might have to revisit and improve later.

I'm not sure where I fall on this, really.

Considering Skype is at best laughable compared to other IM applications, I'd not boast about working on it. I used Skype over 10 years and after it got bought by Microsoft it gradually started to be worse and worse, to the point I had to look at other IM in order to communicate with my clients.

I have a question, why is that Whatsapp and FB messenger can and will deliver notifications when you receive a message every single time, while for Skype this seems to be an unachievable feature?

Some real-life practical examples: knowing when a simple O(n) linear search beats O(log n) binary search, or knowing when a multiple substring search algorithm based on a simple Rabin-Karp and L1 cached hash table lookup will outperform the theoretically more optimal Aho-Corasick.

But as a senior developer, I daily have to understand the graph of code submitted for review to propose a simplified one to increase readability and ease future maintenance.

But does this mean you need to learn them by rote or be able to figure them out on a whiteboard? No. And although they appear regularly, I don‘t spend enough time on them that this would meaningfully affect my performance. So the time you spend thinking doesn‘t matter, very unlike a whiteboard situation.

Technical interviewing for long term employees based on exam essay like questions is rarely productive. My first objective is determining the applicant's honesty on their prior experience. It is amazing that the vast majority of applicants will out right lie on their resumes and to your face when questioned.

Past success in solving/implementing difficult projects is the best indicator of future success.

I'd wish more of those problems showed up in my daily work, though.

Btw, a cool popsci book about algorithms occuring in day to day life is "Algorithms to live by".

IMHO take home tests with a following discussion of the solution is the best way to go. Interviewers can judge the code quality as well as critical thinking with the follow up discussions.

http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf

Remember people processes need to be the least bad, not the best. Most of the best are either unworkable or tyrannical.

As for data structures, the only one I occasionally need to code myself is a simple tree.

even though real world problems are better interview questions, they suffer from requiring more candidate/interviewer prep. they can also stall out due to integration/machine/etc issues

Does look like there's some interesting stuff in the article though, so I'll read it properly later.

That has some aspects of software development that I rarely hear discussed, like testing, usability, accessibility, aesthetics, graphic design, error handling and recovery, documentation, support, configuration management, and lots of system framework knowledge.

If I am supposed to be writing apps for iOS devices, then I’d think knowledge of UIKit would be a heck of a lot more important than balancing a binary tree. I can tell you, from personal experience, that it takes a long time to learn, and is very important, if you want actual, shipping apps.

Even so, I have often encountered obsession with “büzzwürd du jour,” and people get hung up on things like MVVM/MVP, VIPER, etc.

I remember once, getting a “take home” test that asked me to implement an iOS app that employed MapBox, which is an excellent library, but, at the time, I had never used. I was instructed to use MVVM. I have no idea why.

In four hours, I had a completely functional, localizable, well-code-documented, nearly ship-ready (including a custom app icon and splash screen), high-quality app that implemented MapBox (again, I had never even looked at MapBox before this test), using Dependency Injection (basically, the “D” in “SOLID”). If I incorporate dependencies, I always encapsulate the dependency, and DI is an excellent way to do that.

Oh, also, while I was working on the app, we had a household emergency that required urgent attention. The app would have taken less time to write, otherwise.

It was not received well. To this day, I have never learned why. I suspect that I was supposed to spend a couple of days, creating some kind of chimera that illustrated every buzzword on Earth. No matter. I wasn’t what they wanted, and, after that experience, I realized I would probably not enjoy working with them; which was a bit disappointing, as I liked their product. I felt that I could have had a fairly significant impact on their Apple software.

In my experience, I have found it’s always best to use the development model a framework is designed to support; even if it isn’t particularly “buzzwordy.” If we use UIKit, then MVC is the most practical and simplest approach, as that is how the SDK was designed. If we use SwiftUI, then we have a great deal more flexibility with our models, but very few companies are willing to ship SwiftUI apps (yet).

Shipping is all about practical approach. Ship software should be done quickly, as simply as possible, and needs to be robust, well-documented, organized, testable, Extensible, and maintainable. If we are talking Apple apps, then they should also be performant, responsive, secure, highly usable, intuitive, aesthetically pleasing, accessible, and that employ familiar (to the user) idioms. They also need to pass App Store Review muster, so that means being careful about how we incorporate dependencies and frameworks, as well as not using private APIs.

Since I’ve had over twenty apps in the App Store that I’ve written from scratch (but I'm down to seven, right now: https://littlegreenviper.com/AppDocs/), this is something I do know a bit about.

That usually requires a great deal of frugality, practicality, user empathy, experience, and self-discipline. It’s difficult to figure that out with “Draw Spunky” binary tree tests.

If I'm asked to do a BFS/DFS, Tree traversal, etc for a small company.. I tend to share high level how I'll solve it then basically not actually code it up and say something like "This is pretty tricky...". Why? It's my way to exit the interview quickly because I question the ability of the company to hire talented engineers. Especially when I test your product out and see all sorts of inconsistencies.

Okay, so when do Data Structures matter to a company?

Are you building a product that needs to perform very efficiently at scale and the system is doing something outside the "norms" of what a data store can provide. Examples: Facebook's TAO system and their type ahead search.

Read the design paper for TAO and you'll see how they use very primitive data structured related to Graphs. Their typeahead system also makes use of some very basic data structures and some probabilistic data structures as well.

When do Algorithms matter to a company?

For most traditional companies, you're not going to do a BFS/DFS search, traverse a tree or a Dynamic Programming solution like Levenshtein distance. So unless these algorithms have a practical use case in your company, you're just creating a sort of monoculture.

Once again, Google and Facebook do apply these algorithms so I respect their interview process.

Big O has its place in such large companies. I think most people fail to understand the purpose of Big O; identify upfront if a solution will be sufficient from a time or space perspective as the data grows. Most people speak about Big O on interviews AFTER they code up the solution. You should do that before you code it up.

e.g, So the data for this problem is <100 items then this quadratic solution would work, but if we scale the data set up to say 10,000 items then it won't work. Then you can look at data structures or sorting algorithms for instance that'll help you get it down to say O(n) or O(n log n) etc

Look, I get the frustration a lot of people feel about this sort of interviewing process. I have a very non-traditional background and it could be very scary when you first start learning about this. My advice? Learn it for your own good. It'll make your a better programmer and it'll help you become more aware of so many things you weren't aware of before!

The moment when you realize why using an array for a Min Heap or why a Min Heap must be a complete tree... you'll step back and go "Now that's sexy!" Or when you realize even stupid stuff like "A balanced binary Tree has this weird reality that the leaf nodes account for 50% of all nodes in the tree" It's just fun if you see it in a positive way.

Let's call technical interviews that ask such questions when it doesn't represent the company "interviewer imposter syndrome". When a company tries to act and look like Google early on.. Google has a million+ candidates a year interviewing with them. They MUST allow good candidates slip through their process.

Next project was making a "Countdown" game, where you are given 9 pseudo random letters and have to make the longest word you can. I found a dictionary as a text file, so could see if the word you entered existed. The game was on Gameboy Advance, so not a huge amount of space or very fast CPU. As you can imagine, walking the entire dictionary file from start to end looking for a word was far too slow. So there was another ah-hah moment when binary search was introduced.

Next I worked on a rendering engine for this device called GP32, you basically got a pointer to the screen buffer and could put what you liked in it, so I learned how to write polygon fill routines, back face call, etc but didn't know what perspective projection was or how to find out about it. I finally found a book, Game Programmers Black Book or something like that, which explained perspective projection, at least to some extent, another ah-hah moment (previously I was dividing my XY by Z as I knew I wanted things smaller in the distance but this doesn't give a nice result by itself).

These are just very early examples when I first started programming, when information was harder to find, and when a lot of games development involved DIY, if you want a polygon you need to pixel fill a polygon! Even when PS2 came out you still had to write ASM render programs to take an array of vertices and transform them, their UVs, etc and send them to the Graphics Interface.

But I haven't found later tech developments have stopped me finding and needing to use other algorithms and structures. Just last week I had to diagnose a crash which resulted with the target device and debugger showing a nonsensical callstack, so I enabled the profile options in GCC/Clang so I had an epilogue / prologue for every function that is called, so I could store my own call graph history, and then, on crash, display it nicely, with indentation etc. This allowed me to see what happened just before the crash (turned out to be a system UTF16 conversation routine stomping over a pointers boundaries as the NULL termination of the string was incorrectly done as if the string was a normal char*, effectively NULL terminating half of a UTF16 pair, which wasn't treated as a terminate, so the actual bug was bad string termination done by the off the shelf engine we use). As the profile code ran twice for every single function that was run, it had to be pretty efficient, using appropriate data structures, etc.

So I guess the point of this post is to say I believe having a good knowledge of algorithms and data structures always seems beneficial to me. The extent which some companies push them is too much for me, but I don't think this should lead to us thinking it is all pointless. There is a nice balance out there.

For example if you use dict a lot in Python, that’s not at all the same as writing your own hash table with a custom chaining or probing algorithm for collision resolution.

The original quote from the whole homebrew saga is talking about needing to seriously implement these algorithms entirely yourself for a task. It was not talking about casually knowing a few fundamentals you loosely keep in your mind while using built in libraries.

Whiteboard hazing trivia interviews are also all about obscure implementation specifics, and they are not at all about knowing the coarse fundamentals. That was the entire point of criticizing Google’s parochial barrier to entry hazing crap.

While this author’s stated experience is cool, I think they entirely missed the point of what they are responding to.

However, you should be able to implement some of these more rarely used data structures, given a description. You shouldn't know how to do it ahead of time, however, because your job is to solve problems that aren't solved yet.

What you get with these interview questions is that some applicants prepare for how to solve some of these commonly posed problems specifically. So you have to implement a bug-free linked list, on a whiteboard, in ten minutes, to be competitive. It's doable if you are prepared, but that defeats the purpose.

no, in this thread people are describing actually hard, complex algorithms and ridiculous interviews. so sad to see that these questions are still being asked today.

this is the best thread on this subject that i have ever seen on HN.