Amazon Interview Question
InternsCountry: United States
Interview Type: Phone Interview
The Input specification was given as follows:
Input specification: the first line contains n, the total number of people (students plus teacher). You are guaranteed that n will be an odd integer greater than or equal to 3. Each subsequent line contains two numbers, separated by a space. The first of these numbers is the age of a person. It will either be a 7, an 8, or a third, unique value that corresponds to the age of the teacher. You are guaranteed that (n-1)/2 of the ages will be 7, (n-1)/2 of the ages will be 8, and 1 age will have a different value corresponding to the teacher.
The second number on each line is a floating point value representing the height of that person (in centimeters, although it really doesn't matter).
Input:
7
8 127.6
7 128.4
7 107.8
8 116.5
7 103.9
44 166.4
8 134.3
Outpu:
11
Hi ritikashah017, please try to input as my code below for testing your example. In my machine, it's show result is 11 too.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
Person[] persons = new Person[count];
for (int i = 0; i < count; i++) {
int type = sc.nextInt();
double height = sc.nextDouble();
if (type == 7) {
persons[i] = new Person(height, PersonType.SEVEN_YEAR_OLD);
} else if (type == 8) {
persons[i] = new Person(height, PersonType.EIGHT_YEAR_OLD);
} else {
persons[i] = new Person(height, PersonType.TEACHER);
}
}
System.out.println(numberOfSwap(persons));
}
Not quite sure if I understood the question right but I am assuming we want to sort them in asc/desc order of height. If that is the case why not Quick sort them? It is nlogn and requires only 5 swaps for the input given. Simplifying the input given here is how the initial array looks like: 3,4,1,2,0,6,5
After swap 1: 0,4,1,2,3,6,5
After swap 2: 0,2,1,4,3,6,5
After swap 3: 0,1,2,4,3,6,5
After swap 4: 0,1,2,4,3,5,6
After swap 5: 0,1,2,3,4,5,6
Other nlogn sorting algorithms - merge sort doesn't swap in its simple form and heap sort has more swaps than quicksort.
{
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class schoolLine {
public void getLine() throws Exception{
List<Float> list = new ArrayList<Float>();
BufferedReader buf = new BufferedReader(new FileReader("C:\\Users\\Hitesh\\Desktop\\class.txt"));
String line;
Pattern p = Pattern.compile("\\d*\\.\\d+");
while((line = buf.readLine())!= null){
String[] arr = line.split(" ");
for(int i =0;i<arr.length;i++){
Matcher m = p.matcher(arr[i]);
while(m.find()){
System.out.println(m.group());
list.add(Float.valueOf(m.group()));
}
}
}
float[] arrFinal = new float[list.size()];
for(int i=0;i<list.size();i++){
arrFinal[i] = (float)list.get(i);
System.out.println(arrFinal[i]);
}
sort1(arrFinal);
}
public void sort1(float[] list){
int high = list.length - 1;
int low = 0;
int sum =0;
List<Integer> list1 = new LinkedList<Integer>();
quickSort(list, low, high, list1);
System.out.println(list1);
for(int f : list1){
sum = sum + f;
}
System.out.println(sum);
}
private float array[];
private int length;
public static void quickSort(float[] arr, int low, int high, List<Integer> list1) {
int cnt = 0;
if (arr == null || arr.length == 0)
return ;
if (low >= high)
return ;
// pick the pivot
int middle = low + (high - low) / 2;
float pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
float temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
cnt++;
i++;
j--;
list1.add(cnt);
}
}
// recursively sort two sub parts
if (low < j)
quickSort(arr, low, j, list1);
if (high > i)
quickSort(arr, i, high, list1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
schoolLine sc = new schoolLine();
try {
sc.getLine();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
You will realize that when you want to move a person in position j to position i, our problem will become remove a person in position j and add it to position i with cost is abs(i - j). This means we can use insert sort to solve this problem.
We can solve this problem by following steps below:
+ Take all seven year old students and the teacher to the left and arranged them.
+ Store all remains eight year old students and arranged latter.
Example:
The initial class:
(1, E) (3, S) (-1, T) (9, S) (2, S) (1, E) (2, E)
Add student 2 to 1
(3, S) (1, E) (-1, T) (9, S) (2, S) (1, E) (2, E) -- cost: 1
Add student 4 to 2
(3, S) (9, S) (1, E) (-1, T) (2, S) (1, E) (2, E) -- cost: 2
Add student 5 to 2
(2, S) (3, S) (9, S) (1, E) (-1, T) (1, E) (2, E) -- cost: 4
Add teacher to end of seven year old students
(2, S) (3, S) (9, S) (-1, T) (1, E) (1, E) (2, E) -- cost: 1
Add student 7 to 5
(2, S) (3, S) (9, S) (-1, T) (2, E) (1, E) (1, E) -- cost: 2
Final answer is: 10
- techinterviewquestion.com February 12, 2016