Problems Solved

Question 1

Reservoir Sampling

Given a stream of numbers, generate a random number from the stream. You are allowed to use only O(1) space and the input is in the form of a stream, so can’t store the previously seen numbers. (since that can be unlimited)

So how do we generate a random number from the whole stream such that the probability of picking any number is 1/n. with O(1) extra space? This problem is a variation of Reservoir Sampling. Here the value of k is 1.

Answer 1

https://www.geeksforgeeks.org/select-a-random-number-from-stream-with-o1-space/

1. upon 1st number a0, x = a0
   2) Upon 2nd number a1, p=(int)Random(0,2)]; if p<1 x=a1 else x=x
   3). Upon 3rd number a2, p=(int)Random(0,3)]; if p<1, x=a2 else x=x
   …
   4) upon Nth number aN, p=(int)Random(0,3)]; if p<1, x=aN else x=x

Question 2

Write a stack client Parentheses that reads in a text stream from standard input
and uses a ______ to determine whether its parentheses are properly balanced. For example,
your program should print true for
[()]{}{()()} and false for [(]).

Answer 2

When pop, next pop must be same as the current pop

Question 3

Prints the binary representation of N (110010 when N is 50).

Answer 3

See algorithms 4ed, problem 1.3.5 Page 161

Question 4

Threesum problem:
Give an sequence of integers (Positive/negative)
find all the 3-numbers whose sum is 0

Answer 4

1. brutal force: (O(n^3))
for i = 1 to n 
  for j = 1 to n
    for k = 1 to n
      check (i+j+k) == 0

2. improved to avoid duplicates, still O(n^3)
 for i = 1 to n-2
  for j = i+i to n-1
    for k = j+1 to n
      check (i+j+k) == 0

3. use free primitive O((n^2)*logn)
quicksort(A)
 for i = 1 to n-1
  for j = i+i to n. 
    find -(i+j) in A ---> O(lgn)

Question 5

How to devise an algorithm that in a DAG, the queues for nodes closest to the output/leaf has highest priority?

Answer 5

Google MediaPipe

Consider topological sorting within the graph. For example, nodes closer to the output side of the graph have higher priority, while source nodes have the lowest priority

Question 6

Special/Edge cases

Answer 6

empty
single element
odd element
even element
duplicates in input
duplicate max/min values