Interview Question


Country: United States




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

Arrange students by putting the lowest ranked one first, then the highest, then the second lowest, then the second highest, and so on.

# Input is an array of the children's rankings
def getNumLaddus(arr, numStudents):
    arr = sorted(arr)

    first = arr[:numStudents/2]
    second = list(reversed(arr[numStudents/2:]))
    arr = list()
    for i in xrange(numStudents):
        if i % 2 == 0 and i/2 < len(first):
            arr.append(first[i/2])
        else:
            arr.append(second[i/2])

    ladduArr = [1] * numStudents
    for i in xrange(1, numStudents - 1):
        if arr[i] > arr[i+1] or arr[i] > arr[i-1]:
            ladduArr[i] = max(ladduArr[i-1], ladduArr[i+1]) + 1
    if arr[0] > arr[1]: ladduArr[0] = ladduArr[1] + 1
    if arr[-1] > arr[-2]: ladduArr[-1] = ladduArr[-2] + 1

    return sum(ladduArr)

print getNumLaddus([1,2,2], 3) # Outputs 4
print getNumLaddus([1,2,3], 3) # Outputs 4
print getNumLaddus([5,1,2,1,5], 5) # Outputs 7
print getNumLaddus([5,0,2,1,5,6], 6) # Outputs 9

- Clay Schubiner June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your result for input number 2 3 and 4 are wrong. Its should be 6, 8 , 11 respectively.

- AlgoAlgae June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No. If you arrange 1,2,3 as 1, 3, 2 then you can give them 1, 2, 1 laddu, so 4 total.

5,1,2,1,5 can be arranged as 1, 5, 1, 5, 2. You'd give them 1,2,1,2,1 laddu, so 7 total.

5,0,2,1,5,6 can be arranged as 0, 6, 1, 5, 2, 5. You'd give them 1, 2, 1, 2, 1, 2 laddu, so 9 total.

- Clay Schubiner June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh yeah, I get the question now. So teacher can and should rearrange the students to minimize the laddus. I completely missed that. Thanks for explaining, I upvote your answer :)

- AlgoAlgae June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Created a program in Java (In comments I have provided some of the combinations which are being discussed in the comments above):

package practicing;

import java.util.Arrays;

public class LakshmiLaddoo {

	// int ranking[] = { 3, 1, 5, 5, 5, 5 }; min num of laddos=10
	// int ranking[] = { 3, 1, 2, 2}; min num of laddos=4
	// int ranking[] = { 3, 1, 2, 2, 5 }; min num of laddos=7
	int ranking[] = { 1, 3, 2, 5, 7 };
	int combined[] = new int[ranking.length];
	int laddoGiven[] = new int[ranking.length];
	int first[] = new int[(ranking.length + 1) / 2];
	int second[] = new int[(ranking.length + 1) / 2];
	int sNum;

	void calculatingTotalLaddo() {
		// Sort Original Array
		Arrays.sort(ranking);

		int fNum = 0;

		if (ranking.length % 2 == 0) {
			sNum = ((ranking.length) / 2) - 1;
		} else {
			sNum = ((ranking.length) / 2);
		}

		// Divide the array Such That First array is in Ascending order and
		// Second Array is in Descending order
		for (int i = 0; i < ranking.length; i++) {
			if (i < (ranking.length / 2)) {
				first[fNum] = ranking[i];
				fNum++;
			} else {
				second[sNum] = ranking[i];
				sNum--;
			}
		}

		// Combining the two arrays taking each element from a position of both
		// array
		int pos = 0;
		for (int i = 0; i < (ranking.length + 1) / 2; i++) {
			if (first[i] != 0) {
				combined[pos] = first[i];
				pos++;

			}
			if (second[i] != 0) {
				combined[pos] = second[i];
				pos++;

			}

		}

		// Assigning Laddos according to the ranks and adjacent student

		int prev;
		for (int i = 0; i < ranking.length; i++) {
			prev = i - 1;
			if (i % 2 == 0) {
				if (prev != -1) {
					if (combined[i] != combined[prev]) {
						laddoGiven[i] = 1;
					} else {
						laddoGiven[i] = laddoGiven[prev];
					}
				} else {
					laddoGiven[i] = 1;
				}
			} else {
				if (prev != -1) {
					if (combined[i] != combined[prev]) {
						laddoGiven[i] = 2;
					} else {
						laddoGiven[i] = laddoGiven[prev];
					}
				} else {
					laddoGiven[i] = 2;
				}
			}
		}

		// Printing Student Ranking and Laddo Given:
		int sum = 0;
		for (int i = 0; i < ranking.length; i++) {
			System.out.println("StudentRanking: " + combined[i] + " Laddo: "
					+ laddoGiven[i]);
			sum += laddoGiven[i];
		}

		System.out
				.println("Total Number of Laddo Teacher has to buy is:" + sum);
	}

