dumUser
BAN USER- 0of 0 votes
AnswersGiven a List of Students that are already sorted based on names, write a function to return list of students that is sorted based on grade (four possible grades are a,b,c and d). If two students has same grade, they should be sorted internally based on name.
I have written a code based on bucket sort. Something like this. Not sure whether this is optimal.
- dumUser in United Statespublic List<Student> sortByGrade(List<Student> students) { List<Student> aGradeStudents = new LinkedList<Student>(); List<Student> bGradeStudents = new LinkedList<Student>(); List<Student> cGradeStudents = new LinkedList<Student>(); List<Student> dGradeStudents = new LinkedList<Student>(); for(Student st : students) { switch(st.getGrade()) { case 'a' : aGradeStudents.add(st); break; case 'b' : bGradeStudents.add(st); break; case 'c' : cGradeStudents.add(st); break; case 'd' : dGradeStudents.add(st); break; }; } List<Student> sortedStudents = new LinkedList<Student>(); sortedStudents.addAll(aGradeSudents); sortedStudents.addAll(bGradeSudents); sortedStudents.addAll(cGradeSudents); sortedStudents.addAll(dGradeSudents); }
| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven an array of sorted numbers, find the index of first occurrence of the given number.
- dumUser in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
I have created a recursive version of satveer code, please correct me if I am wrong,
public static int binSrchFirstIndex(int[] arr, int st, int end, int key, int pos){
if(st > end)
return -1;
int mid = (st+end)/2;
if(arr[mid] == key){
if(pos == -1){
pos = mid;
}
else if(mid < pos){
pos = mid;
}
}
//Performing full left search first
int pos1 = binSrchFirstIndex(arr,st,mid-1,key,pos);
if(pos == -1 && pos1 >=0){
return pos1;
}
else if(pos1 >=0 && pos1 < pos){
return pos1;
}
//Goes here only if we are not able to find element in Left full search.
pos1 = binSrchFirstIndex(arr,mid+1,end,key,pos);
if(pos == -1 && pos1 >=0){
return pos1;
}
else if(pos1 >=0 && pos1 < pos){
return pos1;
}
return pos;
}
Hi tiwaripradeep123,
They wanted an efficient solution with less space consumption and time consumption. I also proposed a solution of having a binary search, traversing towards left first to find a presence of element and travelling towards right. But its worst case is O(n) not O(log n) like binary search. Because we are traversing all element atleast once. Please correct me if I am wrong.
Hi,
I have written a recursive program for it. But this program works on an assumption that if we have a shift from single digit to double digit. It treats it as two transition, say for example,
012345678910.
It assumes the transition from 9 to 1 as 1 and transition from 1 to 0 as another one.
- dumUser June 09, 2014