


10272012, 04:00 AM

#76

Senior Member
Join Date: Jan 2012
Posts: 538

Quote:
Originally Posted by iCyborg
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.



10272012, 03:59 PM

#77

Diamond Member
Join Date: Mar 2002
Posts: 4,349

Ehh I just had to find out. So a computed answer is they all die 68.6280% of the time.
Edit: 1,000,000 cycles came out with 68.802980%
Edit2: Running 10,000 lockers 10,000 times came up with 69.42%
I would assume that the limit as lockers and runs approaches infinity the chance they all die will be 70%. But looking back at eLiu's answer 1  ln(2) = 30.6% as N>infinity this number is actually the 69.4%
Edit3: A 20k 20k run revealed a 68.890000000000001%.
Edit4: A 40k 300 run revealed a 69.333333333333329%.
Code:
#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) * (LOCKERCOUNT1));
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;
__________________
All errors are undocumented features waiting to be discovered.
Last edited by Schmide; 10272012 at 07:16 PM.



10282012, 06:05 AM

#78

Diamond Member
Join Date: Jun 2001
Posts: 6,408

Should I just post the solution to the 2nd problem? Is anyone even still paying attention? lol
Quote:
Originally Posted by IHateMyJob2004
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 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 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 45 1hr sessions with various engineers. Some will try to evaluate your coding capability & style, others will check your ability to come up with wellreasoned OO designs, others hit you with nontrivial (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 monkeying 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 graph representation and they still get nowhere, that would be a red flag.
Quote:
Originally Posted by IHateMyJob2004
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 150. =1 takes 2675, =2 takes 51100, =3 takes 76100 and 125. 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.
Quote:
Originally Posted by uclabachelor
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).

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.
Quote:
Originally Posted by Schmide
Ehh I just had to find out. So a computed answer is they all die 68.6280% of the time.
...SNIP...

Cool, thanks for implementing that! Yeah the convergence will be VERY slow and the 1ln(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).
__________________
Their's not to make reply,<BR>Their's not to reason why,<BR>Their's but to do and die.<BR><BR> My Rigs
Last edited by eLiu; 10282012 at 06:07 AM.



10282012, 09:52 AM

#79

Elite Member
Join Date: Aug 2000
Posts: 16,630

For problem #1, consider that an interviewer may lead you a bitIE, 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).
__________________
Quote:
Originally Posted by Crono
I'm 90% certain the hipster movement was started by aliens from another galaxy who have an exaggerated interpretation of earth culture(s).

Last edited by Cerb; 10292012 at 07:45 AM.
Reason: 3 times this week: need to lay off the numpad when not using my Model M, I guess.



10282012, 12:39 PM

#80

Senior Member
Join Date: Jan 2012
Posts: 538

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?



10282012, 04:18 PM

#81

Lifer
Join Date: Sep 2004
Posts: 16,367

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.



10282012, 08:53 PM

#82

Diamond Member
Join Date: Jun 2001
Posts: 6,408

Quote:
Originally Posted by Cerb
For problem #2, consider that an interviewer may lead you a bitIE, 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 NM? 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.
Quote:
Originally Posted by 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?

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 Dsuch 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.
Quote:
Originally Posted by 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.

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 tofinding the best algorithm requires 0 stats; it's all classical CS ( 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 45 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 BigO is absolutely critical to any dev position (based around algorithm development) in silicon valley. Yeah if you're applying to a frontend position or doing purely clientfacing 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 nth fibonacci sequence and you gave this:
int fib(int n){
if(n == 0) return 1;
if(n == 1) return 1;
return fib(n1) + fib(n2);
}
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 isa and hasa 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.
__________________
Their's not to make reply,<BR>Their's not to reason why,<BR>Their's but to do and die.<BR><BR> My Rigs



10292012, 12:45 AM

#83

Golden Member
Join Date: Aug 2008
Posts: 1,055

Quote:
Originally Posted by eLiu
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



10292012, 04:53 AM

#84

Diamond Member
Join Date: Jun 2001
Posts: 6,408

Quote:
Originally Posted by iCyborg
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:
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 bitwise 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,N1]: so there's 1 duplicate. One way to find this duplicate (in which overflow is impossible) is to XOR all the numbers from [1,N1] 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, ... (N1)^(N1), 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:
You need to arrange a "code" with Bob beforehand. One way to do it is as follows. Say I want to transmit the 5bit string S to Bob.
1) Consider all 32 possible 5bit strings and remove the string of all 0s (you'll see why in a sec).
2) Assign each of these 5bit strings to a single bit of the 31 bit string (e.g., 5bit 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 31bit string. If there is a 1 in the nth spot of the 31bit string, XOR the corresponding 5bit string with your temporary. Do this for every bit of the 31bit string. Call this result B.
4) Now solve: ? ^ B > S (compute B^S). Once you determine what ? is, flip the bit in 31bit 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 7bit string (abcdefg), 3bit 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 (ag) 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.
__________________
Their's not to make reply,<BR>Their's not to reason why,<BR>Their's but to do and die.<BR><BR> My Rigs
Last edited by eLiu; 10292012 at 05:05 AM.



10312012, 11:00 AM

#85

Golden Member
Join Date: Aug 2008
Posts: 1,055

For 2)  this shows how to send 5 bits. Is there any rationale/proof that this is the most we can send?



11032012, 05:51 PM

#86

Diamond Member
Join Date: Jun 2001
Posts: 6,408

Quote:
Originally Posted by iCyborg
For 2)  this shows how to send 5 bits. Is there any rationale/proof that this is the most we can send?

Sorry for the slow reply... been hackathoning at my new job XD
Anyway, yes 5 bits being the max has some good intuition behind it: 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.
__________________
Their's not to make reply,<BR>Their's not to reason why,<BR>Their's but to do and die.<BR><BR> My Rigs



11062012, 12:56 PM

#87

Diamond Member
Join Date: Oct 1999
Posts: 8,335

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;
Last edited by Mark R; 11062012 at 01:40 PM.



11062012, 05:58 PM

#88

Diamond Member
Join Date: Jun 2001
Posts: 6,408

Quote:
Originally Posted by 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;

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.
__________________
Their's not to make reply,<BR>Their's not to reason why,<BR>Their's but to do and die.<BR><BR> My Rigs



11062012, 06:34 PM

#89

Lifer
Join Date: Sep 2004
Posts: 16,367

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 coworkers that might know the answer to your question would probably never accept an offer from you.



Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 11:43 AM.
