Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gaming CS Interviews

transitivebullsh.it

Post reply on HN
Print view View original

51–60 of 163 posts

Re: Gaming CS Interviews

#51

Post by Eleison23 »

The first time I encountered a "riddle" type interview question, I'd already held 5+ jobs and I nominally had 8 years' experience in IT.

The job was for a Unix sysadmin job in academia. The interviewer described a room with two lightbulbs in it, and a room down the hall with two switches, and I was supposed to figure out which switch controlled which bulb without going back-and-forth so much.

I was stumped & didn't really know how to proceed, so I just gave up. They hired me anyway. Afterward they explained the answer to me. Start with both bulbs dark; turn on one switch, wait a few minutes, then turn on the other and touch the bulbs. The hot bulb corresponds to the first switch. (This only makes sense in the age of incandescent bulbs.)

I thought it was nice and a clever touch to see whether a candidate can think outside the box, and of course I was grateful to be hired even though I couldn't do so.

Oftentimes I'll report for an interview and it's more like a preliminary onboarding and tour of the premises. Sometimes a company has already made that hire decision before they call you in-person. This might raise a red flag for you, if a company is so desparate to put you at a desk that they don't even make you run the gauntlet, so think about it.

Re: Gaming CS Interviews

#52

Post by aliceryhl »

ctrlmeta wrote: post #34
sfink wrote: post #31

The conflation of "amortized" with "expected" feels a bit off to me. Amortized O(f) strongly suggests that the sum of n operations is very very close to O(n×f). I wouldn't say hashmap insertion is amortized O(1), because if you craft input that always incurs a hash collision, then n insertions is much worse than O(n). I would say that it's expected O(1), meaning that with high probability an insertion takes constant…

> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations. Pardon my ignorance but I don't see the difference between these two sentences. Expected time of a single operation = Sum of time taken for all possible input cases / Number of cases (assuming each input case is equally likely to occur). Is it not? Isn't it then the same as amortized time?

They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness).

Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time.

Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1).

So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).

Re: Gaming CS Interviews

#53

Post by thallium205 »

Eleison23 wrote: post #51

The first time I encountered a "riddle" type interview question, I'd already held 5+ jobs and I nominally had 8 years' experience in IT. The job was for a Unix sysadmin job in academia. The interviewer described a room with two lightbulbs in it, and a room down the hall with two switches, and I was supposed to figure out which switch controlled which bulb without going back-and-forth so much. I was stumped & didn't r…

Bulbs nowadays are LED and don't get warm.

Re: Gaming CS Interviews

#54

Post by aliceryhl »

unwind wrote: post #15
felixr wrote: post #8

> a sorting algorithm may take O(n log(n)) runtime which is pretty common but be able to operate on an array in-place, only requiring O(n) storage. If it's in-place the sorting might only require constant space and it can be O(1 ) [edit: in terms of space complexity]

Did you mean O(n)? It seems hard to sort n items without at least touching all of them once, which would make the time complexity linear (O(n)) instead of constant (O(1)). Or are you talking about storage needs? Then it sounds very hard to go sub-linear ... I'm confused. I'm certainly not a good theoretical computer scientist, but I did quickly google this and I couldn't find any trace of constant-time sorting (unles…

They mean the amount of storage, and they're only counting additional memory allocated by the algorithm, and not the memory containing the input.

Re: Gaming CS Interviews

#55

Post by ThePadawan »

Jensson wrote: post #9
Planktonne wrote: post #7

If you're using an interview that bares 'little relevance to an employee’s day-to-day work' and that requires dedicated prep to pass, then what you're doing is optimising a process for finding people who will tick boxes and jump through meaningless hoops. That's fine - some jobs do require that - but it does mean that any 'best and brightest' rhetoric should be shelved. Everyone knows that tech hiring is broken, but…

> If you're using an interview that bares 'little relevance to an employee’s day-to-day work' and that requires dedicated prep to pass, then what you're doing is optimising a process for finding people who will tick boxes and jump through meaningless hoops. You mean all those jobs requiring college degrees? Or is that different somehow? The main reason is that difficult tests has positive signal even if they are part…

