2 puzzles for you

[serpretetsky]

I'm not sure what you mean by "NOT purely probability based". You calculate probability, it's no more or less probability based than getting the 0.5^100 answer...

I simply meant the problem is not just calculating the probability that 100 prisoners each choose 50 lockers randomly. There is a strategy that is involved that works off a different field of math.

 

[Schmide]

Ehh I just had to find out. So a computed answer is they all die

Spoiler

68.6280%

of the time.

Edit: 1,000,000 cycles came out with

Spoiler

68.802980%

Edit2: Running 10,000 lockers 10,000 times came up with

Spoiler

69.42%

I would assume that the limit as lockers and runs approaches infinity the chance they all die will be

Spoiler

70%

. But looking back at eLiu's answer

Spoiler

1 - ln(2) = 30.6% as N->infinity

this number is actually the

Spoiler

69.4%

Edit3: A 20k 20k run revealed a

Spoiler

68.890000000000001%

.

Edit4: A 40k 300 run revealed a

Spoiler

69.333333333333329%

.

#include <stdlib.h>

#define LOCKERCOUNT 100
#define RUNCOUNT 100000
	int lockers[LOCKERCOUNT];
	for(int i=0;i<LOCKERCOUNT;i++)
		lockers[i]=i;
	int theyAllDieCount=0;
	for(int i=0;i<RUNCOUNT;i++){
		for(int j=0;j<LOCKERCOUNT;j++) {
			int switchLocker=(int)((double)rand() / (RAND_MAX + 1) * (LOCKERCOUNT-1));
			int Temp=lockers[j];
			lockers[j]=lockers[switchLocker];
			lockers[switchLocker]=Temp;
		}
		bool theyAllDieThisRound=false;
		for(int j=0;j<LOCKERCOUNT;j++) {
			int currentLocker=j;
			bool failed=true;
			for(int k=0;k<(LOCKERCOUNT>>1);k++) {
				if(lockers[currentLocker]==j) {
					failed=false;
					break;
				} else {
					currentLocker=lockers[currentLocker];
				}
			}
			if(failed) {
				theyAllDieThisRound=true;
				break;
			}
		}
		if(theyAllDieThisRound)
			theyAllDieCount++;
	}
	double deathPrecentage=(double)(theyAllDieCount*100)/(double)RUNCOUNT;

 

[eLiu]

Should I just post the solution to the 2nd problem? Is anyone even still paying attention? lol

Anyway, this is a tupid question to ask unless you have to write software on statistics. I'm 12 years into software dev. I never needed statistics and i have forgetten everything about it. Seems liek the interviewer is risking finding someone good at math and hrorrible at software dev.

At the risk of sounding like a dick, I'm going to respond to this:
So you have no idea how to solve the problem, but you're willing to claim that:
1) All software dev jobs are the same (you haven't used stats/probability so nobody will)
2) The solution to this problem requires stats/probability (even though you don't know what the solution is)
3) Companies are only asking their candidate this 1 question.
and indirectly,
4) Your 12 years of software dev experience supersede companies like Google, Yelp, Box, Dropbox, Palantir, Facebook, Amazon, etc.

The fallacy in 1) should be obvious. Plenty of software dev & algorithm development tasks require a decent working knowledge of probability & statistics. In fact I would say that ANY developer should know the basics and all of them will have seen this material in an undergrad discrete math class.

As for 2), demonstrating why the optimal solution obtains at best a

Spoiler

30%

success rate requires some math (combinatorics). Other than that, the algorithm behind the optimal solution is totally a CS thing. If you look at the earlier posts (search for SOLUTION: and surrounding posts unless you're still working on it), you'll see that

Spoiler

the key is to exploit the underlying graph structure of this problem. Moreover, LOTS of problems have "hidden" graph structures and graph algorithms are incredibly important.

For 3), dev interviews in Silicon Valley usually involve at least 4-5 1hr sessions with various engineers. Some will try to evaluate your coding capability & style, others will check your ability to come up with well-reasoned OO designs, others hit you with non-trivial (sometimes NP!) algorithm problems, or a combination of these. They want to see that you have the basics down when it comes to actual coding style (that your code is well organized, you obey common conventions, your thought processes are clear, etc) but the really critical component is to figure out if you're good at problem solving. Code monkey-ing can be outsourced. At least for now, a lot of the stuff that requires a brain is being kept local.

