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.
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).
This is dangerous, but if well documented and understood it might be okay. Some data might contain unique things (for argument's sake, say a std::unique_ptr). It can get tricky since you need to know the implementation details of everything that gets inserted and it's ownership behavior, since elements can be kept at two places. (A copy in array n and one in 2n.)
Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
As for the original interview question, there are systems where an occasional longer pause is not OK. Personally, I think that sticking to your gun must have come across as being stubborn and unyielding and maybe not ready to admit errors. As an interviewer, and for having worked with people who always think they're right and inflexible, it would have been a red flag.
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
> As for the original interview question, there are systems where an occasional longer pause is not OK.
As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten.
I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.
To be clear, there is no tradeoff in the number of operations. You are doing the exact same number on average (or total or amortized), while improving the worst-case.
You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
This is the exact same average cost per element, just spread out evenly. Consider that each element still gets copied to the array of twice the size once whether you use this technique or the classic amortized version. Same average performance without the hitches (although copying a larger block of memory at once would likely be a bit faster).
> This is dangerous, but if well documented and understood it might be okay.
I agree in principle. I think even something like std::unique_ptr could work; the concern would be self-referential types. Notably Rust doesn't allow those anyway, so I think any Rust type would be fine, not just Copy types.
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
Still might be a lot better than a linked list for small types (due to less RAM spent on pointers and better cache locality because it's contiguous). With the exception of intrusive linked lists of stuff that is separately allocated anyway, I really hate linked lists.
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.
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.
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.
It's pretty easy to make sure an arbitrary sequence is valid if you make push and pop be almost exact opposites of each other.
Let me walk through a simple version based on the description above, ignoring that it's rather inefficient:
Start with an array of size 64, with 32 elements.
Our first action is either a push or a pop. I'll split those up.
* * * If the first action is a push:
From here, call the existing array Small and make a new 128 element array called Big.
For the first push, store it in Small[32]. Then copy Small[0] and Small[1] to Big[0] and Big[1].
For the second push, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3].
Then for a pop, just remove the element in Small[33].
Then pushing again, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Notice how this is exactly the same as the previous push. And if you undid two pushes, then did two more pushes, both of them would be the same as they were before.
So, analyzing this, once we push once, any arbitrary sequence of pushes and pops is going to do one of the following:
* Pushes is always more than pops, but the difference is always under 32. This bounces around forever, undoing and redoing pushes. This is valid, and always uses the same amount of space for 33-63 elements, so that's clearly linear too.
* Eventually pops catches up to pushes. This means we're back to 32 elements, right where we started. Throw out the 'Big' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions.
* Eventually pushes minus pops reaches 32. So now our Small array is completely full, and our Big array is half full, and they contain exactly the same data. Throw out the Small array. Now we're back where we started, except with twice as many elements in an array twice as big. Use all the same logic as before, but with 2x numbers. This is valid and uses linear space.
* * * If the first action is a pop:
From here, call the existing array Big and make a new 32 element array called Small.
For the first pop, copy Big[0] to Small[0]. Then delete and return Big[31].
For the second pop, copy Big[1] to Small[1]. Then delete and return Big[30].
If we get a push, put it in Big[30].
If there's another pop, copy Big[1] to Small[1]. Then delete and return Big[30]. Notice how this is exactly the same as the previous pop. And if you undid two pops, then did two more pops, both of them would be the same as they were before.
So, analyzing this, once we pop once, any arbitrary sequence of pops and pushes is going to do one of the following:
* Pops are always more than pushes, but the difference is always under 16. This bounces around forever, undoing and redoing pops. This is valid, and always uses the same amount of space for 17-31 elements, so that's clearly linear too.
* Eventually pushes catch up to pops. This means we're back to 32 elements, right where we started. Throw out the 'Small' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions.
* Eventually pops minus pushes reaches 16. So now our Small array is half full, and our Big array is one quarter full, and they contain exactly the same data. Throw out the Big array. Now we're back where we started, except with half as many elements in an array half as big. Use all the same logic as before, but with numbers cut by 2x. This is valid and uses linear space.
There.
Now, there are easy optimizations that could be done on top of that to cut the memory use in half, or combine pushing and popping into the same logic, or all sorts of other improvements.
And you want to have a special case if the size gets too small to stop shrinking.
But that should be a perfectly good basic explanation of an algorithm that's very straightforward and has no wiggle room for anything to go wrong.
Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be.
I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead.
If moves aren't available then a resizable array was doomed from the start.
Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back)
Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.
You don't need placeholders. Can you explain why you're thinking about placeholders?
For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent.
Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array.
> (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back)
So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array.
Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array.
Seems problem-free to me.
If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop.
When the arrays are size 32 and 64, the logic to access an element looks like this:
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.
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.
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything.
Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.
GP basically created a hypothetical situation wherein they were right, and then here you are saying they're wrong. The only case in which you would be right in saying the GP is unequivocally wrong is if dynamic arrays were Pareto-optimal compared to linked lists.
Alice: Can you think of any situation where apples are better than oranges?
Bob: Well, if someone had a craving for apples, then they would be better.
Charlie: Unfortunately, you are wrong. Even in that situation, oranges are juicier, have more tang, and contain more vitamin C.
> That is because to find insertion/deletion place you must first run linear search on linked list and that costs a lot.
That isn't always true. If you already have a pointer to the position in the list, and the list has an API that supports it (which a good implementation would), then with a linked list you wouldn't need to traverse the list again.
That said, in most cases that probably isn't worth the downsides of a linked list, especially if the size of the list is small.
> 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).
I think you're overcorrecting here.
There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true.
Today, in many cases, arrays are faster. And that awareness of caching effects is becoming greater. But I think there's a tendency to over-apply new knowledge that seems counter-intuitive.
The reality is somewhere in the middle. Arrays can be surprisingly fast, even when you need to shift stuff around to insert or copy to grow. But there are still plenty of cases where linked lists are better if you are doing a lot of inserting or rearranging. I don't think the guidance is so much "linked lists bad!" as it is "arrays maybe not bad".
> There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true.
Nothing to do with caches or conventional wisdom no longer being true.
Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert?
Unless you have some kind of index to the list (in which case it no longer is a linked list, it is some other data structure), you have three options:
a) at the beginning of the list
b) at the end of the list
c) in the middle of the list, in which case you need to run linear search to find the place.
If you want to do this at the end of the list, then array list has the same amortized cost as linked list.
If you need to do this at the beginning of the list, then array list can be reversed. Unless you have the very special case of having to add at both beginning and end of the list.
So most likely you need to insert somewhere within the list to see the improvement over an array list.
But then you need to do the linear search and the search is so much slower with linked list that it completely offsets the cost of copying of all that data.
They were talking about big-O analysis (or whatever you want to call it), then you jump in talking about speed and performance. That's not the same thing, and as you say, may not even be closely related. I think your right, but again, it's not applicable to the point of contention the above comments were discussing.
Also, in an interview, it should be fine to talk about all this. It could lead to some good technical discussion where you can show your knowledge. If such a conversation does arise though, remember you have to make these people like you and ramming your point down their throats and forcing them to acknowledge that you're right and they're wrong probably doesn't do that. Also, don't forget you may, indeed, be wrong.
If one person says a linked list is faster than an array list but the opposite is true, then why do you claim it is not applicable?
Isn't it exactly the point of the article, that sometime you need to say what the interviewer wants to hear rather than what is the actual truth?
It is an unfortunate truth that a lot of interviewers will ask about linked lists vs array lists and at the same time will not understand that linked lists will be slower for insertions or deletions in most cases.
That is because you first need to find the insertion/deletion place, and any benefit of faster insertion/deletion for linked list will be offset by much slower search.
None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.
> None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.
I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster?
I think you have lost your way and need to backtrack a little bit.
The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.
If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. That might end up being slower, but so what, maybe that's what I need.
If I ask for an O(1) algorithm and you build something that is as fast as possible, faster in every case, but sometimes it's really fast and sometimes it's a little less fast but still fast -- well, then it's not O(1) and not what I asked for. It may be fast, but if it's sometimes faster than at other times it's not O(1).
Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.
> Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.
Maybe not synonymous in the sense of technically exactly equal, but certainly a pretty good approximation -- and absolutely synonymous in the sense that the whole purpose of big-O notation is to be able to reason about speed in more general terms, comparing algorithms in pseudo code in stead of having to actually write the program so you can run it through a benchmark.
So, no: If "the best possible big-O, O(1), does not necessarily mean the fastest," then it isn't actually the best.
I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.
What it really means is that the execution time does not depend on the size of input (n).
What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time.
For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.
> an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.
According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) <= M * 1. But according to your own words there's no upper limit to 1/(randFloat()), therefore there's no such constant M, therefore it's not O(1).
(In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)
More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class.
What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.
> The whole point of big-O analysis is to be able to reason about how fast a program will be given input size.
It's an important technicality that matters when you are doing performance tuning of code on modern CPU's. Big-O is asymptotic but omits the constant multiplier, so if you're comparing, for example, deletion from a naive binary search tree vs. an unsorted array, it's not necessarily obvious that a tree search on a naive pointer based tree (O(log n)) is faster than a find, swap, and delete (O(n)) until n is sufficiently large.
Another example is iterating through the pixels of a very large bitmap on the order of 10m+ pixels. While iterating through all pixels should be linear to the number of pixels (O(width * height)), assuming it's a row-oriented bitmap, which most are, scanning row by row can be substantially faster than scanning column by column because of caching behaviors.
Point being, big-O and actual performance are not always the same thing because the constant factor can sometimes dominate depending on what you're trying to do.
"Performance" depends on a number of factors beyond the code itself.
To take a real world example, immutable operations in Javascript are often more performant than mutable operations--thanks to the fact that the Chrome Engine "cheats" with its hot path functionality.
However, in Big O, constantly generating new data structures, even within loops, would clearly trash the algorithm's space complexity. On compilers that don't optimize for immutability, the Big O algorithm is more performant; on the ones that do, the immutable approach is more performant.
It's because of example like these that you want to disconnect the concept of "performance" from Big O. Because context matters for the former, while the latter relates only to the algorithm itself.
In cryptography the goal might be to ensure the algorithm always takes the exact same amount of time, or the exact same number of CPU instructions, even if it is slower than alternatives. This is a case where we are interested in complexity without regard to speed.
Thus, the answer to why we care about complexity is "it depends". But it is not always about speed.
In those cases, if you click on the "X minutes ago" timestamp you'll get a single comment view with a reply box. Yours didn't have a reply link in-thread, so just like I did here.
Immutable doesn't necessarily mean unchanging in the context of data structures.
An immutable data structure can support adding, removing, and/or changing the data but the way it does it is in such a way that once data is created it isn't modified until it is completely unused and unreferenced.
So an immutable data structure has the benefit that data stays the same and stays the same in memory so it can be shared where duplication exists. You can copy said data-structure but it won't actually modify the underlying data and will just allocate a new tag/head that holds some reference to the underlying data. Now this new copy can be modified and it will instead just allocate a new block of memory for the changed portion and stitch it in to the head/tag structure as if it was just some diff/delta.
Here immutable means that the underlying data is unchanging and can be reused/shared by multiple instances, not that it is unchanging at all from an external point of view.
Now in the case of your comment, an array is extraordinarily bad in most cases for an immutable data structure as it is extremely difficult to sub-divide and let go of unused/old parts without breaking that immutability for the in-use data. Linked lists have their own issues as well but can be a valid trade-off for certain types of immutable data structures. Generally though trees will be the primary underlying structure for these immutable data structures as they are easy to use for this purpose, have reasonably good lookup times, have reasonable worst time complexity, and most importantly decent average/amortised time complexity.
The term you are looking for is pointer stability. It can be a useful property, but you can also get it storing pointers in a vector. That would often be faster in practice than a linked list.
Isn't that a persistent DS and I thought OP mistook it for immutable-at-memory-level data structure.. like an array you create once but read many times from..
Well yes but I've always seen immutable DS as synonymous for persistent DS. What OP refers to I've found to be referred to as fixed, const, const static, or compile-time static data structures.
Of course naming in CS and Math is terrible and we love reusing terminology so that everything is confusing but that's just where we are.
I wasn't trying to be negative towards OP or anything. I just saw that since their comment was downvoted so heavily (which it really shouldn't have been), it might be beneficial to reply with an explanation to clear up any misconceptions and smooth out the conversation.
I think you would have a hard time finding someone who knows me describe me that way. Maybe the way I related the anecdote here doesn't present me well. I am pretty meek and easily flustered. I don't think I was any more confident back then than I am now which is, alas, not very.
> The fact that you were unable to incorporate this into the conversation
In this case, it was an interview with three other engineers simultaneously (a truly cursed interview format), so it was hard to incorporate much of anything into the conversation. It felt much like I imagine a thesis examination where the three of them were in charge of pacing and questions. (Also, it was ten years ago, so I'm sure my memory has faded.
What I recall was them asking me how I'd do some sort of growable collection. I said I'd probably do a dynamic array. I mean, that is the way 99% of growable collections are done today—look at Java's ArrayList and C#'s List. This is a company that does strictly PC games and I was hiring for a tools position. Dynamic arrays are the right solution most of the time in that context.
They asked what the complexity was. I said something like "Constant time, across multiple appends." They didn't seem to get that and asked what the worst case was. I was some appends are O(n) but amortized across a series of them, it's constant. When I tried to clarify, they said they wanted to move on. I think in their minds I was hopelessly lost and they wanted to get to the next question so that I didn't embarrass myself further.
I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for. My impression was that they had never heard of amortized analysis at all, and thought I was confusing average case and worst case analysis (which I was not). From their perspective, I can see how I looked lost or wrong.
Overall, they had a superior tone that I found off-putting. (For comparison, I didn't get that impression from any of the interviews I had at Google the very next day. My Google interviewers were all kind, engaging, and really fun to talk to.)
You may be entirely correct in your analysis. There are definitely a fair share of toxic interview setups and interviewers out there. What I found off putting about the way you presented the story was the bit at the end where you gloated about your current employment status and achievements as if they missed out on some great mind. It gives the impression that in your view, your intellectual prowess was more important than being a good candidate and potential teammate. While that of course may just be the way it came off, that was my perception. So it drove me to present the alternate, less charitable, interpretation where the interviewers did in fact understand amortized complexity and simply didn't find it suitable.
> I would have been happy to have a more productive discussion about which problems amortized analysis was the right fit for.
This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system. I also might try to bait this topic by specifying O(1) worst case insertion up front and watch for how the candidate interprets the requirement, what type of questions are asked, etc. If you started implementing an array backed thing I might stop you early and prompt the insertion analysis specifically. However, in my experience people tend to discuss an overview of the solution before writing any code which is a great point to iron out any clear non-starters or missing requirements.
> Overall, they had a superior tone that I found off-putting.
Fair. It's a two way street after all. Even if they were entirely fine and it was all a comms misunderstanding, sometimes personalities just don't gel. Glad you found success the next day!
> What I found off putting about the way you presented the story was the bit at the end where you gloated about your current employment status and achievements as if they missed out on some great mind.
Yeah, that's fair. I'm not one to gloat usually but I never felt like I got closure from what was a pretty unpleasant interview experience so I couldn't resist the urge to get a dig in.
> This is the type of conversation I tend to enjoy during interview problem solving because IMO it most accurately reflects the type of conversation you'd actually have with teammates when building a system.
My Google interviews were so much better in this respect. The interviewers were really candid and fluid. They did a great job of letting me bring up points that I thought were relevant but not get too ratholed. Overall just a miles better experience.
> sometimes personalities just don't gel.
One way to look at it was that the interview was a success because it established that I likely wouldn't be happy working with those devs and that kind of culture.
If the question was about constant time complexity but the questioners had a secret additional requirement that they refused to share, that's a flaw in the questioning. If the questioners had that additional secret requirement and understood amortized analysis, then they should have at least given a hint at their secret requirement by saying something like "your proposal does indeed deliver amortized constant time complexity, but what could the potential downsides be of this approach?" If the commenter is giving an accurate description of what happened in the interview, then the questioners were absolutely the ones being stubborn or ignorant. (And, incidentally, I'm pretty sure that dynamic arrays are going to come out ahead in practice even with the secret "tight loop" requirement.)
Games work with time budgets of many milliseconds per frame, relatively long timescales from a cpu pov. It is rare to prefer predictable per iteration latency in loops over higher throughput unless the deferred batch of work is quite big. But of course this can compound in some cases, eg you have thousands of these arrays being extended in lockstep and they all trigger the extra work at the same time...
Yep, and the associated dynamic memory allocation for LL nodes will still have latency spikes from the malloc implementation so its worst case latency is still bad.
I'll add the really correct but stubborn answer. It's a game, why are we allocating memory?
Working in for example Unity I need to not ever allocate anything per frame if I can help it (and then knowing other gotchas such as that foreach and/or getting the .Count on a list will also cause memory to be allocated).
This is so true. It’s about putting as many good vibes and good feelings into the interview as possible while also seeming competent. “Do I want to work with this guy?”
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!
>> 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.
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.
It's probably implicit, it's a gaming company, however it might be fair to say the interviewers didn't appreciate the possibilities outside of gaming and unconsciously assumed this context was understood.
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.
One thing I’d add is in games the workload is known in a way that other general applications don’t have. In this case you can think of the work as “preloading” where the allocations / disk reading can happen several seconds before they are needed for rendering or physics/collision. This is a pretty cool special case as it means you can hit your allocation targets before you need it giving the best of both worlds: the cache coherence in arrays, and perfect framerate because you have far fewer memory allocations focused on known game events (cinematic transitions, enemy changes, or map streaming boundries, etc)
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.
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)
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 :)
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.
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.
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?
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.
> 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.
When you reallocate your array you will in memory have your old array and your new larger array while you move your data over. At the very least you're using 2x and the extra memory for your expansion.
For your other points if you'd mentioned them in the interview you'd probably have been better received. Copying is really only that fast for POD objects (your objects copy constructors may need to do reallocation themselves or worse) so if you're suggesting a general solution you should be aware of that (or at least mention move constructors if they were available at the time) .
I would be surprised if any of the games you worked on actually shipped with an amortised resize of dynamic arrays (at least not for anything that didn't matter in the first place) so I don't know why you'd suggest it as a general solution in a game dev context.
A linked list needs a pointer for every piece of data. If the data is small, this will also be a 2-fold memory impact. Plus impacts on cache coherency.
A typical C implementation would be using realloc():
The realloc() function tries to change the size of the allocation pointed to by ptr to size, and returns ptr. If there is not enough room to enlarge the memory allocation pointed to by ptr, realloc() creates a new allocation, copies as much of the old data pointed to by ptr as will fit to the new allocation, frees the old allocation, and returns a pointer to the allocated memory.
Worst case definitely 2x memory. But not necessarily always.
> 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.
That doesn't smell right to me, assuming you're talking about userspace applications on newer hardware. aarch64 supports at least 39-bit virtual addresses [1] and x86-64 supports at least 48-bit virtual addresses [2]. Have you actually had allocations fail on these systems due to virtual address space fragmentation?
Certainly this is something to consider when dealing with low-RAM devices with no MMU or on 32-bit, but the former hasn't applied to the device categories you mentioned in probably 20 years, and in 2021 the latter is at least the exception rather than the rule.
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.
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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
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.
This answer is the epitome of all of the answers here pointing probably in the wrong direction.
The OP is basically saying any discussion of 'amortization' or anything past something very simple, was completely beyond them.
And your response, like many others here, is gong way off into the weeds, suggesting 'what they were really expecting' etc..
I definitely understand HNers willingness to go into the weeds for no apparent reason, but the lack of social comprehension here is really odd.
The OP has reiterated over and over the social context and yet everyone seems to be happy to dismiss it whilst providing their bit of extraneous extra input.
It goes on like a comedy.
"But they must have been expecting this niche/novel thing way over here in the corner, and well if you didn't get that ..."
It's as though the respondents are validating the poor ability of we techies to establish context.
Any specific requirements in the interview, it would seem, could have been discussed by the interviewer and frankly without providing very specific contextual details, there's no such thing as a 'right answer' because it always 'depends'.
And finally, why anyone would expect specific correct answers instead of a discussion about the constraints is also odd to begin with.
> 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.
There is a tradeoff between the cost of introducing another component, and the advantages of a perfect component.
If you already have an ACID database at hand, and your queue requirements are not that big, using the database and NOT having to have someone around who knows exactly how Rabbit MQ was set up is better than to require everyone around you to know the piece of specialized software that you happen to be a domain expert on.
Conversely if your needs are demanding enough, then it is best not to let your team discover the hard way why people build dedicated queueing systems.
If you are unable to accept that this tradeoff even exists, then I wouldn't want to be your team lead.
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.
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"
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.
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.
> 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.
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.
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.