Below are some answers which I came up for the questions asked in the discussion with a doordash tag. Enjoy! I have prepared correct answers (in about a month).
1.) Get Active Time
# 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.
# Ref: https://leetcode.com/discuss/interview-question/1302606/DoorDash-onsite-interview-(new-question!)
def get_active_time(activity):
pickups = []
dropoffs = []
smallest_pickup = float('inf')
highest_dropoff = float('-inf')
for a in activity:
a = a.split('|')
a_type = a[1].strip()
a_mins = get_mins(a[0].strip())
if a_type == 'pickup':
pickups.append(a_mins)
smallest_pickup = min(smallest_pickup, a_mins)
else:
dropoffs.append(a_mins)
highest_dropoff = max(highest_dropoff, a_mins)
interval = []
for p, d in zip(pickups, dropoffs):
interval.append([p, d])
total_time = highest_dropoff - smallest_pickup
idle_time = 0
for idx in range(len(interval) - 1):
curr = interval[idx]
nxt = interval[idx + 1]
if curr[1] < nxt[0]:
idle_time += nxt[0] - curr[1]
else:
nxt[1] = max(nxt[1], curr[1])
return total_time - idle_time
def get_mins(t):
t = t.split(':')
hrs = int(t[0])
mins = int(t[1][:-2])
if t[1][-2:] == 'pm':
if hrs < 12:
hrs += 12
else:
if hrs == 12:
hrs = 0
return 60*hrs + mins
if __name__ == '__main__':
activity = [
'8:30am | pickup',
'9:10am | dropoff',
'10:20am| pickup',
'12:15pm| pickup',
'12:45pm| dropoff',
'2:25pm | dropoff',
]
idle_time = get_active_time(activity)
print(idle_time)
2.) All Shortest Path
# Ref: https://leetcode.com/discuss/interview-question/1353434/Doordash-Phone-Screen-or-Senior-Software-Engineer-or-July-2021
import collections, heapq
def find_shortest_paths(g_nodes, sources, destinations, weights):
graph = collections.defaultdict(list)
weight_between = {}
for s, d, w in zip(sources, destinations, weights):
graph[s].append(d)
graph[d].append(s)
weight_between[(s, d)] = w
weight_between[(d, s)] = w
parents = collections.defaultdict(set)
dist = collections.defaultdict(lambda: float('inf'))
dist[1] = 0
def relaxation(v, u, w):
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
parents[v] = {u}
elif dist[v] == dist[u] + w:
parents[v].add(u)
q = [(0, 1)]
relaxed = set()
while q:
_, node = heapq.heappop(q)
for nei in graph[node]:
if nei not in relaxed:
relaxation(nei, node, weight_between[(nei, node)])
heapq.heappush(q, (weight_between[(nei, node)], nei))
relaxed.add(node)
shortest_edges = set()
visited = set()
dfs(g_nodes, parents, visited, shortest_edges)
ans = []
for s, d in zip(sources, destinations):
if (s, d) in shortest_edges or (d, s) in shortest_edges:
ans.append('YES')
else:
ans.append('NO')
print(parents)
print(ans)
def dfs(node, parents, visited, shortest_edges):
if node in visited:
return
visited.add(node)
while parents[node]:
p = parents[node].pop()
shortest_edges.add((node, p))
dfs(p, parents, visited, shortest_edges)
if __name__ == '__main__':
find_shortest_paths(
5,
[1, 2, 3, 4, 5, 1, 5],
[2, 3, 4, 5, 1, 3, 3],
[1, 1, 1, 1, 3, 2, 1]
)
3.) Closest Drivers
# Ref: https://leetcode.com/discuss/interview-question/1293040/Doordash-or-Phone-Screen-or-Software-Engineer-E4-or-Closest-Drivers-to-Restaurant
import random
class Dasher:
def __init__(self, id, lastLocation, rating):
self.id = id
self.lastLocation = lastLocation
self.rating = rating
class Location:
def __init__(self, longitude, latitude):
self.longitude = longitude
self.latitude = latitude
def GetDashers():
loc1 = Location(1, 3)
d1 = Dasher(1, loc1, 4)
loc2 = Location(2, 2)
d2 = Dasher(2, loc2, 4)
loc3 = Location(4, 0)
d3 = Dasher(3, loc3, 4)
loc4 = Location(1, 1)
d4 = Dasher(4, loc4, 5)
loc5 = Location(4, 3)
d5 = Dasher(5, loc1, 2)
loc6 = Location(7, 2)
d6 = Dasher(6, loc6, 4)
loc7 = Location(4, 0)
d7 = Dasher(7, loc3, 4)
loc8 = Location(1, 1)
d8 = Dasher(8, loc4, 3)
return [d1, d2, d3, d4, d5, d6, d7, d8]
def find_k_closest_drivers(k):
dashers = GetDashers()
quick_select(0, len(dashers) - 1, dashers, k)
return dashers[:k]
def quick_select(left, right, dashers, k):
while left <= right:
pivot = random.randint(left, right)
pivot = partition(pivot, left, right, dashers)
if pivot == k:
return
elif pivot < k:
left = pivot + 1
else:
right = pivot - 1
def get_sum_hash(dasher):
loc = dasher.lastLocation
return (loc.longitude ** 2 + loc.latitude ** 2, - dasher.rating)
def partition(pivot, left, right, dashers):
pivot_ele = get_sum_hash(dashers[pivot])
dashers[right], dashers[pivot] = dashers[pivot], dashers[right]
store_idx = left
for idx in range(left, right):
if get_sum_hash(dashers[idx]) < pivot_ele:
dashers[store_idx], dashers[idx] = dashers[idx], dashers[store_idx]
store_idx += 1
dashers[store_idx], dashers[right] = dashers[right], dashers[store_idx]
return store_idx
if __name__ == '__main__':
howmany_dashers = 3
dashers = find_k_closest_drivers(howmany_dashers)
for dasher in dashers:
print(
f'dasher_id: {dasher.id}, rating: {dasher.rating},'
f'location: {dasher.lastLocation.latitude},'
f' {dasher.lastLocation.longitude}'
)
4.) Longest Valid Order
# Find longest valid subarray
# Ex 1: orders = ['P1', 'P1', 'D1'], return ['P1', 'D1']
# Ex 2: orders = ['P1', 'P1', 'D1', 'D1'], return ['P1', 'D1']
# Ref: https://leetcode.com/discuss/interview-question/914113/Longest-valid-orders-path-(Doordash)
def longest_valid_order(orders):
longest_idxs = [0, 0]
for start in range(len(orders)):
for end in range(start + 1, len(orders)):
pickups = set()
deliveries = set()
is_valid = True
for idx in range(start, end + 1):
order_type = orders[idx][0]
order_id = orders[idx][1:]
if order_type == 'P':
if order_id not in pickups and order_id not in deliveries:
pickups.add(order_id)
else:
is_valid = False
break
else:
if order_id in pickups and order_id not in deliveries:
deliveries.add(order_id)
else:
is_valid = False
break
if is_valid and len(pickups) == len(deliveries):
update_logest_idxs(longest_idxs, start, end + 1)
ans = []
for idx in range(longest_idxs[0], longest_idxs[1]):
ans.append(orders[idx])
print(ans)
def update_logest_idxs(longest_idxs, start, end):
if longest_idxs[1] - longest_idxs[0] < end - start:
longest_idxs[0] = start
longest_idxs[1] = end
if __name__ == '__main__':
orders = ['P1', 'P1', 'P2', 'D3', 'P1', 'P2', 'D2', 'D1', 'P4', 'D3', 'D1']
longest_valid_order(orders)
5.) Median finder with followups:
# find running median of a data stream
# case 1: data stream contains only nums btw 0 and 100
# case 2: 99% nums are btw 0 to 100
# Ref: https://leetcode.com/problems/find-median-from-data-stream/
class MedianSearch:
def __init__(self):
self.middle = [0] * 101
self.middle_ct = 0
self.left = []
self.right = []
def add_num(self, num):
if num < 0:
self.edge_insert(self.left, num)
elif num > 100:
self.edge_insert(self.right, num)
else:
self.middle[num] += 1
self.middle_ct += 1
def add_num2(self, num):
self.middle[num] += 1
self.middle_ct += 1
def get_median2(self):
first = second = None
if self.middle_ct % 2 != 0:
first = (self.middle_ct // 2) + 1
else:
first = (self.middle_ct // 2)
second = first + 1
first_val = second_val = None
curr = 0
ith = 0
while ith < len(self.middle):
curr += self.middle[ith]
if curr >= first:
first_val = ith
if second is not None:
if curr >= second:
second_val = first_val
else:
ith += 1
while ith < len(self.middle):
curr += self.middle[ith]
if curr >= second:
second_val = ith
break
ith += 1
break
ith += 1
if second is None:
return first_val
else:
return (first_val + second_val) / 2
def edge_insert(self, arr, num):
arr.append(num)
i = len(arr) - 1
while i > 0 and arr[i - 1] > num:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
i -= 1
def get_median(self):
total_nums = self.middle_ct + len(self.left) + len(self.right)
first = (total_nums // 2) + 1
second = None
if total_nums % 2 == 0:
second = first - 1
first_val = self.find_idx(first)
if second is not None:
second_val = self.find_idx(second)
else:
return first_val
return (first_val + second_val) / 2
def find_idx(self, ith):
if ith <= len(self.left):
return self.left[ith - 1]
elif ith > len(self.left) + self.middle_ct:
return self.right[ith - len(self.left) - self.middle_ct - 1]
else:
curr_ct = len(self.left)
for ith_val in range(0, 101):
if self.middle[ith_val] + curr_ct >= ith:
return ith_val
curr_ct += self.middle[ith_val]
if __name__ == '__main__':
ms = MedianSearch()
input = [
('add_num', 5), ('add_num', 0), ('get_median'), ('add_num', 99),
('add_num', 50), ('add_num', 20), ('get_median'), ('add_num', 19),
('add_num', 5), ('add_num', 95), ('get_median'), ('add_num', 0),
('add_num', 100), ('add_num', 20), ('get_median'), ('add_num', 19),
]
queries = [
"addNum","findMedian","addNum","findMedian","addNum",
"findMedian","addNum","findMedian","addNum","findMedian",
"addNum", "findMedian", "addNum", "findMedian","addNum", "findMedian"
]
values = [[-1],[],[-2],[],[-3],[],[-4],[],[-5],[]]
values = [
[-1],[],[2],[],[3],[],[4],[],[5],[],
[100], [], [33], [], [333], []
]
values = [
[1],[],[-2],[],[-3],[],[4],[],[5],[],
[100], [], [332], [], [133], []
]
# values = [
# [1],[],[2],[],[3],[],[4],[],[5],[],
# [100], [], [33], [], [33], []
# ]
# queries = ["addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
# values = [[155],[],[66],[],[114],[],[0],[],[60],[],[73],[],[109],[],[26],[],[154],[],[0],[],[107],[],[75],[],[9],[],[57],[],[53],[],[6],[],[85],[],[151],[],[12],[],[110],[],[64],[],[103],[],[42],[],[103],[],[126],[],[3],[],[88],[],[142],[],[79],[],[88],[],[147],[],[47],[],[134],[],[27],[],[82],[],[95],[],[26],[],[124],[],[71],[],[79],[],[130],[],[91],[],[131],[],[67],[],[64],[],[16],[],[60],[],[156],[],[9],[],[65],[],[21],[],[66],[],[49],[],[108],[],[80],[],[17],[],[159],[],[24],[],[90],[],[79],[],[31],[],[79],[],[113],[],[39],[],[54],[],[156],[],[139],[],[8],[],[90],[],[19],[],[10],[],[50],[],[89],[],[77],[],[83],[],[13],[],[3],[],[71],[],[52],[],[21],[],[50],[],[120],[],[159],[],[45],[],[22],[],[69],[],[144],[],[158],[],[19],[],[109],[],[52],[],[50],[],[51],[],[62],[],[20],[],[22],[],[71],[],[95],[],[47],[],[12],[],[21],[],[32],[],[17],[],[130],[],[109],[],[8],[],[61],[],[13],[],[48],[],[107],[],[14],[],[122],[],[62],[],[54],[],[70],[],[96],[],[11],[],[141],[],[129],[],[157],[],[136],[],[41],[],[40],[],[78],[],[141],[],[16],[],[137],[],[127],[],[19],[],[70],[],[15],[],[16],[],[65],[],[96],[],[157],[],[111],[],[87],[],[95],[],[52],[],[42],[],[12],[],[60],[],[17],[],[20],[],[63],[],[56],[],[37],[],[129],[],[67],[],[129],[],[106],[],[107],[],[133],[],[80],[],[8],[],[56],[],[72],[],[81],[],[143],[],[90],[],[0],[]]
for i in range(len(queries)):
query = queries[i]
if query == 'addNum':
value = values[i][0]
ms.add_num(value)
else:
print(ms.get_median())
6.) Nearest City
# Ref: https://leetcode.com/discuss/interview-question/1379696/DoorDASH-Onsite
import collections, random
def find_nearest_cities(x_list, y_list, cities, query_cities):
xi = collections.defaultdict(list)
yi = collections.defaultdict(list)
city_cords = {}
for x, y, c in zip(x_list, y_list, cities):
xi[x].append((y, c))
yi[y].append((x, c))
city_cords[c] = (x, y)
for xk in xi.keys():
xi[xk].sort()
for yk in yi.keys():
yi[yk].sort()
ans = []
for q_city in query_cities:
if q_city not in city_cords:
ans.append(None)
x, y = city_cords[q_city]
nearest_city = get_nearest_city(xi, yi, x, y, q_city)
ans.append(nearest_city)
return ans
def get_nearest_city(xi, yi, x, y, q_city):
mins = {
'city': None,
'dist': float('inf'),
}
find_mins(0, len(xi[x]) - 1, xi[x], y, q_city, mins)
find_mins(0, len(yi[y]) - 1, yi[y], x, q_city, mins)
return mins['city']
def find_mins(left, right, axis_n_cities, axis_to_compare, q_city, mins):
while left <= right:
mid = random.randint(left, right)
mid_city = axis_n_cities[mid][1]
mid_axis = axis_n_cities[mid][0]
if mid_city == q_city:
if mid > 0:
mid_city = axis_n_cities[mid - 1][1]
mid_axis = axis_n_cities[mid - 1][0]
mid_dist = abs(axis_to_compare - mid_axis)
update_mins(mid_dist, mid_city, mins)
if mid < len(axis_n_cities) - 1:
mid_city = axis_n_cities[mid + 1][1]
mid_axis = axis_n_cities[mid + 1][0]
mid_dist = abs(axis_to_compare - mid_axis)
update_mins(mid_dist, mid_city, mins)
break
if mid_axis < axis_to_compare:
left = mid + 1
else:
right = mid - 1
def update_mins(mid_dist, mid_city, mins):
if mid_dist < mins['dist']:
mins['dist'] = mid_dist
mins['city'] = mid_city
elif mid_dist == mins['dist']:
mins['city'] = min(mins['city'], mid_city)
if __name__ == '__main__':
cities = ['axx', 'axy', 'az', 'axd', 'aa', 'abc', 'abs']
xs = [0, 1, 2, 4, 5, 0, 1]
ys = [1, 2, 5 ,3, 4, 2, 0]
query_cities = ['axx', 'axy', 'abs']
nearest_cities = find_nearest_cities(xs, ys, cities, query_cities)
print(nearest_cities)
7.) Pickup & Delivery Permutaions
# print all valid order paths e.g.: delivery after pickup given n
def get_all_patterns(n):
picked_up = set()
delivered = set()
patterns = []
pattern = []
find_pattern(picked_up, delivered, pattern, patterns, n)
return patterns
def find_pattern(picked_up, delivered, pattern, patterns, n):
if len(pattern) == n * 2:
patterns.append('->'.join(pattern))
else:
for task in range(1, n + 1):
pickup = 'P' + str(task)
delivery = 'D' + str(task)
if pickup not in picked_up:
picked_up.add(pickup)
pattern.append(pickup)
find_pattern(picked_up, delivered, pattern, patterns, n)
pattern.pop()
picked_up.remove(pickup)
if pickup in picked_up and delivery not in delivered:
delivered.add(delivery)
pattern.append(delivery)
find_pattern(picked_up, delivered, pattern, patterns, n)
pattern.pop()
delivered.remove(delivery)
if __name__ == '__main__':
print(get_all_patterns(3))
# Time:
# O((N) ^ 2*N)
# Space:
# O(2* N) => O(N) to hold a single pattern
# 2n -1 5 3 1
# for p: N! for d => p1, p2..pn-1..pn
# 2n-1 2n - 3 ..... 3, 1
# p1 p2....p3..pn
8.) Stream last x max
# 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.
# Ref: https://leetcode.com/discuss/interview-question/1302614/DoorDash-Onsite-Interview-(new-question-again!)
import collections
class StreamProcessor:
def __init__(self, x):
self.x = x
self.deque = collections.deque()
def set_value(self, t, v):
while self.deque and t - self.deque[0][0] > self.x:
self.deque.popleft()
while self.deque and self.deque[-1][1] < v:
self.deque.pop()
self.deque.append((t, v))
def max_value(self, cur_t): # this will be always current time
while self.deque and cur_t - self.deque[0][0] > self.x:
self.deque.popleft()
if not self.deque:
return -1
return self.deque[0][1]
if __name__ == '__main__':
sp = StreamProcessor(5)
sp.set_value(0, 5)
sp.set_value(1, 6)
sp.set_value(2, 4)
sp.set_value(5, 5)
sp.set_value(9, 19)
sp.set_value(15, 4)
sp.set_value(16, 25)
sp.set_value(19, 6)
sp.set_value(20, 4)
print(sp.max_value(22))
9.) Time increament
# Ref: https://leetcode.com/discuss/interview-question/1387937/Doordash-new-Q
def get_increments(times):
days = {
'mon': 1,
'tue': 2,
'wed': 3,
'thu': 4,
'fri': 5,
'sat': 6,
'sun': 7,
}
start = clean_time(times[0], days)
end = clean_time(times[1], days, True)
end_borders = set()
for minutes in range(1, 6):
end_borders.add(add_delta(end, minutes))
ans = []
curr = start
while curr not in end_borders:
ans.append(int(curr))
curr = add_delta(curr, 5)
print(ans)
def clean_time(t, days, is_end=False):
t = t.split()
day = days[t[0]]
hrs_mins = t[1].split(':')
hrs = int(hrs_mins[0])
mins = int(hrs_mins[1])
if t[2] == 'pm':
if hrs < 12:
hrs += 1
else:
if hrs == 12:
hrs = 0
nearest = mins % 5
if nearest < 3:
mins -= nearest
else:
if not is_end:
return add_delta(
str(day) + get_str(hrs) + get_str(mins), 5 - nearest
)
return str(day) + get_str(hrs) + get_str(mins)
def add_delta(t, delta_mins):
day = int(t[0])
hrs = int(t[1:3])
mins = int(t[3:])
if mins + delta_mins < 60:
mins += delta_mins
return str(day) + get_str(hrs) + get_str(mins)
else:
mins = 0
if hrs + 1 < 24:
hrs += 1
return str(day) + get_str(hrs) + get_str(mins)
else:
hrs = 0
if day + 1 < 8:
day += 1
return str(day) + get_str(hrs) + get_str(mins)
else:
day = 1
return str(day) + get_str(hrs) + get_str(mins)
def get_str(i):
if i < 10:
return '0' + str(i)
return str(i)
if __name__ == '__main__':
times = ['tue 00:29 am', 'mon 11:56 pm']
get_increments(times)
10.) Valid order
# given an pickup delivery, return whether it is valid or not
def validate(pattern):
picked_up = set()
delivered = set()
for task in pattern:
task_type = task[0]
task_id = task[1:]
if task_type == 'P':
if task_id not in picked_up:
picked_up.add(task_id)
else:
return False
else:
if task_id not in delivered and task_id in picked_up:
delivered.add(task_id)
else:
return False
return len(picked_up) == len(delivered)
if __name__ == '__main__':
pattern = [
'P1', 'P3', 'P2', 'D3', 'P4', 'P404', 'D2', 'D1', 'D404', 'D4',
'P33', 'D33',
]
print(validate(pattern))
Prepare these ones and LC doordash tagged.
(Please go to Ref: link too see question statement)
Comments (10)