4) I didn't personally run into this problem in an interview, but a friend of mine (who talked to the same companies) did. This also wasn't the only problem he was asked in that 1 hr session either. He's now employed & contemplating using this problem as an interviewer. It is worth pointing out that having a candidate find the exact correct solution solo isn't necessarily the only way to succeed. Typically we're guessing most people will spend a lot of time trying to come up with clever things you can do with probability or trying to make additional assumptions and relax them later. That's fine and we hope to see some clever/interesting approaches. But if we hint at a

Spoiler

graph representation

and they still get nowhere, that would be a red flag.

That would mean that people with even numbers in line should take even numbers. Or oddly numbered people should take odd numbers. Or even numbers take the first half of lockers and odd numbered people take the last 50.

I wonder if this concept can be improved by overlapping. (line position)mod 4 = 0 takes 1-50. =1 takes 26-75, =2 takes 51-100, =3 takes 76-100 and 1-25. I don't even want to get into the math. But if this is better odds than the basic strategy, it probably means that each person starting with their place in line as their starting point and doing the first 50 from their would be optimal. But i don't see that as as good solution intuitively.

NEW IDEA
What about time?

And one could even improve upon this by using non linear stepping when choosing lockers. Time could be used as a method of information passing. Using time, one could pass information on about what the content of locker 1,2,3 are when person 1 finds his number in 4. he could wait an extra 26 ms to pass information via time that locker 1 had id=26 in it and that locker 4 had his number in it. Thus solving two lockers for everyone else. using some sort of hashcode, the contents of 1,2 and 3 could also be passed on via time based messaging.

In an interview, they don't want to see a solution. But they want to see a thought process. Of course, this says little about team work ability though since we collectively are figuring this one out and my ideas are not all from my own intellectual musings.

These are all interesting ideas when trying to approach the problem from a purely probabilistic standpoint. It's also kinda interesting to think about how much information prisoners have to be able to pass in order to raise the probability of success to 50%. It breaks the game a bit though b/c if prisoner 1 succeeds & reports back a few lockers, the owners might be able to waste their trials to gain more information depending on prisoner order. Still I'm not sure that you can guarantee 50% success without passing info about all 50 lockers opened (assuming random prisoner order).

That said, you can't use time. Information passing is illegal regardless of whether it is direct or indirect. Also, using time doesn't scale well to larger N. If N = 100000000 or something, the size of the hash would be enormous.

The optimal strategy works if the prisoners are chosen in a random, unknown order... and each time a prisoner is picked, he can open a random number of lockers (btwn 1 & 50), until he succeeds or dies (goes back in line otherwise). Everything is *completely* independent.

Spoiler

Because each locker's content points to the next locker, you can build a one way imaginary chain whose link points to the next. If you're the prisoner, you won't know the contents of the chain but the only thing you know is your prisoner number. If every prisoner started out by opening a locker corresponding with their prisoner #, then they can greatly increase the chances and here's why.

If prisoner #1 starts at locker 1 and succeeds, prisoner #2's search space is now half of all possible combinations, otherwise prisoner #2 would not be alive.

Continuing onward, prisoner #3 opens locker #3 and so forth...

If you think of the search space as a binary tree, prisoner #1 visits the first left node. Prisoner #2's search space starts at the first left node for reasons described above (the whole right branch of the tree is irrelevant for prisoner #2).

Spoiler

This is the correct solution but I'm pretty sure your intuition is incorrect. But at the same time I don't understand the structure of the binary tree you're envisioning. Since prisoners 1 & 2 (and in fact, everyone) have no idea when the others have succeeded/failed, the success/failure of each prisoner does not inform the others about the search space.

That's what's so elegant about the optimal solution. It decorrelates the success of all the prisoners and in this way, makes the end result independent of N (instead of going to 0 as N->infinity). That is, if there are N lockers and prisoners are allowed to open N/2 lockers, there can be anywhere from 1 to N prisoners (inclusive) and the probability of success remains essentially the same.

Check out the earlier spoilers (search for SOLUTION: and posts around it) to see an explanation of how you compute the probability of success as well as my own intuition for why it's good.

Ehh I just had to find out. So a computed answer is they all die

Spoiler

68.6280%

of the time.
...SNIP...

Cool, thanks for implementing that! Yeah the convergence will be VERY slow and the 1-ln(2) result is a strict upper bound (for sufficiently large values of N). The harmonic series shows up in the analysis; it grows logarithmically (so each time you double the number of trials, the information gained is halved from the time before).

 

[Cerb]

