YOUTUBE SDE 1 Interview Experience

Round 1: Technical Interview

1. Introduction

• Tell me about yourself.
• Briefly introduce your educational background, technical skills, and projects.

2. DSA – Dutch National Flag Algorithm

Question: Sort an array containing only 0s and 1s using the Dutch National Flag algorithm.

• Explain the approach.
• Discuss the time and space complexity.

3. DSA – Running Median of a Stream

Question:

You will be given N numbers, one at a time. Each time you are given a number, write out the median of all the numbers received so far.

• The total time complexity of the algorithm should be O(N log N).
• Also, argue why the algorithm cannot be O(N).

Expected approach: Use two heaps:

• Max Heap to store the smaller half of the numbers.
• Min Heap to store the larger half of the numbers.
• Balance the heaps after every insertion.
• Calculate the median based on the sizes of the two heaps.