14 ms·

I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me

I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of appends. I don't know if I remembered the term "amortized complexity" or not, but it was clear that they had never heard of doing amortized analysis across a series of operations and they absolutely did not get my answer. They got hung up on the idea that some appends force the array to grow and get copied. I tried to explain that that was only true for a predictable fraction of them, but they were stuck on the idea that this meant dynamic arrays had O(n) worst case performance. They clearly thought I didn't know what the hell I was talking about. I'm pretty sure that was the point where they decided to pass on me. But now I'm a senior software engineer at Google and I just finished writing a textbook that explains dynamic arrays including their amortized analysis, so joke's on them.

chaps 5y ago
Just a thought -- gaming is latency sensitive. Maybe their issue with it wasn't about average performance, but that the once-in-a-while perf hit would be enough to cause a bad experience for the person playing the game? I know I'd be frustrated if there was a predictable lag spike while playing a game.
- typon 5y ago
  Any game engine design worth its salt would: 1. Probably not used linked lists (contiguous layout means better cache efficiency) 2. Would try to understand their data requirements and allocate memory up front as much as possible - doing a similar amortized analysis the OP is suggesting rather than a generic "always have O(1) insertion" at the cost of using an inferior data structure (a linked list)
  - BrS96bVxXBLzf5B 5y ago
    Any game engine architect worth her salt would know to not speak so absolutely about cache coherency, and that if you're dealing with a use-case where iteration is massively infrequent but random insertions and removals are likely, you could be better off with the linked list :)
    - typon 5y ago
      Certainly if you design a scenario where linked lists are superior to use, you should use linked lists. Fortunately, these are few and far between in real production software.
- munificent 5y ago
  No, latency didn't come up. (I agree that could be a reason not to use a dynamic array.) They were hung up on the idea that a dynamic array must be O(n) because at least some of the appends copy.
  - 8note 5y ago
    Assuming you can average over all requests imposes that latency does not matter, doesn't it? If you're the interviewee, it's up to you to get that clarification
    - munificent 5y ago
      The question they asked was about its complexity in big-O terms, not so much about its real world performance, at least as I recall.
  - deleted 5y ago
    [deleted]
  - qu4z-2 5y ago
    You explicitly said they were hung up on the "worst case O(n)" situation, so I suspect they were concerned about the latency. Insertion into a dynamic array has a worst case of O(n) and an average case of O(1), no?
lor_louis 5y ago
Can you link the textbook? I'd be interested in reading it.
- munificent 5y ago
  I talk about dynamic arrays in Crafting Interpreters: http://craftinginterpreters.com/chunks-of-bytecode.html#a-dynamic-array-of-instructions http://craftinginterpreters.com/chunks-of-bytecode.html#a-dy...
  - weaksauce 5y ago
    i really dig the art style of your diagrams! playful and clear
  - pmulard 5y ago
    Thank you for giving away your book for free. I signed up for the mailing list and hope to purchase a copy when you're releasing printed versions.
    - munificent 5y ago
      You're welcome! I'm getting really close to having the print and ebook editions ready for sale.
pavpanchekha 5y ago
Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has been entirely copied to the second array—so discard the first array, move the second array to be first, and allocate a new "next" array. The same trick can be applied to many amortized data structures (but it gets very complicated when you have many operations).
- vladf 5y ago
  One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?
  - mjevans 5y ago
    It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
  - Dylan16807 5y ago
    Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.
    - vladf 5y ago
      I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.
