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.