27 ms·

An Algorithm for Passing Programming Interviews (2020)

411 points by spekcular 5y ago

mrkentutbabi 5y ago
After practicing bunch of Leetcode questions (around 300), and looking at videos from hiring managers that claimed to work at FAANG, or even the example interview at FAANG itself. I am actually more confused, whether Leetcode is the thing that they are looking for or not. Here is what I observed: - Some Leetcode questions require tricks/complex algorithm that you absolutely won't find in the span of 45 mins. If you do, either you are ultra genius, that able to find and modify a variation of Kadane's algorithm in 45 mins (even though it is a simple one), or you just have seen the question before and you just somewhat memorized it. Obviously the answer is the latter. In this case, what do actually FAANG companies really looking for? Is it the proof that a candidate has been finishing hundreds of questions? - I've seen videos on interview example on Youtube, and they all present medium to easy Leetcode questions. The onsite interview at FAANG is mostly hard questions. So that means there are disconnect from how FAANG actually interviews and how these interview samples are conducted. And again, solving a hard question that you've never seen before optimally require way more than 45 mins, unless you've seen the question before, which goes back to no. 1 - Hiring managers or recruiters that gave advice. Saying stuff like "talk a lot, talk to the interviewer, interview is a 2 way street" and other feel-good self-help stuff that has nothing to do with the actual interview and don't help at all. Claimed that what the companies are looking are your thought process. Nope, lies. What companies are looking is whether you can solve this problem optimally in 45 mins. If you have thought process, speaking during the interview, etc, and you couldn't even finish the question in brute force, then you fail. If you able to finish the question with brute force, but not optimal, you also fail. - Experienced senior engineers that definitely rusty on Leetcode and just did basic DS&A brushup and definitely couldn't pass Leetcode hard, got offered with TC way higher than these fresh grads. So, I'm quite confused on what are the companies really looking for? I think I concluded that FAANG companies are indeed practicing what they say "eliminating false positives and have a really high false negatives". Therefore the whole interview Leetcode fiasco is just a number's game. A few things: - If you are senior engineers and have track record at other companies, then you don't need Leetcode to prove your worth. Since statistically, you are already worthy and can perform in your job. - If you are not a senior engineer from other FAANG companies, then you just have to play the number's game. I.e, keep interviewing (and Leetcoding) until somehow the combination of your studies and the mood of the interviewer and the questions that come up during that interview day rolls in your favor.
LewisVerstappen 5y ago
> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.
- strstr 5y ago
  I’d turn that question back around at the candidate, unless it were for a junior candidate. I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.
  - MathCodeLove 5y ago
    Why??
    - sjburt 5y ago
      Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.
      - vanusa 5y ago
        Because in the real world you don't know the runtime of the optimal solution, The question specifically referred to target performance, which IRL is almost always known and freely communicated (in at least ballpark terms). As in: "Find the median of this array of 10k integers in .01 seconds please. Not 10 billion, just 10k". You say: "OK, sort and done." IRL if someone at your job says: "Write some code to find the median of an array of integers. I'm not going to tell you how many, even the order of magnitude. Could be 10k, could be 10 billion." You say "WTF?" They say: "I don't care about whether you get the right solution or not! I just want to see how think about a problem." I think you'd know where to tell them where to put that question.
kjgkjhfkjf 5y ago
Many interviewers ask candidates to explain their thinking. I don't think this dubious process of elimination would pass that test.
- colechristensen 5y ago
  Right? When I’m interviewing I care most about the thought process and the ability to communicate in depth about something technical, the actual solution isn’t really that important at all.
  - travisjungroth 5y ago
    This is the thought process. I use something very similar and have done well in interviews. I found I did better in interviews when I showed my thinking less, or adapted it to the interviewer. Stating the things I'm not doing is useful, but too risky. Just hearing the words "linked list" in a problem that can't be solved with linked lists (even in the sentence "linked list doesn't seem to be right") startles some interviewers. A high enough percentage I don't want to roll that die six times during a round. The silliest example is I like to work on problems by writing code. Yes, even if I don't understand the problem perfectly. Seeing some code helps clarify my thinking and I throw most of it away. Freaks. People. Out. Writing down some wrong line of code may as well be blasphemy. Strangely, not the case with comments. So my technique in interviews was to write comments that were as equivalent as possible to code and then convert it to regular code when I felt things were close enough. The biggest challenge in Python is not making it so similar that it becomes obvious what you're doing.
    - hemloc_io 5y ago
      lol yeah having been through these loops and training to do these loops it really seems like most people say they want to see “thought process”, but what they’re really looking for are the usual cues you see in all the prep info online. E.g. ask some clarifying questions before coding, write or suggest a brute force, and then write an optimized algo.
aurelianito 5y ago
The first example test given (rate limiter) gives a bad answer. I wouldn't use this method.
- bonoboTP 5y ago
  Elaborate?
  - sk5t 5y ago
    The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Tabulating call count by division(s) of time would be less obviously problematic.
    - taeric 5y ago
      Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.
      - sk5t 5y ago
        I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work? - putting 500 timestamps into a queue - inspecting 500 queue entries and removing each - putting 500 new timestamps into a queue
        bonoboTP 5y ago
        Depends on the requirements. If it's enough that the client doesn't make >N requests within the same "calendar second", then counting in bins is enough, no need to store timestamps. But then you could have a client send N requests in the second half of second k and N requests in the first half of second k+1, so you'd have a 1 second period (that spans two "calendar seconds") with 2N requests allowed. Since such rate limits are often not extremely exact, just an order of magnitude, this quantization/rounding effect may be negligibe and the speed may be worth it. But maybe not always. The original problem statement did not say that it's fine. Probably it's a good sign if an interviewee asks if this would be okay too.
arduinomancer 5y ago
Interviews are really a dumb game these days so if you want to really game it you can go with a statistical approach: * Practice questions by company on LeetCode, sort by frequency of last 6 months and work down the list, do maybe 75-100, the list updates once a week * Search for the company on the LeetCode forums and sort by most recent. If a question is not on LC yet it will likely get posted there, so you can get really fresh intel. I've read of people doing this and getting like 6/6 questions they've seen before.
- henning 5y ago
  This is a great way to start off a business relationship with dishonesty and cynicism. Enjoy your career.
  - ThalesX 5y ago
    Can I have some of that ‘work through tens or hundreds of coding problems that are of no future relevance to me’ dishonesty and cynicism?
    - WalterBright 5y ago
      It filters out the frauds. Fraud on resumes is very common.
  - aaronbrethorst 5y ago
    This is a great way to start off a business relationship with a company that wants to haze you to get you to prove your desire to work there.
  - dang 5y ago
    Please don't cross into personal attack, no matter how wrong's interview preparation strategy is or you feel it is. Perhaps you don't feel you owe them better, but you owe this community better if you're participating here. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- 5y ago
posharma 5y ago
This is a good post for beginners. Fortunately or unfortunately coding interviews have become much tougher. This resource [1] has helped some. [1]: https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed https://hackernoon.com/14-patterns-to-ace-any-coding-intervi...
ldjkfkdsjnv 5y ago
Before people start complaining about leetcode and how it doesnt exemplify skills: its a proxy for a combination of: intelligence and how hard you are willing to study the computer science knowledge shown is just a bonus EDIT: One last thing to throw in, its pretty clear that theres a correlation between the top software companies and how hard their leetcode interviews are. You can claim all you want it doesnt work, but facebook and google have very hard leetcode interviews and are known for the best software
- lostcolony 5y ago
  The former only in case of the latter. I.e., if someone isn't willing to grind leetcode, their intelligence is irrelevant. If someone is willing to grind leetcode, then yes, their intelligence is a secondary variable. Regardless, such styled interviews are intended to minimize the number of false positives (since the companies have so many applicants it's safer to err on the side of "no"; there are more in the pipeline), which means they will also generate a tremendously high number of false negatives.