dilap 5y ago
In some cases amortized isn't good enough though, and games could certainly be one of them! (Anywhere you're servicing some kind of interactive request might qualify, depending on this size of your datastructures.) This is actually something I like to work through in interviews: OK, you've got amortized-constant-time append to your array-backed colletion, but now what if we need it to be really constant time? How could we achieve this? (Same question & trick applies to hashtables.) (The answer can be found, amongst other places, in the Go or redis source code.) edit: or in pavpanchekha's comment, they beat me to it :-) also, just realized you're the author of crafting interpreters. absolutely love that book!
- phkahler 5y ago
  >> In some cases amortized isn't good enough though, and games could certainly be one of them! Real time systems including games have hard limits on how long something can take in the worst case, not the average. In games this manifests as: All the stuff has to be done in 16ms to render a frame on time, if we're late the user will perceive a glitch. The consequences can be worse in control systems in any number of real-world systems where a glitch can lead to stability problems. So getting back to TFA, this is part of knowing what the "right" answer is for the context.
  - tomxor 5y ago
    > worst case, not the average Yup, I can't remember which book but I'm pretty sure I remember reading some stuff from Michael Abrash about how some of the algorithms in quake were changed for worse average performance but better worst case performance. It's fairly intuitive when you think about the context... and that is the critical point - abstract problems are interesting, but it's important to evaluate them in their full context.
  - SilasX 5y ago
    So it would be fine if they had said, "okay, for this problem let's add the requirement that every add must be fast, because it's within a frame rendering loop", but (from OP's description) they didn't even seem to understand that's a separate desideratum, or that it doesn't mean the amortized time is bad.
kubb 5y ago
You wrote a book about std::vector?
tester756 5y ago
Couldnt you show them example on e.g whiteboard how it'd work? it'd be huge pros that you can explain concepts to people who do not know them in 5mins.
- munificent 5y ago
  I was on a whiteboard, but the social cues I was getting from them made it pretty clear that even my attempts to explain were just digging myself deeper into a hole in their eyes.
chacham15 5y ago
So, amortized complexity is different than actual complexity. The doubling the size of the array whenever you overflow leads to log(n) performance which isnt constant. What they were looking for was an array of arrays such that each consecutive nested array is double the size of the previous. This way, you get the same number of expected allocations, but you dont ever have to copy data (and therefore inserts are actually constant time). It also has the benefit of being able to consolidate the subarrays into a single one at places where there is time to do so. So, you didnt actually give the question asker what they were asking for.
- munificent 5y ago
  I'm fairly certain they were looking for a linked list, but I could be wrong.
  - gopalv 5y ago
    > fairly certain they were looking for a linked list, but I could be wrong They were probably looking for an answer which went along the lines of a linked list and then what to fix - the ratio of pointer sizes to data (16-item nodes), sorted insert optimizations, the ability to traverse to the 500th element faster etc (skips with pow-10 or a regular skip list etc). I bombed a similar soft-ball interview question in the past, because I was asked to build out a work item queue using a database in SQL & I got stuck failing to explain why it was a bad idea to use an ACID backend for a queue. Some constructive feedback from the person who referred me came back as "dude, you just wouldn't let go of the topic and the interviewer gave up on you". That was definitely true for me, but I remember that feedback more than the actual technical correctness of my opinion. That was a clear failure of fit in multiple ways, but it didn't matter whether I was right or not, I had failed to persuade someone who would be my team lead on a topic which I had deep knowledge on. Even if I was hired, it wasn't going to work out.
    - marcosdumay 5y ago
      > it was a bad idea to use an ACID backend for a queue Why do you think so? It completely depends on the utilization of their ACID backend, and how well it handles independent data.
kleiba 5y ago
Why didn't you just say "...or, you could use a linked list" when you notice them doubting your first answer?
- munificent 5y ago
  By that point, they said we should just move on to the next question.
deleted 5y ago
[deleted]
winrid 5y ago
In game dev, that one copy might cause a frame drop. Even if amortized over time the frame rate would be slightly higher, the occasional dip might make it unplayable. Of course, arrays have better cache locality, but they didn't ask about that. They were probably looking for a linked list with a small array in each node, which gives more constant write performance and less cache misses on read.
- munificent 5y ago
  They didn't ask about latency either. I would have been happy to have the discussion of real-world performance, but we were stuck on the basic "what is the algorithmic complexity of this?" question.
- chakkepolja 5y ago
  If they had the clue what they were asking about, wouldn't they have corrected GP? "No dude we can't have that worst case here in game dev!!". But they asked about algo complexity and couldn't recognize GP was talking about amortized complexity, something sounds wrong.
superrad 5y ago
It's not great to have to double your memory usage while you reallocate your array. On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. There's also the cost of copying objects especially if you don't know if the objects you're copying from your original array to the resized array have an overloaded copy constructor. Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour. If you're holding pointers to these elements elsewhere re-allocating invalids those, and yes you probably shouldn't do that but games generally are trying to get the most performance from fixed hardware so shortcuts this will be taken, its a least something to talk about in the interview. I can see why they were confused by your answer as its really not suited to the constraints of games and the systems they run on.
- munificent 5y ago
  > It's not great to have to double your memory usage while you reallocate your array. You don't have to use a growth factor of 2. Any constant multiple of the current size will give you amortized constant complexity. > On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. If fragmentation is a concern, you can pre-allocate a fixed capacity. Or you can use a small-block allocator that avoids arbitrary fragmentation at some relatively minor cost in wasted space. > Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour. We have an intuition that moving stuff around in memory is slow, but copying a big contiguous block of memory is quite faster on most CPUs. The cost of doing that is likely to be lower than the cost of cache misses by using some non-contiguous collection like a linked list. > as its really not suited to the constraints of games and the systems they run on. For what it's worth, I was a senior software engineer at EA and shipped games on the DS, NGC, PS2, Xbox, X360, and PC.
  - superrad 5y ago
gamblor956 5y ago
It sounds like you bombed the interview because your answer was not the correct answer for the domain. For games, it absolutely does matter that only some appends trigger latency, because that causes stuttering in the game play. A linked list may be slower in most use cases...but the performance cost is fixed and can be easily designed around.
- munificent 5y ago
  I feel like I've replied to this same thing about five times now, but, yes, I completely understand the latency concern with growing a dynamic array. At the time, we weren't talking about it. Their question was, "What is the complexity of this?" And I said, "It's constant time over a series of appends." We didn't get past that.
  - asr21 5y ago
    The guy worked at EA for 8 years.. He must know what he is talking about
    - sudopluto 5y ago
      he also wrote the crafting interpreter book : )
      - munificent 5y ago
        And Game Programming Patterns, which has a chapter on the performance effects of contiguous data: https://gameprogrammingpatterns.com/data-locality.html https://gameprogrammingpatterns.com/data-locality.html :)
    - deleted 5y ago
      [deleted]
    - wffurr 5y ago
      That means nothing. Time != experience. You have to have actually learned during that time for it to count for anything.
