Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
public class CarData
{
private int checkOutHour;
private int returnHour;
}
public class Interval
{
private int start;
private int end;
private int cars;
}
public class RentalService
{
public int getMaxRentalPeriod(ArrayList<CarData> cd)throws IllegalArgumentException
{
if(cd==null||cd.isEmpty())
{
throw new IllegalArgumentException("input list cannot be null or empty");
}
int[] timeSlots=new int[24];//each index represents a time period from hour 0 to hour 24 (on a 24 hour clock) and the number of cars Checked out at a specific hour.
for(CarData c:cd)
{
timeSlots[checkOutHour]++;//If a car was checked out add 1 to the number at index checkOutHour
timeSlots[returnHour]--;//If a car was returned subtract 1 to the number of cars taken out at returnHour;
}
//find the contiguous LIS in the array
Interval maxTime=new Interval();
Interval currTime=new interval();
for(int i=1;i<timeSlots.length;i++)
{
if(timeSlots[i]>timeSlots[i-1])
{
currTime.cars+=timeSlots[i];
currTime.end++;
if(currTime.cars>timeSlots[i])
{
maxTime.end=currTime.end;
maxTime.cars=currTime.cars;
}else{
maxTime.start=i;
currTime.start=i;
maxTime.end=i;
currTime.end=i;
maxTime.cars=timeSlots[i];
currTime.cars=timeSlots[i];
}
}else{
currTime.start=i;
currTime.end=i;
currTime.cars=timeSlots[i];
}
}
return maxTime;
}
//Time: O(n) space: O(1)
class rental {
public:
int carid;
int start;
int end;
};
void rentalsByHour()
{
vector<rental> rentals = { { 0, 0, 1 }, { 1, 0, 2 }, { 2, 1, 2 }, { 3, 1, 5 }, { 4, 2, 5 }, { 5, 3, 6 }, { 6, 4, 8 } };
int hourlyTotals[8];
int max = 0;
for (int i = 0; i < 8; i++) {
cout << "hour: " << i << " --> ";
for (int j = 0; j < rentals.size(); j++) {
if (i >= rentals[j].start && i < rentals[j].end) {
cout << "car" << j << " ";
hourlyTotals[i]++;
if (hourlyTotals[i] >= max) {
max = hourlyTotals[i];
}
}
}
cout << endl;
}
cout << endl << "Peak hour(s) = ";
for (int i = 0; i < 8; i++) {
if (hourlyTotals[i] == max) {
cout << i << " ";
}
}
cout << endl;
}
Assuming 8 hour day, output:
hour: 0 --> car0 car1
hour: 1 --> car1 car2 car3
hour: 2 --> car3 car4
hour: 3 --> car3 car4 car5
hour: 4 --> car3 car4 car5 car6
hour: 5 --> car5 car6
hour: 6 --> car6
hour: 7 --> car6
Peak hour(s) = 4
/*
* This class represents intervals
* For eg : Car A start time 12:00 and end time 1:30
* Car B start time 2:50 and end time 3:30
* Car A start time 7:00 and end time 8:30
* There will be 3 interval objects two for Car A(as 2 different intervals) and one for Car B
*/
public class Interval {
public Interval(float startTimehrs,float startTimeMin,float endTimehrs,float endTimeMin,String carNumber) {
this.startTimehrs = startTimehrs;
this.startTimeMin = startTimeMin;
this.endTimehrs = endTimehrs;
this.endTimeMin = endTimeMin;
this.carNumber = carNumber;
}
public float startTimehrs;
public float startTimeMin;
public float endTimehrs;
public float endTimeMin;
public String carNumber;
}
public class CarRentalPlanner {
/*
* We will have a 2d array of 24 rows where each row represents time interval(we are following 24 hr format)
* and carRentalData[row][0] will store bookings
* carRentalData[row][0] will store returns
* carRentalData[row][1] will store time on road
*/
static float carRentalData[][] = new float[24][3];
public static void main(String[] args) {
Interval interval = new Interval(2,50,9,40,"XYZ");
pouplateCarRentalData(interval);
/*
* We can populate the CarRentalArray by iterating over the intervals
* we can find the max on road time from carRentalData[perios][2]
*/
}
public static void pouplateCarRentalData(Interval interval){
int startTime = (int)(interval.startTimehrs);
int endTime = (int)interval.endTimehrs;
float onRoadTime = 0;
int temp = startTime;
float bookings = carRentalData[startTime][0];
carRentalData[startTime][0] = ++bookings;
float returns = carRentalData[endTime][1];
carRentalData[endTime][1] = ++returns;
/*
* For calculating the on road time during a period i am using weighted time for a better solution
* eg : - Start Time - 4:30 , End Time - 8:15
* time periods impacted - 5
* 4 - 5 On road time : - (30/60)/5 - (min/60)/overlapping periods
* 5 - 6 1/5
* 6 - 7 1/5
* 7 - 8 1/5
* 8 - 9 (15/60)/5
*
*/
int timeIntervalsOverlap = endTime - startTime;
int timeIntervalsOverlapActual = timeIntervalsOverlap+1;
for (int i = 1; i < timeIntervalsOverlap; i++) {
onRoadTime = carRentalData[++temp][2];
onRoadTime += (1F/timeIntervalsOverlapActual);
carRentalData[temp][2] = onRoadTime;
}
onRoadTime = carRentalData[startTime][2];
onRoadTime += (interval.startTimeMin/60)/timeIntervalsOverlapActual;
carRentalData[startTime][2] = onRoadTime;
onRoadTime = carRentalData[endTime][2];
onRoadTime += (interval.endTimeMin/60)/timeIntervalsOverlapActual;
carRentalData[endTime][2] = onRoadTime;
}
}
package test;
import java.util.ArrayList;
import java.util.TreeMap;
import java.util.Map.Entry;
public class AmazonCarMaxRental {
public static void main(String[] args) {
CarRental<String> carRental1 = new CarRental<String>("car1", 1, 5);
CarRental<String> carRental2 = new CarRental<String>("car2", 5, 6);
CarRental<String> carRental3 = new CarRental<String>("car3", 6, 9);
CarRental<String> carRental4 = new CarRental<String>("car4", 4, 5);
ArrayList<CarRental<String>> list = new ArrayList<>();
list.add(carRental1);
list.add(carRental2);
list.add(carRental3);
list.add(carRental4);
process( list);
}
private static void process(ArrayList<CarRental<String>> list){
TreeMap<Integer, Integer> mapTotal = new TreeMap<>();
for (CarRental<String> carRental: list){
int index = carRental.start;
while(index<=carRental.fin){
if (mapTotal.containsKey(index) )
mapTotal.put(index, mapTotal.get(index)+1);
else
mapTotal.put(index, 1);
index++;
}
}
Entry<Integer, Integer> entryMax= mapTotal.firstEntry();
for (Entry<Integer, Integer> entryMap: mapTotal.entrySet()){
int value=entryMap.getValue();
int keyFirst = entryMax.getValue();
if (value > keyFirst)
entryMax = entryMap;
}
System.out.println(entryMax);
}
static class CarRental <T>{
T car;
int start;
int fin;
public CarRental (T car, int start, int fin){
this.car = car;
this.start = start;
this.fin = fin;
}
public int getDistance(){
return fin-start;
}
}
}
package test;
import java.util.ArrayList;
import java.util.TreeMap;
import java.util.Map.Entry;
public class AmazonCarMaxRental {
public static void main(String[] args) {
CarRental<String> carRental1 = new CarRental<String>("car1", 1, 5);
CarRental<String> carRental2 = new CarRental<String>("car2", 5, 6);
CarRental<String> carRental3 = new CarRental<String>("car3", 6, 9);
CarRental<String> carRental4 = new CarRental<String>("car4", 4, 5);
ArrayList<CarRental<String>> list = new ArrayList<>();
list.add(carRental1);
list.add(carRental2);
list.add(carRental3);
list.add(carRental4);
process( list);
}
private static void process(ArrayList<CarRental<String>> list){
TreeMap<Integer, Integer> mapTotal = new TreeMap<>();
for (CarRental<String> carRental: list){
int index = carRental.start;
while(index<=carRental.fin){
if (mapTotal.containsKey(index) )
mapTotal.put(index, mapTotal.get(index)+1);
else
mapTotal.put(index, 1);
index++;
}
}
Entry<Integer, Integer> entryMax= mapTotal.firstEntry();
for (Entry<Integer, Integer> entryMap: mapTotal.entrySet()){
int value=entryMap.getValue();
int keyFirst = entryMax.getValue();
if (value > keyFirst)
entryMax = entryMap;
}
System.out.println(entryMax);
}
static class CarRental <T>{
T car;
int start;
int fin;
public CarRental (T car, int start, int fin){
this.car = car;
this.start = start;
this.fin = fin;
}
public int getDistance(){
return fin-start;
}
}
}
public class CarsMaxSetIntersection {
static class Slot {
LocalDateTime start;
LocalDateTime end;
public Slot(LocalDateTime start, LocalDateTime end) {
this.start = start;
this.end = end;
}
}
static int findMaxIntersecton(List<Slot> input) {
// instead of the two lists we could have used a priority queue with different comparators if size is of importance
List<Slot> byStart = new ArrayList<>(input);
byStart.sort((e1, e2) -> e1.start.compareTo(e2.start));
List<Slot> byEnd = new ArrayList<>(input);
byEnd.sort((e1, e2) -> e1.end.compareTo(e2.end));
int result = 0;
int max = 0;
ListIterator<Slot> iterator = byEnd.listIterator();
for (Slot s : byStart) {
while (byEnd.get(iterator.nextIndex()).end.isBefore(s.start)) {
result--;
iterator.next();
}
max = Math.max(++result, max);
}
return max;
}
public static void main(String[] args) { }
}
public class CarsMaxSetIntersection {
static class Slot {
LocalDateTime start;
LocalDateTime end;
public Slot(LocalDateTime start, LocalDateTime end) {
this.start = start;
this.end = end;
}
}
static int findMaxIntersecton(List<Slot> input) {
// instead of the two lists we could have used a priority queue with different comparators if size is of importance
List<Slot> byStart = new ArrayList<>(input);
byStart.sort((e1, e2) -> e1.start.compareTo(e2.start));
List<Slot> byEnd = new ArrayList<>(input);
byEnd.sort((e1, e2) -> e1.end.compareTo(e2.end));
int result = 0;
int max = 0;
ListIterator<Slot> iterator = byEnd.listIterator();
for (Slot s : byStart) {
while (byEnd.get(iterator.nextIndex()).end.isBefore(s.start)) {
result--;
iterator.next();
}
max = Math.max(++result, max);
}
return max;
}
public static void main(String[] args) { }
}
My understanding of question :-
Start time can be anything, but endTime - startTime = 1 hr.
Now we need to find the intersecting time period with most number of intervals.
One way could be:
Design each interval as a node, and if interval1 and interval2 intersect, then add edge between node1 to node2.
Now find the node with max degree(max num of edges from the node). This is the interval intersecting with most others.
Now simply find intersection of all intervals of this node with its adjacent ones - to get overlap.
Assign 1 for start time, 0 for end time.
- santoshgupta.nits July 15, 2015Now sort collectively start and end times.
Use another array to store results. Traverse the entire sorted array. When u encounter 1 increase the cumulative count by 1 and when you encounter 0 decrease the cumulative count by 1.