Interview Question
Country: United States
Your result for input number 2 3 and 4 are wrong. Its should be 6, 8 , 11 respectively.
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.
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
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.
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]);
}
}
}
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;
}
}
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.
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
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
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;
}
Arrange students by putting the lowest ranked one first, then the highest, then the second lowest, then the second highest, and so on.
- Clay Schubiner June 19, 2014