Bloomberg LP Interview Question


Country: United States




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

# First sort the tickets by their start times

# let curr_start & curr_end be the start & end times of the current contiguous queue
curr_start = 0
curr_end = 0 

# let longest be the length of the longest contiguous queue so far
longest = 0

For each ticket (a,b):
	If a > curr_end Then
		longest = max(longest, curr_end - curr_start)
		curr_start = a
		curr_end = b
	Else
		curr_end = max(b, curr_end)
	End
End

return max(longest, curr_end - curr_start)

- Sunny December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice.

- bobthrollop April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

assuming only one ticket can be processed at a time....imagine trickets are marked as (start,end)....->
let we have tickets (1,2).,(6,8).,(11,20).,(4,6).,(2,4)..etc.

STEP1:

so,store all of these structures in an array of structures...and then sort the array according to 1st element.

STEP2:
now simply take a scan from starting element of array up to where 1st element is continous...
eg.=>(1,2),(2,4),(4,6),(6,8)....
now our result is =>8-1=7 unit time is longest continous time

- rvndr December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not a single table restaurant i suppose

- kkr.ashish December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a basic solution: i am sure there will be an elegant one for this problem
Keep a disjoint time SET (can be done without sorting) and for every entry check if there is an overlapping element in SET and then take a UNION if its there(you will need to run a further overlaping check for the updated element in SET till it keeps updating) or create a new element. The SET can be maintained in a sorted order for better performance
Steps:
new duration: SET
(1,2) : S{(1,2)}
(2,3): S{(1,3)}
(4.5): S{(1,3),(4,5)}
(4,8): S{(1,3),(4,8)}
(3,5): S{(1,3),(3,8)} : S{(1,8)}

- kkr.ashish December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

An issue with this disjoint set approach is that if you have say {(1,3), {4,8}, {9,12)} and all of a sudden you have (2,10) you would need to merge all 3 so that it becomes {(1,12)}. Still doable, just not as simple anymore.

- Sunny December 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

At the end of day sort the tickets based on start_time. (O(nlogn) )
Traverse the list and check whether the ticket time overlaps with the previous one (or) next one. Calculate the max contiguous time. (O(n)).

- Anonymous December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We have to put begin and end points to an array with flag equals to 1 when it is begin an -1 when it's end. After that sort points by time. Then we scan an array.

int balance = 0;
int max = 0;
int maxBegin = 0;
int maxEnd;

for(int i =0;i < array.lenght;i++) {
	balance = 0;
        int j = i;
	
       do{
		balance += array[j];
	}
	while(balance > 0);
	
	if(j - i > max) {
		max= j - i;
		maxBegin = i;
		maxEnd = j;	
	}
	i = j;
}

- glebstepanov1992 December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting of the initial array endup with O(nlogn) complexity. However, this problem might be resolved with O(n).
Let assume that the finest time is a second. Then array of seconds in a day will handle if and order was processed that time.
During the scan of the order list this array will be filled with info.
Second path on the "seconds" array the longest time will be calculated.
This code also is very easy to parallel, no syncronization is required.
The code:

#define NUM_OF_SECONDS (24*60*60) 
struct order_info {
    int start;
    int end;
    int price;
}
int find_longesttime(std::list<order_info> order_list){
    std::vector<bool> schedule(NUM_OF_SECONDS+1); // last entry for end condition
    std::for_each(order_list.begin(), order_list.end(), [&](const order_info& order){
        for(int i=order.start;i<=order.end;++i)
            schedule[i]=true;
    });
    // Now we should go over schedule table and find longest processing time
    int max_time=0, current_time=0;
    std::for_each(schedule.begin(), schedule.end(), [&](const bool& busy) {
        if ( busy )
            current_time++;
        else {
             if ( current_time > max_time) {
                 max_time = current_time;
             current_time = 0;
         }
    });
    return max_time;
}

- ee.fiksman December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is knapsack problem and can be solved with dynamic programming

// Input:
// Start Date (stored in array v)
// End Date (stored in array w)
// Number of distinct items (n)
// Capacity to hold customers, tables (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

- CyberPhoenix December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My recursive java solution

import java.util.HashMap;
import java.util.Map;

public class ContigentOrder {
	
	/*returns length of contigent orders starting from "start" order*/
	public int getLength(int[] start, HashMap<Integer, Integer> map, int length)
	{
		
		if(!map.containsKey(start[1])){
			return length;
		}
		int[] s=new int[2];
		//end time of input, is start time of next order
		s[0]=start[1];
		//returns end time of next order
		s[1]=map.get(start[1]);
		int len=start[1]-start[0];
		return length=length+getLength(s , map, s[1]-s[0]); 
	    	
		
	}
	
	public static void main(String[] args){
	   
		int[] o1={1,5};
		int[] o2={5,10};
		int[] o3={10,15};
		int[] o4={15,20};
		int[] o5={25,28};
		int[] o6={28,32};
		
		
		HashMap<Integer, Integer> hm=new HashMap<>();
		hm.put(o1[0], o1[1]);
		hm.put(o2[0], o2[1]);
		hm.put(o3[0], o3[1]);
		hm.put(o4[0], o4[1]);
		hm.put(o5[0], o5[1]);
		hm.put(o6[0], o6[1]);
		
		
		ContigentOrder co=new ContigentOrder();
		
		int maxLength=0;
		for(Map.Entry<Integer, Integer> m: hm.entrySet()){
		
			int[] in={m.getKey(), m.getValue()};
			int len=co.getLength(in, hm, in[1]-in[0]);
			
			if(len>maxLength){
				maxLength=len;
			}
			
		}
		
		System.out.println(maxLength);
	}

}

- ATuring September 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

one word: Greedy algorithm

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Two words: That doesn't work.

- bobthrollop April 21, 2014 | Flag


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