You have a better shot at these types of interviews coming straight out of college than you do after X years of job experience. The interviewing mindset is very different from the working mindset. If you want to do well, you should study these PDFs for a few weeks (repetition is the mother of learning) before your interviews. I did exactly that before my last round of interviews, and it made a huge difference.
I didn't post them on HN because, honestly, I don't want them to be too publicized. These are the exact questions that you will be asked at these types of interviews. It's borderline cheating.
Agree that the comment was good, what guidelines are you thinking of?
In my interviews I generally started with a naive answer, got the good answer on my own and got to the best answer with some hints from the interviewer. They didn't seem to regard this as a bad thing.
At one point when I started working on the "better answer" straight after a "good answer", the interviewer asked me why. I confessed that it looked to be a similar class of problem to one in the previous interview, and he told me that was excellent.
There were two problems I did badly at. One was a math question (number theory), which I got after a bit of work. The other didn't really get anywhere with. It wasn't included in any of these linked items, either, so I guess I can't say much more about it. It was a fair question though.
While these are good questions, in my experience they're so widely known from books/websites that I'd be amazed if a company like Google was using them for anything other than early screening of candidates.
I was going for an overseas position, which complicated the process, because they had to fly me to another city for a combination of onsite and video interviews.
Obviously they asked other questions, too.
My impression was that they hadn't planned on doing another round of interviews, but the mixed feed back I got confused them (I did very well on at least on question, but totally bombed on another). Who knows, though - the whole interviewing process was a bit of a mess to be honest.
I am curious if there are any employers out there with tips for follow employers about how to screen candidates.
I find that a vital skill is understanding good code design, that is, placing the responsibilities with the correct code, keeping dependencies down to a minimum, proper encapsulation of the complex stuff, separation of concerns, etc.
I recently hired someone who is a decent coder and problem solver, but I regularly have to “correct him” when he starts new submodules because he still doesn’t master the “design” aspect of coding.
That is, he might do some rudimental analysis about how to structure things and what the API should be, but if I don’t stop him, it always ends up being more complex than need be, and I honestly don’t think he knows how he could do it better, because it is really the same things I say to him over and over.
Since I will hire more people down the road and since I am tired of having to point out the same design flaws over and over, I am interested in tips for “testing peoples design skills” and also book recommendations about how to master big software projects without it ending up as tightly coupled components with arcane code — which sadly seems to be how most projects do end up…
Also with some problems there seems to be a conservation of complexity notion. It's inherent in the system and depends on where you push it.
For the book, you might want to check out Large-Scale C++ Software Design. Unfortunately it's at home so I can't crack it open and double check, but it seemed full of suggestions on structuring code and layout a large software project.
Giving it some more thought, I think it boils down to realizing when one is solving more than one problem, and then being able to write the code so that each problem is solved in isolation, yet without introducing complex APIs between the different pieces of code.
Often though the sub-problems are subtle and hard to predict, plus realizing that two problems are being solved is not in itself enough to figure out how to actually split it up (sometimes splitting things up contributes to the perceived complexity)…
Actually I think that advice is misguided, as in my experience when you tell an interviewer you're already familiar with their favorite brainteaser they're just as impressed as if you solved it yourself, and you don't feel dishonest.
Instead of giving a Boyer-Moore style solution (with sub-linear complexity), it gives the naive approach (with quadratic complexity).
It covers time complexity, hash tables, binary search trees, and some other things you might learn in 6.046. However, most of the time is devoted to topics you won't learn in class, such as crafty bitwise logic and tricks to solving problems.
Any definition of polymorphism should at least mention something about the method that is invoked depends on runtime data, and is not resolved (or known) at compile time.
At least in C++ world, it's not true. There things like compile time polymorphism, and run-time polymorphism.
And by the way, why do you think polymorphism should be based on run-time data? simpler things can be achieved at compile time with static analysis, which many OO languages do [C++, and Java for sure].
Just because it's simple to do, you don't have to declassify it from being polymorphic.
I'm not sure that's always true. Or at the very least seems language dependent.
If Class X has two methods:
void foo(Object i);
void foo(Integer i);
then: Object test = new Integer(4);
X x = new X();
x.foo(test);
will invoke 'void foo(Object o);' based on the compile time type of test.Java does do dispatch based on the runtime type of X - but it is quite limiting once you are used to having proper multiple dispatch at your disposal.
(caveat: not in front of a javac - this is from memory).
I think the emphasis on runtime data is a mistake. It would be possible to imagine an static, OO language which has polymorphism implemented using static analysis - perhaps in limited circumstances.
(I agree with your point about their definition also being met by overloading)
Polymorphism is certainly not a very well defined notion. Personally, I think the best answer would be "I don't know a precise definition, I've heard it mean different things based on context, for example...".
Yes
class A { ... f() ... }
class B extends A { ... f() ... }
class C extends A { ... f() ... }
A x = ... // a B object or a C object
x.f()
is polymorphism if anything.That doesn't make the definition incorrect; there are many types of polymorphism.
Function overloading is an example of ad-hoc polymorphism; generics is an example of parametric polymorphism; and inheritance is an example of inclusion polymorphism.
"Note that finding the median of an array is a special case of this where k = n/2."
I'm pretty sure it should be k = (n+1) / 2. (If there are 5 numbers, you want the 3rd one, if there are 6 numbers you want the average of 3 and 4.)
For arrays whose length is even, I think it's also acceptable to take either one of the two values (instead of the mean of the two) as the median value. Wikipedia is fairly ambiguous on this as it only states "one often takes the mean" and "sometimes one takes the average of the two median numbers".
I believe that for a large enough sample size the discrepancy shouldn't even matter all that much.