How to Crack the Toughest Coding Interviews

Perhaps they're assuming that the cube is a set of integral points and they want you to count lattice paths. This is trivial in 2-space (e.g., give me the number of paths that go from (0,0) to (5,5) by going only up or right one point with each move (that is, each move is either (0,1) or (1,0))). However, I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution. Could be completely wrong on that, though, and don't feel like looking it up just now.

You could of course write a program that would solve it (trivially), but it might take exponential time :)

Of course, the phrasing doesn't say they have to be lattice paths, so perhaps we can say a countably infinite number of paths of we're only considering integral (or rational) points and have no direction invariant. Uncountably many if we're allowing the reals. Still uncountably many if we allow the reals and have a directional invariant. We reach the realm of a finite solution if it's a finite set of points and we have a directional invariant or another constraint (e.g., the path might be prohibited from visiting any given point more than once). Most of these are still completely intractable as far as I know :)

My favorite way of phrasing this question is "how does working here compare to other tech companies you've worked at?".

Here's a list of 100 questions applicants should consider asking a subset of during the interview: http://www.basilv.com/psd/blog/2009/100-interview-questions-...

Just my two cents, Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and the quality of the hashing algorithm they can see real world performance that is not O(1). Inserting into a hash table can cause the hash table to expand, if the hash table is too small you will get collisions, etc. etc. Some choices of hash functions are actual O(n) instead of O(1). Sometimes hash tables are not appropriate due to the memory requirements. You get the idea.

I actually like people to point these things out, even if the amortized cost is constant in lots of real world usage. When talking about time complexity I appreciate attention to detail, rather then just hand waving and saying its constant. My answer is always, 'well it depends'.

Be careful though, back up your answers in a way that shows you do know what you are doing. Otherwise you can come off as blowing smoke.

Truly understanding writing performance critical code is a black art, and you need to understand more then just the big O of some common algorithms. Showing that you know that performance and complexity are hard and you know there are hidden costs that can bite you and tradeoffs you have to take into account shows maturity.

Very true, looking at the types and state of the cars in there car park and haveing a chat with the smoking cabals outside fire exits is often a easier way to get a answear to some degree.

But indirectly asking questions is the way and it is those clever ways that are the types of questions i'm realy interested in, like my question about ISO/BS standards, it opend them up to so much more than a simple yes and no and gives you insight into other area's. Like working conditions, are they documented well, badly, not at all, do they even know about those standards, is it something there looking at (often crops up that last answear on many area's sadly).

Is the pay individual perofmance based or team based and is it limited/capped in that if I do 200% better am I capped at some rate of inflation % rise anyhow. I also like to ask about problems, what was the worst day like this past year and why and how likely is that to happen again. That tells you alot about so many area's and also opens them up into telling you how it is as well as allowing you to highlight your relevant skills and chip in with did you try this or that at the right times, even if you agree and play noddy whilst they talk.

One I always ask is can I have a look around the office, the area were I would be working if I was to be offered a position. That is useful in guaging there interest as if they are not interested they will come up with a reason why they can't do that, if they are keen for that you can see what your dealing with and also get a good feel from the way others have there desks decorated. Be they anal, stuffed south park toys, simpsons posters, collection of 2600 mags. Those type of things, you can get a feel on many levels from that.

Asking them how long they have been there is another good one, longer the better, but if they sound bitter then you can take that as not a good sign as well. Though if there two hyper only been there few months then they are sadly not realy able to give you a a true picture, so again take advantage of there hyper still all new to me as well fun happy time mood and take a look around.