- posharma 5y ago
  You've to be a genius to solve a "hard" unseen leetcode problem in 15 mins correctly. Facebook is notorious at expecting candidates to regurgitate solutions to problems in 15 mins. Intelligence plays a lesser role than exhaustive and painful practice which involves solving the same problem multiple times. It's a full-fledged examination that expects you to excel while being constantly watched and judged.
  - Frost1x 5y ago
    >It's a full-fledged examination that expects you to excel while being constantly watched and judged. and interrupted, frequently, because that's also perfectly normal. It's comical how this industry now thinks these arcane and often quite difficult DS&A interview question processes are reasonable and how it's been so normalized people just study this for weeks before applying to a new position, sacrificing evenings and weekends just for job mobility. These processes are not even proxies for intelligence anymore except maybe the very few people so wired they miraculously could jump through a handful of these with optimized solutions in 15 minutes without ever seeing and solving the problem before. I've worked with very intelligent people before who qualify as geniuses and they couldn't solve these problems under these conditions, especially not multiple of them without having at least seen the problem before.
hsavit1 5y ago
Glad to hear that the software engineer selection method is determined by this very rigorous process of character assessment. No wonder why big corporations produce such amazing teams.
- avl999 5y ago
  I am not gonna die on a hill defending these types of interviews but they are infinitely better than the alternatives. Alternatives are often subjective criteria like "culture fit" which can lead to nepotism/other types of biases or hiring being done by sorting resumes based on the prestige level of the college of the applicant and just running down the list from the top (which happens in other professions like law). Ofcourse the interview process is (or atleast is supposed to be multifaced) and passing these problems is just one of the facets of the process. A great candidate can bomb one of these questions but I wouldn't necessarily reject them just because of that (although that happens in practice in the industry) and wouldn't necessarily okay someone just because they aced one of these questions. I'd take complaining about these type of problems any day over complaining about only being able to get a job in certain companies by having connections or having gone to an Ivy League school.
  - vanusa 5y ago
    Alternatives are often subjective criteria like "culture fit" There's a vast territory of approaches that are neither leetcode hazing or culture fit tests. And which, while nuanced, are basically objective. Work sample evaluations do quite well, for example. As do in-depth technical discussions about ... just about any subject the candidate claims to know about. Neither of which have anything to do with "culture fit".
    - esyir 5y ago
      >As do in-depth technical discussions about ... just about any subject the candidate claims to know about. Having attempted to do this after reading all the HN screeds, I found that this failed horribly. You'll find a large number of people who seemingly know the theory, but can't execute worth a damn. They can happily talk on and on about normalization, regularization, imbalanced datasets and so on. Then they fail fizzbuzz. I then put the programming screen first.
avl999 5y ago
I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough. If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Recursion but they have subtlety to them that requires practice for most people. They tend to be tricky to get right in an interview setting without practice as due to the really bad time complexity of most problems of this type they almost never come up in production for most people so they're not even on the radar of most engineers.
- malisper 5y ago
  There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time. Of course there are even more niche data structures like a Fibonacci heap which have O(1) insertion, but you will have to get extremely unlucky to get asked about a Fibonacci heap in an interview.
  - avl999 5y ago
    That's reasonable, makes a lot of sense.
  - arduinomancer 5y ago
    Wouldn't that mean you have to implement the binary tree as part of your solution? Seems way easier/time efficient to just use the built-in heap/priority queue of the language standard lib
    - Jensson 5y ago
      C++ has built in binary trees with fast iteration. The C++ binary tree is my favourite standard library data structure of any language I've used, it isn't the fastest out there but it has so many useful things you can do with it. You can use it as a heap, you can use it as a dictionary, you can use it to sort things, you can insert items at the same time you iterate through it and if they are after where you are in the tree then you will find them in your iteration etc. It does so many things right that others don't do, I'm sure the others data structures are slightly faster but the C++ binary tree is so powerful and still fast enough for basically every problem.
wackget 5y ago
That website's choice of font colour makes for frustratingly low contrast and therefore is a recipe for eye strain. I didn't waste time reading it.
samspenc 5y ago
Good stuff. A couple of comments to the post: Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Post doesn't mention this, but one other common pattern I've seen requires a tree data structure, and those interview questions can be solved with recursion. Basically once you have a tree data structure, you write a f(node) that will simply call f(left) & f(right) recursively -- or for-each(child in children) { f(child) } for non-binary trees.
- bradleybuda 5y ago
  I agree with your answer on the rate limiter, but I think it depends on whether the spec is for rolling or fixed one-minute windows. The question is ambiguous, but the sample answer implies that we want to track rolling windows. If that's the case, an improvement on the answer is to use a ring buffer instead of a linked list, which allocates a fixed set of memory up front (slower to initialize) but then is allocation-free on each invocation.
- malisper 5y ago
  > Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. As Bradley said this implementation can be called more than 10 times within a 1 minute window. If it's called 9 times at the last second of one minute and 9 times at the start of the next minute, it will be called 18 times within a two second interval.
- john_moscow 5y ago
  >Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Why on Earth? Given that the timestamp cannot randomly jump backwards, you can achieve the same results by just storing the timestamp of the first call after a reset, and the number of calls sharing the same date/hour/minute, resetting it to 0 when the minute advances. That said, it won't be entirely what was asked, since it won't have the rolling behavior.
ofou 5y ago
Backup link https://archive.is/fg8hI https://archive.is/fg8hI
dmurray 5y ago
There's a bit of a "draw the rest of the owl" thing going on here. If you have the experience to confidently eliminate the likely approaches that don't work, then you must know quite a bit about those approaches and their applications. And in particular, I'm not sure I can agree on eliminating recursion in the anagrams problem. He just says > Recursion – No way to apply recursion to the problem. but...there is? One plausible approach, I sort each of the strings and put them in a trie. A fancy sounding thing, but really just a data structure which allows me to rephrase "someString in myTrie" as the recursive "someString is null || (head(someString) in myTrie.keys && rest(someString) in myTrie[someString])". I'm not arguing that this is better than a hash table, though I think it probably is on some workloads - just that it's not possible to rule this out and solve the problem by pure process of elimination.
- travisjungroth 5y ago
  That's the nature of thought frameworks. You need to fill in the gaps yourself. It's still useful to have an organized approach. In my experience, people can know how well each technique would be suited to the task at hand if asked. But, they rarely consciously go through each technique they know and consider if it's the right approach. Most people would be well served to do this more often. Btw, this is a big failing in interviewers who help. Asking the right questions (what data structure could you use here?) is incredibly helpful. So helpful that you're not testing them on a slow moving, relevant skill (structured thinking) but instead a fast moving, less relevant skill (what data structures do you know?). Bad move.
  - asxd 5y ago
    I kind of agree, in that a good candidate should probably already be thinking "what data structure should I use here" no matter what the problem is. Just always think about what data structure to use. Every problem requires one. More in the vein of what you're getting at though, I think helping a nervous candidate by asking obvious questions like this can be helpful: "What data structure would you recommend using for this problem?", or "What programming paradigm do you think would fit this problem best?". It's a bit of an ice breaker, and can lead to more interesting conversation than the candidate just sitting there, quietly thinking (admittedly, possibly not a good sign for a candidate if they do this, but interviews should be built around making it a good experience for the candidate as well).
