## Amazon Interview Question

Software Engineer / Developers**Country:**United States

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class FindMaxPersons {

public static void main(String[] args) {

List<PersonTime> data = new ArrayList<PersonTime>();

data.add(new PersonTime(0,3));

data.add(new PersonTime(2,3));

data.add(new PersonTime(0,4));

data.add(new PersonTime(1,3));

data.add(new PersonTime(3,5));

data.add(new PersonTime(3,6));

data.add(new PersonTime(4,5));

Map<Integer, Integer> timeCount = new HashMap<Integer,Integer>();

for (PersonTime pt: data){

for (int i = pt.arrivalTime ; i<= pt.departureTime ; i++){

Integer count = timeCount.get(i);

if (count==null){

timeCount.put(i, 1);

} else {

timeCount.put(i, ++count);

}

}

}

int maxPerson = 0, time = 0;

for (Map.Entry<Integer, Integer> entry : timeCount.entrySet()){

if (entry.getValue() > maxPerson){

maxPerson = entry.getValue();

time = entry.getKey();

}

}

System.out.format("time is %d, max person is %d", time, maxPerson);

}

private static class PersonTime {

int arrivalTime;

int departureTime;

public PersonTime(int arrivalTime, int departureTime){

this.arrivalTime = arrivalTime;

this.departureTime = departureTime;

}

}

}

He has a list of people and attached to those people are their arrival and departure times. He iterates through each person in the list and add a count to the map for each hour they were there. That's why you see two for loops.

Then to get the max and time and all that good stuff, he iterates through his newly created map and figures that out.

The end.

Your solution complexity is big.

This one is O = nm

public class FindMaxPersons {

public static void main(String[] args) {

List<PersonTime> data = new ArrayList<PersonTime>();

data.add(new PersonTime(0,3));

data.add(new PersonTime(2,3));

data.add(new PersonTime(0,4));

data.add(new PersonTime(1,3));

data.add(new PersonTime(3,5));

data.add(new PersonTime(3,6));

data.add(new PersonTime(4,5));

int maxTime = 0, maxPerson = 0;

for (int i = 0; i < 10; i++) {

int tempMaxPerson = 0;

for (PersonTime pt: data) {

if(pt.arrivalTime <= i && pt.departureTime >= i) {

tempMaxPerson ++;

}

}

if(tempMaxPerson > maxPerson) {

maxPerson = tempMaxPerson;

maxTime = i;

}

}

System.out.format("time is %d, max person is %d", maxTime, maxPerson);

}

private static class PersonTime {

int arrivalTime;

int departureTime;

public PersonTime(int arrivalTime, int departureTime){

this.arrivalTime = arrivalTime;

this.departureTime = departureTime;

}

}

}

I modified my code. Now the O is (mn) which m is individual visitor, n is average stay hours.

```
public class FindMaxPersons {
public static void main(String[] args) {
List<PersonTime> data = new ArrayList<PersonTime>();
data.add(new PersonTime(0,3));
data.add(new PersonTime(2,3));
data.add(new PersonTime(0,4));
data.add(new PersonTime(1,3));
data.add(new PersonTime(3,5));
data.add(new PersonTime(3,6));
data.add(new PersonTime(4,5));
Map<Integer, Integer> timeCount = new HashMap<Integer,Integer>();
int maxPerson = 0, time = 0;
for (PersonTime pt: data){
for (int i = pt.arrivalTime ; i<= pt.departureTime ; i++){
Integer count = timeCount.get(i);
if (count==null){
count = 1;
timeCount.put(i, count);
} else {
timeCount.put(i, ++count);
}
if (count > maxPerson){
maxPerson = count;
time = i;
}
}
}
System.out.format("time is %d, max person is %d", time, maxPerson);
}
private static class PersonTime {
int arrivalTime;
int departureTime;
public PersonTime(int arrivalTime, int departureTime){
this.arrivalTime = arrivalTime;
this.departureTime = departureTime;
}
}
}
```

Frank, thanks for the comments. I was in a hurry and did not have time.

Viktor, my code is slightly better since mine did not iterate for 10 times, only hours he/she spent (eg, 0-3 only 4 times)

Hi,

we can do this in O(n logn).

1. Have two arrays, one sorted on arrival time and the other sorted on departure time. O(n logn)

2. Then, we can do a walk on the arrival array from time 0 to max, finding total no of people at any moment. Will be no of arrivals till time T (index of arrival array for time T) - no of departures till time T (index of departure array for time less than or equal to T). This operation will be O(n) (by using one index each on arrival and departure arrays).

3. The max of total no of people at any moment will be the answer.

Hence order O(n logn); (Data structure mentioned in post below)

data structures:

```
struct person_time {
int person_id; /* or char person name */
datetime time;
};
vector<person_time> arrival;
vector<person_time> departure;
```

