---
# System prepended metadata

title: interview preparations

---

# interview preparations

## Question 1: Missing two elements in a stream
You have a huge stream of numbers coming in say n numbers which are distinct but not in order. There are two numbers missing from it. Find those missing two numbers.
https://leetcode.com/discuss/interview-question/1105693/interview-experience-with-razorpay

### Ideas:
- O(n) space. Maintain in a hashMap
- We may use bloom filter if we can afford to pay penalty for false positives.
- Since only two numbers are missing. We may just keep very few parameters and compute the missing numbers
    - Let S = sum of elements of stream
    - Then, $S + a + b$ = (sum of first n numbers) = $n * (n + 1) / 2$
    - Now, we need to find another equation to get values of a, b. (Two variables/unknowns, so we need two equations)
    - Another equation could be like sum of square of elements of stream
    - Let $S_2$ = sum of square of elements of stream
    - $S_2 + a^2 + b^2$ = sum of squares of first n numbers = $n * (n + 1) * (2n + 1) / 6$
    - Now, find a, b.
    - Space required is $2 * \log(n)$ 
- To go into deep, we have to figure out what are the producers to the stream? Are they producing algorithmically? Do we have some bound over N?
- Do we need to parallelise the solution? In that case, we have to compute these parameters in parallel, e.g. you can use spark etc.
- How much should you wait for your stream to end? A good idea is to kind of batch for some duration and then compute this and keep doing this.
- How much is the solution worth it? What are use cases? Can we find alternates?
- https://www.quora.com/Programming-Puzzles-Given-a-continuous-input-stream-of-integers-can-you-find-the-maximum-N-numbers-at-any-given-instance


-----

## Question 2: Design In Memory SQL.
Design in-memory SQL(Questions like write function to add, remove the table, select * from table, delete from a table, etc)


## Question 3: External sort



## Question 4: Notification System


## Question 5: Red Bus Design


## Basic SQL analytics related queries
https://colab.research.google.com/drive/1gqerE0k1IGzQRuJzqonKg5iImow5guvT?usp=sharing&authuser=1#scrollTo=QBH1Au59oYiG

Nice examples of SQL queries that can be asked in any interview.

## Basic overview of TCP/IP, http and https, DNS protocols. It may be useful. 