## A9 Interview Question for Interns

• 1
of 1 vote

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){
}
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;
}
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...

Comment hidden because of low score. Click to expand.
0

Hey Zortlord you really like PriorityQueues! :D

Comment hidden because of low score. Click to expand.
0

@gigi84

Heaps can be like magic in lots of cases.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 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);
}``````

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) {
}

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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:

``````-> 100
-> 0
-> 0
-> 0
-> 0
-> 200
-> 0
-> 0
-> 0
-> 0
-> 300
->-100
-> 0
-> 0
-> 0
-> 0
->-100
-> 0
-> 0
-> 0
-> 0
->-400
-> 0
-> 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;
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>();
System.out.println(intervals);
System.out.println("MaxFlow: "+maxFlow(intervals));
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

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
2. for each range add up the flow
3. get the max out of the array.

int H={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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int day = {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);
}``````

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".

Comment hidden because of low score. Click to expand.
0

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.

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;

}``````

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]),]``````

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

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.

### 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.