ACTUAL INTERVIEW QUESTIONS and my solution
# Question:
# Print all possible sequences of 1s and 2s that sum up to the given number N.
def print_sequence(N):
def backtrack(remaining,sequence):
if remaining==0:
print(sequence)
return
if remaining<0:
return
sequence.append(1)
baacktrack(remaining-1,sequence)
sequence.pop()
sequence.append(2)
backtrack(remaining-2,sequence)
sequence.pop()
backtrack(N,[])
print_sequences(3)
[1,1,1]
[1,2]
[2,1]
print_sequences(1)
[1]
print_sequences(0)
[]
N=0
Expected : "[[]] #an empty sequence
def test_three(self):
self.assertCountEqual(get_sequence(3),[[1,1,1],[1,2].[2.,1]]])
# Test cases:
# TC1: N = 3
# TC2: N = 1
# TC3: N = 0
# Complexity:
#
O(2^N) = Time complexity
O(N)= space complexity
# Question:
# Given a list of timestamp ranges, each range represents a user using a Google service. Write a function that returns all users using the Google services at specific query timestamp.
# Example
# A range can be represented as: [starting, ending], e.g., [1, 3] or [0, 10] and so on.
# For instance, given a list of ranges:
#
# [0, 5]
# [6, 8]
# [2, 9]
# [4, 10]
# [3, 5]
# Return: 3
# [0, 5], [2, 9], [3, 5]
def count_active_users(range,timestamp):
count=0
for r in ranges:
if r[0]<=timestamp and timestamp<=r[1]:
count=count+1
return count
# timestamp - array
def preprocess_range(ranges):
events={}
for start,end in ranges:
if start not in events:
events[start]=0
events[start]=events[start]+1
endp1=end+1
if endp1 not in events:
events[endp1]=0
events[endp1]=events-end[p1]-1
sorted_times=sorted(events.keys())
count=[]
current=0
for t in sorted_times:
current+=events[t]
counts.append(current)
return sorted_times, counts
def query_active_users(sorted_times,counts,timestamp):
idx=bisect.bisect_right(sorted_times,timestamp)-1
if idx<0:
return 0
else:
return count[idx]
range= [0, 5], [6, 8], [2, 9], [4, 10], [3, 5]
sorted_times,counts=preprocess_ranges(range)
print(query_active_users(sorted_times,counts,11))
[0,5].[2,9],[3,5],[4,10],[6,8]
def test_active_users():
range= [[0, 5], [6, 8], [2, 9], [4, 10], [3, 5]]
sorted_times,counts=preprocess_ranges(range)
asssert query_active_users(sorted_times,counts,6)==3
assert query_active_users(sorted_times,counts,0)==1
assert query-active_users(sorted_times,counts,3)==0
#overlapping
ranges=[[1,10],[2,9],[3,8],[4,7]]
sorted_times,counts=preprocess_ranges(range)
assert query_active_users(sorted_times,counts,1)==1
assert query_active_users(sorted_times,counts,11)==0
# Complexity
Time complexity= O(N log N) for sorting events
Space Complexity=O(N) for storing event data