planet-and-halo 5y ago
I had a less dramatic one where someone argued with me that the lookup time on a binary tree was O(H), the height of the tree, not O(log2n). I was so baffled by the argument that I didn't realize until after the interview that I should have pointed out that the height of a binary tree is log2n.
- slavak 5y ago
  They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
  - planet-and-halo 5y ago
    Doesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?
    - wtetzner 5y ago
      No, not all binary trees are balanced binary trees.
      - planet-and-halo 5y ago
        Ah got it, thanks.
exdsq 5y ago
I really enjoyed your Crafting Interpreters book! Jokes on them for missing out.
mrxd 5y ago
There was a meme going around where a doctor took a high school biology quiz. Q: What are mitochondria? A: [Long complex scientific answer about ATP synthesis] Grader: Wrong. Mitochondria are the powerhouse of the cell.
- TomNomNom 5y ago
  In a "Business and Communication Systems" exam at school I got the question "Explain how email works". Being the nerdy teen I was, I wrote about SMTP, MX records and that sort of thing. That was not the right answer.
AtNightWeCode 5y ago
Typically interviewers are looking for the general known common way to do things. I heard people failed cause they wrote code that use bitwise AND instead of MODULO to check if a positive integer is even. Just the way it works even if I don't like it.
wly_cdgr 5y ago
You should have just said "Look guys, trust me, I am going to write Game Programming Patterns one day"
- munificent 5y ago
  I was already writing it when I did this interview! (Though, I hadn't gotten to the chapter on data locality yet.) One of the main reasons I started writing it was to help my job search. Which, ironically, ended up not being necessary because I left the game industry. What's crazy to think about is that if I hadn't failed this interview, I probably wouldn't have gone to Google. So this one weird failure to explain the big-O of dynamic arrays may have dramatically changed the course of my career. Or, who knows, maybe they failed me for other reasons.
  - wly_cdgr 5y ago
    Well, all's well that ends well. Failing that interview just might have made you a couple million dollars richer. With all due lip service to all the other advantages of working on hard problems at Google, of course :) Funnily enough, I am trying to go the other way over the next decade or so, ...so looking forward to reading your book, heh
gmadsen 5y ago
am I the only one concerned that this would even be a point of contention? This seems too trivial for anyone doing hiring or being hired to be hung up on.
- munificent 5y ago
  I mean, I'm guessing this is the main reason that they passed on me, but I'll never know for sure. Maybe they didn't like my personality. Maybe it was some other question I thought I did well on but didn't even realize I got wrong. Maybe a combination of things. For what it's worth, I didn't get a very good vibe from them. The impression I got was that their culture was more aggressive and competitive than I like. (Maybe this was to be expected for a company that made a competitive eSports game.) I'm not really what you'd call a brogrammer. So it was probably for the best that they said no. I ended up at Google, which has been better for me in every possible way.
  - DonHopkins 5y ago
    >I'm not really what you'd call a brogrammer. I'd say you dodged a bullet, but it's more like you dodged a ball. https://www.youtube.com/watch?v=W-XbDZUnUmw&ab_channel=MovieclipsClassicTrailers https://www.youtube.com/watch?v=W-XbDZUnUmw&ab_channel=Movie...
- scottlamb 5y ago
  > am I the only one concerned that this would even be a point of contention? This seems too trivial for anyone doing hiring or being hired to be hung up on. You'd be surprised! I've done probably 200+ interviews across a couple companies. Over time if anything my questions have gotten simpler. I look for someone who understands the fundamentals of the stuff on their resume, asks good requirements questions, thinks a bit before leaping into the weeds, can explain their thought process, ideally does some of their own double-checking, and (if it comes up) can debug a problem I spot without my spelling out their error. And last but not least: I don't want to cause a panic attack, which would be mean and tell me nothing. Sometimes my candidates have been too nervous for me to know if I should hire them, and it's not a good experience for anyone. So I make the problem as simple as I can and make sure we get through the rest of that in as relaxed a fashion as I can manage. I'll ask a simple (often first-year CS) coding problem or a design problem, rarely both in the same interview slot. I never ask for tons of code on a whiteboard in a 45-minute slot.
deleted 5y ago
[deleted]
dcow 5y ago
I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on a show than a practical solution to the task at hand. The worst case performance for a dynamic array is O(n), but the amortized performance is constant. They aren't the same thing. You may be a different, more mature, engineer nowadays. But, when I encounter the type of persona your story describes I tend to respond with strong no’s irrespective of whether you have since written a textbook.
- lmilcin 5y ago
  Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complexity yet hugely different costs. For example, you can easily parallelize operations on array lists but you can't do that on linked list where to get to next node you need to dereference a pointer. Even without this, you get bonus from prefetching data to cache when searching through array list or when doing things like moving data. Speculative dereferencing pointers is nowhere close to just regular prefetch. Array lists are denser in memory than linked lists (because of additional pointers). This means that a lot of things works just more efficiently -- cache, memory transfers, prefetching, less need to resolve TLBs, etc. Inserting into array list at the end is as fast as into linked list (after taking account for amortized cost), but what not many people appreciate is that finding an insertion place and inserting within array list is also the same cost or even better than in linked list. That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. Actually, it costs more than copying the same size of array list.
  - deleted 5y ago
    [deleted]
benhoyt 5y ago
Link to said textbook content on dynamic arrays: http://www.craftinginterpreters.com/chunks-of-bytecode.html#a-dynamic-array-of-instructions http://www.craftinginterpreters.com/chunks-of-bytecode.html#... Edit: Ah, I just saw munificent linked to this in a reply elsewhere in the thread.
Siira 5y ago
I, too, lost a question on my Data Structures final exam by using amortized analysis.
lostcolony 5y ago
I see a lot of responses defending the interviewers, or saying what you should have done. Maybe so, but I'm just gonna go ahead and say - those interviewers were shit. Most interviewers are, so it's not really a judgement on them, but the problem in that room wasn't you.
javajosh 5y ago
Next you'll try to convince us that "munificent" is a real word and not just a misspelling of "magnificent". Sheesh.
lowbloodsugar 5y ago
Here is the question that was asked, and here is the question that was answered (quoting): Asked: "constant time complexity" Answered: "constant time when averaged over a series of appends" In an interview, the onus is really on candidate to answer the question as it was asked. Candidate did not answer question, and there was a breakdown in communication. Candidates interpretation is that interviewers didn't know what candidate was talking about. Interviewers could just as easily have been frustrated that candidate did not see significance of the difference. In my experience, interview technique requires establishing a common ground. As an interviewee, I find that the first step of answering a question is to first go through a number of possibilities starting with the most obvious first. They were most certainly looking for a linked list. This is a simple question with an obvious answer. It would have been good practice to start with the answer they obviously wanted, and then try to broaden their minds. Instead, candidate willfully derailed the interview. To me this looks like a classic breakdown of communication with a root cause of hubris (quite possibly on both sides). While both sides failed in this account, only one has the benefit of hindsight in writing about it here today. Time has offered an opportunity for reflection. What has candidate learned? "[look how clever I am] so joke's on them"
stirfish 5y ago
Game Programming Patterns is one of my favorite books btw

chaps 5y ago

Just a thought -- gaming is latency sensitive. Maybe their issue with it wasn't about average performance, but that the once-in-a-while perf hit would be enough to cause a bad experience for the person playing the game? I know I'd be frustrated if there was a predictable lag spike while playing a game.

typon 5y ago
Any game engine design worth its salt would: 1. Probably not used linked lists (contiguous layout means better cache efficiency) 2. Would try to understand their data requirements and allocate memory up front as much as possible - doing a similar amortized analysis the OP is suggesting rather than a generic "always have O(1) insertion" at the cost of using an inferior data structure (a linked list)
- BrS96bVxXBLzf5B 5y ago
  Any game engine architect worth her salt would know to not speak so absolutely about cache coherency, and that if you're dealing with a use-case where iteration is massively infrequent but random insertions and removals are likely, you could be better off with the linked list :)
  - typon 5y ago
    Certainly if you design a scenario where linked lists are superior to use, you should use linked lists. Fortunately, these are few and far between in real production software.
munificent 5y ago
No, latency didn't come up. (I agree that could be a reason not to use a dynamic array.) They were hung up on the idea that a dynamic array must be O(n) because at least some of the appends copy.
- 8note 5y ago
  Assuming you can average over all requests imposes that latency does not matter, doesn't it? If you're the interviewee, it's up to you to get that clarification
  - munificent 5y ago
    The question they asked was about its complexity in big-O terms, not so much about its real world performance, at least as I recall.
- deleted 5y ago
  [deleted]
- qu4z-2 5y ago
  You explicitly said they were hung up on the "worst case O(n)" situation, so I suspect they were concerned about the latency. Insertion into a dynamic array has a worst case of O(n) and an average case of O(1), no?

lor_louis 5y ago

Can you link the textbook? I'd be interested in reading it.

munificent 5y ago
I talk about dynamic arrays in Crafting Interpreters: http://craftinginterpreters.com/chunks-of-bytecode.html#a-dynamic-array-of-instructions http://craftinginterpreters.com/chunks-of-bytecode.html#a-dy...
- weaksauce 5y ago
  i really dig the art style of your diagrams! playful and clear
- pmulard 5y ago
  Thank you for giving away your book for free. I signed up for the mailing list and hope to purchase a copy when you're releasing printed versions.
  - munificent 5y ago
    You're welcome! I'm getting really close to having the print and ebook editions ready for sale.

pavpanchekha 5y ago

Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has been entirely copied to the second array—so discard the first array, move the second array to be first, and allocate a new "next" array. The same trick can be applied to many amortized data structures (but it gets very complicated when you have many operations).

vladf 5y ago
One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?
- mjevans 5y ago
  It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
- Dylan16807 5y ago
  Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.
  - vladf 5y ago
    I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.

dilap 5y ago

In some cases amortized isn't good enough though, and games could certainly be one of them! (Anywhere you're servicing some kind of interactive request might qualify, depending on this size of your datastructures.) This is actually something I like to work through in interviews: OK, you've got amortized-constant-time append to your array-backed colletion, but now what if we need it to be really constant time? How could we achieve this? (Same question & trick applies to hashtables.) (The answer can be found, amongst other places, in the Go or redis source code.) edit: or in pavpanchekha's comment, they beat me to it :-) also, just realized you're the author of crafting interpreters. absolutely love that book!