YMMV but in college I learned lots about

- having to work together with assholes towards a common goal

- how sometimes you can cram for a deadline, but sometimes you can't

- how, often, how well you do is just politics and networking

Obviously fuck everything I learned about however pushdown automata worked. That's not relevant to my career now. All the above still is.

Re: Gaming CS Interviews

#56

Post by orlp »

thallium205 wrote: post #53
Eleison23 wrote: post #51

The first time I encountered a "riddle" type interview question, I'd already held 5+ jobs and I nominally had 8 years' experience in IT. The job was for a Unix sysadmin job in academia. The interviewer described a room with two lightbulbs in it, and a room down the hall with two switches, and I was supposed to figure out which switch controlled which bulb without going back-and-forth so much. I was stumped & didn't r…

Bulbs nowadays are LED and don't get warm.

Nowadays everyone and their mother has a smartphone on them. Place down your smartphone and start recording. Move to the switches and flip them as needed. Check back the recording to provide your answer.

Re: Gaming CS Interviews

#57

Post by sarchertech »

leetrout wrote: post #2

> Guidance is expected; a great interview should be more of a conversation than a one-sided question and one-sided answer. I had a particularly awful interview at Google where the interviewer scoffed at me needing assistance. And in an interview at Twitter with a xoogler they asked me what I knew about number theory and I said "nothing" and they said they majored in it and proceeded to ask me number theory questions.…

The fact that the twitter interviewer introduced themselves as a xoogler is absurd.

Re: Gaming CS Interviews

#58

Post by sfink »

bitbearr wrote: post #39
saagarjha wrote: post #29

> Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?) > The “aha” moment here comes if you realize that by sorting the input, you can just walk along the array with all duplicates being next to each other, resulting in an efficient solution. You could also stick all the numbers in a set, since it seems like order doesn't matter…

Yeah, which improves the time complexity too. Plus many languages offer easy list to set conversion

It doesn't change the time complexity. Both are O(n). Your point about convenience stands, though.

Actually, if you go into fully pedantic mode, the set version is worse. Hash-based set insertion is commonly taken to be O(1), but that depends on hash comparison being O(1), which depends on using single-word hash values, which means your n is bounded by eg 2^63 (50% occupancy) or whatever. Honestly fine in practice, but hash lookup isn't "as" O(1) as indexing into an array. (ie, it requires a less realistic cost model.)

You also need your keys' length to be bounded by a constant. Otherwise just hashing everything will exceed O(n).

Re: Gaming CS Interviews

#59

Post by delta_p_delta_x »

leetrout wrote: post #2

> Guidance is expected; a great interview should be more of a conversation than a one-sided question and one-sided answer. I had a particularly awful interview at Google where the interviewer scoffed at me needing assistance. And in an interview at Twitter with a xoogler they asked me what I knew about number theory and I said "nothing" and they said they majored in it and proceeded to ask me number theory questions.…

Oh, this is hilarious. Well done for the 'Autobots roll out'! :D

Re: Gaming CS Interviews

#60

Post by sarchertech »

ThePadawan wrote: post #55
Jensson wrote: post #9

Earlier quoted context omitted.

> If you're using an interview that bares 'little relevance to an employee’s day-to-day work' and that requires dedicated prep to pass, then what you're doing is optimising a process for finding people who will tick boxes and jump through meaningless hoops. You mean all those jobs requiring college degrees? Or is that different somehow? The main reason is that difficult tests has positive signal even if they are part…

YMMV but in college I learned lots about - having to work together with assholes towards a common goal - how sometimes you can cram for a deadline, but sometimes you can't - how, often, how well you do is just politics and networking Obviously fuck everything I learned about however pushdown automata worked. That's not relevant to my career now. All the above still is.

The automata class I took years ago has been one of the more relevant to my career.
Post reply on HN