I suspect I’m not qualified. I don’t know Python (the only languages I’d consider myself competent in are C++ and Perl) and am basically at the “fresh out of college” level of competency at programming.
On the other hand… I think I can solve those screening questions!
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.)
I think you can do this in O(1) space, actually. Would it be inappropriate to post a solution here?
Edit: Actually, I guess my solution does technically use O(log(n)) space, because it takes O(log(n)) space to store an unsigned integer that can grow arbitrarily large...
Write a (stateless) function nextPermutation that takes a permutation (as a list) on the elements of the set {1, …, n} and returns the “next” permutation, so that chaining n! calls to nextPermutation([1, …, n]) results in the generation of every permutation on the set {1, …, n}.
I’m not sure I understand the question properly. Is the list you’re given as input literally a permutation of the first N integers, or is it an arbitrary list of N things? If you’re not allowed to “look at” the N items in the list and have to use an implementation that always performs the same transformation of the input, this is impossible. If N equals 3, there are six possible output cycles you can produce...
none of which include all 3! permutations of {a,b,c}. So you have to “cheat”… which should be possible, because everything is stored as just bits (integers) anyway...
I live in New Jersey. Would it be worth moving across the country to work there?
It might be. I suggest you go ahead and apply.
/me looks up the job description on the website
I suspect I’m not qualified. I don’t know Python (the only languages I’d consider myself competent in are C++ and Perl) and am basically at the “fresh out of college” level of competency at programming.
On the other hand… I think I can solve those screening questions!
I think you can do this in O(1) space, actually. Would it be inappropriate to post a solution here?
Edit: Actually, I guess my solution does technically use O(log(n)) space, because it takes O(log(n)) space to store an unsigned integer that can grow arbitrarily large...
I’m not sure I understand the question properly. Is the list you’re given as input literally a permutation of the first N integers, or is it an arbitrary list of N things? If you’re not allowed to “look at” the N items in the list and have to use an implementation that always performs the same transformation of the input, this is impossible. If N equals 3, there are six possible output cycles you can produce...
{a,b,c} → {a,b,c} {a,b,c} → {a,c,b} → {a,b,c} {a,b,c} → {b,a,c} → {a,b,c} {a,b,c} → {b,c,a} → {c,a,b} → {a,b,c} {a,b,c} → {c,a,b} → {b,c,a} → {a,b,c} {a,b,c} → {c,b,a} → {a,b,c}
none of which include all 3! permutations of {a,b,c}. So you have to “cheat”… which should be possible, because everything is stored as just bits (integers) anyway...