	public static void main(String[] args) {
		LakshmiLaddoo lakLad = new LakshmiLaddoo();
		lakLad.calculatingTotalLaddo();
	}
}

Output:
StudentRanking: 1 Laddo: 1
StudentRanking: 7 Laddo: 2
StudentRanking: 2 Laddo: 1
StudentRanking: 5 Laddo: 2
StudentRanking: 3 Laddo: 1
Total Number of Laddo Teacher has to buy is:7

- rahulkeshar.career June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

G

- g fatma March 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The strategy for spending minimum money is to arrange the students in such a way that if the immediate neighbor has more score then he gets 2 laddu else he gets 1. So the students should be arranged in such a way that each student with a high score is followed by a student with a score <= to him. This arrangement can be made by sorting the students by score and then swapping the adjacent element e.g. if the scores are 1,6,3,5,4,2 then the arrangement will be 2,1,4,3,6,5.
Once the arrangement is finalized use the following to calculate the number of laddus

if(score[prev]>=score[curr]
laddus[curr]=1
else
laddus[curr]=2

Now just sum the elements of laddus array.

- kr.neerav June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work exactly.

With your solution, students ranked 1, 2, 2 will be arranged as 2,1,2, which means we'd have to use 5 laddu to satisfy the requirement.

You'll find my answer in a comment below. Let me know what you think

- Clay Schubiner June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class chocs {
	static int min[];
	public static int func(int [] a ,int count,int index){
		if (index == a.length-1){
			min[index] =  count;
			return count;
		}
		if(a[index]>a[index+1]){
			count=1;
			min[index] =   Math.max(index>0?min[index-1]+1:1,1 + func(a,count,index+1));
			
		}
		else if(a[index]<= a[index+1]){
			min[index]= count;
			count= count +1;
			func(a,count,index+1);
			
		}
		return min[index];
			
	}
	
	public static void main(String atgv[]){
		int a[] = {2,1,0,4,3,2,6};
		min= new int[a.length];
		func(a,1,0);
		for(int i=0;i<a.length;i++){
			System.out.println(min[i]);
		}
	}
}

- Anonymous June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

O(n) solution.

package com.google.practice;


public class LadduKhor {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int noOfGreedyBs = 4;
		int[] childRanking = new int[noOfGreedyBs+2];
		
		
		childRanking[0]=Integer.MAX_VALUE;
		childRanking[1] = 1;childRanking[2] = 2;childRanking[3] = 1;childRanking[4] = 1;
		childRanking[childRanking.length-1]=Integer.MAX_VALUE;
		
		int[] childLaddu = new int[noOfGreedyBs+2];
		childLaddu[0] = 0;
		for(int i=1;i<noOfGreedyBs+1;i++)
			childLaddu[i]=1;
		childLaddu[childLaddu.length-1] = 0;
		
		System.out.println(helpPoorTeacher(childRanking,childLaddu));
	}
	
	//Parse through the line from both end. Give 1 laddu token more than previous child has if previous child has lower ranking.
	//Once parse is done. Poor teacher can exchange token for real laddu. 
	public static int helpPoorTeacher(int[] childRanking, int[] childLaddu){
		if(childRanking.length<=2)
			return 0;

		int f=1,b=childLaddu.length-2;
		int prev=0,next=0;

			prev = childRanking[0];
			next = childRanking[childRanking.length-1];
		
		while(f<childRanking.length-1){
			int fCurrent = childRanking[f];
			int bCurrent = childRanking[b];
			
			if(fCurrent==Integer.MAX_VALUE)
				break;
			

			if(fCurrent>prev){
				childLaddu[f]=childLaddu[f-1]+1;
			}
			

			if(bCurrent>next){
				childLaddu[b]=childLaddu[b+1]+1;
			}
			prev = childRanking[f];
			next = childRanking[b];
			f++;
			b--;
		}
		
		int totalLaddu = 0;
		for(int k=0;k<childLaddu.length;k++){
			totalLaddu = totalLaddu + childLaddu[k];
		}
		
		return totalLaddu;
	}

}

