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

41–50 of 163 posts

Re: Gaming CS Interviews

#41

Post by NalNezumi »

_the_inflator wrote: post #32
atoav wrote: post #20

Earlier quoted context omitted.

In such situations I tend to ask that question directly: "It was my understanding that you looking for someone who will help you with Django tooling. I can do that. Although number theory sounds interesting, I never felt the need of diving into it in order to solve any Django-related issue. I would be happy to learn more about how you think number theory relates to Django tooling should I start working here." When pe…

Great answer. Connect with the current position. I would add here, that you may ask in a polite way, how number theory relates to the position at hand, here Django. This way, the interviewer has to open up specifically. There might be something, that could be important and interesting or simply a bluff.

Not exactly the same situation, but from a snarky interviewer I've gotten the answer equivalent to

"lol I was told you were the Django expert? According to your resume? Are you not supposed to know that?"

Still it does tell you that you have to work with this massive asshole, so it's a worthwhile approach to get more info about the workplace you'll be in.

Re: Gaming CS Interviews

#42

Post by [deleted] »

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…

[deleted]

Re: Gaming CS Interviews

#43

Post by vient »

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?

A difference is in the number of times you use some operation.

For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least).

On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value.

You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.

Re: Gaming CS Interviews

#44

Post by mlatu »

NalNezumi wrote: post #41
_the_inflator wrote: post #32

Earlier quoted context omitted.

Great answer. Connect with the current position. I would add here, that you may ask in a polite way, how number theory relates to the position at hand, here Django. This way, the interviewer has to open up specifically. There might be something, that could be important and interesting or simply a bluff.

Not exactly the same situation, but from a snarky interviewer I've gotten the answer equivalent to "lol I was told you were the Django expert? According to your resume? Are you not supposed to know that?" Still it does tell you that you have to work with this massive asshole, so it's a worthwhile approach to get more info about the workplace you'll be in.

> get more info about the workplace you'll be in.

or about the bullet you just dodged...

if someone connected django with number theory in their head and assumed everyone else can see the connection just as spontaneously, i'd much rather leave than try to handle that arse.

Re: Gaming CS Interviews

#45

Post by trinovantes »

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

Does it? Set insertion is O(log n) and you need to insert n items.

Re: Gaming CS Interviews

#46

Post by AlchemistCamp »

bodge5000 wrote: post #23
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.…

I remember being told once in an interview "I'll be your google, your stackoverflow, so anything you'd usually search for on there ask me". Eventually I got to the point where I forgot how to do something simple where you'd usually just google it to refresh your memory. I decided to take his advice seriously and asked him, to which he responded to me basically by rephrasing my question as another question back to me.…

A more realistic answer would have been, "[duplicate] Closed 4 seconds ago."

Re: Gaming CS Interviews

#47

Post by orlp »

trinovantes wrote: post #45
bitbearr wrote: post #39

Earlier quoted context omitted.

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

Does it? Set insertion is O(log n) and you need to insert n items.

Not if you use a hash set. This is expected O(n) time to de-duplicate an array of integers while maintaining the original order (more explicitly written than I normally would in Rust for didactical purposes):

    let mut hash_set = HashSet::new();
    let mut len = 0;

    for i in 0..arr.len() {
        if !hash_set.contains(&arr[i]) {
            hash_set.insert(arr[i]);
            arr[len] = arr[i];
            len += 1;
        }
    }

    arr.truncate(len);

Re: Gaming CS Interviews

#48

Post by ctrlmeta »

vient wrote: post #43
ctrlmeta wrote: post #34

Earlier quoted context omitted.

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

A difference is in the number of times you use some operation. For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least). On the other hand, an individual arr…

Ah! Finally it clicked! Thanks for the nice example in your comment.

Re: Gaming CS Interviews

#49

Post by sfink »

orlp wrote: post #40
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…

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++: template struct ConstantTimeVector { T* buf; T* next_buf; size_t len; size_t cap; void p…

Hah! That's awesome.

I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble.

And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.

Re: Gaming CS Interviews

#50

Post by orlp »

sfink wrote: post #49
orlp wrote: post #40

Earlier quoted context omitted.

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++: template struct ConstantTimeVector { T* buf; T* next_buf; size_t len; size_t cap; void p…

Hah! That's awesome. I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble. And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the l…

It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf.

This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust.

If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.

Post reply on HN