For problem #1, consider that an interviewer may lead you a bit--IE, not being worried as much about specifically having every bit of background for the problem, as much as being able to work through it. While I simply don't have the background necessary to prove optimality of the solution, I probably would have gotten very close to the solution fairly quickly if I had made the connection to completely disjoint cycles very early on. With something close to the proper solution in mind, even Jython is fast enough to perform enough randomized iterations to get within 0.1% in under a minute, on an old COre at 1.83GHz (I never split the work up across cores; also, Jython was no faster than CPython, but the random number generator was clearly more fair).

 

[serpretetsky]

for problem 2: does the reciever need to be able to decypher alice's message as well? Or does he simply need to get your message with as many bits as possible?

 

[IHateMyJob2004]

eLui,

I think you made assumptions about what I was saying. That or I wasn't clear.

I'm shocked that any company would expect people to take 5 half days off of their current job to do 5 interviews. Are these 5 interviews all in one day?

I'd be more than willing to entertain hypotheticals just to show my thought process. But if people expect me to start taking about big O notation type stuff and statistics, forget it. All I am saying is that there are alot of people with alot of experience that are very good that have not used that knowledge in a long time and most of it is forgotten. If it is absolutely required for a job, fine. But if people are pulling these questions out for no valid reason, it is stupidity. You can filter people out just as easily by asking stupid things like what is a good example of multiple inheritance. I'd bet that 50% of interviewees would actually try to come up with good reasons when the answer is that there are no good answers.

 

[eLiu]

For problem #2, consider that an interviewer may lead you a bit--IE, not being worried as much about specifically having every bit of background for the problem, as much as being able to work through it. While I simply don't have the background necessary to prove optimality of the solution, I probably would have gotten very close to the solution fairly quickly if I had made the connection to completely disjoint cycles very early on. With something close to the proper solution in mind, even Jython is fast enough to perform enough randomized iterations to get within 0.1% in under a minute, on an old COre at 1.83GHz (I never split the work up across cores; also, Jython was no faster than CPython, but the random number generator was clearly more fair).

Yeah and that would've been fine. Unless the problem is very easy (and more meant to see how you code), it's totally ok to have to ask some questions, get help, and otherwise back & forth w/the interviewer. For this problem, it's also probably ok to not know how to analyze the result. You shoudl be able to say that it's the probability that there are NO cycles of length > N/2 even if you can't compute it. And then the interviewer might help you through that if they care: how many total combinations? in a cycle of length M, how many ways to arrange a cycle? how many ways teh arrange the remaining N-M? how many ways to choose M things out of N? Each of those you should be able to do individually since it's like high school level discrete math.

For optimality, I don't even know how to prove optimality. But if you can pass any info you want, you still can't do better than 50%. So in most scenarios, 30% will be good enough even if you could manage slightly better.

for problem 2: does the reciever need to be able to decypher alice's message as well? Or does he simply need to get your message with as many bits as possible?

The receiver does not need to be able to decypher alice's message, but this is not relevant. If Alice and Bob agreed on a convention beforehand (e.g., first 30 bits are the msg, last bit is for parity & Alice sets parity so that the sum of all 31 bits is even), Bob can detect whether you have changed something. But he won't have enough info to figure out what you changed. Or if they're willing to more substantially reduce the number of bits transmitted, they can select an error correcting code valid for hamming distance of D--such codes can recover the original message even after at most D bits are flipped (here D = 1).

So Bob being able to understand Alice's message would entirely be a function of the convention they use for their 31 bits; it has no bearing on how you will transmit info to Bob by flipping 1 bit. You and Bob need to decide a plan for him to understand as many bits of info from you as possible.

eLui,

I think you made assumptions about what I was saying. That or I wasn't clear.

I'm shocked that any company would expect people to take 5 half days off of their current job to do 5 interviews. Are these 5 interviews all in one day?

I'd be more than willing to entertain hypotheticals just to show my thought process. But if people expect me to start taking about big O notation type stuff and statistics, forget it. All I am saying is that there are alot of people with alot of experience that are very good that have not used that knowledge in a long time and most of it is forgotten. If it is absolutely required for a job, fine. But if people are pulling these questions out for no valid reason, it is stupidity. You can filter people out just as easily by asking stupid things like what is a good example of multiple inheritance. I'd bet that 50% of interviewees would actually try to come up with good reasons when the answer is that there are no good answers.

