## SDE1 Interview Questions

- 1of 1 vote
Design a data structure to keep track of top k elements out of 2 billion records.

Each record is numberd with a key which is 30 bit and a number which is count of how many times the customer has visited us.

Come up with an data structure so that the updation of element in 2 billion records will be faster.

Getting top k element will be faster

- 0of 2 votes
You are given large number of files each approx: 10MB.

Assume a million such files.

You are required to find the most frequent word or top 5 most frequent word.

How would you design the solution

- 0of 0 votes
Find whether a number (which is less than 10000) is a perfect square or not. If it is perfect square, calculate square root in O(1) without using sqrt function.

Example : 1024 => 32

1025=> not perfect square.

- 3of 3 votes
Given a String find the first non repeating char in a single pass of the string.

Assume a big character set like utf-8 (eleminate use of char[256])

Avoid any subloop to have a very optimal solution

- 0of 0 votes
Annosance problem. Like you are given a string and you have to find words starting with a vowel and move that each word untill next to the previous vowel word ..

- -1of 1 vote
Well ordered string problem

- 0of 0 votes
The Jumper Game problem.

- 0of 0 votes
I had my online test today. Do the careercup questions as they will really help you in your preparation.

Q1. 2 numbers given . First no have to be divided into 2 halves such that the sum of its halves must be less than or equal to the second half. You have to find such 2 hal pairs which are as close to the second no.

- 3of 3 votes
Given a dictionary that contains mapping of employee and his/her manager like this

Dictionary<string, string> employees = new Dictionary<string, string>()

{

{ "A","C" },

{ "B","C" },

{ "C","F" },

{ "D","E" },

{ "E","F" },

{ "F","F" }

};

Write a function to get no of employees under each manager in the hierarchy not just their direct reports.

In the above dictionary the root node/ceo is listed as reporting to himself.

Output should be a Dictionary<string,int> that contains this

A - 0

B - 0

C - 2

D - 0

E - 1

F - 5

- 0of 0 votes
Given an integer array with multiple repeated elements, print all distinct elements in array. O(n) c code/link??

- 0of 0 votes
The person who wrote this problem is going through the bad phase of his life. But, fortunately he won some cash in his last programming event.

Now to make his girlfriend feel special, he wants to buy her some chocolates. As mentioned, he is not having good time so he want to spend as less as possible.

Keeping that in mind, he decided to play a game with her. The rule of game is as follows:

1) There are N chocolates represented by type 1..N

2) He will arrange them in a row in some random order

3) Now she (his girlfriend ofcourse) has to pick an index say i, then she will get all the chocolates at index j such that j>i and type of chocolate at j is strictly less than type of chocolate at index i.

He believes that his girlfriend is not that clever and will surely not choose the most optimal index, but he wants to know that if by any chance she picked the optimal index then how many chocolates will he have to buy.

Input:

First line contain N. then next line contain N space separated integers.

output :

A single integer which is the answer.

Constraints :

1 ≤ N ≤ 105

1<=A[i]<=10^5

Sample Input (Plaintext Link)

10

7 6 10 5 2 8 1 9 3 4

Sample Output (Plaintext Link)

7

Explanation

If she chooses i=3, then all the elements in right of i have type less than 10, hence ans is 7. In none of the other case she can get more chocolates.

- 0of 0 votes
There is a dictionary with few words each of length 3 and start and finish word is given. You can reach from one word to another word by changing only one digit. Like from cat, you can reach to hat or bat or cap. What is the minimum number of steps should be taken to reach finish word from start word

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