A9 Interview Question for Interns


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 3 vote

Assumptions:
1. The times are not hours, but some measure. could be day, could be millis, etc
2. The flow rates are always positive

Simple algorithm that will running in O(n log n):
1. Sort all the events by their start time into a priority queue (earliest First) (heap1)
2. create a Priority Queue of events sorted by their end time (earliest first) (heap2)
4. create a value to track the best flow rate total
5. create a value to track the running flow rate total
6. while contents still exist in the heap1
___a. find the earliest value from heap1 and heap2
___b. while heap1 starts with the earliest starting time
______i. remove the event from heap1 with that starting time.
______ii. add the flow rate from the event to the running value total
______iii. add the event to heap2
___c. while heap2 starts with the earliest ending time
______i. remove the event from heap2 with that ending time
______ii. remove the flow rate from the even from the running total
___d. if the running flow rate total is better than the best flow rate total, store it
7. return the best flow rate total

static class Event{
	int startTime, endTime, rate;
}

public static int getMaxFlow(Event[] events){
	PriorityQueue<Event> heap1 = new PriorityQueue<Event>(events.length, new Comparator<Event>(){
		public int compare(Event e1, Event e2){
			return e2.startTime-e1.startTime;
		}
	});
	PriorityQueue<Event> heap2 = new PriorityQueue<Event>(events.length, new Comparator<Event>(){
		public int compare(Event e1, Event e2){
			return e2.endTime-e1.endTime;
		}
	});
	for(Event event : events){
		heap1.add(event);
	}
	int bestFlowRate = Integer.MIN_VALUE;
	int totalFlowRate = 0;
	while(!heap1.isEmpty()){
		int earliest = heap1.peak().startTime;
		if(!heap2.isEmpty() && heap2.peek().endTime < earliest){
			earliest = heap2.peek().endTime;
		}
		while(!heap1.isEmpty() && heap1.peek().startTime == earliest){
			Event event = heap1.poll();
			totalFlowRate += event.rate;
			heap2.add(event);
		}
		while(!heap2.isEmpty() && heap2.peek().endTime == earliest){
			Event event = heap2.poll();
			totalFlowRate -= event.rate;
		}
		if(totalFlowRate > bestFlowRate){
			bestFlowRate = totalFlowRate;
		}
	}
	return bestFlowRate;
}

Edit: PriorityQueue constructor using a comparator must also have a capacity specified...

- zortlord December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Zortlord you really like PriorityQueues! :D

- gigi84 December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gigi84

Heaps can be like magic in lots of cases.

- zortlord December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, they can be really useful sometime, I should start using them more ;)

- gigi84 December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution! You have a couple of minor bugs
1. the compare function should be:

public int compare(Event e1, Event e2){
			return e1.startTime-e2.startTime;
		}

and

public int compare(Event e1, Event e2){
			return e1.endTime-e2.endTime;
		}

Right now you have a max heap instead of a min heap

2. You need to do this check for the best flowrate right after you look through heap1 as well. If you run the example case your solution will return 500 instead of 600

- rizhang December 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

move
if(totalFlowRate > bestFlowRate){
bestFlowRate = totalFlowRate;
}
between two inner while loops.

