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

261–270 of 409 posts

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

#261

Post by dcomp »

catillac wrote: post #255
banana_giraffe wrote: post #242

I was once asked to write a function that, given the time, draw an analog clock. Given the nature of the position I was applying for, this wasn't an unreasonable question. I wrote something on a whiteboard. What followed was the most surreal discussion I've had in an interview. My function took into account the seconds, minutes and hour for the hour hand, and so on. Just like a normal clock would. The interviewer ins…

Haha amazingly there’s a chance I interviewed you, or you interviewed with my company when we were first rolling this out, or another company was also using the same question. I remember the idea was to make the analog like one of those analogs that didn’t move continuously but ticked at every sixty second interval. So it never needed to be in between minute ticks. Lots of us didn’t fully understand the question when…

For the record. Most analog clocks have smooth motion for minute and hour (for the precision of the gearing). Its the second hand that ticks.

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

#263

Post by btilly »

gopalv wrote: post #196
munificent wrote: post #150

Earlier quoted context omitted.

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

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

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.

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

#264

Post by [deleted] »

pierrebai wrote: post #202
pavpanchekha wrote: post #133

Earlier quoted context omitted.

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…

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

[deleted]

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

#265

Post by jollybean »

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…

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.

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

#266

Post by lmilcin »

dcow wrote: post #259
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 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 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)

#267

Post by loudlambda »

I strongly suspect that Google didn't extend me an offer because one of my interviewers was insistent that a race condition could only be a bug and could not be used strategically, but with a electrical engineering background I could not let that slide. Unfortunately it didn't occur to me during the interview to pull up Wikipedia. I'd prefer not to work somewhere which requires dishonest agreement, so it's been for the best.

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

#268

Post by jimmaswell »

tyingq wrote: post #21

This isn't a great example to me. I doubt the interviewers would disagree that the actual code in MVC runs at the "application tier". I think they were just trying to elicit the idea that the model defines interaction with the database and that the view defines interaction with the browser client. That there is some relation there between MVC and 3-tier architecture. The Wikipedia snippet that disputes any relationsh…

MVC always seemed totally arbitrary and impractical to me.

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

#269

Post by fulafel »

dcow wrote: post #259
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 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…

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)

#270

Post by [deleted] »

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…

[deleted]
Post reply on HN