News for hackers. Stuff that matters.
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @05:18PM (#27887359)
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.

Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @05:29PM (#27887464)
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.

Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @05:50PM (#27887648)
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.

Re:I had to give a wrong answer to get the job (2017) by whatshisface on Monday July 19, 2021 @09:49PM (#27889309)
I have never ever seen a linked list in a game, anywhere, serving any purpose.
Re:I had to give a wrong answer to get the job (2017) by areyousure on Tuesday July 20, 2021 @12:52PM (#27896146)
Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Wednesday July 21, 2021 @03:18AM (#27903297)
He is still probably technically right.

"I have never seen (...)"

Re:I had to give a wrong answer to get the job (2017) by dcow on Wednesday July 21, 2021 @09:57AM (#27906337)
Nobody responding asserted anything to the contrary. Rather, examples were provided rhetorically and for anybody interested in exploring more.
Re:I had to give a wrong answer to get the job (2017) by dcow on Tuesday July 20, 2021 @12:21AM (#27890033)
Re:I had to give a wrong answer to get the job (2017) by rytill on Monday July 19, 2021 @05:56PM (#27887707)
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.

Re:I had to give a wrong answer to get the job (2017) by emerged on Monday July 19, 2021 @08:23PM (#27888820)
Sorry but your analogy makes no sense because Kiwis are better.
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @08:50PM (#27888995)
Worth the DVs (;
Re:I had to give a wrong answer to get the job (2017) by thayne on Monday July 19, 2021 @09:00PM (#27889045)
> 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.

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @06:03PM (#27887777)
> 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".

Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @06:08PM (#27887844)
> 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.

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @06:29PM (#27888029)
> Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert?

You usually have a pointer to the node where you want to insert.

I don't think many people would suggest using linked lists in cases where you actually do need to seek for the insertion point.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @05:58PM (#27887731)
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.

Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @05:59PM (#27887744)
What is not applicable?

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.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @06:10PM (#27887868)
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.
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @06:13PM (#27887897)
> 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.

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @06:51PM (#27888196)
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.

Re:I had to give a wrong answer to get the job (2017) by CRConrad on Monday July 26, 2021 @03:03PM (#27963790)
> 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.

Re:I had to give a wrong answer to get the job (2017) by sagarm on Wednesday July 21, 2021 @10:48AM (#27907043)
A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1).

Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.

Re:I had to give a wrong answer to get the job (2017) by indeed30 on Monday July 19, 2021 @07:20PM (#27888393)
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.
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @07:33PM (#27888487)
Well, not exactly.

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.

Re:I had to give a wrong answer to get the job (2017) by peferron on Monday July 19, 2021 @10:30PM (#27889511)
> 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.)

Re:I had to give a wrong answer to get the job (2017) by randomswede on Wednesday July 21, 2021 @02:56AM (#27903124)
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.

Re:I had to give a wrong answer to get the job (2017) by dcow on Wednesday July 21, 2021 @10:02AM (#27906418)
Re:I had to give a wrong answer to get the job (2017) by munchbunny on Monday July 19, 2021 @10:22PM (#27889475)
> 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.

Re:I had to give a wrong answer to get the job (2017) by dentemple on Monday July 19, 2021 @06:48PM (#27888170)
"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.

Re:I had to give a wrong answer to get the job (2017) by DangitBobby on Monday July 19, 2021 @06:51PM (#27888199)
Replying here because I can't to the relevant comment:

> No it’s not, it’s about trying to quantify algorithmic complexity.

And what would you say is the goal of quantifying algorithmic complexity?

Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @07:00PM (#27888270)
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.

Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @07:10PM (#27888324)
BTW I've found that in cases where the reply and/or edit button(s) disappear, refreshing the page usually causes them to appear.
Re:I had to give a wrong answer to get the job (2017) by Buttons840 on Monday July 19, 2021 @07:49PM (#27888597)
There's a delay before the reply button appears to encourage more thought as discussions get deeper. A HN thing.
Re:I had to give a wrong answer to get the job (2017) by rhizome on Monday July 19, 2021 @08:10PM (#27888738)
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.
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @08:10PM (#27888736)
Wow I thought this was some rendering bug for the longest time. Is there any (un)official list of HN quirks, out of curiosity?
Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @06:45PM (#27888150)
No it’s not, it’s about trying to quantify algorithmic complexity.
Re:I had to give a wrong answer to get the job (2017) by benibela on Monday July 19, 2021 @07:23PM (#27888414)
Linked lists are better for immutable/persistent structures
Re:I had to give a wrong answer to get the job (2017) by lmilcin on Monday July 19, 2021 @07:27PM (#27888442)
If your data structure is immutable, then an array is always faster than a linked list.
Re:I had to give a wrong answer to get the job (2017) by jacoblambda on Monday July 19, 2021 @08:53PM (#27889008)
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.

Re:I had to give a wrong answer to get the job (2017) by sagarm on Wednesday July 21, 2021 @10:53AM (#27907105)
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.
Re:I had to give a wrong answer to get the job (2017) by chakkepolja on Tuesday July 20, 2021 @08:49AM (#27893072)
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..
Re:I had to give a wrong answer to get the job (2017) by jacoblambda on Tuesday July 20, 2021 @01:15PM (#27896465)
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.

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @05:57PM (#27887718)
> for being stubborn and drunk on ego.

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.)

Re:I had to give a wrong answer to get the job (2017) by dcow on Monday July 19, 2021 @07:32PM (#27888480)
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!

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @08:20PM (#27888806)
> 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.

Re:I had to give a wrong answer to get the job (2017) by lwansbrough on Monday July 19, 2021 @09:53PM (#27889328)
> I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego.

This flippant remark followed by the egotistical follow up is the kind of art I read hacker news for, thank you.

Re:I had to give a wrong answer to get the job (2017) by tshaddox on Monday July 19, 2021 @05:50PM (#27887642)
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.)
Re:I had to give a wrong answer to get the job (2017) by chakkepolja on Tuesday July 20, 2021 @08:45AM (#27893040)
If they were not dumb, they would've explained him why amortized complexity is not suitable measure for their application.

If they were not dumb, they would definitely understand what he was saying and not sit clueless.

Re:I had to give a wrong answer to get the job (2017) by fulafel on Monday July 19, 2021 @05:37PM (#27887537)
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...
Re:I had to give a wrong answer to get the job (2017) by Dylan16807 on Monday July 19, 2021 @09:23PM (#27889180)
If the arrays are big enough for growing them to mess up your time budget, then it's quite likely that a linked list would already be failing.
Re:I had to give a wrong answer to get the job (2017) by fulafel on Tuesday July 20, 2021 @03:49AM (#27891017)
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.
Re:I had to give a wrong answer to get the job (2017) by animal531 on Tuesday July 20, 2021 @11:02AM (#27894621)
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).

Re:I had to give a wrong answer to get the job (2017) by op00to on Monday July 19, 2021 @08:12PM (#27888754)
Interviews are about shows, not boring answers.
Re:I had to give a wrong answer to get the job (2017) by bunfunton on Monday July 19, 2021 @10:12PM (#27889438)
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?”