Yeah I went a bit overboard responding to your post. Claiming that the problem is silly to ask of anyone not doing stats (even though you didn't/don't know the solution) rubbed me the wrong way. That's really the main thing I wanted to respond to--finding the best algorithm requires 0 stats; it's all classical CS (

Spoiler

graphs

). And as I noted above, the analysis requires only a very basic understanding of how to count permutations & combinations.

Anyway, the most common thing I saw were 4-5 1 hour interviews. These were done during a single day, at the company's offices. The sessions are typically back to back with some time for a break or lunch in the middle. My shortest interviews were only ~3 hrs and my longest were ~8 hrs. For companies I really cared about, I would hang around after the interview was done to meet more engineers, talk to people, and just hang out. Interviews were as much about companies testing me as they were about me testing the companies. Before that, they may also have 1 or 2 1hr phone interviews that you can schedule at your convenience. I would guess that for higher positions (like an exec at google), the interview process will probably be more drawn out than "new grad" hires.

I would say that understanding Big-O is absolutely critical to any dev position (based around algorithm development) in silicon valley. Yeah if you're applying to a front-end position or doing purely client-facing stuff, it probably doesn't matter/you won't get tested on that. But those aren't exactly [classical] computer science either.

I mean when you come up with an algorithm, you should be able to tell me if its running time is constant, logarithmic, linear, polynomial, or exponential. There are of course other possibilities but I think those are the biggies. I mean if you were asked to implement a function returning the n-th fibonacci sequence and you gave this:
int fib(int n){
if(n == 0) return 1;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
and thought that was a great solution, you'd be in a lot of trouble. And no, (tail) recursion is not what's wrong here. Or similarly if you knew the closed from expression (using floating point) and claimed that is "constant" time, I would be raising eyebrows there too.

Most of my interviewers asked me to design and code an algorithm (meant the algorithm would be pretty simple) or just design an algorithm. In all cases, performance was the first thing asked b/c the O(n^3) naive algorithm is not practical for n = billions, but the O(n) optimal is.

I also wouldn't be all that happy with someone who says multiple inheritance is always bad. It is a part of the language, and in the right circumstances (+ with a well thought out style guide to ensure things don't go crazy), maybe it's also the best solution. I mean in Java, you can have as many interfaces as you want; in C++, there's no interface construct and multiple inheritance would be the only solution.

But if I were testing OO design (e.g., design an elevator is a popular one), and the person was using inheritance for is-a and has-a relations (so maybe the elevator inherits from the button panel, control unit, motor, etc), that would be raising red flags all over the place. Definitely not a place where multiple inheritance (or any inheritance) should be used.

 

[iCyborg]

Should I just post the solution to the 2nd problem? Is anyone even still paying attention? lol

I'm not sure about the others, but it's been a stressful week at work for me, so I'm pretty much waiting for a complete solution

 

[eLiu]

I'm not sure about the others, but it's been a stressful week at work for me, so I'm pretty much waiting for a complete solution

Sure, why not.

First, some intuition about XOR for those who don't know it well:

Spoiler

The whole thing hinges on XOR which I'll denote w/the C operator, ^. A few things to know about XOR if you didn't:
1) 0 is the identity: a^0 = a, always
2) each value is its own inverse: a^a = 0, always
3) it's commutative & associative

This means a number of neat things... like of all the bit-wise operations, XOR is the only "symmetric" one. By symmetric, I mean say we have the expression "a OP b -> c" (a op b results in c) and I give you 2 of the 3 values. With XOR (and only XOR), you can determine what the 3rd value is. Like even if I give you ? ^ 5 = 8, you can work out what ? is. This is not possible with OR and AND. And "solving" for ? is always easy:
? ^ b -> c
? ^ b ^ b -> c ^ b (= b^c)
? ^ 0 -> c ^ b
? -> c ^ b
So to find the missing one, just XOR the other two together.

I also want to remind y'all about the finding duplicates problem from earlier. Say I give you a list of N numbers in the range [1,N-1]: so there's 1 duplicate. One way to find this duplicate (in which overflow is impossible) is to XOR all the numbers from [1,N-1] together, then XOR the result with the numbers in my list. The final answer will be the duplicate. Why? Well the duplicate number will appear in the XOR operation 3 times. We can use the commutative property to rearrange the operations so that it looks like 1^1, 2^2, ... dup^dup^dup, ... (N-1)^(N-1), where "dup" is the duplicated value. Using the inverse property, everything comes out to 0 except for one dup, and 0^0 = 0, and dup^0 = dup.

Hopefully that helps build some intuition about XOR for those of y'all who aren't familiar with it.

