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

221–230 of 409 posts

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

#221

Post by tomxor »

phkahler wrote: post #157
dilap wrote: post #136

Earlier quoted context omitted.

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…

>> In some cases amortized isn't good enough though, and games could certainly be one of them! Real time systems including games have hard limits on how long something can take in the worst case, not the average. In games this manifests as: All the stuff has to be done in 16ms to render a frame on time, if we're late the user will perceive a glitch. The consequences can be worse in control systems in any number of re…

> worst case, not the average

Yup, I can't remember which book but I'm pretty sure I remember reading some stuff from Michael Abrash about how some of the algorithms in quake were changed for worse average performance but better worst case performance. It's fairly intuitive when you think about the context... and that is the critical point - abstract problems are interesting, but it's important to evaluate them in their full context.

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

#223

Post by bialpio »

ball_of_lint wrote: post #153
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.

If you're computing the time complexity this way, then the simple linear dynamic programming is actually quadratic, and the matrix exponentiation algorithm is still faster. Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise. That might be less appropriate for fibonacci than most other problems though.

> Generally I would assume that multiplication and addition are constant time for big-O analysis, until given a reason otherwise.

I think this assumption can still be taken for the exponentiation version - I'm more nitpicking about the fact that there is a simple way to rephrase the problem (see below) to arrive at a different meaning of "linear" vs "sublinear" and it's better to be very explicit in cases where things may be misunderstood.

Rephrasing: fib(x) takes an x which is an array of bits of length m, which are the binary representation of number n. Return nth Fibonacci number.

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

#224

Post by Jtsummers »

bialpio wrote: post #220
Jtsummers wrote: post #148

Earlier quoted context omitted.

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.

They are representing n to mean 2 different things. In this case, n is meant to represent a value passed in to the algorithm. The problem is that complexity is usually expressed relative to size of the input, which in case of this algorithm is log(n) = m bits. This makes the exponentiation version actually linear in terms of bits needed to represent the input. It's like saying that an algorithm that accepts n x n mat…

What two things do they use it to mean? There's literally only one thing it refers to in the original comment: The nth Fibonacci number. Show me the second.

All additional uses of n in that comment are references to that same thing, the nth Fibonacci number.

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

#225

Post by munificent »

pmulard wrote: post #212
munificent wrote: post #140

Earlier quoted context omitted.

I talk about dynamic arrays in Crafting Interpreters: http://craftinginterpreters.com/chunks-of-bytecode.html#a-dy...

Thank you for giving away your book for free. I signed up for the mailing list and hope to purchase a copy when you're releasing printed versions.

You're welcome! I'm getting really close to having the print and ebook editions ready for sale.

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

#227

Post by sdoering »

raptorfactor wrote: post #101
crispyambulance wrote: post #77

Earlier quoted context omitted.

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…

Isn't there some confirmation bias (not sure if that's necessarily the correct term here, but you'll get the gist regardless) here in that you're more likely to remember the situations in which you catch up with the person who passed you (i.e. "look at this idiot getting nowhere"), and less likely to remember the situations in which that person makes a light that you don't and you never see them again? Massively depe…

Years ago the did an experiment in Germany (I know, a one time test with 2 cars/drivers is more or less anecdata).

The task was to drive from Duesseldorf to Munich. Two identical cars, two very experienced drivers. one was told to go as fast as possible without breaking speed limits on the way (we don't have a general speed limit on the German Autobahn (highway)) tthe oother ro drive at a relaxed 120 km/h were possible and also honor speed limits.

Both were equipped with EEG (heart rate and stuff).

The driving distance is slightly above 600km.

The first drive (as fast as possible) arrived first. Waiting for the relaxed driver to come in second. That happened 20 minutes later. So on a trip of > 5 hours the gain was 20 minutes.

But at what cost. The EEG told a story of pure stress, massive heart rate spikes even for an experienced driver like the one behind the wheel. While the other one came in not only at a relaxed speed but a way more relaxed body and mind.

Medical doctors concluded that the EEG of number two was way more healthy.

Btw: One reason why the first car was only 20 minutes quicker was the fact that the driver had to stop to refuel. This cost him minutes. While the second driver arrived with gas to spare. So even economically it made sense to drive a relaxed style. Not to speak of the ecological aspect.

So to wrap up. The fast driver often comes in first. But not as quick as the feel they are. And at a high price.

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

#228

Post by sneak »

thescriptkiddie wrote: post #125
karmakaze wrote: post #82

Earlier quoted context omitted.

The goal of the interview shouldn't always be to get the job. If you have any length of career, you are interviewing the company as much (or more) than they are interviewing you. My approach would have been to go with the new idea and see what discussion can come out of it. If they don't have time to get into it, that's one thing but if they are simply not open-minded to new ideas, I don't want to work there.

In the real world, people have to apply to dozens if not hundreds of jobs just to get an offer. The company has all of the power, so you tell them what they want to hear or you starve.

That's true of unskilled jobs where there are usually more applicants than positions. That's not what's being discussed here.

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

#229

Post by sudopluto »

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

he also wrote the crafting interpreter book : )
Post reply on HN