PaulHoule 5y ago
It is amazing how far you can go with: 1. Look it up in the hash table, 2. Look it up in the literature
yawgmoth 5y ago
This might get you OK marks on the "problem solving" portion of a coding interview. But a programming interview will also look for signals of other skills -- did you communicate your approach? Really good candidates will verbally communicate their solution before writing code. The best often write out how a particular data structure changes with some iteration. If you're a senior engineer, a coding interview should include some demonstration of correctness. Maybe you write one primitive test harness for a positive test case and add comments or empty methods enumerating a few other test cases.
SMAAART 5y ago
https://archive.is/fg8hI https://archive.is/fg8hI
Supermancho 5y ago
The anagram solution leaves the actual hard part unfinished^. Also, to solve in O(n) you need a bit array (or a database like Postgres that can do an XAND on a string). > Sort the characters of the words alphabetically. Since anagrams are all made up of the same letters. This will give us the same string for any pair of words that are anagrams of each. Correct. > Produce a dictionary of the number of times each letter occurs in each word. Well, yeah...algorithms aren't the hard part for this kind of question. "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word. Take a string of zeroes, which is (maxWordlength*26) long. Each segment of 26 represents a compositional letter from the word. So 100000 00000 00000 00000 00000 is 'a' Now you can create your dictionary from the sorted word indexes. pin becomes inp becomes 000000 00100 00000 00000 00000 000000 00000 00100 00000 00000 000000 00000 00001 00000 00000 same as nip (becomes inp, etc) You can add 26 zero sets, to pad out to the length of longest word, if words are variable length. ^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise.
- malisper 5y ago
  > "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word. How so? "aab" is an anagram of "baa", but they are not anagrams of "ab".
  - Supermancho 5y ago
    100000 00000 00000 00000 00000 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 aab and baa 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 000000 00000 00000 00000 00000 ab You aren't "counting" the number of characters. You're making an encoding that includes that information, without the aggregation. The aggregation is irrelevant as is the order of duplicate characters.
- 5y ago
deleted 5y ago
[deleted]
troutwine 5y ago
There’s also two additional programming techniques you should be aware of: * Dynamic Programming </snip> How often do folks here use dynamic programming techniques in their professional lives? My own niche is systems programming. Dynamic programming is an important technique, sure, but given how rarely I see it used in practice compared to, say, statistical estimation it feels very overrepresented in interviews. But, maybe that's my own niche being unusual.
- hinkley 5y ago
  More than my coworkers, not often enough, and not very often. Many people think DP and caches are synonymous, unfortunately.
  - titanomachy 5y ago
    I usually reach for caching first because it’s more intuitive (for me and my reviewers) and because we often have well-known size bounds and relaxed enough performance requirements that make an “analytical” solution unnecessary.
    - hinkley 5y ago
      Caching creates a mature product, no matter what your product roadmap says. If a rewrite is the tool of last result, caching is the second to last. Like pruning shears, once you use them, your world of options collapses considerably. All of those opportunities are gone and nature won't let you put them back. Critically, caches are global shared state. That's why cache invalidation is the hardest thing. Global state also means people stop trying to have a data flow/architecture. None of these call trees need to advertise that they use a particular value because I can just grab it from a global if I need it. You don't know where things are actually used anymore because they all come from cache lookups, and because the lookup is so cheap (under typical system load, but catastrophic under high load), people don't even try to hold onto previously acquired data. They just fetch it again. Which is another boundary condition for cache invalidation (what if half a transaction has the old value and half the new value?) They make flame graphs essentially useless. Sometimes immediately, or once the above starts happening. You quickly have no clear idea what the cost of anything is, because you never pay it, or if you try to pay it you end up amplifying the cost until there is no signal. Once people are promiscuously fetching from the cache, they don't even attempt to avoid duplicate lookups, so activities will end up fetching the same data 6 times. If you turn off the cache entirely for perf analysis then the cost skyrockets and the flame chart is still wrong. You are back to dead reckoning and manually adding telemetry to potential hotspots to sort it out. This is very slow, and can be demoralizing. Quickly this becomes the fastest our app will be for a very long time.
rrradical 5y ago
For the second problem, I had an idea for a different hash function. Basically map each letter to a prime number (e.g. c = 5, d = 7) and then multiply the values in a word together. I guess depending on the length of the words it might overflow. But I thought it was interesting.
- foreigner 5y ago
  I gave this very solution in Google interview many years ago. It does assume that the input characters are of a limited set, e.g. English alphabet. The interviewer said they hadn't heard that answer before. It wasn't what they were expecting and took them a while to be satisfied it would work. I was offered the job but didn't end up taking it.
shahbaby 5y ago
This type of top down learning doesn't work for interviews. Just like how you can't learn math by reading high level summaries written by others. You have to grind through it and see the connections yourself. The author's lack of depth shows when he says that no graph means you can rule out DFS. I also disagree on asking interviewer for the expected runtime. You're needlessly adding another constraint on yourself by doing that. You should ask for the input size and then figure out the best runtime that you can reach. A working suboptimal solution is more likely to get you to the next round than an incomplete attempt at an optimal solution.
andrew_ 5y ago
Or don't agree to interviews that include algo challenges, leetcode/hackerrank nonsense, array shuffling shenanigans. Choose companies that put thought into their evaluations.
- o10449366 5y ago
  Just my $0.02: I'd much rather spend a few weeks refreshing basic data structures and algorithms than doing the "non-algo" challenges I've gotten because they feel way less objective than getting questions where there's a correct answer. Most of the time the alternative to non-algorithm questions is some form of take home assignment that's usually multiple hours long and that you get no feedback on or chance to correct. For example, I interviewed with a company where they asked me to design a program to parse some CSV data and I was told in the next round I would pair with an engineer to go over an expansion of the code. The parsing was trivial in Python and I submitted my solution with full unit tests and what seemed sensible to me, but it was as useless of an exercise as asking me algorithm questions because on a job I'm almost always going to adjust my coding style and paradigm to the context and needs of the company. I commented my code as such to explain that if there were different constraints on the data size or API I would make different design choices than the one I submitted, but it didn't matter - I submitted and received a rejection less than 24 hours later and never got to the next round where I would actually walk through the code with an engineer. It was a complete waste of multiple hours of my time trying to produce thoughtfully designed code - I'd much rather bang out a breadth first search in 45 minutes.
  - sgerenser 5y ago
    At least you got a rejection! I’ve done take home assignments that resulted in nothing but :crickets: in response.
  - quasiprime 5y ago
    On one hand I like take-home exercises because they are closer to what is a real world job and I guarantee the quality of my deliveries. Up to now I can say I've passed every single take home exercise that was thrown at me. On the other hand... the time I spent on those is abysmal. If I sum it up, I must have spent over a month working on take-home exercises. And even if I passed all of them, in the end no company gave me an offer because I wasn't a cultural fit or something. One company even ghosted me after having me to do a 1-week take-home exercise where I had to build an entire app, front end and back end, that consumed an open data API that had 1 million rows. I still prefer take-home exercises because are more realistic and make more sense than timed, algorithmic exercises. But I wish companies would do their cultural fitness thing _before_ having candidates to spend their time on their code challenges.
