Liron comments on Quixey - startup applying LW-style rationality - hiring engineers - Less Wrong

27 Post author: Liron 28 September 2011 04:50AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (25)
Tags: jobs quixey applied_rationality

Comments (25)

You are viewing a single comment's thread. Show more comments above.

Comment author: Liron 29 September 2011 12:40:36AM 1 point [-]

It might be. I suggest you go ahead and apply.

Comment author: CronoDAS 29 September 2011 06:28:31AM *  0 points [-]

/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!

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

Comment author: CronoDAS 29 September 2011 07:48:33AM *  0 points [-]

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

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

Powered by Reddit Powered by Reddit