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

191–200 of 409 posts

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

#191

Post by planet-and-halo »

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

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

#192

Post by munificent »

gamblor956 wrote: post #184
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…

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.

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

#193

Post by exdsq »

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 really enjoyed your Crafting Interpreters book! Jokes on them for missing out.

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

#195

Post by munificent »

kleiba wrote: post #155
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…

Why didn't you just say "...or, you could use a linked list" when you notice them doubting your first answer?

By that point, they said we should just move on to the next question.

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

#196

Post by gopalv »

munificent wrote: post #150
chacham15 wrote: post #146

Earlier quoted context omitted.

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.

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

Even if I was hired, it wasn't going to work out.

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

#197

Post by 3minus1 »

Who would want to work at a company where you knowingly do things the wrong way due to the fragile egos of your superiors. Debating technical issues is fun and leads to shared knowledge and better outcomes. Part of interviewing is showing off what kind of person you would be to work with. Challenging assumptions and making a good argument should help you in an interview if the place has a good culture.

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

#199

Post by evanmoran »

dilap wrote: post #136
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…

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

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)

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

#200

Post by shadowlight »

I've hit this as well. There are a number of deep technical falsehoods believed by the industry that are very widespread. These falsehoods are so ingrained that pushing against these falsehoods even rationally or logically could land you in hot water. The one that affected me personally has to do with Quaternions.

At the company where I work we convert all of our data to quaternions when transmitting over the wire or for data storage. In the gaming and robotics industry there is a misguided assumption that quaternions are always better, and at my company we force this assumption onto all engineers by using typed protobufs. We can never send EUler angles over the wire, we must always send quaternions.

This is actually fundamentally bad. Like it's not even a design question. It is by logic worse to store things as quaternions. Quaternions are only good for certain transformation calculations. They are not as good for data transmission or storage. So I made a proposal to offer alternatives but I was shot down even by the CEO (who took the time to personally make his own viewpoint known on the entire slack thread out of nowhere) because all of these people buy into the misguided notion that quaternions are always better.

The person I was talking to about this was so hell bent on believing that quaternions are better that if I pressed the point further I could start an all out conflict that could get me fired so I had to stop and pretend (aka lie) to agree.

The fact of the matter is, Quaternions are a higher entropy form of storage for rotation and orientation. You lose information when converting something to a quaternion and this is good for calculation but definitively bad when you choose to use quaternions for data storage or transmission. If you transmit or store things as Euler angles you CAN always convert it to a quaternion. The conversion is trivial and mostly a non-issue.

The problem is that once you have a quaternion you can't go back to Euler Angles without additional assumptions. The back conversion algorithm is not One to One. So by forcing this format as storage you are limiting the future productivity of this data by keeping it in a higher entropy form.

Each quaternion is realized by TWO euler angles within a 360 range of motion across 3 axis-es. When you convert something to a quaternion you cannot go backwards. You cannot find the original euler angle where the quaternion came from because you HAVE two options to choose from.

For gaming this problem is not so apparent because you're in a virtual world and having everything exist in quaternions is ok because rotational orientations don't have to be realized by actual movement or rotations. The computer simply draws the object at the required orientation.

But real world rotations HAVE to be realized by euler angles. You cannot Orient something in reality without actually turning it about an axis. Gimbal lock cannot be erased in the real world and even the Apollo module suffered from this phenomenon despite the fact that the engineers knew about quaternions. People at my company seem to think the issue disappears once you switch everything to quaternions.

Thus for something as simple as having one robot gimbal imitate another... if the communication protocol between them both was exclusively quaternions (with no additional assumptions) the imitating robot can choose an alternative euler angle to project it's motion onto and the two robots WILL not be be in sync. Total information Loss.

So all in all this proposal never went through. I was shut down by stubbornness and over confidence by "robotics experts" who've been brainwashed by false dogma. The people I was proposing this to told me that I should trust the extensive experience their backgrounds of building self driving cars at uber and building robots at CMU. Yeah I respect that but can you not see the literal logic of the issue here? I don't respect people who aren't able to see logic.

The company culture is just part of the story, these falsehoods are likely held industry wide and you'd get these issues everywhere. False Dogma is powerful. Try telling a christian that walking on water is ludicrous when looking at it logically. It's same issue here. Peoples' brains will fight logic if it goes against their beliefs.

Very likely I might even get replies to this post who have so much confidence in quaternions that they'll come up with a retort that doesn't fully understand the problem I illustrated here.

Post reply on HN