52 ms·

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

• mala24bd 6y ago
  Good quality
• pintxo 6y ago
  It’s an interesting question why we focus so much on algorithms that are mostly not used on a day to day basis, but the topic of persistence that’s everywhere and which is often only partially understood is far from being this prominent. 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.
  • eru 6y ago
    Be careful, 'persistent' is used with different meanings in different contexts. See eg https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure and immediately notice the warning 'Not to be confused with persistent storage.'
    • pintxo 6y ago
      Thanks, I usually refer to them as immutable, haven't actually come across the term persistent for these, but seems sensible.
      • eru 6y ago
        Persistent data structures don't have to be immutable. (The Wikipedia article explains.) But immutable data structures are always trivially persistent.
• giomasce 6y ago
  I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions. 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).
  • viraptor 6y ago
    > 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 That immediately brings Tex box badness to my mind. And the related line wrapping algorithm: http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf
    • gridspy 6y ago
      Yes, dynamic programming is how I implemented line wrapping for (the help text in) SingStar PS3 also. Good spotting BTW, the line wrapping algorithm (where each tweet is a "line") is a perfect match for the post you are responding to. When doing programming competitions, you're often trying to figure out what standard algorithm is similar to the problem and how you need to tweak it to match.
    • giomasce 6y ago
      Yes, I was more or less inspired by TeX's algorithm.
    • 72deluxe 6y ago
      Thanks, an interesting paper. I wrote a word-wrapping algorithm once so this will be a good read to see how bad mine was.
  • deleted 6y ago
• zelly 6y ago
  Would you rather be interviewed on algorithm questions or Ravens progressive matrices? They both test the same thing, but at least one you can study for, is somewhat relevant to the job (and is legal).
  • james_s_tayler 6y ago
    Can you not study Ravens progressive matrices?
    • visarga 6y ago
      Only if you remember all the permutations. But I think Ravens progressive matrices are only good for finding people who have good visual acuity, not people who think deep.
    • thaumasiotes 6y ago
      You can; validity drops severely for testees that are familiar with the problems. (The set of problems is not large.)
      • zelly 6y ago
        Sounds like leetcode questions
  • C1sc0cat 6y ago
    I have done that as a child high 120's low 130's IQ, - this was part of the investigation when I was diagnosed with Dyslexia. Unfortunately some old school teachers whet not keen on dyslexia diagnosis
• praptak 6y ago
  I once coded a function to calculate edit distance. It was the algorithmic highlight of my career :) 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.
  • wilsonrocks 6y ago
    I wrote a tree traversal algorithm to allow some custom logic to be specified in an external JSON that we didn't control... Felt great!
  • C1sc0cat 6y ago
    I had a similar problem once and being an atypical programmer and did not know the term edit distance. Some research gave me Levenshtein distance and from there I first used a naive perl implementation before finding that you could extend MySQL and found an example and implemented that. Took me 1/2 a day to go from zero to working prototype
• kerneltime 6y ago
  A good wood worker tends to know the tools of the trades and more importantly know when to not use a tool and when to invent a new one.. That said not every cabinet is a work of art some are just there to be functional for long enough to justify their creation. I feel system interviews that dive deep about decisions and insights are far more useful than hitting a leetcode jackpot. Though it puts a high bar on the interviewer as well.
  • simonhamp 6y ago
    Most wood workers likely won’t know or care how to build their tools from scratch
    • stan_rogers 6y ago
      In the sense of going from rocks to iron to steel to finished tool, no, but otherwise, yes. Making specialised saws, scrapers, chisels, spokeshaves, planes and so forth are part of the luthier's, cabinetmaker's, and shipwright's existence. And that's just the tools, leaving workholding aside. Add in jigs and fixtures and there's a whole lot more. Not everything you need to do the job can be had off the shelf.
      • kerneltime 6y ago
        +1 I have been tracking luthiers and it is fascinating how detailed and varied each builder is.. the likelihood that the instrument will sound good is well correlated to how much time the luthier puts into refining his process. I don’t understand the rational for not wanting to learn DS/Algos this is just one part of it, there is also the whole business/customer side of writing code. There is a difference between never getting a demanding customer who understands the difference between a good instrument and something glued together and not wanting to know how to do something more than glueing it together is appalling. As a coder if you want to learn DS/Algos and you do not find a job the values that maybe there is more to learn so that find a job that values it. It will be competitive and you can fail but it is not wasted.
      • simonhamp 6y ago
