## SDE1 Interview Questions

- 0of 0 votes
Given set of job schedules with start and end time, write a function that returns indexes of overlapping sets.

for ex :-

input -> [1,2][5,6][1,5][7,8][1,6]

return -> [0,1,2,4]

- 1of 1 vote
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 0of 0 votes
Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree.

For example:

Given tree,

1

2 3

4 5 5 4

6 6

output: true

- 1of 1 vote
Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree.

For example:

Given tree,

1

2 3

4 5 5 4

6 6

output: trus

- 1of 1 vote
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 2of 2 votes
Write a function that accepts two character arrays each represents a floating point number and return their sum in character array.

For example function accepts "23.45" and "2.5" and return their sum "25.95".

Restriction: We cannot use predefined functions / methods or parsing. We have to go with basic operations.

- 0of 0 votes
In a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

– Top speed: (150 + 10 * i) km per hour

– Acceleration: (2 * i) meter per second square.

– Handling factor (hf) = 0.8

– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number.

The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.

- 0of 2 votes
Write code to rotate a square matrix:

Input:

1 2 3

4 5 6

7 8 9

Output:

4 1 2

7 5 3

8 9 6

- 1of 3 votes
there are 1 billion stars and you are standing at the earth. From the earth , you know the distance of all 1billion stars. Find the nearest 1 million stars from the earth.

- 0of 0 votes
Given a stairs of very large size. You are standing at the 0th step. You have to perform n actions. 1st action means you can move forward to 1 step or not. 2nd action is you can move 2steps or keep standing. 3rd action is you can move 3 steps or not and so on. Given is a step no. k which is broken. You can't stand on this step. Find out after performing n actions what can be the maximum no. of steps you can go.

- 0of 0 votes
Given a binary tree populate the inorder successor of each node. Do it iteratively.

- 0of 0 votes
{1, 1, 0, 0, 0},

{1, 1, 0, 0, 0},

{1, 0, 0, 1, 1},

{0, 0, 0, 0, 0},

{1, 0, 1, 0, 1}

write a function to return the size of max cluster and coordinate of it, max cluster size to the above example is 5.

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