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

241–250 of 409 posts

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

#241

Post by scottlamb »

superrad wrote: post #165
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's not great to have to double your memory usage while you reallocate your array. On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array. There's also the cost of copying objects especially if you don't know if…

> It's not great to have to double your memory usage while you reallocate your array. On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array.

That doesn't smell right to me, assuming you're talking about userspace applications on newer hardware. aarch64 supports at least 39-bit virtual addresses [1] and x86-64 supports at least 48-bit virtual addresses [2]. Have you actually had allocations fail on these systems due to virtual address space fragmentation?

Certainly this is something to consider when dealing with low-RAM devices with no MMU or on 32-bit, but the former hasn't applied to the device categories you mentioned in probably 20 years, and in 2021 the latter is at least the exception rather than the rule.

[1] https://www.kernel.org/doc/html/v5.8/arm64/memory.html

[2] https://en.wikipedia.org/wiki/X86-64#Virtual_address_space_d...

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

#242

Post by banana_giraffe »

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 insisted this was wrong. I tried to tease out of him if we were talking about what to do if the specs made no sense, or if he wanted me to draw an unusual clock face. Nope. He just insisted I had no idea how clocks work. I spent the interview trying to understand what he was really asking of me as politely as I could while he spent the interview insisting I didn't know how something as basic as a clock works.

To this day I don't know what he really expected out of me. I wasn't surprised when I learned they didn't want to hire me. I doubt I would have wanted to work there after that interview.

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

#243

Post by Jtsummers »

bialpio wrote: post #235
Jtsummers wrote: post #224

Earlier quoted context omitted.

What two things do they use it to mean? There's literally only one thing it refers to in the original comment: The n th Fibonacci number. Show me the second. All additional uses of n in that comment are references to that same thing, the n th Fibonacci number.

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 is being computed. They then say that there is a O(log(n)) algorithm (that is, it grows with the logarithm of the index) that can find the nth Fibonacci number. The n in O(log(n)) is still referring to that same index in the sequence, it has not changed its meaning. I do not know how else to explain this to you. At this point I can only presume that you are confused about the fundamentals of algorithm analysis or you're a troll.

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

#244

Post by gmadsen »

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…

am I the only one concerned that this would even be a point of contention? This seems too trivial for anyone doing hiring or being hired to be hung up on.

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

#245

Post by rcurry »

During an interview for a job with a Wall Street outfit, the interviewer asked me “In C++, how would you determine the concrete type of a pointer to a base class if you did not have runtime type information?”

I couldn’t think of an answer, and then he explains “It’s quite simple - you would use dynamic_cast.”

I needed the job so I just smiled and said “Oh, that’s really cool - I didn’t know about that.”

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

#246

Post by hawk_ »

vecter wrote: post #182
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…

IIUC, this is assuming that memory allocation is O(1)?

yes it's rare to not assume that.

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

#247

Post by steelframe »

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…

The primary thing I like about this approach vs. stopping to copy the entire array on expanding its capacity is cache hotness.

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

#248

Post by wffurr »

asr21 wrote: post #204
munificent wrote: post #192

Earlier quoted context omitted.

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.

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

That means nothing. Time != experience. You have to have actually learned during that time for it to count for anything.

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

#249

Post by nemanjaboric »

dmcginty wrote: post #190

I was in a job interview several years ago and I was given the following prompt: "You have a database containing locations with their corresponding latitudes and longitudes. We want to be able to input an arbitrary latitude and longitude and have the program return all locations within a radius from that point from the database." My initial reaction was to say "I would use a GIS library/API", but the interviewer want…

There's a sizable portion of people believing that spherical coordinates can be directly converted to planar coordinates :-).

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

#250

Post by scottlamb »

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…

> This is dangerous, but if well documented and understood it might be okay.

I agree in principle. I think even something like std::unique_ptr could work; the concern would be self-referential types. Notably Rust doesn't allow those anyway, so I think any Rust type would be fine, not just Copy types.

> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.

Still might be a lot better than a linked list for small types (due to less RAM spent on pointers and better cache locality because it's contiguous). With the exception of intrusive linked lists of stuff that is separately allocated anyway, I really hate linked lists.

Post reply on HN