- Kang May 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not only use one PriorityQueue and push both start and endtimes on it?
Endtimes are sorted behind starttimes and have negative values (as the value that was pushed with starttime must be removed again.

Here is some code (untested)

class Entry implements Comparable {
	final int value;
	final long timestamp;
	final boolean isStartEvent;

	public Entry(int value, long timestamp, boolean isStartEvent) {
		this.value = value;
		this.timestamp = timestamp;
		this.isStartEvent= isStartEvent;
	}
	
	@Override
	public int compareTo(Entry e) {
		if(timstampe != e.timestamp) return timestamp - e.timestamp;
		return isStartEvent ? -1 : 1; // start events must be smaller then end events
	}
}

// given
class Flow {
	long start;
	long end;
	int value;
}

public static int maxFlow(List<Flow> flows) {
	PriorityQueue<Entry> queue = new PriorityQueue<>();

	// push all start and end times on queue
	for(Flow f : flows) {
		queue.add(new Entry( f.value, f.start, true);
		queue.add(new Entry( -f.value, f.end, false);
	}

	int maxSum = 0;
	int curSum = 0;
	// process queue
	while( !queue.isEmpty()) {
		Entry e = queue.poll();
		curSum = curSum + e.value;
		maxSum = Math.max(maxSum, curSum);	
	}
	return maxSum;
}

- Flo January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes this approach works for sure. The solution provided by @Zortlord will also work. But this is easier to understand.

- arsragavan January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But will the solution give max flow at an instant of time ?

- Anonymous June 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would create an array of size 24 to represent the hours of the day;
then for each interval I would add the flow of the interval at the start hour of that interval in the array and subtract the flow of that interval at the end+1 hours of that interval.

After I have populated the array in this way I will find the maxFlow in the array just by scanning the array and keeping the running sum. The max value of the running sum is the MaxFlow.
O(n) time complexity, O(1) space complexity. We could use a sorted Collection to avoid all the empty values in the array but in this case we will lose time to keep the keys sorted, an insertion will take O(logn) and the final time complexity would be O(nlogn). As we are computing intervals just for 24 hours we can assume the cost of having some non used slots in an array of size 24.

Example:

0,10,100 
10,15,300 
16,20,400 
5,15,200

the array would be populated with the following values:

[0]-> 100
[1]-> 0
[2]-> 0
[3]-> 0
[4]-> 0
[5]-> 200
[6]-> 0
[7]-> 0
[8]-> 0
[9]-> 0
[10]-> 300
[11]->-100
[12]-> 0
[13]-> 0
[14]-> 0
[15]-> 0
[16]->-100
[17]-> 0
[18]-> 0
[19]-> 0
[20]-> 0
[21]->-400
[22]-> 0
[23]-> 0

and the running sum will be:

100,100,100,100,100,300,300,300,300,300,600,500,500,500,500,500,400,400,400,400,400,0,0,0

just keep the max while computing the running sum.

This is the code for this solution:

import java.util.*;

class FlowInterval {
	int start;
	int end;
	int flow;
	public FlowInterval(int start, int end, int flow) {
		this.start=start;
		this.end=end;
		this.flow=flow;
	}
	public String toString() {
		return "("+this.start+","+this.end+"):"+this.flow;
	}
}
public class MaxFlow {
	public static int maxFlow(List<FlowInterval> intervals) {
		int maxFlow = 0;
		int currentFlow = 0;
		int[] hours = new int[24];
		for(FlowInterval flowint: intervals) {
			hours[flowint.start]+=flowint.flow;
			hours[flowint.end+1]-=flowint.flow;
		}
		for(int i=0;i<hours.length;i++) {
			currentFlow = currentFlow+hours[i];
			if(currentFlow>maxFlow) {
				//System.out.println("Found new MaxFlow of "+currentFlow+" at "+String.format("%02d", i)+":00");
				maxFlow=currentFlow;
			}
		}
		return maxFlow;
	}
	public static void main(String[] args) {
		FlowInterval f1 = new FlowInterval(0,10,100);
		FlowInterval f2 = new FlowInterval(10,15,300);
		FlowInterval f3 = new FlowInterval(16,20,400);
		FlowInterval f4 = new FlowInterval(5,15,200);
		List<FlowInterval> intervals = new ArrayList<FlowInterval>();
		intervals.add(f1);
		intervals.add(f2);
		intervals.add(f3);
		intervals.add(f4);
		System.out.println(intervals);
		System.out.println("MaxFlow: "+maxFlow(intervals));
	}
}

- gigi84 December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have never mentioned it as instance of hour. I just said it's an instance of time. What if the times are given in seconds ? Will you maintain a array of total no of seconds in a day ? I feel this is not the right approach.

- arsragavan December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is very primitive code for this problem-
idea is-
1. array[24]
2. for each range add up the flow
3. get the max out of the array.


int H[24]={0};

int main()
{
int min, max, value, cmax=0, i, moment;
while(scanf("%d %d %d", &min, &max, &value) != EOF)
{
for(i=min; i<=max; i++)
H[i]+=value;
}
for(i=0; i<24; i++)
{
if( cmax < H[i])
{
cmax = H[i];
moment= i;
}
}

printf("\nmax flow is at moment %d, and vlaue is %d\n", moment, cmax);

return 0;
}

- jp December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>


int day[24] = {0};

main()
{
int start,end,amount,i,max=0,instinct;;
printf("enter the start,end and amount\n");
while(scanf("%d%*c%d%*c%d",&start,&end,&amount) != EOF)
{
        for(i= start;i<=end;i++)
        {
                day[i]+= amount;
        }
}

for(i=0;i<24;i++)
{
        if(day[i]>max)
        {
                max = day[i];
                instinct = i;
        }
}

printf("instinct %i max %i",instinct,max);
}

- kshitiz gupta December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

0. Store all the intervals as a list of 2 element arrays. Call this list "intervals". It would look something like {[0,10],[10,15],[16,20],[5,15]}. Also create a list called "flows", {100,300,400,200}.
1. Store all the start and end times in a list. Sort the list and remove duplicate elements from it. Call this list "times", {0,5,10,15,16,20}.
2. Create a zero initialized list of integers of the same size as "times". The flow rates for all these "times" will be stored in the corresponding elements of this list. Call this list "new_flows".
3. Iterate through all the elements of "times". For every element of "times", iterate through all the elements of "intervals" and check if the time lies in this particular interval. If it does, increment the corresponding element of "new_flows" by the corresponding value in "flows".
4. Find the maximum value in the array "new_flows".

- Anirudh December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have given a brute force approach. The complexity is O(n^2).
There is no use of sorting it based on start time. You can directly compare if the interval is overlapping with other interval and add the values.

- arsragavan December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a C++ implementation of the above algorithm

#include <iostream>
using namespace std;
#include <list>
#include <stdio.h>
#include <fstream>
#include <string>
#include <vector>


int main(int argc, const char * argv[])
{

    list<int> start,end,flow;
    string line;
    string filename = "file.txt";
    fstream myfile(filename);
    if(myfile.is_open())
    {
        while(true)
        {
            int s,e,f;
            char c = ',';
            myfile>>s>>c>>e>>c>>f;
            start.push_back(s);
            end.push_back(e);
            flow.push_back(f);
            if(!getline(myfile,line))
            {
                break;
            }
        }
        myfile.close();
    }
    else{
        cout<<"Could not open file\n"<<endl;
    }
    list<int> times;
    list<int>::iterator i;
    cout<<"Start"<<endl;
    for(i = start.begin();i!=start.end();i++)
    {
        times.push_back(*i);
        cout<<*i<<"\t";
    }
    cout<<endl;
    cout<<"End"<<endl;
    for(i = end.begin();i!=end.end();i++)
    {
        times.push_back(*i);
        cout<<*i<<"\t";
    }
    cout<<endl;
    cout<<"Flow"<<endl;
    for(i = flow.begin();i!=flow.end();i++)
    {
        cout<<*i<<"\t";
    }
    
    times.sort();
    times.unique();
    cout<<endl;
    cout<<"Times"<<endl;
    for(i = times.begin();i!=times.end();i++)
    {
        cout<<*i<<"\t";
    }
    cout<<endl;
    int num_intervals = start.size();
    int size = times.size();
    vector<int> new_flow(size);
    int j;
    for(j=0;j<size;j++)
    {
        new_flow[j]=0;
    }
    vector<int> intervals(2*num_intervals);
    list<int>::iterator x;
    list<int>::iterator y;
    x = start.begin();
    y = end.begin();
    j = 0;
    while(x!=start.end())
    {
        intervals[j] = *x;
        intervals[j+1] = *y;
        x++;
        y++;
        j = j+2;
    }
    
    j = 0;
    for(x = times.begin();x!=times.end();x++)
    {
        y = flow.begin();
        for(int k=0;k<2*num_intervals;k+=2)
        {
            
            if(*x<intervals[k] || *x>intervals[k+1])
            {
                
            }
            else
            {
                new_flow[j] = new_flow[j]+(*y);
            }
            y++;
        }
        j++;
    }
    cout<<endl;
    cout<<"New flows"<<endl;
    int max = 0;
    for(j=0;j<size;j++)
    {
        cout<<new_flow[j]<<"\t";
        if(new_flow[j]>max)
        {
            max = new_flow[j];
        }
    }
    cout<<endl;
    cout<<"The maximum flow is "<<max<<endl;
    
    
    return 0;
    
    
    
    
}

- Anirudh December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void maxFlowInAInstance() {

		class Flow{
			private int start; 
			private int end;
			private int flow;
			Flow(int start,int end, int flow){
				this.start=start;
				this.end=end;
				this.flow=flow;
			}
			
			public int getStart() {
				return start;
			}

			public int getEnd() {
				return end;
			}
			
			public int getFlow() {
				return flow;
			}
			
		}
		
		Flow[] flows = { new Flow(0,10,100), new Flow(10,15,300), new Flow(16,20,400), new Flow(5,15,200)};
		int maxFlow=0;
		int instance=0;
	    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(Flow flow : flows){
			for(int start=flow.getStart();start<flow.getEnd();start++ ){
				Integer abc = map.containsKey(Integer.valueOf(start)) ?						
						map.put(start, map.get(start)+flow.getFlow()):map.put(start, flow.getFlow());
						if(map.get(start) > maxFlow){
							
							maxFlow=map.get(start);
							instance=start;
						}
			}
		}
		System.out.println("************* Max Flow : "+ maxFlow +"  , instance:"+instance);
	}

- Abdul Mohsin December 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

R

a <- matrix(c(0,10,100,10,15,300,16,20,400,5,15,200), ncol=3, byrow=T)
> a
[,1] [,2] [,3]
[1,]    0   10  100
[2,]   10   15  300
[3,]   16   20  400
[4,]    5   15  200


alla <- data.frame()
for(i in 1:nrow(a)){
  sa <- seq(a[i,1], a[i,2], by = 1)
  ta <- data.frame(sa, rep(a[i,3], length(sa) ))
  alla <- rbind(alla, ta)
}
names(alla) <- c('time', 'flow')

ag <- aggregate(alla$flow, by=list(alla$time), FUN=sum)
ag[which.max(ag[,2]),]

- Mr.JoshuaGordon January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Written in C++ using heap data structure.

struct Entry{
    int start;
    int end;
    int flow;
};

struct CompStart
{
    bool operator()(const Entry& a, const Entry& b)
    {
        return a.start > b.start;
    }
};

struct CompEnd
{
    bool operator()(const Entry& a, const Entry& b)
    {
        return a.end > b.end;
    }
};

int findMaxFlow(vector<Entry> entries)
{
    vector<Entry> entriesStart(entries);
    vector<Entry> entriesEnd(entries);

    make_heap(entriesStart.begin(), entriesStart.end(), CompStart());
    make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());

    int runningFlow = 0;
    int maxFlow = 0;
    int time = 0;
    while(!entriesStart.empty())
    {
        time = entriesStart.front().start;
        runningFlow += entriesStart.front().flow;

        pop_heap(entriesStart.begin(), entriesStart.end(), CompStart());
        entriesStart.pop_back();
        make_heap(entriesStart.begin(), entriesStart.end(), CompStart());

        while(!entriesEnd.empty() && time >= entriesEnd.front().end)
        {
            time = entriesEnd.front().end;
            runningFlow -= entriesEnd.front().flow;

            pop_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());
            entriesEnd.pop_back();
            make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());

            if(runningFlow > maxFlow)
                maxFlow = runningFlow;
        }

        if(runningFlow > maxFlow)
            maxFlow = runningFlow;
    }

    return maxFlow;
}

int main()
{
    vector< Entry > entries = {{0,10,100}, {10,15,300}, {16,20,400}, {5,15,200}};

    cout << findMaxFlow(entries) ;

    return 0;
}

- mahmutdemir January 31, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More