So he describes a problem hes actually working through when he was "interrupted" to come interview me. He was trying to terminate an SSL connection, modify the stream (for video manipulation) and send it along to the client. I explained public key and how what he wanted to do was called a MitM attack and how he couldn't continue on the stream without the private key of the server. We had a real conversation with me explaining (to a very smart guy) so he could completely understand everything he "needed" to know to solve the problem he was working on.
I got the job. It was the only interview I've had where I really felt they were asking me something relevant to the work and the kind of work I would be required to do. I ended up having to write Symbian OS code, which I had no prior experience in.
TBH most of the comments so far are the interview questions I hate as they have no relevance to anything I care about or will ever be asked to do.
This is the interview method espoused in Reinventing the Interview:
I was lucky to stumble on this when I was young and it has been very useful in thinking about both being interviewed and interviewing.
Not a good thing, but thats how it is some places.
What has been your biggest screw up to cause a production outage and what did you take from that?
If they say they never caused an outage or give some answer that isn't a screw up, I know one of two things
1) They arent senior level to be put in charge of handling major changes on production
2) They are the type of person that tries to hide screw ups from the rest of the team.
The big thing I'm looking for is mistakes are good learning experiences for people and if you make a mistake its time to reflect on the mistake to make sure it never happens again.
So I want to hear how they made sure that mistake or anything like it won't happen again.
The trick is to sample random nodes from the remote graph. If you get back a node that has the same hash as a node in your graph, you know that local and remote have all the same ancestors of the node too. Otherwise, you know that local doesn't have any of the children (on remote) of that node.
Turns out that is basically what mercurial does .
This is the sort of open, large architectural question that I love and think really helps to understand a developer's skill set. It's great to be able to start very broad, but focus down into detail like CPU caching and the possible on-disk layout.
To answer your question - none.
But being too academic is actually good. The academic questions are constants irrespective of the domain in which the coding is done.
Or any variation on "here's a real problem we are actually having. Do you have any ideas about how one might go about solving it?"
and bonus worst question:
"do you have kids/what does your family life look like?"
But hey you know what, actually, fuck these requirements, they're pretty bad.
This is a stupid and wrong solution and the actual correct way to do it (which is guaranteed to work) is to sort the list in-place (or into a copy, if you need the original), then iterate through from the beginning, making sure it starts with one, that every value is in there, and that it is missing one and only one number. On the second missing number or if after sorting it does not start with 1, or if any value is not an integer, or if any value is repeated, then say that the array does not meet the promises, and you can even error with the exact way in which it fails. This is much better and in-place sort is pretty fast. Quicksort, which I will use, requires pointers and is not actually constant space (despite being an in-space sort) but because it's better and we should use it.
So, with all due respect, fuck the requirements, that is going to be our solution. I realize it misses both your linear time and constant space requirements, but I really feel these requirements are stupid and lead to a brittle solution - this solution is better and is the one I stand by. Sorry. :)"
How'd I do? Would I get the job? (Probably NOT.)
But if I'm looking for a senior position, you're probably in. Senior people do push back on bad requirements, and they know when to do so, and why. If I want experience and leadership, what you did is exactly what I'm looking for.
The difference is that the senior person is going to do it when they know that the spec is a bad idea (and know why it's a bad idea), and the junior person is going to do it all the time because they're a show-off know-it-all and a hothead...
that was my first answer. the interviewer pointed out that even if n fit within an int, there was no guarantee that n^2 would. my immediate second thought was to multiply every even number by -1, but i realised that you could always provide an input that would make that overflow too.
Here, I coded this for you - http://codepad.org/kdqoLXFA (scroll down for the output! it's not just a pastebin but runs it for you). As you can see my code contains tests at the end to show it's working, but not a robust testing class because it's a brittle piece of shit. I don't even want to know what it would do with input that doesn't meet its promises.
I also Googled this and an alternative (that admittedly I did not think of) given such tight restraints is to keep a running bitwise xor of your elements, and also bitwise xor'ing in (1..n) similar to the above - then you don't need to do it from a head and a tail, at the end rather than a difference you just end up with the missing number. This is probably superior to what I just coded.
But both algorithms are really stupid and really brittle. Sorting is fast and there is no reason not to do it that way.
i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)
With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong.
What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice.
btw thanks for the feedback on the sum thing :)
"What's the best you can do within ..." adds an extra challenge - in particular I don't think I'd often see the constant space solution as perhaps one in logspace.
"If you were to start on Monday, what do you feel most confident about, and where will you need help?"
Write an interpreter for first order logic.
Define an algorithm for reordering the x87 floating point stack.
I talked with one hiring lady 30 minutes about movies and surfing.
The technical questions are usually superfluous if you have a proper resume and published work online. Nobody needs that crap.
I know you've met with the senior leadership team. What questions do you have for me?
It's a brilliant question, both disarming and straight to the point. He's looking for how I think. Can this guy solve my problems?
Contracting job, but still... That was the first "question" I got from the company. I was expecting at least to talk about my past experience, and maybe do some irrelevant CS riddles...
(I haven't been asked this)
push(1) : 
push(2) : [1,1]
push(3) : [1,1,1]
push(3) : [1,1,1,0]
pop() : 3, [1,1,1]
pop() : 3, [1,1]
pop() : 2, 
pop() : 1 
Anyways I had failed to give proper answer and I was rejected in the interview. This was the last question of my last round!
Spoiler: Here is one such solution using a simple but very clever trick: http://www.geeksforgeeks.org/design-a-stack-that-supports-ge...
Is that it?