Bloomberg LP Interview Question
Country: United States
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
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)}
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;
}
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;
}
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
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);
}
}
- Sunny December 07, 2013