# Quixey interview questions

http://www.quixey.com
Quixey is a start-up that tries to optimize application search.
A twenty something year old kid introduced himself as Quixey’s CTO.
The CTO was a typical smart senior-year college kid who had a good idea and received a huge investment to implement it.
There is no doubt the CTO is a smart guy but there is also little doubt that his way of thinking is extremely inflexible and that he thinks that he is the smartest person on the planet Earth.
Nevertheless, Quixey has a hard problem to solve and it looks like they are doing a good job.
And here in the valley, you either have your own company or you sell your skills to freaks.
Here are the questions:
1)      Calculate the sum: 1 + 2 + 4 + 8 + 16 + … + 1024
Unless you are lucky, and remember the formula for the series from the high-school, you have to find a quick way to calculate the sum.
1,2,4,8 .. How do they look in binary?
00000000001
00000000010
00000000100
00000001000
And if add them all up, we get eleven ones:
11111111111
And 11111111111 = 100000000000 -1
And 100000000000 = 2048
And the closed formula is: 2^(n+1) – 1
2)      You are given a list that contains another list, an array of strings, or a string as its values. Write a function to print out all the strings in the list.
That is a fairly simple question; just do not try to do it in C++ (like I did).
The trick here is that we have to use recursion for if one of the values is a list.
i.e. sum += func(list);
3)      Write a JavaScript function countTo(n) that counts from 1 to n and call console.log for each number. Your function has to cleverly work around this ridiculous constraint: You’re not allowed to use JavaScript’s iterative control structures, for and while. (And you’re not allowed to make the interpreter execute those control structures using tricks like eval, or dynamically generated elements appended to the DOM tree.)
function countTo(n) {
if (n > 0) {
countTo(n-1);
console.log(n);
}
}
There is also a much trickier way to achieve that; for instance, using function pointer or template specialization in C++.
4)      A client connects to a server which will stream it N 32-bit integers and then disconnect, where N is a-priori unknown to the client. Describe an O(log N)-space algorithm you could run on the client that would return any of the N integers with probability 1/N. (The algorithm only gets run once.)
#include <iostream>
#include <ctime>
using namespace std;
//
// Generate a random integer [1,...,n] with probability 1/n
int urand(int n)
{
if (n > 0)
{
int rnd = (int) ((rand() / double(RAND_MAX)) * n) +1;
return (rnd > n) ? n : rnd;
}
return 0;
}
//
// Reset the random number generator with the system clock.
void seed()
{
srand((unsigned int) time(NULL));