phkahler 5y ago
>> In some cases amortized isn't good enough though, and games could certainly be one of them! Real time systems including games have hard limits on how long something can take in the worst case, not the average. In games this manifests as: All the stuff has to be done in 16ms to render a frame on time, if we're late the user will perceive a glitch. The consequences can be worse in control systems in any number of real-world systems where a glitch can lead to stability problems. So getting back to TFA, this is part of knowing what the "right" answer is for the context.
- tomxor 5y ago
  > worst case, not the average Yup, I can't remember which book but I'm pretty sure I remember reading some stuff from Michael Abrash about how some of the algorithms in quake were changed for worse average performance but better worst case performance. It's fairly intuitive when you think about the context... and that is the critical point - abstract problems are interesting, but it's important to evaluate them in their full context.
- SilasX 5y ago
  So it would be fine if they had said, "okay, for this problem let's add the requirement that every add must be fast, because it's within a frame rendering loop", but (from OP's description) they didn't even seem to understand that's a separate desideratum, or that it doesn't mean the amortized time is bad.

kubb 5y ago

You wrote a book about std::vector?

tester756 5y ago

Couldnt you show them example on e.g whiteboard how it'd work? it'd be huge pros that you can explain concepts to people who do not know them in 5mins.

munificent 5y ago
I was on a whiteboard, but the social cues I was getting from them made it pretty clear that even my attempts to explain were just digging myself deeper into a hole in their eyes.

chacham15 5y ago

So, amortized complexity is different than actual complexity. The doubling the size of the array whenever you overflow leads to log(n) performance which isnt constant. What they were looking for was an array of arrays such that each consecutive nested array is double the size of the previous. This way, you get the same number of expected allocations, but you dont ever have to copy data (and therefore inserts are actually constant time). It also has the benefit of being able to consolidate the subarrays into a single one at places where there is time to do so. So, you didnt actually give the question asker what they were asking for.

munificent 5y ago
I'm fairly certain they were looking for a linked list, but I could be wrong.
- gopalv 5y ago
  > fairly certain they were looking for a linked list, but I could be wrong They were probably looking for an answer which went along the lines of a linked list and then what to fix - the ratio of pointer sizes to data (16-item nodes), sorted insert optimizations, the ability to traverse to the 500th element faster etc (skips with pow-10 or a regular skip list etc). I bombed a similar soft-ball interview question in the past, because I was asked to build out a work item queue using a database in SQL & I got stuck failing to explain why it was a bad idea to use an ACID backend for a queue. Some constructive feedback from the person who referred me came back as "dude, you just wouldn't let go of the topic and the interviewer gave up on you". That was definitely true for me, but I remember that feedback more than the actual technical correctness of my opinion. That was a clear failure of fit in multiple ways, but it didn't matter whether I was right or not, I had failed to persuade someone who would be my team lead on a topic which I had deep knowledge on. Even if I was hired, it wasn't going to work out.
  - marcosdumay 5y ago
    > it was a bad idea to use an ACID backend for a queue Why do you think so? It completely depends on the utilization of their ACID backend, and how well it handles independent data.

kleiba 5y ago

Why didn't you just say "...or, you could use a linked list" when you notice them doubting your first answer?

munificent 5y ago
By that point, they said we should just move on to the next question.

deleted 5y ago

[deleted]

winrid 5y ago

In game dev, that one copy might cause a frame drop. Even if amortized over time the frame rate would be slightly higher, the occasional dip might make it unplayable. Of course, arrays have better cache locality, but they didn't ask about that. They were probably looking for a linked list with a small array in each node, which gives more constant write performance and less cache misses on read.

munificent 5y ago
They didn't ask about latency either. I would have been happy to have the discussion of real-world performance, but we were stuck on the basic "what is the algorithmic complexity of this?" question.
chakkepolja 5y ago
If they had the clue what they were asking about, wouldn't they have corrected GP? "No dude we can't have that worst case here in game dev!!". But they asked about algo complexity and couldn't recognize GP was talking about amortized complexity, something sounds wrong.

superrad 5y ago

It's not great to have to double your memory usage while you reallocate your array. On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. There's also the cost of copying objects especially if you don't know if the objects you're copying from your original array to the resized array have an overloaded copy constructor. Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour. If you're holding pointers to these elements elsewhere re-allocating invalids those, and yes you probably shouldn't do that but games generally are trying to get the most performance from fixed hardware so shortcuts this will be taken, its a least something to talk about in the interview. I can see why they were confused by your answer as its really not suited to the constraints of games and the systems they run on.

munificent 5y ago
> It's not great to have to double your memory usage while you reallocate your array. You don't have to use a growth factor of 2. Any constant multiple of the current size will give you amortized constant complexity. > On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. If fragmentation is a concern, you can pre-allocate a fixed capacity. Or you can use a small-block allocator that avoids arbitrary fragmentation at some relatively minor cost in wasted space. > Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour. We have an intuition that moving stuff around in memory is slow, but copying a big contiguous block of memory is quite faster on most CPUs. The cost of doing that is likely to be lower than the cost of cache misses by using some non-contiguous collection like a linked list. > as its really not suited to the constraints of games and the systems they run on. For what it's worth, I was a senior software engineer at EA and shipped games on the DS, NGC, PS2, Xbox, X360, and PC.
- superrad 5y ago

gamblor956 5y ago

It sounds like you bombed the interview because your answer was not the correct answer for the domain. For games, it absolutely does matter that only some appends trigger latency, because that causes stuttering in the game play. A linked list may be slower in most use cases...but the performance cost is fixed and can be easily designed around.

munificent 5y ago
I feel like I've replied to this same thing about five times now, but, yes, I completely understand the latency concern with growing a dynamic array. At the time, we weren't talking about it. Their question was, "What is the complexity of this?" And I said, "It's constant time over a series of appends." We didn't get past that.
- asr21 5y ago
  The guy worked at EA for 8 years.. He must know what he is talking about
  - sudopluto 5y ago
    he also wrote the crafting interpreter book : )
    - munificent 5y ago
      And Game Programming Patterns, which has a chapter on the performance effects of contiguous data: https://gameprogrammingpatterns.com/data-locality.html https://gameprogrammingpatterns.com/data-locality.html :)
  - deleted 5y ago
    [deleted]
  - wffurr 5y ago
    That means nothing. Time != experience. You have to have actually learned during that time for it to count for anything.

