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

21–30 of 163 posts

Re: Gaming CS Interviews

#21

Post by Twisol »

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…

The fiddly detail here is that big-O notation can be used to measure the usage of any resource, not just time. The poster above noted that an in-place sort might have constant space complexity -- although this only makes sense if you discount the space required for the input anyhow (which is literally linear in the input size!).

Wikipedia distinguishes two measures of space, "total" (including the input) and "auxiliary" (excluding the input). The poster above you is likely referring to auxiliary space.

Re: Gaming CS Interviews

#22

Post by mnsc »

jonathankoren wrote: post #10
HelloNurse wrote: post #5

> Strings are just arrays of characters, so any algorithms you learn for arrays also applies to strings. I.e. don't believe the anti-American propaganda on Unicode.org.

Every squiggle language transliterates to 7 bit ascii without loss of fidelity anyway. ¯\_(ツ)_/¯

Of course, eg.

{lefthandraised}\_({eyes}{slantedmouthkindabelowtheeyes})_/{righthandraised}

Re: Gaming CS Interviews

#23

Post by bodge5000 »

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.

I can tell you now there is no chance Stackoverflow would be as big as it is if the responses you got back where riddles.

Re: Gaming CS Interviews

#24

Post by bootsmann »

>One common subtopic I would recommend having a basic familiarity with is amortized big-O, aka expected big-O, whereby you use some neat probability theory to say that the expected value of an operation is, for instance, O(1) even though sometimes it may be O(n) for individual calls.

Isn't he mixing two terms here?

If I recall correctly amortisation shows up in deterministic algorithms where some steps might frontload work that consecutively makes others easier. For instance you have some graph algorithm that looks at all the neighbours of some node in every iteration which means the runtime theoretically depends of the degree of the node, but if you can guarantee that each edge will only be inspected once your total time complexity only depends on the number of edges.

On the other hand expected time complexity is used when you run a probabilistic algorithm like quicksort, where individual sort calls actually have a variance in time complexity.

Re: Gaming CS Interviews

#25

Post by IshKebab »

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.

Re: Gaming CS Interviews

#26

Post by saagarjha »

bradlys wrote: post #19
hardware2win wrote: post #3

So basic data structures and their Os, trees, proficiency with strings, sorting and recursion? It doesnt feel like something really hard

The issue isn't telling people about basic things like you learn in a CS major - it's about taking random problems and solving them on a whiteboard without any errors (syntactically or otherwise) while explaining the solution, alternative solutions, and figuring out any gotchas that they love to throw in less than 20 minutes. An easier one would be something like this - https://leetcode.com/problems/combination-sum-i…

I've seen some very bad interviewers that will fault you for non-perfect solutions, but most will have some sort of reasonable leeway in what they will take as a solution.

Re: Gaming CS Interviews

#27

Post by moooo99 »

bradlys wrote: post #19
hardware2win wrote: post #3

So basic data structures and their Os, trees, proficiency with strings, sorting and recursion? It doesnt feel like something really hard

The issue isn't telling people about basic things like you learn in a CS major - it's about taking random problems and solving them on a whiteboard without any errors (syntactically or otherwise) while explaining the solution, alternative solutions, and figuring out any gotchas that they love to throw in less than 20 minutes. An easier one would be something like this - https://leetcode.com/problems/combination-sum-i…

I’ve been solving leetcode questions for a few months now. Primarily for fun because coding interviews aren’t really a thing in my country (salaries comparable to the US aren’t either).

It is a really interesting exercise and as you mentioned, there is a world of difference between knowing the basics and actually being able to solve those kind of problems on an interview level. It’s not uncommon for me to check the first test cases, submit my solution and then be screwed by the one edge case I did not think about.

Doing all of this in a 20 minute interview seems insane to me. I occasionally check out commonly asked FAANG questions on Leetcode and how people actually solve these kinds of problems in such a short time while communicating with an interviewer is beyond me.

Re: Gaming CS Interviews

#28

Post by felixr »

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…

Sorry, wasn't clear. Was talking about the space complexity. If you sort in-place you don't need O(n) space, you can do with O(1 ). Not talking about time complexity

Re: Gaming CS Interviews

#29

Post by saagarjha »

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

Re: Gaming CS Interviews

#30

Post by falcor84 »

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

I agree in principle, but also see how the interviewer might have felt that there's a good opportunity there to assess your reasoning skills about that thing. I actually like it when an interview takes some small detours.
Post reply on HN