bottled_poe 5y ago
It’s almost as if you’re learning what is expected of a suitable candidate.
transitivebs 5y ago
Here's a similar resource for anyone interested in this topic: https://transitivebullsh.it/gaming-cs-interviews https://transitivebullsh.it/gaming-cs-interviews
shp0ngle 5y ago
What kind of hash table is O(1)? Or did I forgot everything from university already? You cannot have a general O(1) hash Well maybe in best case/average case, when you design the hash space big enough. Ugh I really did forgot everything.
- hailwren 5y ago
  The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost across all inserts. There are always more inserts than the cost of resizing, so you end up w/ amortized O(1).
- vlovich123 5y ago
  Not sure I understand your concern. Are you asking about worst case? All hash tables I believe are O(n) worst case because of the possibility of collisions (or the need to resize in the case of an insert). Most people talk about amortized performance though (ie when you are successful at reducing the likelihood of worst case to a rare event). Amortized time is obviously dangerous if you’re in a real-time system (eg games) where it’ll manifest as stuttering or latency spikes or potentially even worse if you’re having to respond to hardware events in a timely manner for proper operation.
  - Dylan16807 5y ago
    It's possible to gradually resize a hash table to prevent spikes. For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.
    - vlovich123 5y ago
      > It's possible to gradually resize a hash table to prevent spikes. Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. > For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'. Yes, but the vast majority of implementations don't do a good job here. Howard's "Types Don't Know #"[1] paper is extremely well thought out and I have yet to see this adopted (except for Rust - Rust has a good track record of adopting good ideas like this and having the benefit of coming late to the game). I think it's safe to say that most hash tables don't have good worst case times (which when combined with resizing behavior of insertions, means you have super-linear worst case times on insertion). [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...
solididiot 5y ago
Interviewing has become a theater of the absurd. You get examined on things that won't be useful in 99% of your work. People put in hours to prepare and game it. Overall countless hours go to waste to just play the role. Most times it doesn't even show whether someone can think (what you might see as thinking might be well rehearsed "act as dumbfounded for a while").
feoren 5y ago
Am I crazy or is the first answer terrible? I sat down and wrote out and answer for the problem and I initialized one integer and one timestamp. It should be O(1) time and O(1) memory easily, right? I'm seeing comments saying they'd use an array or a hash table -- why are you using any data structure? You don't need to remember how many times it was called 61 seconds ago; just keep a timestamp and the last time you reset the timestamp. If you need it to be clock-minutes instead of rolling (it doesn't; whose clock, anyway?), then just round the timestamp. The obvious follow-up question is "ok, what if it needs to be limited to 10,000 calls per minute?" You're going to keep 10,000+ elements in some collection for no reason? I wouldn't immediately reject a candidate for coming up with this answer but I would seriously question their thought process on this one. In fact it's kind of ironic that his first example exposes how bad this advice is: by trying to meta-game, starting from a few example data structures, he shows he completely misses the solution that is both simpler and much more performant.
- branko_d 5y ago
  I don't think you can have a "sliding window" of time just based on that. The next time you call the function, you need to count how many of the old calls are still "unexpired". This number (potentially) gets lower with each passing quantum of time. How can you do that without holding a timestamp for each call? Please clarify if I misunderstood you.
  - GistNoesis 5y ago
    I think you can have a more performant algorithm if you soften the constraint a little. (see my previous comment https://news.ycombinator.com/item?id=29776678 https://news.ycombinator.com/item?id=29776678 ) TLDR : You have a maximum of N credits, when time pass you earn credit at a rate of N credit by window_size, but if the time since previous request is less than window_size/N you lose 1 credit. I don't think you can have more than 2*N requests in any sliding window without tripping the filter, but you can't consume more than the average of N requests / window_size without tripping the filter. I think it's a better solution than the question asked by the author, because when you are rate limiting, you and the client may not have exactly the same time, and you might have edge cases like where the client batch 60 requests in a few ms every minute. If there is some time-jitter in the requests you may have 120 requests in 59.9 seconds. (Bonus question : What time-stamping of the request should be used ?) Whereas with my solution it is more forgiving, it allow the client to use all its rate credit without risking to trip the filter if he respect the rate intent.
angarg12 5y ago
Almost all advice online about interviewing is written from the point of view of the candidate. Sometimes this is good advice, but sometimes it devolves into some kind of astrology, where candidate are just guessing how things work. I've done +300 interviews at FAANG so I can share bit of advice from the interviewer's side. The caveat is that this is based on how I conduct interviews, so YMMV with other people. * Always ask clarifying questions. Almost all problems have some level of ambiguity that you need to clarify. This is intended. The more senior you are, the more important this becomes. * Explain your approach before you begin, and even while you code. This gives the interviewer a chance to help you if you are down the wrong path, or even just understand what you are up to. * If you get stuck, ask for help! think of this as a pair programming session rather than an interview. I much prefer a candidate who gets stuck, ask for hints, gets unblocked and writes good code, rather than one that doesn't ask for help and writes not-so-good code. * Caveat: There is a tension with asking questions. There is such a thing as too much help, e.g. I need to explicitly tell you how to solve the problem. Use judiciously. * Take interviewer's hints. The interviewer has probably asked this question dozens of times and knows it inside out. If they give you a hint, 99% of times they are on to something. * Personally I don't like "hard LC" problems. Instead I prefer medium difficulty problems, and spend extra time probing the candidate's coding skills. This includes: 1. Write tests. 2. Handle corner cases/incorrect inputs. 3. Discuss how to scale the code. 4. Discuss how to refactor the code. * If nothing else, write the simplest brute force solution you can think of. As an interviewer I need a coding sample to evaluate the candidate. Trying to and failing to implement an optimal solution is worse than implementing a correct brute force one.
- deleted 5y ago
  [deleted]
- mettamage 5y ago
  I appreciate the caveat. Caveats are almost never given when people give advice and it is exactly the thing that people get stuck on when they take the advice to heart.
- Jaygles 5y ago
  Have you ever passed someone who wrote brute force algorithms?
jb1991 5y ago
> You probably won’t be expected to implement a binary search or sorting algorithm, but you should be aware that they exist. Lol. Pixar‘s coding interviews are well known to do exactly just that: implement a binary search tree from scratch.
wly_cdgr 5y ago
Just be likeable
lucraft 5y ago
Maybe the title should be "An Algorithm for Passing Algorithm Programming Interviews". This wouldn't help you pass our Programming Interview in the slightest.
hiyer 5y ago
Hash Tables Linked Lists Binary Search Trees I would add tries to this list - I was asked trie-based questions in 4 of the companies I interviewed with over the last couple of years, including a FAANG.
deleted 5y ago
[deleted]
mettamage 5y ago
One thing that I have noticed that FAANG doesn’t do well is: help people with sleep issues. It’s not their job [0], but I do think there are some talented insomniacs that are great employees (given that they can mostly work on their own schedule, except for meetings). I remember that I interviewed for Facebook and I was so sleep deprived, I could barely write a for-loop. Ironically, I passed that interview but I couldn’t pass others that required some more creative thinking or more memorization. [0] While it is not their job, FAANG companies do mention that they are accommodating candidates with mental health issues, and I’d argue that insomnia (diagnosed or undiagnosed) should be one of them.

411 points by spekcular 5y ago

After practicing bunch of Leetcode questions (around 300), and looking at videos from hiring managers that claimed to work at FAANG, or even the example interview at FAANG itself. I am actually more confused, whether Leetcode is the thing that they are looking for or not. Here is what I observed: - Some Leetcode questions require tricks/complex algorithm that you absolutely won't find in the span of 45 mins. If you do, either you are ultra genius, that able to find and modify a variation of Kadane's algorithm in 45 mins (even though it is a simple one), or you just have seen the question before and you just somewhat memorized it. Obviously the answer is the latter. In this case, what do actually FAANG companies really looking for? Is it the proof that a candidate has been finishing hundreds of questions? - I've seen videos on interview example on Youtube, and they all present medium to easy Leetcode questions. The onsite interview at FAANG is mostly hard questions. So that means there are disconnect from how FAANG actually interviews and how these interview samples are conducted. And again, solving a hard question that you've never seen before optimally require way more than 45 mins, unless you've seen the question before, which goes back to no. 1 - Hiring managers or recruiters that gave advice. Saying stuff like "talk a lot, talk to the interviewer, interview is a 2 way street" and other feel-good self-help stuff that has nothing to do with the actual interview and don't help at all. Claimed that what the companies are looking are your thought process. Nope, lies. What companies are looking is whether you can solve this problem optimally in 45 mins. If you have thought process, speaking during the interview, etc, and you couldn't even finish the question in brute force, then you fail. If you able to finish the question with brute force, but not optimal, you also fail. - Experienced senior engineers that definitely rusty on Leetcode and just did basic DS&A brushup and definitely couldn't pass Leetcode hard, got offered with TC way higher than these fresh grads. So, I'm quite confused on what are the companies really looking for? I think I concluded that FAANG companies are indeed practicing what they say "eliminating false positives and have a really high false negatives". Therefore the whole interview Leetcode fiasco is just a number's game. A few things: - If you are senior engineers and have track record at other companies, then you don't need Leetcode to prove your worth. Since statistically, you are already worthy and can perform in your job. - If you are not a senior engineer from other FAANG companies, then you just have to play the number's game. I.e, keep interviewing (and Leetcoding) until somehow the combination of your studies and the mood of the interviewer and the questions that come up during that interview day rolls in your favor.

LewisVerstappen 5y ago

> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.

strstr 5y ago
I’d turn that question back around at the candidate, unless it were for a junior candidate. I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.
- MathCodeLove 5y ago
  Why??
  - sjburt 5y ago
    Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.
    - vanusa 5y ago
      Because in the real world you don't know the runtime of the optimal solution, The question specifically referred to target performance, which IRL is almost always known and freely communicated (in at least ballpark terms). As in: "Find the median of this array of 10k integers in .01 seconds please. Not 10 billion, just 10k". You say: "OK, sort and done." IRL if someone at your job says: "Write some code to find the median of an array of integers. I'm not going to tell you how many, even the order of magnitude. Could be 10k, could be 10 billion." You say "WTF?" They say: "I don't care about whether you get the right solution or not! I just want to see how think about a problem." I think you'd know where to tell them where to put that question.

kjgkjhfkjf 5y ago

Many interviewers ask candidates to explain their thinking. I don't think this dubious process of elimination would pass that test.

colechristensen 5y ago
Right? When I’m interviewing I care most about the thought process and the ability to communicate in depth about something technical, the actual solution isn’t really that important at all.
- travisjungroth 5y ago
  This is the thought process. I use something very similar and have done well in interviews. I found I did better in interviews when I showed my thinking less, or adapted it to the interviewer. Stating the things I'm not doing is useful, but too risky. Just hearing the words "linked list" in a problem that can't be solved with linked lists (even in the sentence "linked list doesn't seem to be right") startles some interviewers. A high enough percentage I don't want to roll that die six times during a round. The silliest example is I like to work on problems by writing code. Yes, even if I don't understand the problem perfectly. Seeing some code helps clarify my thinking and I throw most of it away. Freaks. People. Out. Writing down some wrong line of code may as well be blasphemy. Strangely, not the case with comments. So my technique in interviews was to write comments that were as equivalent as possible to code and then convert it to regular code when I felt things were close enough. The biggest challenge in Python is not making it so similar that it becomes obvious what you're doing.
  - hemloc_io 5y ago
    lol yeah having been through these loops and training to do these loops it really seems like most people say they want to see “thought process”, but what they’re really looking for are the usual cues you see in all the prep info online. E.g. ask some clarifying questions before coding, write or suggest a brute force, and then write an optimized algo.

aurelianito 5y ago

The first example test given (rate limiter) gives a bad answer. I wouldn't use this method.

bonoboTP 5y ago
Elaborate?
- sk5t 5y ago
  The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Tabulating call count by division(s) of time would be less obviously problematic.
  - taeric 5y ago
    Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.
    - sk5t 5y ago
      I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work? - putting 500 timestamps into a queue - inspecting 500 queue entries and removing each - putting 500 new timestamps into a queue
      - bonoboTP 5y ago
        Depends on the requirements. If it's enough that the client doesn't make >N requests within the same "calendar second", then counting in bins is enough, no need to store timestamps. But then you could have a client send N requests in the second half of second k and N requests in the first half of second k+1, so you'd have a 1 second period (that spans two "calendar seconds") with 2N requests allowed. Since such rate limits are often not extremely exact, just an order of magnitude, this quantization/rounding effect may be negligibe and the speed may be worth it. But maybe not always. The original problem statement did not say that it's fine. Probably it's a good sign if an interviewee asks if this would be okay too.

arduinomancer 5y ago

Interviews are really a dumb game these days so if you want to really game it you can go with a statistical approach: * Practice questions by company on LeetCode, sort by frequency of last 6 months and work down the list, do maybe 75-100, the list updates once a week * Search for the company on the LeetCode forums and sort by most recent. If a question is not on LC yet it will likely get posted there, so you can get really fresh intel. I've read of people doing this and getting like 6/6 questions they've seen before.

henning 5y ago
This is a great way to start off a business relationship with dishonesty and cynicism. Enjoy your career.
- ThalesX 5y ago
  Can I have some of that ‘work through tens or hundreds of coding problems that are of no future relevance to me’ dishonesty and cynicism?
  - WalterBright 5y ago
    It filters out the frauds. Fraud on resumes is very common.
- aaronbrethorst 5y ago
  This is a great way to start off a business relationship with a company that wants to haze you to get you to prove your desire to work there.
- dang 5y ago
  Please don't cross into personal attack, no matter how wrong's interview preparation strategy is or you feel it is. Perhaps you don't feel you owe them better, but you owe this community better if you're participating here. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
5y ago

posharma 5y ago

This is a good post for beginners. Fortunately or unfortunately coding interviews have become much tougher. This resource [1] has helped some. [1]: https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed https://hackernoon.com/14-patterns-to-ace-any-coding-intervi...

ldjkfkdsjnv 5y ago

Before people start complaining about leetcode and how it doesnt exemplify skills: its a proxy for a combination of: intelligence and how hard you are willing to study the computer science knowledge shown is just a bonus EDIT: One last thing to throw in, its pretty clear that theres a correlation between the top software companies and how hard their leetcode interviews are. You can claim all you want it doesnt work, but facebook and google have very hard leetcode interviews and are known for the best software

lostcolony 5y ago
The former only in case of the latter. I.e., if someone isn't willing to grind leetcode, their intelligence is irrelevant. If someone is willing to grind leetcode, then yes, their intelligence is a secondary variable. Regardless, such styled interviews are intended to minimize the number of false positives (since the companies have so many applicants it's safer to err on the side of "no"; there are more in the pipeline), which means they will also generate a tremendously high number of false negatives.
posharma 5y ago
You've to be a genius to solve a "hard" unseen leetcode problem in 15 mins correctly. Facebook is notorious at expecting candidates to regurgitate solutions to problems in 15 mins. Intelligence plays a lesser role than exhaustive and painful practice which involves solving the same problem multiple times. It's a full-fledged examination that expects you to excel while being constantly watched and judged.
- Frost1x 5y ago
  >It's a full-fledged examination that expects you to excel while being constantly watched and judged. and interrupted, frequently, because that's also perfectly normal. It's comical how this industry now thinks these arcane and often quite difficult DS&A interview question processes are reasonable and how it's been so normalized people just study this for weeks before applying to a new position, sacrificing evenings and weekends just for job mobility. These processes are not even proxies for intelligence anymore except maybe the very few people so wired they miraculously could jump through a handful of these with optimized solutions in 15 minutes without ever seeing and solving the problem before. I've worked with very intelligent people before who qualify as geniuses and they couldn't solve these problems under these conditions, especially not multiple of them without having at least seen the problem before.

