Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

dewitters.com

Post reply on HN
Print view View original

141–150 of 409 posts

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

#141

Post by munificent »

chaps wrote: post #129
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…

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.

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.

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

#142

Post by tester756 »

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…

Couldnt you show them example on e.g whiteboard how it'd work?

it'd be huge pros that you can explain concepts to people who do not know them in 5mins.

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

#143

Post by bialpio »

Jtsummers wrote: post #122
bialpio wrote: post #119

Earlier quoted context omitted.

Is it really sublinear though? The data that the algorithm accepts is a number n, the size of the data is thus m=log(n), so the algorithm runs in O(m) time -> linear in terms of data size. I vaguely recall there was some nuisance related to this (pseudopolynomial algorithms ring a bell), but haven't interviewed in a while so may be misremembering it.

It is sublinear, n is the nth Fibonacci number, or the size of the series up to the desired value. The standard (non-naive) algorithm is linear with respect to n. The matrix version makes use of fast exponentiation which is log(n), using the same n as before the target Fibonacci number.

log(n) is ok. Sublinear with respect to n is also ok. "Sublinear" on its own is not, at least if my understanding is correct (sublinear relative to what?), although I can see that it can be a common shortcut to make.

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

#144

Post by Izkata »

crispyambulance wrote: post #77
mewpmewp2 wrote: post #36

Earlier quoted context omitted.

Same with some driving exam questions I have had. For example worded something like that, "does driving faster in some sections of the journey affect your planned time of arrival?" I don't remember if the wording was specifically like this, but it was something that to me logically obvious answer is "yes", but the correct answer and what they expect is "no", to show that you are a reasonable driver who won't speed un…

If I remember correctly, that question likely refers to some argument in the driving manual about speeding. Something along the lines of "speeding in most urban areas doesn't actually help get someone to their destination faster. There are always multiple traffic lights and other cars to contend with, so it's not helpful to go over the speed limit and it increases the risk and severity of an accident." It's perfectly…

There's that, but there's also the possibility that it's conflating two things: If you're speeding, you'll also have to go around cars that aren't, which reminds me of this one about weaving between lanes vs sticking to one lane that the Mythbusters tested: https://www.youtube.com/watch?v=ZefgUVg3qx0 (4 minute long cut of segments from the episode).

They found that weaving between lanes is faster, but not by very much depending on which lane you're comparing it to. The final result (shown at 3:54 in the link) was:

* Weaving between lanes: 1h 16m

* Lane 1: 1h 19m

* Lane 2: 1h 20m

* Lane 3: 1h 29m

* Lane 4: 1h 33m

Lanes 1 and 2 are close enough I can imagine it being chance and more tests resulting no noticeable difference. And for an over-an-hour drive, it's already no reasonable difference anyway.

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

#145

Post by oeiiooeieo »

I believe I missed out on a google job because I used uint32_t from stdint.h (rather than unsigned long). The interviewer in this case worked on compilers and didn't like a recent-college-grad schooling him on the dangers of assuming integer type sizes.

I don't regret it. =)

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

#146

Post by chacham15 »

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…

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.

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

#147

Post by silentsea90 »

Not exactly this, but I ran into a similar situation in an Uber SWE interview where I presented 2 solutions for a problem, one after another with the latter being better. However, the Senior SWE interviewer didn't know better and was fixated on the 1st solution and didn't see a problem with it. Always a bit frustrating when this happens and I chose to stick with what was the "right" answer without a fuss.

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

#148

Post by Jtsummers »

bialpio wrote: post #143
Jtsummers wrote: post #122

Earlier quoted context omitted.

It is sublinear, n is the nth Fibonacci number, or the size of the series up to the desired value. The standard (non-naive) algorithm is linear with respect to n. The matrix version makes use of fast exponentiation which is log(n), using the same n as before the target Fibonacci number.

log(n) is ok. Sublinear with respect to n is also ok. "Sublinear" on its own is not, at least if my understanding is correct (sublinear relative to what?), although I can see that it can be a common shortcut to make.

All the necessary information to answer your question is in the original comment. They're talking about computing the nth Fibonacci number and say that the matrix exponentiation version is O(log(n)). Unless you think they're using n to represent two (potentially) different things, there is little room for confusion. "sublinear" refers back to that O(log(n)) algorithm.

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

#149

Post by vladf »

pavpanchekha wrote: post #133
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…

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

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

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

#150

Post by munificent »

chacham15 wrote: post #146
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…

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

I'm fairly certain they were looking for a linked list, but I could be wrong.
Post reply on HN