Algorithm/Data Structure Problems
1. streaming data*
*Given a streaming data of the form (timestamp, value), find the
maximum value in the stream in the last X seconds.*
*Assume time is monotonically increasing.*
*Assume time is in the order of seconds.*
*max_value() function finds the max in the last X seconds.*
*StreamProcessor(5) // last 5 seconds*
*set_value(0, 5)*
*set_value(1, 6)*
*set_value(2, 4)*
*max_value(3) = 6 -> always the current time*
(Using it in Java)
*class StreamProcessor:*
*def __init__(self, x):*
*self.x = x*
*def set_value(self, t, v):*
*pass*
*def max_value(self, cur_t):*
*pass*
2. travels between cities*
A dasher sometimes travels between cities. To avoid delays, the dasher first checks for
the shortest routes. Given a map of the cities and their bidirectional roads represented
by a graph of nodes and edges, determine which given roads are along any shortest
path. Return an array of strings, one for each road in order, where the value is YES if the
road is along a shortest path or NO if it is not.The roads or edges are named using their
1-based index within the input arrays.*
*Given a map of g_nodes = 5 nodes, the starting nodes, ending nodes and road lengths
are:*
*Road Index from-city/to-city/weight*
*1 (1, 2, 1) -> bi-directional*
*2 (2, 3, 1)*
*3 (3, 4, 1)*
*4 (4, 5, 1)*
*5 (5, 1, 3)*
*6 (1, 3, 2)*
*7 (5, 3, 1)*
*The traveller must travel from city 1 to city g_nodes, so from node 1 to node 5 in this
case.*
*The shortest path is 3 units long and there are three paths of that length: [1 → 5], [1 →
2 → 3 → 5], and [1 → 3 → 5].*
*Return an array of strings, one for each road in order, where the value is YES if a road
is along a shortest path or NO if it is not. In this case, the resulting array is*
*[roads 1, 2, 3, 4, 5, 6, 7] -> [‘YES’, ‘YES’, ‘NO’, ‘NO’, ‘YES’, ‘YES’, ‘YES’]. The third and
fourth roads connect nodes (3, 4) and (4, 5) respectively. They are not on a shortest
path, i.e. one with a length of 3 in this case.* (Bellman–Ford)
3. Give Sequence*
# Given a sequence of timestamps & actions of a dasher’s activity within a day, we
would like to know the active time of the dasher. Idle time is defined as the dasher has
NO delivery at hand. (That means all items have been dropped off at this moment and
the dasher is just waiting for another pickup) Active time equals total time minus idle
time. Below is an example. Dropoff can only happen after pickup. 12:00am means
midnight and 12:00pm means noon. All the time is within a day.
# Timestamp(12h) | Action
# 8:30am | pickup
# 9:10am | dropoff
# 10:20am| pickup
# 12:15pm| pickup
# 12:45pm| dropoff
# 2:25pm | dropoff
# total time = 2:25pm-8:30am = 355 mins;
# idle time = 10:20am-9:10am = 70 mins;
# active time = total time-idle time = 355-70 = 285 mins;