And now the SOLUTION TO PROBLEM 2:

Spoiler

You need to arrange a "code" with Bob beforehand. One way to do it is as follows. Say I want to transmit the 5-bit string S to Bob.
1) Consider all 32 possible 5-bit strings and remove the string of all 0s (you'll see why in a sec).
2) Assign each of these 5-bit strings to a single bit of the 31 bit string (e.g., 5-bit string for "1" goes to the 1st bit, string for 2 goes to the 2nd bit, etc).
3) Set a temporary quantity to 0. Read through the 31-bit string. If there is a 1 in the n-th spot of the 31-bit string, XOR the corresponding 5-bit string with your temporary. Do this for every bit of the 31-bit string. Call this result B.
4) Now solve: ? ^ B -> S (compute B^S). Once you determine what ? is, flip the bit in 31-bit string that "owns" it. If ? is all 0s, do nothing.

On Bob's end, he will need to perform step 3). The final result will be the message you intended to send, by construction.

You should be able to see now why we don't need to use the string 00000 in our code. Since a^0 = a, flipping the bit that owns 00000 would never change the result & thus we'd just be wasting a slot.

This is why you get 5 bits of info with a 31 bit message. You might've thought that you would need 32 bits to transmit 5 bits, but in fact "do nothing" is a meaningful way to transmit information!

Let's do an example with a 7-bit string (abcdefg), 3-bit message (to keep it short).
Sorry about the kinda ugly spacing: I can't spoiler things inside of the code tags, heh.
a b c d e f g
| | | | | | |
0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1

So let's start with some easy ones. Say alice's message is 1111111 or 0000000. In both cases, after step 3, the result you have is 000. If your message is all 0s, you're done. Otherwise regardless of what your message is (xyz), just find the letter (a-g) that contains your message, and flip that bit. So if I wanted to send 101, I would flip e (5th bit).

And if Alice's message was more 'weird'? Well let's just try one:
A) Alice sends: 1001011. You want to send: 010
In step 3, you'd compute: 001^100^110^111 = 100
So solve: ? ^ 100 = 010. From before ? is 100 ^ 010 = 110.
Thus you should flip the 6th bit. Then Bob receives:
1001001
He computes the XOR process: 001^100^111 = 010.
Tada! Bob has received your message.

Again, this process is completely general & you can prove every component using the properties of XOR. The examples are just for illustration. The solution is nice b/c it easily generalizes to any message size. Yes, you could write a program based on the hamming distance solution I gave earlier (3 bit msg from Alice, transmit 2 bits to Bob), but it's not clear to me how efficient that process could be. Here, the solution is at worst linear in the number of bits! (And could even be made constant with table lookups.)

Lastly, you can also transpose the whole process and do XOR operations on groups of bits in the message string (first half w/last half, etc). I didn't try to work this through b/c I find it incredibly awkward to think about but my friend thinks it's more natural.

 

[iCyborg]

For 2) - this shows how to send

Spoiler

5

bits. Is there any rationale/proof that this is the most we can send?

 

[eLiu]

For 2) - this shows how to send

Spoiler

5

bits. Is there any rationale/proof that this is the most we can send?

Sorry for the slow reply... been hackathon-ing at my new job XD

Anyway, yes

Spoiler

5

bits being the max has some good intuition behind it:

Spoiler

we're allowed to flip at most one bit. So with a 31 bit message + doing nothing, that's 32 possible actions. Hence we can convey at most log_2(32) = 5 bits of information.

 

[Mark R]

I think I have solved puzzle 2! Interstingly, I didn't need to use XOR. instead, I applied some rather butchered graph theory.
I'll post an update once I've written out my thoughts.

Pages of Scribbles: 1; 2; 3; 4;

 

[eLiu]

I think I have solved puzzle 2! Interstingly, I didn't need to use XOR. instead, I applied some rather butchered graph theory.
I'll post an update once I've written out my thoughts.

Pages of Scribbles: 1; 2; 3; 4;

At a glance this looks like it works. I'll read/think about it in more detail on my flight tonight.

Wow this is really exciting! I'd be super happy to know of a different way to solve this problem.

 

[IHateMyJob2004]

I've never walked out of an interview in my life. My response would be somethign along the lines of, "is this kind of thinking required for the job?" If the answer is yes, I'd say that the interview is pretty much over and ask to be pointed to the door.

The funny thing is that co-workers that might know the answer to your question would probably never accept an offer from you.