## SDE1 Interview Questions

- 0of 0 votes
Assume you have a starting 4 digit number, say 1234 and and ending 4 digit number 4567. For changing a bit of a number from 1 to 3 (for example), it will take 2 steps (from 1->2 and from 2->3). So to convert 1234 to 4567, you’ll have to change each and every bit individually in some number of steps. (Change 1->4 in 3 steps, 2->5 in 3 steps and so on). Now there is a list of blacklisted numbers. So while transforming start to end, if you reach a blacklisted number, then you cannot change that particular bit, you’ll have to move to another bit. E.g. Assume 1434 is a blacklisted number, and while transforming you reach it, then you have to change either 1, or 3 or the last 4. So you have to find the least number of steps in which start number can be transformed to end number.

- 0of 0 votes
I was asked to design a snake and ladder game. The game can have more obstacles than just snake and ladders.

- 0of 0 votes
There is a n player game of cards. The deck of card is not fair, i.e. any card can be there any number of times. A card has a number and a color. Each player gets k card each (n and k can be harcoded in the solution). The computer starts the game by throwing a card from the deck of cards. Assume the card is 4 of Green. Then the other player has to throw either a 4 of any color or Green of any number. If the player does not have any such card, then it can say pass. The player who finishes all his card wins. The logic of selecting the card by the user can be hardcoded (Eg, If you use a list data structure for storing the cards for a player, then you can say that the player always throws the first card from the list). The logic was required only to start and conclude the game.

- 0of 0 votes
Two players, two field; and have multiple ships located in their fields. They are guessing each others ship position and hitting. Tell who wins first. Design maintainable code which can incorporate future change.

- 0of 0 votes
Design a cricket series. Extend it to olympics.

- 0of 0 votes
Design and build tic tac toe game. The code should be up and running. It should be scalable to multi-users and nXn grid.

- 0of 0 votes
advantages and disadvantages of Circular queue according to its implementation in array and linkedlist ??

- 0of 0 votes
Two players, two field; and have multiple ships located in their fields. They are guessing each others ship position and hitting. Tell who wins first. Design maintainable code which can incorporate future change.

- 0of 0 votes
Print the bottom view of the binary tree.

Example :

1

/ \

/ \

2 3

/ \ / \

4 5 6 7

/ \ / \

8 9 10 11

/

12

Output should be :

8 12 9 10 5 6 11 7

Solution is different from http://www.geeksforgeeks.org/bottom-view-binary-tree/

- 0of 0 votes
Given an array and a target number. you have to print all sequences that generates the target number.

you can use two arithmetic operators '+' and '-' to perform operations among array elements.

Note: you can't modify the array and you have to use all the elments of the array. and the order would be same as given in the array.

Example : 1 9 1 2 , Target Number = 9

1 + 9 +1 -2 =9

output should be "1 + 9 +1 -2 "

- 6of 6 votes
You are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.

Expecting a O(nk) solution where n = number of works and k is length

There can be multiple pairs

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