planet-and-halo 5y ago

I had a less dramatic one where someone argued with me that the lookup time on a binary tree was O(H), the height of the tree, not O(log2n). I was so baffled by the argument that I didn't realize until after the interview that I should have pointed out that the height of a binary tree is log2n.

slavak 5y ago
They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
- planet-and-halo 5y ago
  Doesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?
  - wtetzner 5y ago
    No, not all binary trees are balanced binary trees.
    - planet-and-halo 5y ago
      Ah got it, thanks.

exdsq 5y ago

I really enjoyed your Crafting Interpreters book! Jokes on them for missing out.

mrxd 5y ago

There was a meme going around where a doctor took a high school biology quiz. Q: What are mitochondria? A: [Long complex scientific answer about ATP synthesis] Grader: Wrong. Mitochondria are the powerhouse of the cell.

TomNomNom 5y ago
In a "Business and Communication Systems" exam at school I got the question "Explain how email works". Being the nerdy teen I was, I wrote about SMTP, MX records and that sort of thing. That was not the right answer.

AtNightWeCode 5y ago

Typically interviewers are looking for the general known common way to do things. I heard people failed cause they wrote code that use bitwise AND instead of MODULO to check if a positive integer is even. Just the way it works even if I don't like it.

wly_cdgr 5y ago

