CareerCup

marzullo's algorithm

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;
}
}
}

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)

binary search twice on arrival time and depart time

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.

For eg. people came (arrival, departure)
(1,5), (3,10), (4,6),(4,7), (2,15),(13,16), (20,30)

So for eg. the maximum people at the event were at time 4 . ie ppl at (1,5), (3,10), (4,6),(4,7),(2,15), totaling 5 people .

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.

variation of marzullo's algorithm.
Sort arrival times and Departure times..
Lets say these are arrays A and B.

Do merge check of these arrays..
Int Best =0; count=0;
for (i=0;j=0;i<num;)
{
if (Ai<=Bj) { count++; i++;}
else {count--; j++}
if (count>Best) Best=Count;
}

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.

while(there are more people in list)
	find min of departure time
	find count of people who arrived before the departure time
	if count > max : max = count
	remove the person from list

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.

O(n)

count = 0
for(Person p : persons)
{
if(p.getArrivalTime() <= moment && p.getDepartureTime() >= moment )
{
count++;
}
}

classis problem of interval tree.