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.
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 valuexin an arrayarrwhich, as a precondition, must be sorted from least to greatest. Or, ifarrdoesn’t contain an element equal tox, 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.