You should have just said "Look guys, trust me, I am going to write Game Programming Patterns one day"

munificent 5y ago
I was already writing it when I did this interview! (Though, I hadn't gotten to the chapter on data locality yet.) One of the main reasons I started writing it was to help my job search. Which, ironically, ended up not being necessary because I left the game industry. What's crazy to think about is that if I hadn't failed this interview, I probably wouldn't have gone to Google. So this one weird failure to explain the big-O of dynamic arrays may have dramatically changed the course of my career. Or, who knows, maybe they failed me for other reasons.
- wly_cdgr 5y ago
  Well, all's well that ends well. Failing that interview just might have made you a couple million dollars richer. With all due lip service to all the other advantages of working on hard problems at Google, of course :) Funnily enough, I am trying to go the other way over the next decade or so, ...so looking forward to reading your book, heh

gmadsen 5y ago

am I the only one concerned that this would even be a point of contention? This seems too trivial for anyone doing hiring or being hired to be hung up on.

munificent 5y ago
I mean, I'm guessing this is the main reason that they passed on me, but I'll never know for sure. Maybe they didn't like my personality. Maybe it was some other question I thought I did well on but didn't even realize I got wrong. Maybe a combination of things. For what it's worth, I didn't get a very good vibe from them. The impression I got was that their culture was more aggressive and competitive than I like. (Maybe this was to be expected for a company that made a competitive eSports game.) I'm not really what you'd call a brogrammer. So it was probably for the best that they said no. I ended up at Google, which has been better for me in every possible way.
- DonHopkins 5y ago
  >I'm not really what you'd call a brogrammer. I'd say you dodged a bullet, but it's more like you dodged a ball. https://www.youtube.com/watch?v=W-XbDZUnUmw&ab_channel=MovieclipsClassicTrailers https://www.youtube.com/watch?v=W-XbDZUnUmw&ab_channel=Movie...
scottlamb 5y ago
> am I the only one concerned that this would even be a point of contention? This seems too trivial for anyone doing hiring or being hired to be hung up on. You'd be surprised! I've done probably 200+ interviews across a couple companies. Over time if anything my questions have gotten simpler. I look for someone who understands the fundamentals of the stuff on their resume, asks good requirements questions, thinks a bit before leaping into the weeds, can explain their thought process, ideally does some of their own double-checking, and (if it comes up) can debug a problem I spot without my spelling out their error. And last but not least: I don't want to cause a panic attack, which would be mean and tell me nothing. Sometimes my candidates have been too nervous for me to know if I should hire them, and it's not a good experience for anyone. So I make the problem as simple as I can and make sure we get through the rest of that in as relaxed a fashion as I can manage. I'll ask a simple (often first-year CS) coding problem or a design problem, rarely both in the same interview slot. I never ask for tons of code on a whiteboard in a 45-minute slot.

deleted 5y ago

[deleted]

dcow 5y ago

I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on a show than a practical solution to the task at hand. The worst case performance for a dynamic array is O(n), but the amortized performance is constant. They aren't the same thing. You may be a different, more mature, engineer nowadays. But, when I encounter the type of persona your story describes I tend to respond with strong no’s irrespective of whether you have since written a textbook.

lmilcin 5y ago
Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complexity yet hugely different costs. For example, you can easily parallelize operations on array lists but you can't do that on linked list where to get to next node you need to dereference a pointer. Even without this, you get bonus from prefetching data to cache when searching through array list or when doing things like moving data. Speculative dereferencing pointers is nowhere close to just regular prefetch. Array lists are denser in memory than linked lists (because of additional pointers). This means that a lot of things works just more efficiently -- cache, memory transfers, prefetching, less need to resolve TLBs, etc. Inserting into array list at the end is as fast as into linked list (after taking account for amortized cost), but what not many people appreciate is that finding an insertion place and inserting within array list is also the same cost or even better than in linked list. That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot. Actually, it costs more than copying the same size of array list.
- deleted 5y ago
  [deleted]

benhoyt 5y ago

Link to said textbook content on dynamic arrays: http://www.craftinginterpreters.com/chunks-of-bytecode.html#a-dynamic-array-of-instructions http://www.craftinginterpreters.com/chunks-of-bytecode.html#... Edit: Ah, I just saw munificent linked to this in a reply elsewhere in the thread.

Siira 5y ago

I, too, lost a question on my Data Structures final exam by using amortized analysis.

lostcolony 5y ago

I see a lot of responses defending the interviewers, or saying what you should have done. Maybe so, but I'm just gonna go ahead and say - those interviewers were shit. Most interviewers are, so it's not really a judgement on them, but the problem in that room wasn't you.

javajosh 5y ago

Next you'll try to convince us that "munificent" is a real word and not just a misspelling of "magnificent". Sheesh.

lowbloodsugar 5y ago

Here is the question that was asked, and here is the question that was answered (quoting): Asked: "constant time complexity" Answered: "constant time when averaged over a series of appends" In an interview, the onus is really on candidate to answer the question as it was asked. Candidate did not answer question, and there was a breakdown in communication. Candidates interpretation is that interviewers didn't know what candidate was talking about. Interviewers could just as easily have been frustrated that candidate did not see significance of the difference. In my experience, interview technique requires establishing a common ground. As an interviewee, I find that the first step of answering a question is to first go through a number of possibilities starting with the most obvious first. They were most certainly looking for a linked list. This is a simple question with an obvious answer. It would have been good practice to start with the answer they obviously wanted, and then try to broaden their minds. Instead, candidate willfully derailed the interview. To me this looks like a classic breakdown of communication with a root cause of hubris (quite possibly on both sides). While both sides failed in this account, only one has the benefit of hindsight in writing about it here today. Time has offered an opportunity for reflection. What has candidate learned? "[look how clever I am] so joke's on them"

stirfish 5y ago

Game Programming Patterns is one of my favorite books btw