## SDE-2 Interview Questions

- 1of 1 vote
Constructing City

In a country the cities are connected through roads of 3 types 1, 2, 3.

All the roads are bi-directional. The roads of a city has some restriction.

Road of type 3: both men and women can walk

Road of type 2: only women can walk

Road of type 1: only men can walk

Now the govt. wants to remove extra roads.But the cities should be connected for both men & women.

Connected means one should able to reach from one city to other & vice-versa.

Find out the maximum no of roads can be removed so that the cities can be accessible to both men & women.

Input:

5 5

1 2 3

2 3 3

3 4 3

5 3 2

5 4 1

First line gives no of cities & no of roads. Next each 5 lines gives city source, city destination, type for a roads.

5: no of cities 5: no of roads

1: city-1 2: city-2 3: type 3 road

o/p: 2

- 0of 0 votes
Write a program which takes input a sorted array and positive number and updates the array so that if x appears m times in array then it appears exactly min(2,m) times in array. the update should be performed in one pass with no additional memory

- 0of 0 votes
Design a system to monitor services (like when they were down/ CPU time) etc.

- 0of 0 votes
Design a system for dashboard that effectively shows almost real time data.

- 2of 2 votes
Given a sorted array with "n" elements, distributed them into "k" nearly equally weighing buckets.

Space is not constraint.

Ex: [1,3,6,9,10]

bucket size: 3

output:[10],[9,1],[3,6]

- 1of 1 vote
Add two link list, can not modify the link list, can not reverse the link list first and second.

Link list 1 - 1->2->3->7

Link list 2 - 2->9

Out put Sum - 1->2->6->6

- -2of 4 votes
Find the frequency of a number in array in less than bigo n time

Array 1,2,2,3,4,5,5,5,2

Input 5

Output 3

Array 1,1,1,1,

Input 1

Output 4

Keep in mind less than bigo n

Thanks

- 3of 3 votes
Design backend system for bookMyShow.com like system which supports below use cases:

1) When user selects cities, list of cities is displayed.

2) When user selects city, movie list is displayed.

3) When user selects movie, list of theatre is displayed.

4) When user selects theatre, show timing is displayed.

5) When show timing is selected, user is asked for no of seats that he wants to book

6) When user selects no of seats, seats are displayed to choose from.

7) When user selects seats, then total price is displayed.

8) When total price is selected, then user is directed to payment gateway and payment is done and on payment success, ticket is mailed to him.

More questions on how can we scale the system, and handle concurrent users request for same seat etc.

- 1of 1 vote
Design a movie ticket booking system like bookmyshow.com

Follow-up question -

1) How do you handle issues like scalability, concurrency, fault-tolerance etc.

2) Show movie theaters near to user where movie is playing and seats are available

3) Design database. What kind of DB would you use SQL or No-SQL

4) In real time how would you show which seats are booked which are free

5) If theaters do not have any api for fetching information then what can we do about it.

- 1of 1 vote
Design Uber. Low level Design needed (OOPS based - classes, relations, message flow etc.)

- 0of 0 votes
Design Cricinfo website

- 0of 0 votes
Design snake n ladder game to be played online

- 0of 0 votes
Given a movie X that the user had watched, write an algorithm to suggest more movies to the user. How to display the other movies based on same genre?

- 0of 0 votes
How to Design an Meeting scheduler

- 0of 0 votes
Implement a Message Broker, with Publisher and Subscriber. There can be multiple Topic or Subject in Message Broker.

- 0of 0 votes
Implement Thread safe timer with start, stop and reset functionality.

- -1of 1 vote
Find K which decides the number of open brackets are equal to the number of closed brackets.

input : (())

output : 2

Reason : if we divide the string at 2nd position, we get two open brackets and two closing brackets, and they are same .

input : (())))(

output : 4

Reason : if we divide the string(not necessarily equally) at 4rth position, we have (()) on the left side and on the right side we have ))( , as you can see, on the left half, we have two opening brackets and on the right half we have two closing brackets and they are equal .

input : ))

output : 2

Reason : there is no open brackets , so if we divide taking the whole string's length, we have )) on the left half and nothing on the right half. Now you can see that on the left half there is no open brackets and on the right half there is no closed brackets.

This question should be clear by now and remember you have to find out that K .

- 0of 0 votes
Find the Maximum number of distinct nodes in a binary tree path

- 0of 0 votes
find the given Binary tree is mirrored tree or not

should be like

60

/ \

30 30

/ \ / \

20 50 50 20

- 0of 0 votes
Given a BST (Binary Search Tree) , Each node value should replace with sum of the node which are greater-than the given node.

conditions :

No Extra space / variable can use

Modify the existing tree in optimal way.

- 0of 0 votes
Maximum triangle path Sum : Starting from the top of a pyramid of numbers like below, you can walk down going one step on the right or on the left, until you reach the bottom row:

55

94 48

95 30 96

77 71 26 67

One of such walks is 55 -> 94 >- 30 -> 26. You can compute the total of the numbers you have seen in such walk, in this case it’s 205.

Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it’s 321.

- 0of 0 votes
Design a online shipment tracking system.

- 0of 0 votes
Add 1 to the integer represented by a linked list with O(n) time, O(1) space, no recursion(stack space) and without reversing the linked list.

- 0of 0 votes
Design an OOP concept for an application where employee can dispatch their incoming phone call according to their seniority level if they are not able to solve.

- 0of 0 votes
Design a kind of kindle fire application where we can subscribe news channel and read the news from all publishers as a digital format.

- 0of 0 votes
Write a program to check whether it is a valid binary tree or not.

- 0of 0 votes
Multiply two numbers represented as a linked list.

- 0of 0 votes
A ‘plus’ pattern of size 1 is defined as following :

1

1 1 1

1

size 2 :

1

1

1 1 1

1

1

Find size of largest plus pattern in given 2D matrix which has only 0s &1s.

- 0of 0 votes
Given a sorted array which has been rotated n number of times. Find the value of n.

- 0of 0 votes
Clone the binary tree.