hsavit1 5y ago

Glad to hear that the software engineer selection method is determined by this very rigorous process of character assessment. No wonder why big corporations produce such amazing teams.

avl999 5y ago
I am not gonna die on a hill defending these types of interviews but they are infinitely better than the alternatives. Alternatives are often subjective criteria like "culture fit" which can lead to nepotism/other types of biases or hiring being done by sorting resumes based on the prestige level of the college of the applicant and just running down the list from the top (which happens in other professions like law). Ofcourse the interview process is (or atleast is supposed to be multifaced) and passing these problems is just one of the facets of the process. A great candidate can bomb one of these questions but I wouldn't necessarily reject them just because of that (although that happens in practice in the industry) and wouldn't necessarily okay someone just because they aced one of these questions. I'd take complaining about these type of problems any day over complaining about only being able to get a job in certain companies by having connections or having gone to an Ivy League school.
- vanusa 5y ago
  Alternatives are often subjective criteria like "culture fit" There's a vast territory of approaches that are neither leetcode hazing or culture fit tests. And which, while nuanced, are basically objective. Work sample evaluations do quite well, for example. As do in-depth technical discussions about ... just about any subject the candidate claims to know about. Neither of which have anything to do with "culture fit".
  - esyir 5y ago
    >As do in-depth technical discussions about ... just about any subject the candidate claims to know about. Having attempted to do this after reading all the HN screeds, I found that this failed horribly. You'll find a large number of people who seemingly know the theory, but can't execute worth a damn. They can happily talk on and on about normalization, regularization, imbalanced datasets and so on. Then they fail fizzbuzz. I then put the programming screen first.