- AlgoAlgae June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Whoever down voted this, could you please let me know for what input this code fails? Or any other reason for down vote. Just curious.

- AlgoAlgae June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I get it. It doesnt work for odd number of students.
Here is the updated helpPoorTeacher method :

public static int helpPoorTeacher(int[] childRanking, int[] childLaddu){
		if(childRanking.length<=2)
			return 0;

		int f=1,b=childLaddu.length-2;
		int prev=0,next=0;

			prev = childRanking[0];
			next = childRanking[childRanking.length-1];
		
		while(f<childRanking.length-1){
			int fCurrent = childRanking[f];
			int bCurrent = childRanking[b];
			
			if(fCurrent==Integer.MAX_VALUE)
				break;
			

			if(f==b && (fCurrent>prev||bCurrent>next)){
				if(childLaddu[f-1]==childLaddu[b+1]){
					childLaddu[f]=childLaddu[f-1]+1;
				}else{
					if(childLaddu[f-1]>childLaddu[b+1]){
						childLaddu[f]=childLaddu[f-1]+1;
					}else{
						childLaddu[b]=childLaddu[b+1]+1;
					}
				}
			}else{
				if(fCurrent>prev){
					childLaddu[f]=childLaddu[f-1]+1;
				}
				
	
				if(bCurrent>next){
					childLaddu[b]=childLaddu[b+1]+1;
				}
			}
			prev = childRanking[f];
			next = childRanking[b];
			f++;
			b--;
		}
		
		int totalLaddu = 0;
		for(int k=0;k<childLaddu.length;k++){
			System.out.println(childLaddu[k]);
			totalLaddu = totalLaddu + childLaddu[k];
		}
		
		return totalLaddu;
	}

input :
5
Rank : 1 3 2 5 7
Laddus : 1 2 1 2 3
Total : 9


input :
5
Rank : 1 3 7 5 7
Laddus : 1 2 3 1 2
Total : 9


input :
4
Rank : 1 3 7 5
Laddus : 1 2 3 1
Total : 7

- AlgoAlgae June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is still incorrect. You can arrange 1, 3, 7, 5 as 1, 7, 3, 5 and give them 1, 2, 1, 2 laddu, so 6 laddu total. My python solution above works for this input; check it out

- Clay Schubiner June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree. My answer is horribly wrong. Deserves down votes. Will correct that.

- AlgoAlgae June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the update. Small change in main method and a rearrange method. helpPoorTeacher method remains same.

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int noOfGreedyBs = 4;
		int[] childRanking = new int[noOfGreedyBs];
		
		
		//childRanking[0]=Integer.MIN_VALUE;
		childRanking[0] = 1;childRanking[1] = 3;childRanking[2] = 7;childRanking[3] = 5;//childRanking[4] = 5;//childRanking[5] = 6;
		//childRanking[childRanking.length-1]=Integer.MAX_VALUE;
		
		int[] childLaddu = new int[noOfGreedyBs+2];
		childLaddu[0] = 0;
		for(int i=1;i<noOfGreedyBs+1;i++)
			childLaddu[i]=1;
		childLaddu[childLaddu.length-1] = 0;
		
		Arrays.sort(childRanking);
		
		childRanking = rearrange(childRanking);
		
		System.out.println(helpPoorTeacher(childRanking,childLaddu));
	}
	
	public static int[] rearrange(int[] childRanking){
		int[] tmp = new int[childRanking.length+2];
		tmp[0] = Integer.MAX_VALUE;
		int i=0,j,k=1;
		j = childRanking.length%2==0?childRanking.length/2:childRanking.length/2+1;
		for(;i<childRanking.length/2;i++,j++){
			tmp[k++] = childRanking[i];
			if(j<childRanking.length)
				tmp[k++] = childRanking[j];
		}
		tmp[k] = Integer.MAX_VALUE;
		return tmp;
	}

- AlgoAlgae June 20, 2014 | Flag


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