Yahoo Interview Question for Software Development Managers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

Lets assume the same example
A = ['a', 'b', 'c']
W = [0.3, 0.5, 0.2]

By probability, when randomChar( ) is called 10 times, a should appear 3 times, b should appear 5 times, c should appear 2 times.

Here 10 is a good number because it ensures every probability is turned into an integer corr. character is printed that many times. If we had an example like,
A = ['a', 'b', 'c']
W = [0.03, 0.5, 0.47]
we have to take 100 as the baseline since 0.03*100=3.

This method finds this ā€˜nā€™

int findN()
{
n=minElement(W);
while(n>0)
{
n=n*10;
}
return n;
}

// Create a copy of W in W1 and multiply all elements of W with this n.
void initializeWeights()
{
for(int i=0;i<W.length();i++)
{
W1[i]=W[i]*n;
}
}
This W1 is the number of times each character has to be printed if randChar( ) is called ā€˜nā€™ times.
If the randChar( ) is run for n times, our code should ensure that every A[i] is print W[i] times *randomly*. Remember, it cant just print every element sequentially, then randChar() has no meaning! ;)

char randChar()
{
while(1)
{
p=rand(W1.length()); // printing a random number from 1 to W.length()
if(W1[p]>0) // this ensures that when a char at A[p] is printed for that many times it is supposed to
{
W1[p]--;
return A[p];
}
}
}


int main()
{
int j,n;
n=findN();
m=100; // number of times we are asked to print it
for(j=1;j<=10;j++)
{
initializeWeights() // assign back all the weights
for(k=1;k<=n;k++)
{
cout<<randChar( );
}

}
// set W back to its original numbers every n times
}


This is the first time I am posting answers in this forum. Please pardon syntactical mistakes!

- iprep.bc November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

this method has flaws, what if the probability list is[0.1,0.22222,0.67778]? the big N will be only 10, which led to W1:[1,2.2222,6.7778], and the output number would be[1,3,7].

- xmy January 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The findN function needs to be modified as below:

int findN( double W[] )
{
double num = minElement( W );
int n = 1;
while( num < 1 )
{
n = n*10;
num = num*10;
}
return n;
}

- nharryp March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry did not read the comment above. Do the below modification:

int findN( double W[] )
{
int num_digits = max_digits( W ); //gives the max digits after decimal point
int n = 1;
while( num_digits >= 1 )
{
n = n*10;
num_digits = num_digits--;
}
return n;
}

- nharryp March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

char randomchar()
{
	double temp = 0;
	int random = rand() % 100;

	for(int i=0; i<n; i++)
	{
		temp += W[i];
		if(random < temp*100)
			return A[i];
	}
}

- algos November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As mentioned in question, these weights and characters are given once but the randomChar() is called multiple number of times. You are doing a O(n) for each of these calls. A good approach would be finding cumulative probabilities in one parse initially. And then whenever the randomChar() is called, you do a binary search with complexity O(logn).

- nosyDeveloper November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Character random(
char[] cha, double[] dba) {
if (cha.length == dba.length) {
List<Character> arr = new ArrayList<>();
int[] inta = new int[cha.length];
for (int i=0;i<inta.length;i++) {
inta[i]=(int) Math.round(dba[i]*100);
}
for (int i=0;i<inta.length;i++)
for (int j = 0; j < inta[i]; j++)
arr.add(cha[i]);
return arr.get((int) Math.round(Math.random()*100));
} else
return null;
}

- nirupam.astro November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The size of your List arr will be 100. Also, what if the probability of a character to appear is 0.001? You seem to round it to a 0 in your code.

- nosyDeveloper November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Sort the the probability array in decreasing order (sort character array accordingly).
W'=[0.5,0.3,0.2]
A'=['b', 'a', 'c']

2. Iterate over arrays to calculate cumulative probability as suggested.
W'=[0.5,0.8,1.0]

3. Generate random number 'r' between 0 - 1

4. Iterate array to find 'i' until W'[i+1] > r or i ==n

5. Return A'[i]

- pr November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) sequential approach. Question is asking for a binary search approach.

- nosyDeveloper November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nosyDeveloper
Calculating calculating cumulative probability for the array takes O(n)
I don't think there is O(log n) solution for this.

- pr November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NewTest{
		// to search for the given range
	static int binSearch(double[] W, int start, int end, double random){
		if(start==end)
			return start;
		int mid = (end - start)/2;
		if(random <= W[mid])
			return binSearch(W,start,mid,random);
		else
			return binSearch(W,mid+1,end,random);
	}
	
	static char generateRandom(double[] W, char[] A){
		double random = Math.random();				//random double between 0 and 1
		return A[binSearch(W,0,W.length-1,random)];	//
	}
	
	public static void main(String[] args){
		double W[] = {0.2, 0.3, 0.5};
		char A[] = {'a', 'b', 'c'};
		
		//calculating cumulative probability 
		for(int i=1; i < W.length; i++){
			W[i] = W[i-1]+W[i];
		}
		
		//calling multiple times and counting - for test only
		int count[] = {0,0,0};
		for(int i=0;i<10000;i++)
			{
				char r = generateRandom(W,A);
				count[r-'a']++;
			}
		for(int i=0; i<count.length; i++)
			System.out.println((char)('a'+i)+" - "+count[i]);
	}
}

- nosyDeveloper November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Once you computed cumulative sum:

for(int i=1; i < W.length; i++){
			W[i] = W[i-1]+W[i];
		}

your algo has become O(n) solution since A.length = W.length.