avl999 5y ago

I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough. If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Recursion but they have subtlety to them that requires practice for most people. They tend to be tricky to get right in an interview setting without practice as due to the really bad time complexity of most problems of this type they almost never come up in production for most people so they're not even on the radar of most engineers.

malisper 5y ago
There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time. Of course there are even more niche data structures like a Fibonacci heap which have O(1) insertion, but you will have to get extremely unlucky to get asked about a Fibonacci heap in an interview.
- avl999 5y ago
  That's reasonable, makes a lot of sense.
- arduinomancer 5y ago
  Wouldn't that mean you have to implement the binary tree as part of your solution? Seems way easier/time efficient to just use the built-in heap/priority queue of the language standard lib
  - Jensson 5y ago
    C++ has built in binary trees with fast iteration. The C++ binary tree is my favourite standard library data structure of any language I've used, it isn't the fastest out there but it has so many useful things you can do with it. You can use it as a heap, you can use it as a dictionary, you can use it to sort things, you can insert items at the same time you iterate through it and if they are after where you are in the tree then you will find them in your iteration etc. It does so many things right that others don't do, I'm sure the others data structures are slightly faster but the C++ binary tree is so powerful and still fast enough for basically every problem.

wackget 5y ago

That website's choice of font colour makes for frustratingly low contrast and therefore is a recipe for eye strain. I didn't waste time reading it.

samspenc 5y ago

Good stuff. A couple of comments to the post: Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Post doesn't mention this, but one other common pattern I've seen requires a tree data structure, and those interview questions can be solved with recursion. Basically once you have a tree data structure, you write a f(node) that will simply call f(left) & f(right) recursively -- or for-each(child in children) { f(child) } for non-binary trees.

bradleybuda 5y ago
I agree with your answer on the rate limiter, but I think it depends on whether the spec is for rolling or fixed one-minute windows. The question is ambiguous, but the sample answer implies that we want to track rolling windows. If that's the case, an improvement on the answer is to use a ring buffer instead of a linked list, which allocates a fixed set of memory up front (slower to initialize) but then is allocation-free on each invocation.
malisper 5y ago
> Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. As Bradley said this implementation can be called more than 10 times within a 1 minute window. If it's called 9 times at the last second of one minute and 9 times at the start of the next minute, it will be called 18 times within a two second interval.
john_moscow 5y ago
>Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Why on Earth? Given that the timestamp cannot randomly jump backwards, you can achieve the same results by just storing the timestamp of the first call after a reset, and the number of calls sharing the same date/hour/minute, resetting it to 0 when the minute advances. That said, it won't be entirely what was asked, since it won't have the rolling behavior.

ofou 5y ago

Backup link https://archive.is/fg8hI https://archive.is/fg8hI

dmurray 5y ago

There's a bit of a "draw the rest of the owl" thing going on here. If you have the experience to confidently eliminate the likely approaches that don't work, then you must know quite a bit about those approaches and their applications. And in particular, I'm not sure I can agree on eliminating recursion in the anagrams problem. He just says > Recursion – No way to apply recursion to the problem. but...there is? One plausible approach, I sort each of the strings and put them in a trie. A fancy sounding thing, but really just a data structure which allows me to rephrase "someString in myTrie" as the recursive "someString is null || (head(someString) in myTrie.keys && rest(someString) in myTrie[someString])". I'm not arguing that this is better than a hash table, though I think it probably is on some workloads - just that it's not possible to rule this out and solve the problem by pure process of elimination.

travisjungroth 5y ago
That's the nature of thought frameworks. You need to fill in the gaps yourself. It's still useful to have an organized approach. In my experience, people can know how well each technique would be suited to the task at hand if asked. But, they rarely consciously go through each technique they know and consider if it's the right approach. Most people would be well served to do this more often. Btw, this is a big failing in interviewers who help. Asking the right questions (what data structure could you use here?) is incredibly helpful. So helpful that you're not testing them on a slow moving, relevant skill (structured thinking) but instead a fast moving, less relevant skill (what data structures do you know?). Bad move.
- asxd 5y ago
  I kind of agree, in that a good candidate should probably already be thinking "what data structure should I use here" no matter what the problem is. Just always think about what data structure to use. Every problem requires one. More in the vein of what you're getting at though, I think helping a nervous candidate by asking obvious questions like this can be helpful: "What data structure would you recommend using for this problem?", or "What programming paradigm do you think would fit this problem best?". It's a bit of an ice breaker, and can lead to more interesting conversation than the candidate just sitting there, quietly thinking (admittedly, possibly not a good sign for a candidate if they do this, but interviews should be built around making it a good experience for the candidate as well).

