Amazon Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
import java.util.*;
public class Qus {
public static void main(String[] args) {
TreeSet set=new TreeSet();
set.add(new Csv("Alice",30));
set.add(new Csv("Bob",17));
set.add(new Csv("Clyde",49));
Iterator it= set.iterator();
while(it.hasNext())
{
Object ob=it.next();
System.out.println(ob);
}
}
}
class Csv implements Comparable
{
String name;
int age;
public Csv(String name,int age)
{
this.name=name;
this.age=age;
}
@Override
public int compareTo(Object o) {
if(o instanceof Csv)
{
Csv v=(Csv)o;
return this.age-v.age;
}
return 0;
}
public String toString()
{
return name+"\t"+age;
}
}
public static string SortByAge(string fileContent)
{
var minHeap = new SortedDictionary<int, List<string>>();
foreach(string line in fileContent.Split('\n'))
{
string[] parsed = line.Split(',');
string name = parsed[0];
int age = Convert.ToInt32(parsed[1]);
if(!minHeap.ContainsKey(age))
{
minHeap.Add(age, new List<string>() { name });
}
else
{
minHeap[age].Add(name);
}
}
StringBuilder sb = new StringBuilder();
foreach(var kvp in minHeap)
{
foreach(string name in kvp.Value)
{
sb.Append(string.Format("{0},{1}\n", name, kvp.Key));
}
}
return sb.ToString();
}
this is using heap , although a nested loop is used , the time complexity is (nlogn),
and the nested loop is just iterate all items from CSV files , the time complexity
should be O(n) and find min is O( logn)
import java.util.*;
public class Qus {
public static void main(String[] args) {
TreeSet set=new TreeSet();
set.add(new Csv("Alice",30));
set.add(new Csv("Bob",17));
set.add(new Csv("Clyde",49));
Iterator it= set.iterator();
while(it.hasNext())
{
Object ob=it.next();
System.out.println(ob);
}
}
}
class Csv implements Comparable
{
String name;
int age;
public Csv(String name,int age)
{
this.name=name;
this.age=age;
}
@Override
public int compareTo(Object o) {
if(o instanceof Csv)
{
Csv v=(Csv)o;
return this.age-v.age;
}
return 0;
}
public String toString()
{
return name+"\t"+age;
}
}
import java.util.*;
public class CSV implements Comparable<CSV>{
private String name;
private int age;
public CSV(String name,int age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(CSV o) {
if(this.age > o.getAge()){
return 1;
}else if(this.age < o.getAge()){
return -1;
}
return 0;
}
@Override
public String toString() {
return this.name + " "+this.age;
}
public static void main(String[] args) {
CSV ob1 = new CSV("Alice",30);
CSV ob2 = new CSV("Bob",17);
CSV ob3 = new CSV("Clyde",49);
List<CSV> list = new ArrayList<CSV>();
list.add(ob1);
list.add(ob2);
list.add(ob3);
Collections.sort(list);
System.out.print(list);
}
}
package com.cnu.ds.programs;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import com.cnu.ds.sorting.MergeSortVersion2;
public class PersonSortClient {
public static void main(String[] args) {
MergeSortVersion2 mergeSort = new MergeSortVersion2();
Comparable<Person>[] persons = persons();
System.out.println("Before sort");
for (Comparable<Person> person : persons) {
System.out.println(person);
}
mergeSort.sort(persons);
System.out.println("After sort");
for (Comparable<Person> person : persons) {
System.out.println(person);
}
}
public static Comparable<Person>[] persons() {
List<Comparable<Person>> persons = new LinkedList<>();
BufferedReader bufferedReader =null;
try {
bufferedReader = new BufferedReader(new FileReader(
"persons"));
String personDetails = null;
while ((personDetails = bufferedReader.readLine()) != null) {
String details[] = personDetails.split(",");
Person person = new Person(details[0],
Integer.valueOf(details[1]));
persons.add(person);
}
Person[] personss = new Person[persons.size()];
return persons.toArray(personss);
} catch (IOException e) {
e.printStackTrace();
}finally {
if (bufferedReader!=null) {
try {
bufferedReader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return null;
}
}
package com.cnu.ds.sorting;
/**
* @author cnu8
* @see It is the improved version of {@link MergeSort}
*/
public class MergeSortVersion2 extends Sort {
private static Comparable<?>[] aux;
@Override
public void sort(Comparable<?>[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
protected void sort(Comparable<?>[] a, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
sort(a, low, mid);
sort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
private void merge(Comparable<?>[] a, int low, int mid, int high) {
// !less(a[mid], a[mid + 1]) : No merge required if the last element of
// first array is
// less than or equal to the first element of second array. Because the
// complete array is already in sorted order
// !a[mid].equals(a[mid + 1]) -- check for equality of the above two
// elements
if (!less(a[mid], a[mid + 1]) || !a[mid].equals(a[mid + 1])) {
for (int i = low; i <= high; i++) {
aux[i] = a[i];
}
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (less(aux[i], aux[j])) {
a[k] = aux[i];
i++;
} else {
a[k] = aux[j];
j++;
}
k++;
}
while (i <= mid) {
a[k] = aux[i];
i++;
k++;
}
while (j <= high) {
a[k] = aux[j];
j++;
k++;
}
}
// Testing the output of array : a after merging
// for (int k2 = low; k2 <= high; k2++) {
// System.out.print(a[k2]);
// }
// System.out.println();
}
public static void main(String[] args) {
char[] aa = "MERGEEXAMPLE".toCharArray();
System.out.println("Before Sort");
Comparable<?>[] a = new Comparable[aa.length];
for (int i = 0; i < a.length; i++) {
a[i] = aa[i];
}
for (Comparable<?> comparable : a) {
System.out.print(comparable);
}
System.out.println();
MergeSortVersion2 mergeSortVersion2 = new MergeSortVersion2();
mergeSortVersion2.sort(a);
if (mergeSortVersion2.isSorted(a)) {
System.out.println("After Sort:");
for (Comparable<?> comparable : a) {
System.out.print(comparable);
}
} else {
System.out.println("Array is not sorted");
}
}
}
package com.cnu.ds.sorting;
@SuppressWarnings("rawtypes")
abstract public class Sort {
int count;
protected boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
// a[i].equals(a[i + 1]) is to allow duplicate elements
if (less(a[i], a[i + 1]) || a[i].equals(a[i + 1])) {
continue;
}
return false;
}
return true;
}
@SuppressWarnings("unchecked")
protected boolean less(Comparable i, Comparable j) {
return i.compareTo(j) < 0;
}
protected void excahnge(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public abstract void sort(Comparable<?>[] a);
}
Here is C++ solution using set
class Person {
char name[80];
int age;
public:
Person(char *_name,int _age) : age(_age) {
strcpy (name, _name);
}
Person(const Person& p1) : age(p1.age) {
strcpy (name, p1.name);
}
/* operator less than required to sort SET elements*/
bool operator < (const Person& p1) const
{
return (age < p1.age);
}
/* Display the elements */
friend ostream& operator << (ostream& ostr, const Person& p1)
{
return (ostr << p1.name << " "<< p1.age << endl);
}
};
int main () {
ifstream if1 ("input.csv");
string strLine;
set<Person> personSet;
while ( if1.good())
{
int age;
char name[80],ageStr[4];
if (getline (if1, strLine) ) {
/* read name and age in character string*/
sscanf (strLine.c_str (),"%[^,],%s", name, ageStr);
/*converting age from char string to numeric */
age= atoi (ageStr);
personSet.insert (Person(name, age));
}
}
/* iterate over the set */
for (set<Person>::iterator itr=personSet.begin (); itr!= personSet.end (); itr++)
cout << *itr;
}
The perl way:
my $hash={};
my $arr = [];
while(<STDIN>) {
chomp;
my ($name, $age) = split ',' ;
$hash->{$name} = $age;
}
print sort {$hash->{$a} cmp $hash->{$b} } keys %$hash
Using Priority queue in C++:
#include<string>
#include<iostream>
#include<queue>
#include<cstdlib>
struct Person {
std::string name;
int age;
Person(std::string n , int a):name(n), age(a) {}
};
struct personCompare {
bool operator ()(const Person &p1, const Person &p2) const {
return p1.age > p2.age;
}
};
int main() {
std::priority_queue<Person, std::vector<Person>, personCompare> pq;
std::string line;
while (std::getline(std::cin, line)) {
std::string name = line.substr(0, line.find_first_of(',',0));
int age = std::atoi(line.substr(line.find_first_of(',',0) + 1).c_str());
Person p(name,age);
pq.push(p);
}
while (!pq.empty()) {
Person p = pq.top();
std::cout << p.name << std::endl;
pq.pop();
}
}
This is a trick question.
Any one of the options work but each of them needs to be maintained (reordering a tree, sorting etc.) and not use something very crucial: it's an age field. use the fact that there's a maximum of lets say 100 (150 if you REALLY want to be optimistic :) ).
Use an array of linkedList, and just add each new value to the right place.
You can use a TreeSet instead of linkedlist and that way also each age is sorted by the name.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortObject {
public static void main(String[] args){
SortObject sort = new SortObject();
sort.SortObj();
}
public void SortObj(){
List<CSV> list = new ArrayList<>();
list.add(new CSV("Alice", 30));
list.add(new CSV("Bob", 17));
list.add(new CSV("Clyde", 49));
Collections.sort(list);
for(CSV csv: list){
System.out.println(csv.getName() + " = "+csv.getAge());
}
}
}
class CSV implements Comparable<CSV>{
private String name;
private int age;
public CSV(String name, int age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(CSV o) {
if(age > o.getAge())
return 1;
else if(age == o.getAge())
return 0;
else
return -1;
}
}
import java.util.*;
- Anonymous July 01, 2015public class Qus {
public static void main(String[] args) {
TreeSet set=new TreeSet();
set.add(new Csv("Alice",30));
set.add(new Csv("Bob",17));
set.add(new Csv("Clyde",49));
Iterator it= set.iterator();
while(it.hasNext())
{
Object ob=it.next();
System.out.println(ob);
}
}
}
class Csv implements Comparable
{
String name;
int age;
public Csv(String name,int age)
{
this.name=name;
this.age=age;
}
@Override
public int compareTo(Object o) {
if(o instanceof Csv)
{
Csv v=(Csv)o;
return this.age-v.age;
}
return 0;
}
public String toString()
{
return name+"\t"+age;
}
}