## SDE1 Interview Questions

- 0of 0 votes
Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}

ar2[] = {6, 7, 20, 80, 100}

ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}

ar2[] = {3, 4, 5, 5, 10}

ar3[] = {5, 5, 10, 20}

Outptu: 5, 5

- 0of 0 votes
quicksort takes O(n2) when elements are sorted what is the solution to reduce it to O(nlogn)?

- 0of 0 votes
given a bst, convert it to a binary tree such that each element is replaced by the sum of all the elements greater than it+ its own sum?

- 0of 2 votes
Given an array of random integers and a sum value, find two numbers from the array that sum up to the given sum.

eg. array = {2,5,3,7,9,8}; sum = 11

output -> 2,9

Implement in O(n) time complexity. Find all distinct pairs. (2,9) and (9,2) are not distinct.

- 0of 0 votes
What are the advantages of an array over a linked list? and vice versa.

- 4of 4 votes
in a tree any root can have any number of children. Every node has an integer value. Find the maximum length on consecutive number sequence anywhere in the tree. For example if root is 2 and one child is 3, its child is 4 its child is 6 then max length will be 3. I was able to write the code the find of one sequence but when one sequence ends and other starts I was not able to handle that case. I think its hard to do by recursion. Is there any other trick or algorithm for this??

- 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?

- 2of 2 votes
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.