PaulHoule 5y ago

It is amazing how far you can go with: 1. Look it up in the hash table, 2. Look it up in the literature

yawgmoth 5y ago

This might get you OK marks on the "problem solving" portion of a coding interview. But a programming interview will also look for signals of other skills -- did you communicate your approach? Really good candidates will verbally communicate their solution before writing code. The best often write out how a particular data structure changes with some iteration. If you're a senior engineer, a coding interview should include some demonstration of correctness. Maybe you write one primitive test harness for a positive test case and add comments or empty methods enumerating a few other test cases.

SMAAART 5y ago

https://archive.is/fg8hI https://archive.is/fg8hI

Supermancho 5y ago

The anagram solution leaves the actual hard part unfinished^. Also, to solve in O(n) you need a bit array (or a database like Postgres that can do an XAND on a string). > Sort the characters of the words alphabetically. Since anagrams are all made up of the same letters. This will give us the same string for any pair of words that are anagrams of each. Correct. > Produce a dictionary of the number of times each letter occurs in each word. Well, yeah...algorithms aren't the hard part for this kind of question. "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word. Take a string of zeroes, which is (maxWordlength*26) long. Each segment of 26 represents a compositional letter from the word. So 100000 00000 00000 00000 00000 is 'a' Now you can create your dictionary from the sorted word indexes. pin becomes inp becomes 000000 00100 00000 00000 00000 000000 00000 00100 00000 00000 000000 00000 00001 00000 00000 same as nip (becomes inp, etc) You can add 26 zero sets, to pad out to the length of longest word, if words are variable length. ^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise.

malisper 5y ago
> "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word. How so? "aab" is an anagram of "baa", but they are not anagrams of "ab".
- Supermancho 5y ago
  100000 00000 00000 00000 00000 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 aab and baa 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 000000 00000 00000 00000 00000 ab You aren't "counting" the number of characters. You're making an encoding that includes that information, without the aggregation. The aggregation is irrelevant as is the order of duplicate characters.
5y ago

deleted 5y ago

[deleted]

troutwine 5y ago

There’s also two additional programming techniques you should be aware of: * Dynamic Programming </snip> How often do folks here use dynamic programming techniques in their professional lives? My own niche is systems programming. Dynamic programming is an important technique, sure, but given how rarely I see it used in practice compared to, say, statistical estimation it feels very overrepresented in interviews. But, maybe that's my own niche being unusual.

hinkley 5y ago
More than my coworkers, not often enough, and not very often. Many people think DP and caches are synonymous, unfortunately.
- titanomachy 5y ago
  I usually reach for caching first because it’s more intuitive (for me and my reviewers) and because we often have well-known size bounds and relaxed enough performance requirements that make an “analytical” solution unnecessary.
  - hinkley 5y ago
    Caching creates a mature product, no matter what your product roadmap says. If a rewrite is the tool of last result, caching is the second to last. Like pruning shears, once you use them, your world of options collapses considerably. All of those opportunities are gone and nature won't let you put them back. Critically, caches are global shared state. That's why cache invalidation is the hardest thing. Global state also means people stop trying to have a data flow/architecture. None of these call trees need to advertise that they use a particular value because I can just grab it from a global if I need it. You don't know where things are actually used anymore because they all come from cache lookups, and because the lookup is so cheap (under typical system load, but catastrophic under high load), people don't even try to hold onto previously acquired data. They just fetch it again. Which is another boundary condition for cache invalidation (what if half a transaction has the old value and half the new value?) They make flame graphs essentially useless. Sometimes immediately, or once the above starts happening. You quickly have no clear idea what the cost of anything is, because you never pay it, or if you try to pay it you end up amplifying the cost until there is no signal. Once people are promiscuously fetching from the cache, they don't even attempt to avoid duplicate lookups, so activities will end up fetching the same data 6 times. If you turn off the cache entirely for perf analysis then the cost skyrockets and the flame chart is still wrong. You are back to dead reckoning and manually adding telemetry to potential hotspots to sort it out. This is very slow, and can be demoralizing. Quickly this becomes the fastest our app will be for a very long time.

rrradical 5y ago

For the second problem, I had an idea for a different hash function. Basically map each letter to a prime number (e.g. c = 5, d = 7) and then multiply the values in a word together. I guess depending on the length of the words it might overflow. But I thought it was interesting.

foreigner 5y ago
I gave this very solution in Google interview many years ago. It does assume that the input characters are of a limited set, e.g. English alphabet. The interviewer said they hadn't heard that answer before. It wasn't what they were expecting and took them a while to be satisfied it would work. I was offered the job but didn't end up taking it.

shahbaby 5y ago

This type of top down learning doesn't work for interviews. Just like how you can't learn math by reading high level summaries written by others. You have to grind through it and see the connections yourself. The author's lack of depth shows when he says that no graph means you can rule out DFS. I also disagree on asking interviewer for the expected runtime. You're needlessly adding another constraint on yourself by doing that. You should ask for the input size and then figure out the best runtime that you can reach. A working suboptimal solution is more likely to get you to the next round than an incomplete attempt at an optimal solution.

andrew_ 5y ago

Or don't agree to interviews that include algo challenges, leetcode/hackerrank nonsense, array shuffling shenanigans. Choose companies that put thought into their evaluations.

o10449366 5y ago
Just my $0.02: I'd much rather spend a few weeks refreshing basic data structures and algorithms than doing the "non-algo" challenges I've gotten because they feel way less objective than getting questions where there's a correct answer. Most of the time the alternative to non-algorithm questions is some form of take home assignment that's usually multiple hours long and that you get no feedback on or chance to correct. For example, I interviewed with a company where they asked me to design a program to parse some CSV data and I was told in the next round I would pair with an engineer to go over an expansion of the code. The parsing was trivial in Python and I submitted my solution with full unit tests and what seemed sensible to me, but it was as useless of an exercise as asking me algorithm questions because on a job I'm almost always going to adjust my coding style and paradigm to the context and needs of the company. I commented my code as such to explain that if there were different constraints on the data size or API I would make different design choices than the one I submitted, but it didn't matter - I submitted and received a rejection less than 24 hours later and never got to the next round where I would actually walk through the code with an engineer. It was a complete waste of multiple hours of my time trying to produce thoughtfully designed code - I'd much rather bang out a breadth first search in 45 minutes.
- sgerenser 5y ago
  At least you got a rejection! I’ve done take home assignments that resulted in nothing but :crickets: in response.
- quasiprime 5y ago
  On one hand I like take-home exercises because they are closer to what is a real world job and I guarantee the quality of my deliveries. Up to now I can say I've passed every single take home exercise that was thrown at me. On the other hand... the time I spent on those is abysmal. If I sum it up, I must have spent over a month working on take-home exercises. And even if I passed all of them, in the end no company gave me an offer because I wasn't a cultural fit or something. One company even ghosted me after having me to do a 1-week take-home exercise where I had to build an entire app, front end and back end, that consumed an open data API that had 1 million rows. I still prefer take-home exercises because are more realistic and make more sense than timed, algorithmic exercises. But I wish companies would do their cultural fitness thing _before_ having candidates to spend their time on their code challenges.

