I had to give a wrong answer to get the job (2017) • Hacker News Board

Re: I had to give a wrong answer to get the job (2017)

#281

Post by lmilcin » Mon, Jul 19, 2021, 9:59 PM UTC

Buttons840 wrote: post #280

lmilcin wrote: post #266

Earlier quoted context omitted.

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 complex…

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…

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)

#282

Post by bialpio » Mon, Jul 19, 2021, 10:01 PM UTC

Jtsummers wrote: post #243

bialpio wrote: post #235

Earlier quoted context omitted.

In our case n = value of the input, log(n) = size of the input. Complexity is expressed relative to the size of the input. Size of the input is also usually expressed as n, which is shadowed by "value of the input" in the problem statement, so "sublinear with respect to n" has different meaning than "sublinear with respect to size of the input", & saying "sublinear" when talking about complexity implicitly translates…

Asymptotic analysis is about finding some quantifiable property (or properties) of an algorithm (in this case it can be seen as the index into the sequence of Fibonacci numbers) and determining how fast the algorithm "grows" (in this case it's about time, not space, though can be used for space as well) with respect to that quantifiable property. The original commenter uses n to indicate which value in the sequence i…

I really cannot make it clearer that I'm nitpicking on the statement that it is "sublinear". I'm not disagreeing that it's O(log(n)). I'm also not disagreeing that it's "sublinear with respect to n". I'm disagreeing with it being "sublinear", because there are at least 2 meanings that come to my mind: 1. "it's sublinear with respect to n" - this is true 2. "it's sublinear with respect to size of the input" - this is false

I do not know how else to explain this to you that it is the size of the input that matters when talking about complexity. Example quora answer that recognizes the distinction (discussions about the technicality in the naive isPrime impl that checks numbers from 2 to sqrt(n)): https://qr.ae/pGuORe.

Re: I had to give a wrong answer to get the job (2017)

#283

Post by Siira » Mon, Jul 19, 2021, 10:02 PM UTC

munificent wrote: post #127

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 ap…

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

Re: I had to give a wrong answer to get the job (2017)

#284

Post by munificent » Mon, Jul 19, 2021, 10:03 PM UTC

lmilcin wrote: post #266

dcow wrote: post #259

Earlier quoted context omitted.

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…

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 complex…

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

#285

Post by munificent » Mon, Jul 19, 2021, 10:05 PM UTC

8note wrote: post #156

munificent wrote: post #141

Earlier quoted context omitted.

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.

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

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.

Re: I had to give a wrong answer to get the job (2017)

#286

Post by lmilcin » Mon, Jul 19, 2021, 10:08 PM UTC

munificent wrote: post #284

lmilcin wrote: post #266

Earlier quoted context omitted.

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 complex…

> 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 effec…

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

#287

Post by munificent » Mon, Jul 19, 2021, 10:08 PM UTC

wly_cdgr wrote: post #240

munificent wrote: post #127

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 ap…

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

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.

Re: I had to give a wrong answer to get the job (2017)

#288

Post by munificent » Mon, Jul 19, 2021, 10:09 PM UTC

sudopluto wrote: post #229

asr21 wrote: post #204

Earlier quoted context omitted.

The guy worked at EA for 8 years.. He must know what he is talking about

he also wrote the crafting interpreter book : )

And Game Programming Patterns, which has a chapter on the performance effects of contiguous data:

https://gameprogrammingpatterns.com/data-locality.html

:)

Re: I had to give a wrong answer to get the job (2017)

#289

Post by Buttons840 » Mon, Jul 19, 2021, 10:10 PM UTC

lmilcin wrote: post #281

Buttons840 wrote: post #280

Earlier quoted context omitted.

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…

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…

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)

#290

Post by lmilcin » Mon, Jul 19, 2021, 10:13 PM UTC

Buttons840 wrote: post #289

lmilcin wrote: post #281

Earlier quoted context omitted.

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…

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.