## SDE1 Interview Questions

- 0of 0 votes
Link all the level order nodes to makes a linked list with the first node of each level acting as the root of that linklist.

10

/ \

6 17

/ / \

4 14 19

So the Linklist will be

10->null

6->17->null

4->14->19->null

- 0of 0 votes
You have three containers, small, medium and large. Passenger comes in, checkin the luggage. You have to store the baggage in the appropriate container and generate a unique token number. Then passenger should get back the bag using the same token number. Trick was if small container is full store in medium if available or large. Now if the large bag comes in and there is now a empty space in small, than move the small bag back to small & store the large bag. How to generate the unique token number and move the baagage internally without changing the token number?

Lookup should be in constant time complexity and insertion in minimum complexity.

- 1of 3 votes
New CareerCup Android App!!!

Hey Guys,

Lately I was trying to get android app for this website and no single app was good enough for me.

So I thought of developing it myself. After 2 weekends of work I released first version of the app. With lot more new features lined up.

Please download it here

https://play.google.com/store/apps/details?id=com.careercup

and give your reviews and ratings.

Thanks

- 0of 0 votes
Your are given two strings str1 and str2, you have to generate another unique string str3, which can only generated by these two string str1 and str2, no other string can generate that string str3. Some later point you have to retrieve back those two string str1 and str2 form that unique string str3.

- 0of 0 votes
You are given an array, you have to replace each element of the array with product of the rest element. Example: {1,2,3}==> {6,3,2}

- 0of 0 votes
Suppose you have an array with infinite numbers, which is sorted and there may be duplicates. Find the occurrence of a number.

- 0of 0 votes
How will implement an auto complete feature? Eg: if you type clo it shows clothes etc

- 0of 0 votes
Suppose there are 2 streams, which has infinite value and write a method that returns a stream that would be a combination of both the streams in a sorted form

- 0of 0 votes
Write printf method.

- 1of 1 vote
Which is best Merge Sort or QuickSort?

Why and How?

- 0of 0 votes
150 men are standing in a line heightwise. A blind man has to find where he should stand in the line and for that he has to find the first taller boy than him in the line. As he can't see he is allowed to ask any number of man the question : "Are you taller than me?". Answer can be Yes or No. But he is just allowed only two YESes (BUT there is not limit on number of NOs) as reply after that he is not allowed to ask any man. Calculate fewest number of men he'll require to ask question in the worst case possible.

Options

1. 14

2. 17

3. 25

4. 33

- 0of 0 votes
How would you design a system to store the search history of your users?

- 0of 0 votes
How does Google know that you are who you say you are?

- 0of 0 votes
How would you design the search future in Google from frontend to backend?

- 0of 0 votes
(Variant of Children-Sum Problem better than O(n^2))

Given a tree, implement a function which replaces a node’s value with the sum of all its childrens’ value, considering only those children whose value is less than than the main node’s value.

Eg: input = 60->50->80->40 , output = 90->40->40->0

- 0of 0 votes
Find if a given number can be expressed in the form of p^q, where p and q are integers

- 0of 0 votes
Find all palindromes in a given string. Single letters are also considered as palindromes.

- 0of 0 votes
Given a number A, find the smallest number which has only 1s and 0s as its digits which divisible by the number A. For example: if the given number A is 4, the smallest number with 1s and 0s is which is divisible by 4 is 100.

- 2of 2 votes
{{

There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.

Your objective is to minimize the number of sort operations and number of data transfer operations.

Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.

}}

- 0of 0 votes
Entry in the log file is like this:

User 1 visited Page 4

User 3 visited Page 2

User 7 visited Page 9

.

.

.

Design an efficient data structure which supports queries like the following:

Which page was visited by exactly 2 users in day?

Which page was visited by only one user exactly 2 times in a day?

Which page was visited by ‘User 3? more than 5 times in a day?

- 0of 0 votes
Design a system for finding the costliest element always whenever we pick up an element from a box.(concept of Max Heap)

- 0of 0 votes
Entry in the log file is like this:

User 1 visited Page 4

User 3 visited Page 2

User 7 visited Page 9

.

.

.

Design an efficient data structure which supports queries like the following:

Which page was visited by exactly 2 users in day?

Which page was visited by only one user exactly 2 times in a day?

Which page was visited by ‘User 3? more than 5 times in a day?

- 1of 1 vote
Given N scientists and K black holes, each scientist can query on radius, size and temperature of a black hole, what data structure would you use?

Following queries are important.

Which scientist had queried on which black hole.

What were the queries made by that scientist.

- 0of 0 votes
In a tennis tournament of N players every player plays with every other player.

The following condition always hold-

If player P1 has won the match with P2 and player P2 has won from P3, then Player P1 has also defeated P3.

Find winner of tournament in O(N) time and O(1) space. Find rank of players in O(NlogN) time.

- 0of 0 votes
Write code for scheduling algorithms for such a cab services provided you have a list of future bookings, and list of cabs in your fleet.

- 0of 0 votes
In an auctioning system, the bidder with the highest bid wins but charged at kth highest price. Develop a system for it. Solved it using a hashmap. Was asked to write a code for the same.

- 0of 0 votes
Design a system which would make a schedule for a user to complete a book in given number of days. A pre condition is that the schedule for every day should end at the end of some chapter.

Ex – 3 chapter with 10 pages each and user has to complete this book in 2 days, then the schedule should be either be 2 chapters on first day and 1 chapter on second or 1 chapter on first day and 2 chapters on second. (code)

- 1of 1 vote
Implement DFS

After I implemented this, I was told to implement it without recursion. He told me to write pseudo code. I wrote it using stacks.

- 1of 1 vote
Given a matrix (0,0 is to the botto9m left like co-ordinate system)of 0s and 1s and two co-ordinates find if there is a path between them, Also you can only travel via 1s and you can only go up or right.

Answer: Backtracking algorithm

- 0of 0 votes
given K sorted arrays merge them

Answer: Told him how to do using merge of merge sort. He wanted me to do another approach I googled later you can use min heap for it.