An interview question:
Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1. Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 1.
My implementation is:
function g(x) = { if (f(x) == 0){ // 1/4 var s = f(x) if( s == 1) {// 3/4 * 1/4 return s // 3/16 } else { g(x) } } else { // 3/4 var k = f(x) if( k == 0) {// 1/4 * 3/4 return k // 3/16 } else { g(x) } } }
Am I right? What's your solution?(you can use any language)
Probability questions are often asked in both data science and analytics interviews at FAANG companies and other big tech firms. Testing your probability knowledge provides companies with a good idea of your analytical reasoning skills and intelligence, and they often take the form of case studies.
Since we are interested in whether or not someone will be an active user in 6 months or not, we can test this assumption by first looking at the existing data. One way to do so is to put users into buckets determined by friend size six months ago and then look at their activity over the next six months.
If you call f(x) twice in a row, the following outcomes are possible (assuming that successive calls to f(x) are independent, identically distributed trials):
00 (probability 1/4 * 1/4) 01 (probability 1/4 * 3/4) 10 (probability 3/4 * 1/4) 11 (probability 3/4 * 3/4)
01 and 10 occur with equal probability. So iterate until you get one of those cases, then return 0 or 1 appropriately:
do a=f(x); b=f(x); while (a == b); return a;
It might be tempting to call f(x) only once per iteration and keep track of the two most recent values, but that won't work. Suppose the very first roll is 1, with probability 3/4. You'd loop until the first 0, then return 1 (with probability 3/4).
The problem with your algorithm is that it repeats itself with high probability. My code:
function g(x) = { var s = f(x) + f(x) + f(x); // s = 0, probability: 1/64 // s = 1, probability: 9/64 // s = 2, probability: 27/64 // s = 3, probability: 27/64 if (s == 2) return 0; if (s == 3) return 1; return g(x); // probability to go into recursion = 10/64, with only 1 additional f(x) calculation }
I've measured average number of times f(x)
was calculated for your algorithm and for mine. For yours f(x)
was calculated around 5.3 times per one g(x)
calculation. With my algorithm this number reduced to around 3.5. The same is true for other answers so far since they are actually the same algorithm as you said.
P.S.: your definition doesn't mention 'random' at the moment, but probably it is assumed. See my other answer.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With