Screening Round:
2 coding questions- One Binary Search based other BFS
Round1
A List of size N each with multiple time intervals is given. Each time interval denotes that this time is free. Find the maximum time interval which is free in all N lists. My solution:
Initially set the intervals free as first entry. Then traverse each entry and take out intersection of current free interval and free interval.
Time complexity: Number of entries
Round2
Design a HashMap
Functions expected:
- Get
- Remove
- Add
My Solution:
I used an ArrayList of ArrayList with hash calculated with %. The size of Map would become 3x if 75% of the map was filled and would become 0.5x if 25% of the map was filled.
Coding Round3
- Given start and end dates of when different dinosaurs came into existence and became extinct, tell maximum number of dinosaurs that existed at the same time.
My solutions:
a) Sort start and end time separately. Add pointers at beginning of each array, select lower of each time, if start, add one else subtract one. Update max at each point.
Time Complexity: N log N
b)He asked if any other solution came to mind. So I made a TreeMap(sorted HashMap) with key as time and value as +1(if existence) and -1(if extinction). Iterate through map to increase and decrease value.
Time Complexity : N log N
c) When asked to solve in O(N) I proposed array of size year, and to +1 if (if existence) and -1(if extinction).
Time Complexity: Last Extinction- First existence
Can be done with radix sort too for O(N)- realised later
- 2-D array of people. 0 is immune, 1 is healthy, 2 is sick.
Calculate number of cycles for all healthy people to become sick if it takes one cycle for sick to pass disease to Healthy person.
My Solutions:
BFS
Time Complexity: Size of 2D Array
Coding Round4
Design a game where there are multiple players, you can either add a new player, update their score or display Leadership Board(which should return scores sorted in descending order)
My Solution:
HashMap with Heap.
Complexity: N log N