bottled_poe 5y ago

It’s almost as if you’re learning what is expected of a suitable candidate.

transitivebs 5y ago

Here's a similar resource for anyone interested in this topic: https://transitivebullsh.it/gaming-cs-interviews https://transitivebullsh.it/gaming-cs-interviews

shp0ngle 5y ago

What kind of hash table is O(1)? Or did I forgot everything from university already? You cannot have a general O(1) hash Well maybe in best case/average case, when you design the hash space big enough. Ugh I really did forgot everything.

hailwren 5y ago
The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost across all inserts. There are always more inserts than the cost of resizing, so you end up w/ amortized O(1).
vlovich123 5y ago
Not sure I understand your concern. Are you asking about worst case? All hash tables I believe are O(n) worst case because of the possibility of collisions (or the need to resize in the case of an insert). Most people talk about amortized performance though (ie when you are successful at reducing the likelihood of worst case to a rare event). Amortized time is obviously dangerous if you’re in a real-time system (eg games) where it’ll manifest as stuttering or latency spikes or potentially even worse if you’re having to respond to hardware events in a timely manner for proper operation.
- Dylan16807 5y ago
  It's possible to gradually resize a hash table to prevent spikes. For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.
  - vlovich123 5y ago
    > It's possible to gradually resize a hash table to prevent spikes. Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. > For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'. Yes, but the vast majority of implementations don't do a good job here. Howard's "Types Don't Know #"[1] paper is extremely well thought out and I have yet to see this adopted (except for Rust - Rust has a good track record of adopting good ideas like this and having the benefit of coming late to the game). I think it's safe to say that most hash tables don't have good worst case times (which when combined with resizing behavior of insertions, means you have super-linear worst case times on insertion). [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...

solididiot 5y ago

Interviewing has become a theater of the absurd. You get examined on things that won't be useful in 99% of your work. People put in hours to prepare and game it. Overall countless hours go to waste to just play the role. Most times it doesn't even show whether someone can think (what you might see as thinking might be well rehearsed "act as dumbfounded for a while").

feoren 5y ago

Am I crazy or is the first answer terrible? I sat down and wrote out and answer for the problem and I initialized one integer and one timestamp. It should be O(1) time and O(1) memory easily, right? I'm seeing comments saying they'd use an array or a hash table -- why are you using any data structure? You don't need to remember how many times it was called 61 seconds ago; just keep a timestamp and the last time you reset the timestamp. If you need it to be clock-minutes instead of rolling (it doesn't; whose clock, anyway?), then just round the timestamp. The obvious follow-up question is "ok, what if it needs to be limited to 10,000 calls per minute?" You're going to keep 10,000+ elements in some collection for no reason? I wouldn't immediately reject a candidate for coming up with this answer but I would seriously question their thought process on this one. In fact it's kind of ironic that his first example exposes how bad this advice is: by trying to meta-game, starting from a few example data structures, he shows he completely misses the solution that is both simpler and much more performant.

branko_d 5y ago
I don't think you can have a "sliding window" of time just based on that. The next time you call the function, you need to count how many of the old calls are still "unexpired". This number (potentially) gets lower with each passing quantum of time. How can you do that without holding a timestamp for each call? Please clarify if I misunderstood you.
- GistNoesis 5y ago
  I think you can have a more performant algorithm if you soften the constraint a little. (see my previous comment https://news.ycombinator.com/item?id=29776678 https://news.ycombinator.com/item?id=29776678 ) TLDR : You have a maximum of N credits, when time pass you earn credit at a rate of N credit by window_size, but if the time since previous request is less than window_size/N you lose 1 credit. I don't think you can have more than 2*N requests in any sliding window without tripping the filter, but you can't consume more than the average of N requests / window_size without tripping the filter. I think it's a better solution than the question asked by the author, because when you are rate limiting, you and the client may not have exactly the same time, and you might have edge cases like where the client batch 60 requests in a few ms every minute. If there is some time-jitter in the requests you may have 120 requests in 59.9 seconds. (Bonus question : What time-stamping of the request should be used ?) Whereas with my solution it is more forgiving, it allow the client to use all its rate credit without risking to trip the filter if he respect the rate intent.

angarg12 5y ago

Almost all advice online about interviewing is written from the point of view of the candidate. Sometimes this is good advice, but sometimes it devolves into some kind of astrology, where candidate are just guessing how things work. I've done +300 interviews at FAANG so I can share bit of advice from the interviewer's side. The caveat is that this is based on how I conduct interviews, so YMMV with other people. * Always ask clarifying questions. Almost all problems have some level of ambiguity that you need to clarify. This is intended. The more senior you are, the more important this becomes. * Explain your approach before you begin, and even while you code. This gives the interviewer a chance to help you if you are down the wrong path, or even just understand what you are up to. * If you get stuck, ask for help! think of this as a pair programming session rather than an interview. I much prefer a candidate who gets stuck, ask for hints, gets unblocked and writes good code, rather than one that doesn't ask for help and writes not-so-good code. * Caveat: There is a tension with asking questions. There is such a thing as too much help, e.g. I need to explicitly tell you how to solve the problem. Use judiciously. * Take interviewer's hints. The interviewer has probably asked this question dozens of times and knows it inside out. If they give you a hint, 99% of times they are on to something. * Personally I don't like "hard LC" problems. Instead I prefer medium difficulty problems, and spend extra time probing the candidate's coding skills. This includes: 1. Write tests. 2. Handle corner cases/incorrect inputs. 3. Discuss how to scale the code. 4. Discuss how to refactor the code. * If nothing else, write the simplest brute force solution you can think of. As an interviewer I need a coding sample to evaluate the candidate. Trying to and failing to implement an optimal solution is worse than implementing a correct brute force one.

deleted 5y ago
[deleted]
mettamage 5y ago
I appreciate the caveat. Caveats are almost never given when people give advice and it is exactly the thing that people get stuck on when they take the advice to heart.
Jaygles 5y ago
Have you ever passed someone who wrote brute force algorithms?

jb1991 5y ago

> You probably won’t be expected to implement a binary search or sorting algorithm, but you should be aware that they exist. Lol. Pixar‘s coding interviews are well known to do exactly just that: implement a binary search tree from scratch.

wly_cdgr 5y ago

Just be likeable

lucraft 5y ago

Maybe the title should be "An Algorithm for Passing Algorithm Programming Interviews". This wouldn't help you pass our Programming Interview in the slightest.

hiyer 5y ago

Hash Tables Linked Lists Binary Search Trees I would add tries to this list - I was asked trie-based questions in 4 of the companies I interviewed with over the last couple of years, including a FAANG.

deleted 5y ago

[deleted]

mettamage 5y ago

One thing that I have noticed that FAANG doesn’t do well is: help people with sleep issues. It’s not their job [0], but I do think there are some talented insomniacs that are great employees (given that they can mostly work on their own schedule, except for meetings). I remember that I interviewed for Facebook and I was so sleep deprived, I could barely write a for-loop. Ironically, I passed that interview but I couldn’t pass others that required some more creative thinking or more memorization. [0] While it is not their job, FAANG companies do mention that they are accommodating candidates with mental health issues, and I’d argue that insomnia (diagnosed or undiagnosed) should be one of them.