1. Take all arrival time (ai's) and sort it in the increasing order of time and load to a vector (or list) *arrival*.

2. Similarly take the departure time (di's), sort in increasing order and load to vector *departure*.

To see number or people present in the event at any given time T:

1. Do a binary search on *arrival* to get the index of highest element lower than time T. This index (say indexA) represents total number of people came/arrived to the event till time T.

2. Similarly do a binary search on *departure* to get the index of highest element lower than time T. This index (say indexD) will represent the no of people departed from the start of the event till time T.

3. (indexA - indexD) will be the total number of people present at the event at any given time.

Update:

To find the max no of people present at the event at any given time -

1. Walk through each element in *arrival*. No of people arrived till arrival[i].time will be the index of the arrival vector, ie. "i".

2. No of people departed till arrival[i].time will be the no of elements in the *departure* that have departure[j].time <= arrival[i].time. So, no people departed will be "j".

3. Total no of person at arrival[i].time = (i - j);

Max of (i-j) for each i will be the answer to this Q.

O(n logn)

I agree with the sorting of arrival time and departure time separately. But I didn't understand the part where you are trying to find the maximum number of people present at any given time. Also I don't think we are given the specific time T. We have to find the maximum number of people present at any given time.

Here's what I think to be a possible solution:

1. Sort the arrival times and departure times separately and store them in two separate arrays.

2. Loop through the array of sorted arrival times.

3. For each arrival time in the array, get the corresponding departure time.

4. Now do a binary search on the departure time array to find the index if this departure time.

5. Get the number of entries before this departure time in the departure time array.

6. If this number is greater than current max then set current max to this value.

7. After coming out of loop, return the max.

Time complexity: O(nlogn)

Space complexity: O(n)

Hi,

(indexA - indexD) will give the no of people present in the event at any moment (lets say T);

where indexA => no of people arrived till time T,

and indexD => no of people departed till time T.

Looks like the answer is not complete since the questions is "find out the maximum number of people present at any time during the entire event"

In order to find the maximum no of people present at any time in the entire event, we need to keep track of the no of people currently present at the event when each person arrived. We can keep another array (or vector) for each element in sorted arrival array that will store the no of people present (including the person just arrived) at the event when each new person arrived at the event. This will be (indexA-indexD) for all moment T when an arrival happened. Max value from this third array will be the answer to this question.

Hi Abhishek, i did not understand steps 3 to 7 you mentioned.

You need to ask this question back to the interviewer. How many times we need to find number of people at a given moment ? Or is this after the party we are going through the log ?

The queues and counters will work great if we use something more than just the log but I doubt that was the question.

The later case is you are handed a big log and given a time.

Here is the algorithm to find number of people at the event at a given time T.

1. Eliminate people who left after T.

2. Eliminate people who did not even arrive before T.

Remaining are the people who are present at the event at that moment.

O(n)

at any instance of time,if u want to know the no of ppl present then you have to check that for each person who stay his/her arrival time< current time<departure time.in this case u encounter every person and time complexty is 0(n).

another solution:---

u can preprocess the array on basis of departure time in accending order,now whenever we need to find ppl @ particular instance of time,then we will encounter only those part of array whose departure time is more than current time,this in worse case take n comparision otherwise need less comparision.

nope...thats not the way to do it...........for more ppl this doesnt scale well.

we have to do event based programming here.

Have a priority Q.

There are 3 types of events, person coming ,person leaving and the moment we need to examine.

push all these into a priority Q sorted according to time

remove each element until you get to the moment you want a count of.

Assuming that you have a some space to work with, you could have two 86,400 sized array that represents every second of the day. One that keeps track of total arrivals starting at midnight or 0 and another that keeps track of total departures starting at midnight or 0.

Then if you need to find how many people were there at a specific time you just reference the same index on both arrays and subtract the arrival by the departure. This would be constant time, but also more space consuming, but 86400 isn't all that big in modern computing.

You could get away with doing this with one array, but it wouldn't be as valuable, since you wouldn't have as many metrics other than how many people were there at a given time.

Slightly modify the LIS problem to solve this.

for each entry compare to all previous entries & calculate maximum

bool is_in_range(args1, argrs2)

{

bool flag=FALSE;

if((args1->arrival <= args2->arrival) && (args2->arrival <= args1->departue))

{

flag=TRUE;

}

else if((args2->arrival <= args1->arrival) && (args1->arrival <= args2->departue))

{

flag=TRUE;

}

return flag;

}

Time complexity O(N^2)

Space complexity O(N)

The problem itself is not difficult -- just calulate the count if the the "anytime" in user's (start, end) . Or we can sort the log by start time first to enhance the performance in case of traverse.

ButI think we have to get more detail information first

(1) the max users or the max size of the log. If the log file is too large, may consider to process in a distrubuted network and using algrithom such as mapreduce

(2) The frequency of the query.

(3) The accuracy of the time "any time". Does it accurate to sencond or minutes?

If the raw data is too big and query happens very frequently, and the accuracy is not milli-second, we can pre-process (may use mapreduce) the log first by calculate the max online users of each seconds and store it in a data stucture of memory or database, then it will provide better query performance.

I think there are different solutions based on different assumption.

```
#include<stdio.h>
#define MAX 100
int pairs[MAX];
int CalculateMaxPersons(int num,int count)
{
int i,j,max=0;
int *noPersons;
noPersons=(int *)malloc(num*sizeof(int));
for(j=0;j<num;j++) noPersons[j]=0;
for(i=0;i<count-1;i+=2)
{
for(j=pairs[i];j<pairs[i+1];j++)
noPersons[j]++;
}
for(j=0;j<num;j++)
if(noPersons[j]>max) max=noPersons[j];
printf("\n%d",max);
}
int main()
{
int val=0,index=0,i,max=0;
while(val!=-1)
{
scanf("%d",&val);
if(max<val) max=val;
pairs[index]=val;
index++;
}
CalculateMaxPersons(max,index-1);
getch();
}
```

```
#include<stdio.h>
#define MAX 100
int pairs[MAX];
int CalculateMaxPersons(int num,int count)
{
int i,j,max=0;
int *noPersons;
noPersons=(int *)malloc(num*sizeof(int));
for(j=0;j<num;j++) noPersons[j]=0;
for(i=0;i<count-1;i+=2)
{
for(j=pairs[i];j<pairs[i+1];j++)
noPersons[j]++;
}
for(j=0;j<num;j++)
if(noPersons[j]>max) max=noPersons[j];
printf("\n%d",max);
}
int main()
{
int val=0,index=0,i,max=0;
while(val!=-1)
{
scanf("%d",&val);
if(max<val) max=val;
pairs[index]=val;
index++;
}
CalculateMaxPersons(max,index-1);
getch();
}
```

tell me if i am right

Make an array that is however many seconds the event was in length -- i.e. if the event was three hours, there would be a 10,800 sized array where each index represents that very second of the event. So if the event started at 10am and ended at 1pm, then index 0 represents 10am and index 10,799 represents 1pm. With this information, you can then cycle through the file and place the logs accordingly. If you keep a rolling total of people who attended, you can insert that number into the appropriate index. When a new arrival comes, just increase the total and add it to the appropriate index. When a departure comes, just decrease the total and add it to the appropriate index.

Now if you want to get the how ever many people were there at a given time you can just refer to that time -- O(1).

If you need to get the max it will take O(n)

Space is O(43,200 bytes) assuming 32 bit integers are being used and the array is maxed out.

Python

ad=[(1,5),

(1,5),

(3,15),

(4,25),

(11,53),

(12,51),

(11,15),

(1,15),

(11,15),

(11,52),

(1,5),

(1,5),

(1,5),

]

def mxp(ad):

time=0

max_d=0

max_pres=0

for a in ad:

mxl=0

for b in ad:

if b[0]<=a[0] and b[1]>a[0]:

print a, b

mxl+=1

if mxl>max_pres:

time=a[0]

max_pres=mxl

print max_pres

print time

Let the arrival and departure times be called interval. so if (2,5) and (3,6) are two such intervals , trick is to divide the entire timespan into (2,3) (3,5) and (5,6). Let us call them sub intervals .

Sub intervals being mutually exclusive except possibly for the end points. The Max must be achieved in one such subintervals. As the end points of sub intervals are when arriving and departure events happen .

Now assume that we are processing such pairs of time for the example (2,6); (3,5); (4,7); (5,8). The algorithm tries to create all sub intervals while processing these intervals. So beinging with

1st step

(2,6) ->count 1

2nd step :

With (3,5) break (2,6) into

(2,3)->count 1; (3,5)->count 2 ; (5,6) -> count 1

3rd step : (4,7) disturbs both (3,5) and (5,6) as it overalaps both

(2,3)->count 1;

(3,4)-> count 2

(4,5)-> count 3 (one added)

(5,6)-> count 2 (one added)

(6,7) -> count 2 (one added)

4th step : (5,8)

(2,3)->count 1;

(3,4)-> count 2

(4,5)-> count 3

(5,6) -> count 3 (+1)

(6,7)-> count 3(+1)

(7,8)-> count 1

So (5,6) and (6,7) are maximum over lap intervals

Now the data structure : Use a Binary search tree with each node having sub-intervals. Since sub intervals do not overlap we define order in this way , a sub interval in the left of another sub-interval is smaller while in its right is larger. Note in this scheme there is no overlap. A s we break the overlaps into different sub-intervals . The BST should be balanced as we construct and while constructing we keep updating the count as I did in the example.

Analysis : O (nlog) in time and O(n) in space

As each insertion in the tree of a interval can lead to max of 3 sub-intervals (think a bit in terms of different types of overlap possible based on existing subintervals).

Since we always keep the tree balanced (or almost balanced say we use red-black tree scheme)

Hence construction of such a tree should be O(nlogn) .

We can maintain a variable to keep the max count and keep updating it when we see that a count of a subinterval while updating the tree is crossing the max. (Not sure about this) may be an traversal of the tree after it is constructed and then noting the max is better.

public class EventAttendance {

static int arrivalrime[]={10,12,11,13,14,12,9,14,12,10};

static int departuretime[]={15,14,17,15,15,16,13,15,17,18};

static int count=0;

public static void main(String[] args)

{

Scanner scn=new Scanner(System.in);

System.out.println("enter cjehck time");

int checktime=scn.nextInt();

for(int i=0;i<10;i++)

{

if(arrivalrime[i]<=checktime&departuretime[i]>=checktime)

{

System.out.println(arrivalrime[i]);

count++;

}}

System.out.println("No of people attended the event at"+"["+checktime+"}"+" "+ "is"+" "+" "+count);

}}

This question can be rephrased as: Given a number of time segments on time axis, find out the max number overlaps among the segments; find out the number of overlaps at a particular time t. A segment is defined as [t1, t2), t2 is exclusive. Run the following java code.

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

class Segment implements Comparable<Segment>

{

public int t1 = 0;

public int t2 = 0;

public Segment(final int a, final int d)

{

if (a < 0 || d < 0 || a >= d)

{

throw new IllegalArgumentException("Arguments should be nonnegative and t1 < t2.");

}

this.t1 = a;

this.t2 = d;

}

@Override

public int compareTo(final Segment o)

{

return t1 - o.t1;

}

@Override

public String toString()

{

final StringBuilder sb = new StringBuilder();

sb.append("(" + t1 + ", " + t2 + ")");

return sb.toString();

}

}

public class Amazon

{

int maxOverlaps(final List<Segment> events)

{

if (events.size() == 0)

return 0;

Collections.sort(events);

int max = 1;

int count = 0;

for (int i = 0; i < events.size(); i++)

{

// advance time

final int t = events.get(i).t1;

++count;

if (i == 0 || t == events.get(i - 1).t1)

{

continue;

}

// check who has left by now

for (int j = i - 1; j >= 0; j--)

{

if (t >= events.get(j).t2)

count--;

}

if (count > max)

max = count;

}

return max;

}

//overlaps at a particular time

int overlaps(final List<Segment> events, final int t)

{

if (events.size() == 0 || t < 0)

return 0;

// sort on arrival time t1

Collections.sort(events);

if (t < events.get(0).t1)

return 0;

final Segment event = new Segment(t, t + 1);

int index = Collections.binarySearch(events, event);

if (index < 0)

{

index = -(++index) - 1;

}

int count = 0;

for (int i = 0; i <= index; i++)

{

if (events.get(i).t1 <= t && t < events.get(i).t2)

count++;

}

return count;

}

/**

* @param args

*/

public static void main(final String[] args)

{

final List<Segment> events = new ArrayList<Segment>();

events.add(new Segment(0, 3));

events.add(new Segment(2, 3));

events.add(new Segment(0, 4));

events.add(new Segment(1, 3));

events.add(new Segment(3, 5));

events.add(new Segment(3, 6));

events.add(new Segment(4, 5));

System.out.println("Max number of overlapse is " + new Amazon().maxOverlaps(events));

System.out.println("Number of overlapse at 0 is " + new Amazon().overlaps(events, 0));

System.out.println("Number of overlapse at 2 is " + new Amazon().overlaps(events, 2));

System.out.println("Number of overlapse at 5 is " + new Amazon().overlaps(events, 5));

System.out.println("Number of overlapse at 7 is " + new Amazon().overlaps(events, 7));

}

}

The output is:

Max number of overlapse is 4

Number of overlapse at 0 is 2

Number of overlapse at 2 is 4

Number of overlapse at 5 is 1

Number of overlapse at 7 is 0

To Solve it in o(nlogn) :-

Since we have a pair of arival and departure time.

struct pair{

clock_t arivalTime;

clock_t departureTime;

};

Now sort the pair of array on the basis of arrivalTime. Now you can easily find the overlapping pair of arrival and departure time. You can use stack to do so. If we are getting time in between It then just increase the count if it is greater than maximum till now count then mark this time as a maximum in which you have maximum no. of passenger.

marzullo's algorithm

- algos March 02, 2013