Question

Uber | Interview Experiences| SDE 2 | 2022 | Set-34

Answer 1

Screening Round ( 1hr )
Question 1

 

Given a 2D matrix with 1’s and 0’s. It’s given that there are exactly 2 islands in the matrix ( 4 directionally connected ). Find the minimum number of 0’s to flip to 1’s inorder to have a single island in the matrix.

 

Solution- BFS from any of the islands to the second. Also suggest ways to reduce iterations by considering only the edge of islands. And also suggest to use bi-drectional BFS.

 

Round 1 ( 1hr )

 

Given a Terrain (2D - land and water) implement -

 

• addLand(x, y): sets (x, y) to land
• isLand(x, y): true if (x, y) is a land, false otherwise (water)
• countIslands(): returns the number of unique islands

 

Round 2 ( 1hr )

 

Design Twitter like system. Implement below functionality -

 

1. Post a tweet
2. Like a tweet
3. Dislike a tweet
4. Get Top liked tweets for a user
5. Follow a user
6. Unfollow a user
7. Generate news feed for a user ( consisting of user’s tweets + followee’s tweets in reverse time order)