• ajuc 6y ago
  I've used Dijkstra algorithm for calculating distance in a graph once. It was a highlight of that month. Of course I had to look it up(despite learning it and implementing it at university). Who remembers this stuff exactly after years of glueing libraries together? And even if you remember - won't you check it anyway just to be sure? 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).
  • namdnay 6y ago
    Completely agree. The only thing that's important is knowing what to google for. i.e. being able to map from a real world problem to one or several algorithm/structure classes.
    • WalterBright 6y ago
      > The only thing that's important is knowing what to google for. It's even more important to recognize when the solution found with google is subtly wrong.
  • Taek 6y ago
    We always tell our candidates in advance what algorithms we'll be quizzing them on. And it's pretty much always: + fibbonacci + a sort + a linked list I like having candidates write out these problems on paper because it shows that they know how to think about code. Fibbonacci allows us to see that they have basic recursion understanding, and basic iterative loop understanding. Linked lists shows us that they understand pointers. And a sort shows us that you can structure more complex code well. If you truly want the job, you'll take 15 minutes the night before to remind yourself how all of these things work, none of them should be particularly foreign or confusing to an experienced programmer. That covers the coding part of our interview. For the problem solving part of the interview, we may give you problems that require using heaps or skiplists or graph algorithms, but for this part of the interview we're happy to let you import imaginary libraries that do all the hard work.
• codingslave 6y ago
  Just recently implemented connected components in a spark job that runs on a 100TB of data.
  • bitL 6y ago
    How long did DFS take? In my experience, with Spark it's like factor of 100 slower than what one would expect on a single machine and a sizable dataset.
• deleted 6y ago
  [deleted]
  • deleted 6y ago
    [deleted]
  • deleted 6y ago
    [deleted]
• ddlutz 6y ago
  When I was at Microsoft, we used data structures quite often in our service that powered Azure Frontdoor / Azure CDN. 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.
• unnouinceput 6y ago
  Quote: "... but I have come across everyday use cases of data structures and algorithms when working at Skype/Microsoft, Skyscanner and Uber" 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?
• daviroo 6y ago
  I once thought it would be difficult for big tech company recruiting processes to tell the difference between: 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.
  • ajuc 6y ago
    Working through a lot of problems will make you a better problem solver because the techniques can often be generalized. I just don't think it makes sense to test people on this kind of questions and then make them write CRUD all day.
  • deleted 6y ago
    [deleted]
• nipxx 6y ago
  As sad as it is, I get 90% of my algorithm work done with sorted arrays and binary search. Rarely I need more fancy stuff.
  • tzs 6y ago
    I sometimes suspect that everything is really just a sorting problem. For example, here is a shell script that takes an input file consisting of lines of the form X Y where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting. > alive.$$ while read cells do echo $cells >> alive.$$ set x $cells x=$2 y=$3 echo $x $((y-1)) echo $x $((y+1)) echo $((x-1)) $((y-1)) echo $((x-1)) $y echo $((x-1)) $((y+1)) echo $((x+1)) $((y-1)) echo $((x+1)) $y echo $((x+1)) $((y+1)) done | sort | uniq -c > neighbors.$$ grep '^ *3' < neighbors.$$ | sed -e 's/^ *[0-9].//' grep '^ *2' < neighbors.$$ | sed -e 's/^ *[0-9].//' > has2.$$ sort alive.$$ -o alive.$$ comm -12 has2.$$ alive.$$ rm has2.$$ neighbors.$$ alive.$$
• MarkSweep 6y ago
  I have used graph algorithms a little bit at work. For example if you are generating code for a language like C where order of declaration matters, you can use a directed graph to represent dependencies between data types and then use a topological sort to order how you write structs to the header file.
• throwaway_pdp09 6y ago
  I've done an awful lot of investment in booktime to learn various algos, simple to obscure, and frankly never used any of them. I do find that depressing. 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)
  • mihaifm 6y ago
    I implemented a bloom filter for the KeePass plugin [1] I wrote, using the data from HIBP. It was pretty fun and there were some challenges that you won't typically encounter in online guides. Still, that was a hobby project, I've never had to implement anything similar at my regular job. [1]: https://github.com/mihaifm/HIBPOfflineCheck https://github.com/mihaifm/HIBPOfflineCheck
