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

31–40 of 163 posts

Re: Gaming CS Interviews

#31

Post by sfink »

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 time.

Conversely, "amortized" is only a useful description when it is known that some operations will take much longer than others, yet the total time is bounded. (If you bring up amortized time, you're pretty much implying that the distribution of times is uneven, otherwise you wouldn't have mentioned it.)

For example, if you're doubling the length of an array on overflow, then I would say the amortized time of a push is O(1). It would seem weird to say that the expected time is O(1). If I wanted to be more complete, I'd say "normally a push is constant time, but when the array needs to be expanded then it's O(n). The amortized time is still constant, though."

Expected time refers to a single operation. Amortized time describes the mean time of a series of operations.

Re: Gaming CS Interviews

#32

Post by _the_inflator »

atoav wrote: post #20
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.…

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.

Re: Gaming CS Interviews

#33

Post by felixr »

tempodox wrote: post #16
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]

O(1) would mean same storage requirement regardless of element count.

Yes. Simplest in-place example would be bubble sort. You might need a temp element for swaps, but that's it. Heap sort can also be done with constant space. You need of course O(n) space to store the original data; but that is not part of the sort algorithm.

Re: Gaming CS Interviews

#34

Post by ctrlmeta »

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?

Re: Gaming CS Interviews

#35

Post by fartsucker69 »

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…

>interview prep has nothing on 4 years spent full time

that's just the problem with these interviews. It's kind of obvious that a fresh grad who prepares for 2 weeks for those whiteboard interviews will completely outclass known most productive programmers and engineers in the world (take whatever example you want, I would name someone like John Carmack) who takes the test fresh and unprepared. The modes of thinking and toolboxes required are just entirely different.

That should tell enough about the quality of that style of interview if you are using them for anything other than to weed out people who can't code at all in a phone screen.

Re: Gaming CS Interviews

#36

Post by bboytony »

mckirk wrote: post #6

I was already halfway through the article when I realized I'd misunderstood the title: It's not about about using games to interview people (Factorio style), which still might have made sense to test self-taught engineers, but about how to game the interview process.

I thought this article was about game development interviews.

Re: Gaming CS Interviews

#37

Post by [deleted] »

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…

[deleted]

Re: Gaming CS Interviews

#38

Post by parimal7 »

IshKebab wrote: post #25

Hmm I feel like the best way to "game" these interviews is just to learn solutions to the top 100 leetcode questions and then act as if you're figuring it out on the spot. That's what I started doing in preparation for a Facebook interview but I think that's not actually going to happen in the end anyway due to the hiring freeze and also the ridiculous H1B situation.

Recently gave an interview where they asked me to open my Leetcode profile, and checked if there are any prior submissions to the asked questions. ¯\(ツ)/¯

Re: Gaming CS Interviews

#39

Post by bitbearr »

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

Re: Gaming CS Interviews

#40

Post by orlp »

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 push(T x) {
            if (len == cap) {
                free(buf);
                buf = next_buf;
                cap *= 2;
                next_buf = alloc(cap);
            }
            
            buf[len] = x;
            next_buf[len] = x;
            next_buf[len - cap / 2] = buf[len - cap / 2];
            len += 1;
        }
    }
You can apply a similar trick to hash tables to get expected O(1) time inserts without amortization, by already building the re-hashed table during the building of the previous table.
Post reply on HN