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