• ahnick 6y ago
  One algorithm I keep coming back to is Aho-Corasick, which locates all occurrences of a set of keywords in a string of text in linear time. (https://github.com/ahnick/ahocorasick https://github.com/ahnick/ahocorasick) It's been useful anytime I needed to locate patterns in a group and I didn't want to be looping back over the group repeatedly.
• rorykoehler 6y ago
  I've used loads of algorithms to solve problems during work and memorised the mechanics of none of them. It seems memorising this stuff is the opposite of how to work effectively with computers.
• matsemann 6y ago
  I think it's nice knowing about analogous problems. If you know what you're trying to do is similar to NPC, one can quickly either dismiss the feature/problem, convert it to a problem with an existing solver, or maybe know that in general it's hard to solve but a relaxed variant is good enough. 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".
• kristopolous 6y ago
  Let's say someone can solve the algo problem, what's that show? 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.
  • zozbot234 6y ago
    If so, they're pushing "conformity" and "being a good cog in the machine" well past the point of cargo cult programming. That's what this algorithm-based interviewing is all about: a textbook cargo cult. And people wonder why they aren't seeing quality.
    • kristopolous 6y ago
      I'm not so sure. Maintaining and building an empire are dramatically different. Companies that could build and not maintain: Lotus, Digital Research, Palm, Netscape, MySpace, Digg, Blackberry, Ashton Tate, it's a different set of skills. Heck, you can even toss the French Jacobins in there They all shot themselves in the foot, I know, that's the point. Not having their eye on the ball and instead looking over the horizon is what built the empire, but then the ball hit their nose Some people can do both (gates, zuck, bezos), but once you're at the Apple/Microsoft stage, you need the second group.
• suyash 6y ago
  I've used Sort method several types both in Java and JavaScript but they way it's used it as a library function, I don't need to write my own sorting algorithm. Same for Data Structure commons ones I've used are found in Java Collections - ArrayList, LinkedList, HashMap, Set etc. For Deep Learning have used several algorithms that are best practices and common data structures like Tensors and Vectors. I realize the value of knowing the theoretical underpinning but practically speaking these are only ever written one by library creators, no idea why companies insist everyone to know these and implement by heart, they can ask much more interesting practical problems.
  • Cthulhu_ 6y ago
    Java is an interesting one; while you don't write the sorting algorithm, you do write the sorting conditions, a function that returns a number depending on the compared values. Likewise there's hash functions, although in practice those will be generated by your IDE or Lombok. (I haven't been into Java for a while so there may be better alternatives, iirc Scala and / or Kotlin solve it as well)
    • ajuc 6y ago
      Most of the time instead of writing or even using sort you're better off using a sorting collection like TreeSet or TreeMap. No need to sort everything again after adding 1 element.
  • entha_saava 6y ago
    The point is, they should not actually require candidates to recall these things from memory. But there is certainly value in the non-memorization part of this knowledge and the ability to solve this kind of problems distinguish people who can think from those naive jobsworths. If nothing, they are better than back-of-the-newspaper if-you-have-seen-the-answer-you-know-the-answer kind of trick questions.
• perlgeek 6y ago
  There's a huge distinction between "used" and "implemented myself". 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.
  • dolmen 6y ago
    You still have to understand how things are implemented by others (even at a high level view: ex: what is a RDBMS index) to be aware of their advantages and drawbacks to make the best use of algorithms available to achieve your goals (ex: performance of the solution, ease of evolution of the solution).
    • perlgeek 6y ago
      I agree. It's good to know a name of an algorithm/data structure, and rough characteristics (like bloom filter: O(1) lookup, super memory compact, statistical, can have false positives, no false negatives; perfect for caching lookups in "forbidden" lists). There's not much point though in knowning the minutiae to the level that you can code one on the whiteboard without prior preparation -- which is probably the main point that the article relates to.
  • cmrdporcupine 6y ago
    And this is the measure of a good engineer -- recognizing that it's most likely that battle tested libraries will have superior implementations of algorithms than whatever one can draw up oneself. I use the STL daily. I know fairly well the complexity guarantees behind each data structure. That's one of the things I like about it versus other collections libraries. It forces you to be somewhat literate on data structures in order to make the right choices. But no, I could not write you up a red-black tree from scratch without going away for a few days with my Knuth books and a few pots of coffee. Sorry.
• veselin 6y ago
  For interviewing, I find it most useful if we ask a question that is an algorithmic problem to solve (but we don't tell them it is a graph problem and obviously it's not something as classic as Dijkstra). Then we observe if the candidate can formulate it as such, or can formulate it as anything useful (often there are several options, e.g. some find the problem to be dynamic programming). This gives much more information about the analytical skills of the candidate than about their algorithms knowledge. In terms of knowledge, what I find useful is just to ask what is a hashtable and how it works. 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.
  • tchaffee 6y ago
    False negatives is right. You're skipping over a lot of good engineers with this approach and you'd have to interview fewer people if you could avoid that. How many times even without the pressure of an interview have I been stuck on what seems like a hard problem and then I go for a walk and end up running home because the lightbulb goes off and I can't believe how "stupid" I was and how simple the problem was.
• quonn 6y ago
  Algorithms come up all the time. Sometimes standard algorithms to use, sometimes to implement or modify slightly, sometimes as something completely custom where some inspiration is drawn from the classics. 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.
• mrburton 6y ago
  I'm not at all opposed to companies like Google, Facebook, etc asking Algorithms, Data Structure and Big O related questions. Why? It's very applicable to problems at their scale. That being said, not all engineers there work on such problems. 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.
• buro9 6y ago
  Count-Min Sketch for obtaining heavy hitters above a threshold within a stream is the surprising one that has featured heavily in recent years. http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf
• jurschreuder 6y ago
  I've used many many many algorithms in my job creating search for video. I had no formal IT training though and I just learned them on the spot. I was trained as a researcher (computational neuroscience). When I need one I just read all I can about it and then build it. 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".
• scraft 6y ago
  I remember, when starting university, with no real programming knowledge, making a little game in my spare time (a clone of Pang if you know it) but it was before I knew what a linked list is. I implemented things like the balls which bounce around the level in an array, and just gave that array a max size. I was very unsatisfied by this, and then later finding out about linked lists was an ah-hah moment, very satisfying. 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.
• ChrisMarshallNY 6y ago
  For me, I have spent many years, writing code that presents UI, or controls devices. 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/ 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.
• eru 6y ago
  A few years ago I spend lots of time and effort at Goldman Sachs solving a performance problem in a major part of their internal cloud infrastructure. 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.
  • WalterBright 6y ago
    At Caltech, we'd call that "brute force and ignorance" which is often the best solution. For example, Enzo Ferrari once said that the secret to better performance is more horsepower.
    • eru 6y ago
      Well, I was using less horsepower. The problem in the previous solution was that it took a while to keep the fancy datastructures updated. (It's a globally replicated distributed system..)
    • karolist 6y ago
      The actual quote was something like "aerodynamics are for people who can't build engines" which proves your point a bit better.
      • WalterBright 6y ago
        It's actually a bit ironic, because I consider Ferrari to build elegant cars while my old V8 Dodge is a triumph of brute force and ignorance. They're both great cars at opposite ends of the spectrum :-) A variation on the sentiment I heard in a movie: "turbochargers are for wussies, real cars have cubic inches!"
• saos 6y ago
  What a satisfying read.
• boringcuriosity 6y ago
  Pretty interesting
• colordrops 6y ago
  Many software engineers do indeed go for long periods without using anything but the most rudimentary algorithms. Needing to know or at least be familiar with many complex algorithms is more of a broad specialty now, and you get shunted into different sorts of work depending on your knowledge of algorithms.
• OptionX 6y ago
  Is there any resource, either online, print of any other form, that lists many data structures in a ordered, searchable manner? Something close to a dictionary or compendium that you could, for example, search what data structures had better performance for the search of an element, or insertion/deletion of an element, stuff like that. I learned the basics ones in uni, but I still find many new (new to me anyway) ones, mostly at random, I wish I knew. Most books on the matter that I read don't go much beyond the basic set of most common ones either.
• bananaface 6y ago
  I don't like algorithms as an interview structure but I do think they have one property that people way underestimate. Algorithms test your ability to manipulate a complex problem in your head without being able to break it down. 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.
  • collyw 6y ago
    The problem I have with algorithms is I can get good at them if I practice them all the time - basically like I did at university 20 years ago. I have barely used them in real jobs since, so while I write far better (more readable maintainable, performant) code now, I am far worse at answering this stuff in an interview. Also a number of times I haven't got an answer in an interview only for something to pop into my head ten minutes out of the door (or a far more elegant solution came to me). You might as well toss a coin and save me the hassle.
• gabrielhora 6y ago
  The main problem, I believe, is the time constraint and the interview environment, both add a LOT of stress and will reduce our ability to come up with an answer. I think most people can come up with a good algorithmic solution given the proper time to do so. 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.
• fspear 6y ago
  As an average/below average engineer with 15 yoe who wouldn't pass SV-style interviews no matter how many leetcode problems I solve, I've only had to use algorithms a handful of times in my career. 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.
• misja111 6y ago
  I like algorithms and coding competitions, but in my 22 year career in software engineering I have never had to code any algorithm myself, except in numerous job interviews. As for data structures, the only one I occasionally need to code myself is a simple tree.
• varbhat 6y ago
  Which are the best books to learn Data Structures and Algorithms ? (Or which books did you use/recommend to learn Data Structures and Algorithms?)
  • charlus 6y ago
    Cormen - Introduction to Algorithms (CLRS) is probably the most recommended. Depending on where you are starting from, MIT opencourseware lectures might be helpful too.
    • deleted 6y ago
      [deleted]
  • gderval 6y ago
    Algorithms, Fourth Edition, by Sedgewick and Wayne. A bit more accessible than the CLRS.
    • varbhat 6y ago
      Out of both, which do you think is better in explaining things concisely?
  • qohen 6y ago
    Given that the publisher, Springer, is giving it away for free during the pandemic, you should grab the PDF of Steven Skiena's The Algorithm Design Manual[0] (direct PDF link[1]) -- it's a book that has often been mentioned favorably here on HN. (And you can pick up another book of his, The Data Science Design Manual[2] (direct PDF link[3]), which is similar in its conversational style, but about a different aspect of CS) [0] https://link.springer.com/book/10.1007/978-1-84800-070-4 https://link.springer.com/book/10.1007/978-1-84800-070-4 [1] https://link.springer.com/content/pdf/10.1007%2F978-1-84800-070-4.pdf https://link.springer.com/content/pdf/10.1007%2F978-1-84800-... [2] https://link.springer.com/book/10.1007/978-3-319-55444-0 https://link.springer.com/book/10.1007/978-3-319-55444-0 [3] https://link.springer.com/content/pdf/10.1007%2F978-3-319-55444-0.pdf https://link.springer.com/content/pdf/10.1007%2F978-3-319-55...
• tchaffee 6y ago
  This article is an excellent example of why most companies should never ask about algorithms in an interview. The author has worked for elite companies and yet even there he rarely had to reach something advanced. I've worked on some cool and really hard stuff in my career including cryptography and a popular Facebook app where my team used a graphdb, etc, etc, etc. And I would fail at most of today's interviews. Fortunately I'm often the one doing the interviews so I rarely have to endure this nonsense. If you ask me algorithm questions on an interview and you're not the equivalent of Google or Facebook in their early years then I'll find a way to end the interview early and you just lost the opportunity to work with a talented dev. Get some training in interviewing. Do the research on best practice. Create the type of interview that gets people talking enough about past work that you learn what they are actually good at. It's not really that hard to figure out how to create an effective interviewing process for the types of problems your company is solving. It's surprising at just how many otherwise smart people fail at creating that.
  • heavenlyblue 6y ago
    I had interviewers grill me about the time complexity of dictionary implementations in python while making assumptions about their behaviour from Java. I was impressed by the fact that nobody ever tried to argue with them before. Basically they were hiring for a Python position and I know that part of the test is the same for everyone. Yet they didn’t know about open addressing.
  • cmrdporcupine 6y ago
    Thank you. I've been poking around the job market again after 10 years not searching, and it's disheartening. I have 20 years software development experience, I work at Google, I'm no spring chicken. I'm not the best engineer in the world, I'm sure, but I am a good programmer. I think I'd be an asset in many jobs. But I just turned down proceeding with interviews at a certain payment processing company because in part they wanted to give this kind of whiteboard coding interview. Our industry needs to give its head a shake.
    • ashconnor 6y ago
• rvz 6y ago
  > When we built Skype of Xbox One, we worked on a barebones Xbox OS, that was missing key libraries. We were building one of the first full-fledged applications on the platform. We needed a navigation solution that we could hook up both to touch gestures and to voice commands. 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.
• gridlockd 6y ago
  99% of the time, the "right" data structure is either an array of records or a hash table, or a tree that you traverse depth-first. 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.
• deleted 6y ago
  [deleted]
• parentheses 6y ago
  algo questions come in many forms. it is a problem space that devs can focus on when preparing for interviews. it side-steps integration issues that occur in real world problems like "implement an HTTP server" or "implement a multi-host parallelization framework". 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
• dolmen 6y ago
  I rarely implement graph algorithms in code. 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.
• _tik_ 6y ago
  working on parquet to json conversion recently.I used graph and dept-first search to create the schema operations.
• sciencewolf 6y ago
  I actually wrote a very similar article recently: https://algodaily.com/blog/does-studying-for-whiteboard-interviews-make-you-a-better-engineer https://algodaily.com/blog/does-studying-for-whiteboard-inte... 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.
• mlthoughts2018 6y ago
  This is kind of dumb because most of the examples just involve built-in language implementations or libraries that implement the stated algorithm. 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.
• deleted 6y ago
  [deleted]
• bluedino 6y ago
  Would love to hear a take on this from a game programmer. They might be a bit more specialized these days, but I'm sure in the late 90's, earl 2000's if you were working on a game, or game engine (and their tools) you used numerous algorithms.
• CydeWeys 6y ago
  This article is hurting its credibility right from the get-go by un-critically reproducing yet again this tired saw from Max Howell: > 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.
  • dgb23 6y ago
    I get what you mean, but I think this can be looked at in a more neutral way, especially if we distance ourselves from the exact Homebrew example. The expectation of a large engineering company is to hire someone who fits well into their way of doing things. Typically they want smart, humble team-players with predictable skills (AKA solid educational background and possibly industry experience). However an open source tool author has completely different self-imposed requirements and capabilities. If successful, they have proven that they can ship reliable software, basically on their own, which people want to use. Which is great, exceptional even. But typically not in terms of the metrics of a large engineering company, except they actually do use the tool/library, deem it important and the role of the programmer would involve developing/supporting it. This also poses the question of: "Why would open source author want to get hired by big company in the first place?" Wouldn't this mismatch of expectations and skill-sets be a hindrance/waste? Aren't there much better places for this exceptional open source author? Startups, other open source projects, self-employment/freelancing, SMEs etc.
  • dekhn 6y ago
    Most Googler SWEs have Mac laptops, not linux or windows laptops. But only a fraction of them use brew to install additional software. I'd love to interview the creator of homebrew. There are so many dependency and reliabiltiy questions that it's clear brew doesn't handle well (same criticism of CPAN, and pip to some degree) in terms of performance or correctness that you could just talk for an hour about graph problems... who knows, something like... inverting a binary tree?
• cableshaft 6y ago
  I expected to see a blank article. Was disappointed. Does look like there's some interesting stuff in the article though, so I'll read it properly later.
• mumblemumble 6y ago
  Being able to use algorithms and data structures, which what this article mostly talks about, is rather a different thing from knowing how to implement them, which is what interviews go after. 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.
• dominotw 6y ago
  > come up with simple ones on your own, like a greedy one. 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.
• woadwarrior01 6y ago
  In this case, this was implementing the AES standard. 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?
• agentultra 6y ago
  I think they're useful to know. I don't mind algorithms and data structure questions in interviews. I use them a fair bit even in some of my most benign, enterprise JSON-schlepping tasks. 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.
• spaetzleesser 6y ago
  I use a lot of algorithms through libraries but rarely implement one. I think people get tired of the typical algorithm interviews because they often focus on implementation and not use.
• whack 6y ago
  I'm increasingly convinced that Algorithms-and-Data-Structure interviews are essentially being used as a proxy for: - 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.
  • ojr 6y ago
    - Retention. If this person spent hours on leetcode, they’ll be less likely to leave the job knowing the effort it takes to get through the gate
    • deleted 6y ago
      [deleted]
    • cocoa19 6y ago
      I'll disagree with this one. I'd actually be inclined to job-hop more frequently if I have the skill to pass hard interviews at any tier 1 company, thus maximizing my earnings. If I don't, I just stay put knowing I lucked out at a great company, knowing it would be hard to get lucky again.
    • quicklime 6y ago
      I hear this so often that I wonder if people actually believe it. If you do, keep in mind that it would require a fairly large conspiracy within tech circles to maintain. A more likely explanation is that it's less effort to come up with and apply a leetcode-style question in an interview scenario. Never attribute to malice that which is adequately explained by laziness and cargo-culting.
    • sj3k 6y ago
      Last I read, the average tenure for an employee at FB is about 1.5 years... Could be different at other place.
    • 6y ago
• cordite 6y ago
  I wrote a typed visitor pattern for validating and rewriting objects with an audit log, it became necessary for an integration where an error response would need to return a modified input if the original could not be processed but he modified one could be resubmitted successfully.
• euix 6y ago
  It's like in any competitive exam where there are too many candidates and not enough positions. If you ever look at the type of math and science problems on Chinese university exams they are not necessarily advance in terms of the topic but they are extremely tricky. A electromagnetism question testing your knowledge of Gauss' law usually in a regular setting would use a charged sphere or some other object with geometric symmetry you can take advantage of. I have seen one question where it involved Gauss' law around the corner of a pipe (the elbow part). 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.
  • humourl3ss 6y ago
    > too many candidates and not enough positions. so sad, some of these smart and talented engineers will take the failure personally. The system needs to change, the only way we can progress is to not waste talent like this. We cannot rely on a small set of institutions (Harvard, Oxford, IIT etc) to output a small group of "elite" engineers, surely the world would be better if everybody that wanted to become an engineer had access to "elite" level education. Top companies have one major complaint: not enough engineers. Bootcamps don't help either, what you want is that "elite" education with a bootcamp price, possibly many bootcamps over time, as skill sets need to adapt and grow.
• deleted 6y ago
  [deleted]
• decafninja 6y ago
  I don't think the issue is DS&A or even leetcode problems in general. 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.
  • richthegeek 6y ago
    It is rather ridiculous. "These two guys spent 6 months thinking about this problem to come up with this algorithm. Now pretend like you can independently come up with an identical algorithm in 45 minutes."
  • ahel 6y ago
    > 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 Agree. Also "there is no hard requirement in completing both part of the exercise" is another lie.
  • redisman 6y ago
    Here's an algorithm some elite CS PhD took a year to research and solve. You haven't seen it before? Too bad, better come up with the solution on the spot. If you can't I'll have to write another blog post about how no one I interview can program anymore?!?
• spicyramen 6y ago
  I don't think there is a right or wrong answer. My experience tells me that everyone is different when implementing solutions. I'm working with a new grad, with MS in CS from a top school. He is great theoretically, but this project requires learning and implementing new tech very fast. thinking outside the box and prototyping a lot unfortunately he is overthinking and delaying the project. On the other side I have seen people that doesn't excel in algos and create great products. My take is that the take home assignment provides a better perspective on candidates than just algos and ds
• guidoism 6y ago
  What is annoying about these interviews is that you are expected to have memoized all of the algorithms be able to implement them while someone is watching, on a whiteboard, in a very short amount of time. In my experience at Amazon and Google we all referred to books and colleagues when working through algorithms.
  • jb3689 6y ago
    The grading rubrics for interviewers usually gives the candidate points for even mentioning particular algorithms, and I would hope that any decent interviewer would help you walk through trying to recall something. It's meant to be a design/application test, not a memory test
    • jrockway 6y ago
      That was my experience. One interview question I was asked at Google boiled down to pathfinding on a graph. I suggested using A* and said "but I doubt I can write that on a whiteboard". The interviewer was fine with that, I got hired. I did many SWE interviews at Google. I came up with my own question that obviously required using data structures and algorithms, but probably not something the candidate had ever thought about. Most people had a good thought process which was 90% of the question; some people arrived at the answer I thought was correct. Sadly, nobody ever came up with a better answer than what I decided was best. I was kind of hoping they would ;) The problem with Google's interview system is that everyone gets to come up with their own questions. Some are bad! Some interviewers are bad! It takes the Hiring Committee a few candidates to recognize this and give the interviewer feedback about what's bad. But, that's why the HC exists and that's why you have 4 or more in-person interviews. The uncalibrated first-time interviewer does not have full veto power over hiring you. It can make for an uncomfortable experience (when is meeting new people and writing code on a whiteboard ever comfortable?), but overall the process does find good engineers. The end result of the process, which I really liked, was that people on the team you're joining assume competency and don't explain simple things to you that you already know. I remember a few discussions in my first weeks at Google that blew my mind; we were talking about idempotency, and nobody needed to explain what it was. Every time I've ever used that word it derailed the meeting completely, requiring a remedial CS 101 course to bring everyone else on the team up to speed about that concept. Everyone at Google knows what that is, so you don't have explain it. It was nice. (This came up again when there was a discussion about state machines. Again, everyone knew what a state machine was, and used them somewhat regularly, so what was in my past life a discussion-derailing tangent was just a thing everyone knew.)
• cmrdporcupine 6y ago
  Last I looked we are still in a market where there is supposedly more open positions than there are engineers to fill 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.
  • notacoward 6y ago
    Take an interviewer who has the benefit of having worked through a problem literally a hundred times, further aided by internal training that represents thousands of iterations. Have them judge someone who hasn't had to solve that particular problem more than once or twice, twenty years ago in a different language (and certainly not on a whiteboard). That interviewer will form an inaccurate opinion of the interviewee's relative ability. Not maybe, and not by a little. Any interview process that does nothing to correct for that is broken.
• Datenstrom 6y ago
  Working primarily on autonomous systems from robotics to avionics I have needed to use quite a few data structures and algorithms including: - 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.
• inancgumus 6y ago
  The problem with interviews is not whether those companies are actually using algos in practice. The problem is that they ask the data structures and algorithms as ruthless puzzless to detect a candidate's level. That's a very wrong approach.
• ralfhn 6y ago
  Algorithms and data structures are very useful and a general knowledge is certainly required. However, when you're facing a problem, do you have to come up with an optimal solution, on a whiteboard, in 45 minutes, and with someone looking over your shoulder?
• munchbunny 6y ago
  As an engineer who works on security software, here's what I've empirically used on the job: 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.
  • harha 6y ago
    This absolutely! The interview process is totally broken, as it tests mainly how much someone is willing to prepare for the interview, which might actually show more how little they focus on doing more productive things in their current job, at university or by starting interesting projects. It also scares away people who might actually be better at the job but not as good or interested in interviews - at least this was my experience at Google compared to the usually more interesting people I worked with at university. It’s just more difficult to test beforehand how someone might actually solve a problem in a good way as you describe. If applicable it’s possible to look at prior work, if you have any other good ways I’d be very interested. Edit: this is actually a good thread to get some ideas on improving interviews.
    • munchbunny 6y ago
      I still do algorithms interviews, sort of. The one-hour interview format is an external constraint, so within that constraint I will do ~40 minutes of coding and ~15 minutes of discussing past projects. I ask a question where the algorithm itself is at most some list iterations or tree traversals, but the real difficulty is thinking through the data and figuring out the right generalizations and transformations to apply. It seems to control decently well for people who have practiced for interviews, because they do the usual dance of asking some clarification questions, mocking the functions, and narrating their code, but many of them hit a wall five minutes in. It's not because their algorithm doesn't work. They're using the right algorithm. The problem is that they haven't thought through "ok what do you do with the data now that you've traversed the tree?" In my experience, for my job, that's usually the actual hard question. For example, if you're checking a JWT, are you validating it in a way that is hard to subvert? Are you taking any time to think about pathological data inputs? The counterpoint would be "what about a candidate who has solid coding skills but stumbles on the problem space because they're unfamiliar with it?" In my sample size of approximately n=10 since I started interviewing candidates this way (admittedly a small sample, but it's the sample I have), I have yet to see someone who writes code well who neglects thinking through the characteristics of the data up front. That said, it's a real issue. Data is usually contextual, so you're at an advantage if you have experience in the corresponding problem domain, which is not something I'm measuring for in the coding exercise. While I try to pick topics that should be universal, I inevitably get surprised, so I offer three different topics based on the candidate's resume, and I give the candidate a choice. The biggest weakness I've seen in my interview process (within the scope of what you can do with only one hour) is that it doesn't control for nervousness or people who just don't operate well under time pressure. Unfortunately that's an unavoidable consequence of the mandated form factor, so I have to try my best to help relax the candidate and then rely on my gut for how much nervousness or pressure affected the interviewee.
• chadash 6y ago
  > The most frequent data structure I've used regularly was hashtables and the hashing function. It's such a handy tool from counting, to detecting duplications, to caching, all the way to distributed systems use cases like sharding. After arrays, it's easily the most common data structure I've used on countless occasions. Almost all languages come with this data structure, and it's simple to implement if you'd need it. 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.
• jcranmer 6y ago
  Working on compilers, graph algorithms of various kinds tend to come up rather frequently. The only one that I recall having to implement myself was enumerating elementary cycles in a graph. That said, you often have to do a modified standard tree or graph traversal, so some variant of BFS or DFS is pretty common. 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.
• jorangreef 6y ago
  Where things get interesting is the mismatch between Big-O data structure complexity analysis (as typically discussed in interviews) and actually knowing about the hardware, the operating system, the memory hierarchy and things like cost of context switches and cache misses. 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.
• jkingsbery 6y ago
  Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS (https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844 https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...) this is. The interviewer didn't like this, so he said "Pretend you're an engineer at Google. You need to have a convex hull. What do you do?" And I said probably the most correct thing I've said in any interview: "I would go look it up." He really didn't like this answer, but we struggled together for an hour, with him frustrated that I couldn't remember the details of an algorithm I last had seen 6 years earlier and couldn't recite in 60 minutes what took our professor 180 minutes of lectures to cover, and me frustrated that would have taken me 30 seconds to look up. 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.
  • deleted 6y ago
    [deleted]
  • dmoy 6y ago
    Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it, your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets burned because someone posted it all over the internet in their blog post titled "How I got a job at Google!!" and then bumped way up the list on hackerrankcode-whatever I forget the websites... it's easier to come up with a new one, because you just pick a new esoteric algorithm and ask that. And honestly, coming up with interview questions can take awhile. When you have 5 or 6 very calibrated questions and all of them get burned and banned in a one quarter span, you now have to spend the better part of a whole workweek, plus dozens of more interviews coming up with new questions and recalibrating. But, I just refuse to ask those types of questions anymore. They really don't give useful signal. The only three bits of signal you get are "does the candidate already know this algorithm (or are they a supergenius who just figured it out under time pressure)? can they communicate it to another engineer? can they write code?" Importantly if the answer to the first question is no, then you get zero signal on the other two parts. That basically means as an interviewer you just failed your job.
• haecceity 6y ago
  Who implements AES? I thought everyone just copy paste from reference implementations.
• Vervious 6y ago
  Uber rolled their own crypto? Do they still? I thought you could always import some C library on iOS or Android (or use bouncycastle, unless that wasn't around then)
• kevinventullo 6y ago
  In my first year at Facebook, I saw an opportunity to use a priority queue to improve a service my team supported. It ended up saving something like 30 machines.
• Teknoman117 6y ago
  Can anyone recommend a good resource for learning about Dynamic Programming? Not from a FAANG interview perspective, it's something that I didn't really wrap my brain around in the algorithms courses in University. Five years into my career I still haven't ever had to use it. It's something I feel mildly guilty about.
• posedge 6y ago
  Is it just me or is the author working on far more interesting problems than most of us?
• kelnos 6y ago
  It's interesting to see someone else's list. If I were to make a similar list, I think I'd have very little overlap with this one. And the overlap that is there, like using hashtables and hashing, I'm not sure passes out of the realm of triviality: while I've built hashtables and written hash functions myself, I don't recall any job where I was required to do that, rather than just using something off-the-shelf. 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.
• tonymet 6y ago
  I like his point at the end, that the interviewing process is the most pragmatic one, not the best. It reminds me of boarding airplanes, where we've chosen pragmatic boarding strategies, but not the most efficient. Remember people processes need to be the least bad, not the best. Most of the best are either unworkable or tyrannical.
• ameyv 6y ago
  The comments on this thread are gems. Thank you all. :)
• sharken 6y ago
  Thanks for this insightful look into software engineering in tech companies, as a more DevOps person this is very useful to know about, i.e. there are just too many things outside of programming that are interesting so developing full time is not an option.
• jiveturkey 6y ago
  nice thread. sorry for the noisy comment, but most threads similar to this end up with folks griping that the interviewer asked them to invert a binary tree or other such super basic stuff that -- no, you do not do every day or even ever at all, but -- is 101 level stuff that you better be able do in a few minutes from first principles. sticking with that theme, even AVL or red/black you better be able to describe it off the top of your head although asking to implement a working solution covering all edge cases in the span of an interview session is nonsense. 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.
• phendrenad2 6y ago
  I sometimes look at the hiring experiences of other kinds of engineers longingly. Electrical Engineer? Asked to design a circuit. Chemical Engineer? Asked to synthesize a chemical. Mechanical Engineer? Asked to design a car. Software Engineer? 50 million different processes based on the whims of "senior engineer"s with 4 years out of college, mostly trivia questions out of a book that only 1% of software developers actually use in everyday work
• musicale 6y ago
  > The Algorithm Design Manual and Algorithms: Fourth Edition are both books I picked up back in the day to refresh some of the my university algorithm class studies. I gave up midway, and found them pretty dry, and not applicable to my day-to-day work. 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. ;-(
• thecat08021 6y ago
  I'm surprised that you didn't recommend Knuth as the best reference for algorithms. 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.