Gaming CS Interviews

Post by orlp » Wed, Sep 28, 2022, 10:23 AM UTC

sfink wrote: post #58

bitbearr wrote: post #39

Earlier quoted context omitted.

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, b…

Post by Zalastax » Wed, Sep 28, 2022, 10:29 AM UTC

parimal7 wrote: post #38

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. ¯\(ツ)/¯

Post by trinovantes » Wed, Sep 28, 2022, 10:40 AM UTC

orlp wrote: post #47

trinovantes wrote: post #45

Earlier quoted context omitted.

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);

Post by sfink » Wed, Sep 28, 2022, 10:42 AM UTC

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…

    def sort(self):
        pass

    def __getitem__(i):
        suit = int(i / 13)
        rank = i % 13
        return f"{rank} of {('diamonds', 'hearts', 'spades', 'clubs')[suit]}"

Post by pizza234 » Wed, Sep 28, 2022, 10:46 AM UTC

fartsucker69 wrote: post #35

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…

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