Curefit (Sugarfit) | Phone round (Backend developer) | Pool Table
Anonymous User
943

Two questions were asked to me in the first round:
Given a Pool Table, Lot of balls are present on the table.
(x,y) coordinates are given for each ball.
Each ball has the capability to destroy other balls if they are on the same x or y axis. The ball which is destroying other balls will remain in its position.
Any ball can destroy any other ball any number of times in any order, such that at the end a minimum number of balls should be present.

Eg =>
Input

0,0
1,1
0,1
1,0
2,2

0,0 => 0,1
0,0 => 1,0

3 balls left - non optimal

0,0 => 0,1
1,0 => 1,1
0,0 => 1,0

0,0 2,2 2 balls left

0,0
5,0
7,0
4 2
5,2
9,2
7,5
9,5
ans: 0

Q2: Desqign a data structure which supports -

Insert an element
Delete an element
Search an element
Find Min
Find Max

(Hint: Use custom min heap and max heap, use unordered_map to strore the number and it's correspoding location in heap)

Comments (3)