and you're better than the average Google engineer
I wonder how many Google engineers think they're better than the average Google engineer...
I don't know why tech companies persist in asking these kinds of questions. What research I've seen suggests that job performance is best predicted by past experience doing similar work, not by the ability to answer irrelevant trick questions.
edit: Intelligence also matters but in that case you should just give a proper intelligence test. Too bad that's (stupidly) illegal in America.
These are not trick questions. To an engineer with mastery of the skills we are looking for, the problems should be straightforward to solve in a few minutes, using standard-sized inferential leaps.
The first question is legitimate. The second one sure looks like a trick question to me. You've forbidden both loops and any recursion that would use O(n) space if it wasn't tail-call optimized (even though a real compiler would do that optimization), so the solution pretty much has to be a piece of library or language trivia that uses a loop behind the scenes.
You can use recursive calls to implement this with the same asymptotic space requirements as a simple loop, the trick is algorithmic, not in smuggling in a disguised loop (and is really no trick, once you look at what kind of data running recursion can store at what cost). I think it's a great question.
Except that the question explicitly disallows any recursion that would produce an O(n) or even O(log n) stack size, and asks you to assume that the compiler won't perform tail call optimization. I don't think you can do it with O(1) stack depth and no tail calls.
O(log n) stack size is allowed (since normal loop would also take O(log n) just to write down n), but you need to keep each stack frame constant size, not O(log(n)), since otherwise you get O(log^2 n) total space complexity.
Oh, in that case I see the solution (though I won't post a spoiler here). I was assuming that n was a regular Javascript variable, not a bignum or a float large enough to introduce precision issues, so that the normal solution would only use O(1) memory. That part of the question really ought to be clarified; Javascript normally doesn't even support bignums.
Talking about asymptotic performance characteristics only makes sense when the domain of a problem is infinite, so to me it was clear that the problem should be analyzed as if ints are variable size.
For practical problems -- and you are looking to hire practical people -- asymptotic performance is only relevant up to the size of problem that could be encountered in practice. #2 is putting up a sequence of n alerts: n must be small enough to consider as an atom, i.e. it takes unit space and arithmetic takes unit time. 32 bits is plenty, even if a computer is going to run automated tests of the code. 64, if 32 just seems too small for an integer variable these days, but no more.
When you say O(log n) for #2, you're presumably talking about space? Time is trivially O(n).
Talking about space. My point is just that the practical man can send me an O(log n) solution and explain why it's not worse than the iterative solution. Either you say ints are constant space, and then so is the stack size (at O(log 32)), or you say the iterative solution is O(log n) for unbound n.
I had thought the solution was very simple before you pointed this out. With some difficulty I improved my solution to O(log(log(n)) * log(n)), and it took quite a bit more time for me to get completely constant sized stack frames.
I suspect most people initially come up with the O(log^2(n)) solution and jump next to the O(log(n)) solution without getting stuck in the middle there, but I'm curious if this gave you any problems.
The solution is definitely not language/library trivia. In fact I will accept a solution in any language if you don't use iterative constructs and you don't rely on tail call optimization to limit your asymptotic space usage.
Tee-hee. There are many ways to skin these cats. :)
(What puzzles me is why the formulation of the problem fails to ban the absolutely trivial solution that uses neither type of loop. Wondering if that's intentional or a brain fart.)
If you're thinking of writing n lines of code with calls to alert(), it doesn't work because you have to submit a constant-sized program before you see n. Otherwise please email me this trivial solution because I may have overlooked it.
Actually the brainfart was on my part. I'd forgotten that a common instruction doesn't exist in Javascript, though that hasn't kept some folks from implementing one, as a workaround. (The mind boggles.)
You'll need to specify which version of Javascript to target, since some slightly less obvious solutions may involve version-dependent features.
You can use recursive calls to implement this with the same asymptotic space requirements as a simple loop, the trick is algorithmic, not in smuggling in a disguised loop.
My current solution is 12 lines long and uses only recursion and function calls and addition and variable assignments.
Not sure what all being said above, but cant it be done in just a simple way like
I accept, one gets good set of logics from a good and sound education, but i have to say that in field programing a lot of time experience helps to get simple and straight forward solution for your requirements. Optimization can follow on.
Please don't post your want ads on Less Wrong because that will make my RSS feed really noisy.
My startup, Quixey, is looking to hire a couple top-notch software engineers. Quixey is an early-stage stealth startup founded in October 2009. We are launching our beta product this month: An all-platform app directory and "functional search" engine that lets users query for software by answering the question: What do you want to do?
We are confident that Quixey's functional search will be qualitatively better than all existing solutions for finding web apps, mobile phone apps, desktop apps, browser extensions, etc. Our prototype returns significantly more relevant search results in head-to-head comparisons with all the iPhone and Android app search solutions that currently exist(!)
Our office is on University Ave in Palo Alto. If you live in the Bay Area and want to join a hot tech startup extremely early (employee #1, high-equity compensation package), and you're better than the average Google engineer, then please try our screening questions. If you're the kind of person we're looking for, the questions shouldn't take you more than a few minutes each.
Questions
1. Write a Python function findInSorted(arr, x). It’s supposed to return the smallest index of a value x in an array arr which, as a precondition, must be sorted from least to greatest. Or, if arr doesn’t contain an element equal to x, the function returns -1. Make the code as beautiful as possible (without sacrificing asymptotically optimal performance characteristics).
2. Write a JavaScript function countTo(n) that counts from 1 to n and pops up an alert for each number (i.e. alert(1), alert(2), ..., alert(n)). Easy, right? Except you're not allowed to use while- or for-loops. (And you're not allowed to trick the interpreter using "eval", or dynamically generated <script> elements appended to the DOM tree, or anything like that.)
For problem 2, the time and space requirements of your function should be as good as those of the asymptotically optimal algorithm, even without tail call optimization.
Email your answers to liron@quixey.com and I'll get back to you right away. Please don't post your answers in this thread because that will make my filter really noisy. If you do well on the screening questions, we will want to bring you in for an interview.