39 ms·

I'm not sure I've ever interviewed anybody who can't program at all, but a large number of people I interview are shockingly bad. My go-to question to detect t

by yoklov 12y ago

I'm not sure I've ever interviewed anybody who can't program at all, but a large number of people I interview are shockingly bad. My go-to question to detect this is to remove the odd numbers from a dynamic array of integers in-place, in their language of choice. The ideal candidate writes an O(n) function, a less ideal (but still good) candidate writes an O(n^2) function, and if they're struggling I say that they can return copy of the array with the odds removed (this is worse, but they could easily make up for it later). Not only can most candidates not do any of these, but most don't even know how to tell if a number is odd. I had one suggest that maybe he needed a loop (I don't know what he was planning, because immediately I told him he didn't need a loop to know if a number is odd). This is for a game programming position, and most of these are people who have (or claim to have) programmed games. Every game has a loop like this somewhere. Most have many! I feel like all I do is iterate over arrays and remove things from them, and yet, this is one of those questions that over 95% of people don't get. It boggles my mind.

poikniok 12y ago
How is making a returning a new dynamic array worse than doing a O(n^2) implementation? The former would be perfectly fine in production, the slight increase in memory use is negligible, the n^2 solution would lead to me wanting to fire said person. Edit: In addition if the O(n) in place solution that I am thinking of is the same as what you are thinking of, the downside is that the remaining even elements do not remain in the same order. So overall it is hard to imagine ever wanting to use this solution over the standard create new array with just the even elements.
- Klockan 12y ago
  You can easily make an O(n) solution without reordering them by using two pointers; one to read numbers and the other to keep track of where to put the next even number.
- yoklov 12y ago
  > How is making a returning a new dynamic array worse than doing a O(n^2) implementation Avoiding unnecessary allocations can easily mean the difference between missing a frame and not. Keep in mind that we frequently have to deal with bad mallocs and OSes/hardware without virtual memory capabilities. The main reason I'd prefer O(n^2) vs O(n)+allocation is that I asked for an in-place solution, and there are definitely situations where you'd need to be able to do this (because of pointers to the array base, or because the caller doesn't have access to the allocator to release it, or you're using an arena and then allocating a new array means wasting the memory of the old one...). Another reason that's a bit more subtle is that the O(n^2) is that it's much more likely to show up when profiling, unlike the allocation which will likely just make everything else slightly slower due to fragmentation.

by yoklov 12y ago

poikniok 12y ago

How is making a returning a new dynamic array worse than doing a O(n^2) implementation? The former would be perfectly fine in production, the slight increase in memory use is negligible, the n^2 solution would lead to me wanting to fire said person. Edit: In addition if the O(n) in place solution that I am thinking of is the same as what you are thinking of, the downside is that the remaining even elements do not remain in the same order. So overall it is hard to imagine ever wanting to use this solution over the standard create new array with just the even elements.

Klockan 12y ago
You can easily make an O(n) solution without reordering them by using two pointers; one to read numbers and the other to keep track of where to put the next even number.
yoklov 12y ago
> How is making a returning a new dynamic array worse than doing a O(n^2) implementation Avoiding unnecessary allocations can easily mean the difference between missing a frame and not. Keep in mind that we frequently have to deal with bad mallocs and OSes/hardware without virtual memory capabilities. The main reason I'd prefer O(n^2) vs O(n)+allocation is that I asked for an in-place solution, and there are definitely situations where you'd need to be able to do this (because of pointers to the array base, or because the caller doesn't have access to the allocator to release it, or you're using an arena and then allocating a new array means wasting the memory of the old one...). Another reason that's a bit more subtle is that the O(n^2) is that it's much more likely to show up when profiling, unlike the allocation which will likely just make everything else slightly slower due to fragmentation.