- thelineofcode November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@thelineofcode
you can cache the cumulative sum the first time you calculate it, next time just use this cached value. so the amortised complexity is O(logn),

- Charlie January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Always a trade-off space vs. time:

import java.util.Random;

public class MyRandomChar {

	// Assumption:  Array is not given as part of the randomChar() -
	//       "There is an array of characters... "
	private final char[] A = { 'a', 'b', 'c' };
	private final double[] W = { 0.3, 0.5, 0.2 };
	
	private final int[] lookup;
	private int totalLookupValues = 0;
	
	private final Random rand = new Random();
	
	public MyRandomChar() {

		// Assumption:  Preparation can take O(n) one time:
		totalLookupValues = 0;

		// Assumption:  "... randomChar() called 100 times should return approx. ..."
		// Used m = 10 as the resolution factor (can be increased) hence space O(m):
		for (double w : W)
			totalLookupValues += Math.round(w * 10);

		lookup = new int[totalLookupValues];
		
		int lookupIndex = 0;
		
		for (int weightsIndex = 0; weightsIndex < W.length; weightsIndex++) {
			for (int weightRepeat = 0; weightRepeat < Math.round(W[weightsIndex] * 10); weightRepeat++)
				lookup[lookupIndex++] = weightsIndex;
		}
	}
	

	public char randomChar() {
		
		// O(1):
		return A[lookup[rand.nextInt(totalLookupValues - 1)]];
	}
}

- us November 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Other than statistical testing, are there any other mathematical methods to prove that your code is able to get chars with their corresponding probabilities?

I think the main point of this puzzle lies herein.

- coderfe December 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create an array say P[].

for(i=0;i<len(w);i++)
{
n = w[i]*10;
while(n>0)
{
push(i,P);
n--;
}
}

// Now P will have [0,0,0,1,1,1,1,1,2,2]

random = rand(P);

print A[random];

- mitesh.pant December 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my modification of the binary search to identify the interval:

public int binarySearchInterval(double[] A, double target, int start, int end) {
		if (start > end) return -1;
		int mid = (start + end) / 2;
		if (target <= A[mid] && (mid == 0 || target > A[mid-1])) return mid;
		if (target > A[mid]) return binarySearchInterval(A, target, mid+1, end);
		else return binarySearchInterval(A, target, start, mid-1);
	}

- KJ March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my binary search:

unsigned getIndexLower(const vector<float> &vec, float target){
    
    if (vec.size() <=1 )return vec.size();
    unsigned low =0, high= vec.size()-1;
    while(low < high){
        unsigned mid = (low+high)/2;
        if (vec[mid] <= target && (mid <high && vec[mid+1] > target)){
            return mid+1;
        }
        if (vec[mid] < target) { low = mid+1; }
        else { high = mid; }
    }
    return low;
}

- im.code.warrior July 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main (String[] args) throws java.lang.Exception
	{
		char[] A = {'a','b','c'};
		double[] W = {0.33,0.5,0.17};
		int k=100,x=1000;
		/*
			k is the precison upto which you want to multiply your probability with
			
			x is the number of times this experiment would run, make this number 
			too big it would reach the given probabilities
			
			S containsts the count of number of times a, b or c came
		*/
		int[] S = {0,0,0};
		Random randomGenerator = new Random();
	 	double sum=0.0;
		for (int idx = 1; idx <= x; ++idx){
      		int ra = randomGenerator.nextInt(k);
      		sum=0.0;
      		for(int i=0;i<A.length;i++)
      		{	
      			sum+=W[i]*k;
      			if(ra<sum)
      			{
      				S[i]++;
      				break;
      			}
      		}
    	}
    	for(int i=0;i<A.length;i++)
    		System.out.println((double)S[i]/x);
	}

- Puneet Singh October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main (String[] args) throws java.lang.Exception
	{
		char[] A = {'a','b','c'};
		double[] W = {0.33,0.5,0.17};
		int k=100,x=1000;
		/*
			k is the precison upto which you want to multiply your probability with
			
			x is the number of times this experiment would run, make this number 
			too big it would reach the given probabilities
			
			S containsts the count of number of times a, b or c came
		*/
		int[] S = {0,0,0};
		Random randomGenerator = new Random();
	 	double sum=0.0;
		for (int idx = 1; idx <= x; ++idx){
      		int ra = randomGenerator.nextInt(k);
      		sum=0.0;
      		for(int i=0;i<A.length;i++)
      		{	
      			sum+=W[i]*k;
      			if(ra<sum)
      			{
      				S[i]++;
      				break;
      			}
      		}
    	}
    	for(int i=0;i<A.length;i++)
    		System.out.println((double)S[i]/x);
	}

- Puneet Singh October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main (String[] args) throws java.lang.Exception
	{
		char[] A = {'a','b','c'};
		double[] W = {0.33,0.5,0.17};
		int k=100,x=1000;
		/*
			k is the precison upto which you want to multiply your probability with
			
			x is the number of times this experiment would run, make this number 
			too big it would reach the given probabilities
			
			S containsts the count of number of times a, b or c came
		*/
		int[] S = {0,0,0};
		Random randomGenerator = new Random();
	 	double sum=0.0;
		for (int idx = 1; idx <= x; ++idx){
      		int ra = randomGenerator.nextInt(k);
      		sum=0.0;
      		for(int i=0;i<A.length;i++)
      		{	
      			sum+=W[i]*k;
      			if(ra<sum)
      			{
      				S[i]++;
      				break;
      			}
      		}
    	}
    	for(int i=0;i<A.length;i++)
    		System.out.println((double)S[i]/x);
	}

- Puneet Singh October 27, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More