## Brain Teasers Interview Questions

- 0of 2 votes
A robot on a plane has 2 types of commands:

1. move forward by X units (X is integer 0 <= X <= 10000 )

2. rotate by X degrees (X is integer in range [-180, 180] )

A robot looks like`def robot(commands): while True: for command in commands: execute(command)`

Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.

Example:`[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no`

- 0of 0 votes
/*

Prison cell question

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.

Input example:

8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.

|1|2|3|4|5|6|7|8|

7 gold coins

another example:

20 cells, 3 prisoners to be released: 3, 6 and 14

|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|

release prisoner 3: 19 gold coins

release prisoner 6: 16 gold coins

release prisoner 14: 13 gold coins

release 14: 19 gold coins

release 6: 12 gold coins

release 3: 4 gold coins

input:

number of cells

prisoners that need to be released

output:

least number of gold coins we need to give

*/

- 0of 0 votes
Organization has online services running across world. To use online services, User create account by entering personal details like - First Name, Last Name, Phone number, Address and etc...

Russia has passed new law that any Russian citizen who is creating account to use online services, his account information needs to store in Russia first and then read-only copies allowed to replicate across the world.

Please suggest cost effective solution/design for this scenario otherwise online services will be blocked to use in Russia. How do we handle if any other country Germany is also come up with this law?

Issues:

1. Do not have mechanism to identify citizenship of user.

2. If Russia user creates an account, he/she should not wait to use online services.

What is cost effective solution?

- 0of 0 votes
Find if the characters of the sample string is in the same order in the text string.. Give a simple algo..

Eg.. TextString: abcNjhgAhGjhfhAljhRkhgRbhjbevfhO

Sample string :NAGARRO

- 0of 4 votes
You are given an array of n unique integer numbers 0 <= x_i < 2 * n

Print all integers 0 <= x < 2 * n that are not present in this array.

Example:

find_missing([0]) = [1]

find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]

find_missing([]) = []

find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]

Quirks are about requirements:

Time complexity O(n) - BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.

Space complexity O(1) - you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t).

- 1of 1 vote
You are given a flat room 1x1 metres, a position of victim in it (v_x, v_y) and a position of a killer (k_x, k_y) both inside this room (in range [0, 1]).

Then the killer shoots once at some direction. The bullet reflects of the walls as if it was a light ray - if it falls under angle X degrees, it will reflect at angle X degrees, if it gets into the corner it just reflects back. If the bullet hits guardian (see below) it stops and killer fails.

Write a function that will be given coordinates of victim and a killer and will return a list of coordinates of guardians such that it's impossible for a killer to kill victim.

That is, whichever direction the killer will shoot, the bullet will never reach victim, or will be stopped by a guardian.

Here is an example for the case when we assume the walls don't reflect bullet (for simplicity):

killer: (0, 0), victim: (1, 1). The solution to this simplified problem is to place 1 guardian between killer and victim e.g. on (0.1, 0.1).

Your task is to do this with accounting bullet reflection. E.g. in the previous case the killer can shoot at (1/3, 1), the bullet will reflect to (2/3, 0) and finally get to the victim at (1, 1).

- 1of 1 vote
`John observers the following while driving to work. • 4 were driving a red car. • 3 were driving a blue car. • 3 were driving a black car. He also notices that • 3 of them were listining to Hip Hop • 4 of them were listining to pop music. • 3 of them were listining to Rock. Additionally he notices that, • 3 of them reached office before time on Friday. • 3 of them reached office before time on Tuesday. • 2 of them reached office before time on Wednesday. • 2 of them reached office before time on Thursday. Which of the following practice maximises his chance of getting to office before time. a) He should drive a red car to work listining to pop music on a friday? b) He should drive a blue car to work listining to rock music on a Tuesday. State how did you calculate the probabiltiy for both in your answer.`

- 0of 2 votes
You have 12 marbles. They all weigh the same, except one. You don't know if that one is heavier or lighter. You have a balance scale.What would be the minimum number of weighing required to find the odd one.

- 0of 0 votes
There are three closed doors. Behind two of them there are donkeys, behind the third one there is a Mercedes-Benz. (Your task is to get the Mercedes, not the donkey).

You are asked to choose one of the doors. Once you have chosen, they open one of the remaining two doors with the donkey. Now there are two doors left: one you chose and the other one. To maximize your chance of getting the Mercedes, should you keep your choice or switch to the other door?

- -1of 1 vote
You are a prince of the kingdom of Kireet.

You are handsome and brave.

While you are studying in London, you fall in love with a girl who turns out to be a princess of Tikrit.

The term ends and you return home.

Somehow it becomes public that you the prince of Kireet is in love with the princess of Tikrit.

The kingdoms of Kireet and Tikrit are enemies since time immemorial.

A prince of Kireet taking a Tikrit princess as bride is something unheard of.

The princess is forced not to leave Tikrit.

Your job is to rescue the princess.

However, there are certain conditions that you should be aware of before you embark upon this journey.

You know that the princess is somewhere in the city of Bagore, the capital of Tikrit.

You know that she uses a smartphone.

But, her phone number is changed and you don't know the new number.

You have been removed from her contact list in facebook and your account blocked.

However, she is able to receive and read all your mails on gmail and your messages on facebook through your other facebook account.

But her firewall blocks her every attempt to reply to your mail/message.

Only her closest friends know of her where-abouts and they are asked not to divulge this information to anyone who asks for it.

However, you were able to hack into her school website and get the emails and phone numbers of some of her friends.

You even know the phone number of her father and the location of palace is known to all.

But you know that she may not be in the palace.

You somehow manage to sneak into Bagore.

Once there, you are totally anonymous. Nobody knows who you really are.

Your job is to find out the where the princess is.

Use any technology you want. Use any other resources at your hand.

Use all your spying skills and intellect.

You need to find out where the princess is.

- 0of 0 votes
Tell the following 3 letter in the sequence

A E F H I K _ _ _

- 0of 4 votes
You have 9 balls. 8 of them weigh the same, but one of them weighs heavier than the other 8.

How can we find the heaviest weighted ball in no more than 2 operations?

- 0of 0 votes
On a table there are four papers, one with the letter X written on top, one with the letter Y written on top, one with the number 1 written on top, and one with the number 2 written on top. Every paper has one of those letters on one side and one of those numbers on the other side. To prove that a paper with the letter x contains even number on the other side, what is the minimum number of conditions we have to check?

- 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

- 1of 1 vote
an bacteria grows at the speed that it will double its volume per minute. If you put it in a jar, it will fill the jar in one hour. how long will it take to fill a half of the jar?

- 0of 0 votes
How many minimum numbers from fibonacci series are required such that sum of numbers should be equal to a given Number N?

Note : repetition of number is allowed.

Example1.

N= 7;

answer = 2 (5 + 2 = 7)

Example 2.

N = 70;

Answer = 3 (34 + 34 + 2)

- 7of 7 votes
Given a string (1-d array) , find if there is any sub-sequence that repeats itself.

Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated

2. abba <---- No, a and b follow different order

3. acbdaghfb <-------- yes there is a followed by b at two places

4. abcdacb <----- yes a followed by b twice

The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.

In the sense, it should be checked for every pair of characters in the string.

- 0of 0 votes
If one and a half teenagers, eat one and a half pizzas in one and a half days, how many pizzas can 9 teenagers eat in 3 days

- 0of 0 votes
There is a two storey home. We have three switch on the first floor and three rooms on the second floor. You can go upstairs only once and can touch switches only one. How will you find out which switch is for what room?

- 1of 1 vote
The Question is to find 4 numbers between 1 and 40, so that you can get all the numbers between 1 to 40 by doing either of operation below.

1) Either any of the four number itself.

2) creating an expression by combining among the four number, with either addition or subtraction.

For example suppose we have to find four numbers so that we can get numbers between 1-30.

The answer to above question is 1,3,6,20.

- 1of 1 vote
You stand in one corner of a large room, and your assistant is in its opposite corner. In front of the assistant is a 4-corner table, with a coin in each of the 4 corners. Your objective is to get the coins to be all heads or all tails. When that happens, the coins start jumping up and down; so, you'll know for sure when it happens. What you can do is to tell your assistant: (a) flip one coin; (b) flip two coins on a side of the table; (c) flip two coins on a diagonal of the table. You can't tell the assistant which coin, which side, or which diagonal to use. You can either think of your assistant as being extremely dumb, or that the table is being constantly rotated by external forces. What is the sequence of commands that you should give to your assistant to make sure the coins start jumping up and down?

- 1of 1 vote
Distributing Medals It's the medal distribution ceremony. 10^6 police officers, numbered from 1 to 10^6, are standing in a line. There are N (1<=N<=1000) iterations of medal distribution. In iteration i (0 < = i < N), count[i] ( 1 < = count[i] < = 100) medals are given to all officers from from[i] to to[i] ( 1 < = from[i] < = to[i] < = 10^6 )

If we sum up the number of medals received starting from the first officer, who would be the first officer for which the cumulative sum exceeds a given medal count THRESHOLD ( 1 < = THRESHOLD < = 10^9 )?

Input/Output Specifications Input format:

You are given 5 inputs:

input1 = N, the number of iterations

input2 = count, the array of medal counts in each iteration

input3 = from, the array of starting indices in each iteration

input4 = to, the array of ending indices in each iteration

input5 = THRESHOLD, the medal count threshold

Output format:

An integer, representing the number of the first officer such that the cumulative sum of medals starting from the first officer upto this officer exceeds THRESHOLD. The output should be -1 if such an officer does not exist.

- -2of 2 votes
Distributing Medals It's the medal distribution ceremony. 10^6 police officers, numbered from 1 to 10^6, are standing in a line. There are N (1<=N<=1000) iterations of medal distribution. In iteration i (0 < = i < N), count[i] ( 1 < = count[i] < = 100) medals are given to all officers from from[i] to to[i] ( 1 < = from[i] < = to[i] < = 10^6 )

If we sum up the number of medals received starting from the first officer, who would be the first officer for which the cumulative sum exceeds a given medal count THRESHOLD ( 1 < = THRESHOLD < = 10^9 )?

Input/Output Specifications Input format:

You are given 5 inputs:

input1 = N, the number of iterations

input2 = count, the array of medal counts in each iteration

input3 = from, the array of starting indices in each iteration

input4 = to, the array of ending indices in each iteration

input5 = THRESHOLD, the medal count threshold

Output format:

An integer, representing the number of the first officer such that the cumulative sum of medals starting from the first officer upto this officer exceeds THRESHOLD. The output should be -1 if such an officer does not exist.

- 0of 0 votes
Given an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.

For example, "2,1,1,2", you can get (2+1)*(2+1)=9.

Follow up, if the number may be negative , how to solve it ?

- 0of 0 votes
Estimate the number of USPS boxes (i.e. ones at home address and NOT P.O. Boxes) in the U.S. You are not given USPS data, of course.

- 0of 0 votes
Design a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.

- 0of 0 votes
I've heard this from someone, guess it is not the full question but this question is quite familiar:

Given some kind of operating system that run Tasks. Every task comes with a certain time it should run. For example first task need to run 15 seconds, after 2 seconds comes another task that need to run another 30 seconds, after 7 seconds comes another task need to run another 2 seconds, etc.

You have a scheduler that runs every second and check which task need to be run and run them.

You don't have system clock and need to find a solution without it.

How would you implement it?

- 4of 6 votes
A man goes to a hardware shop and asks for price of an item. The shop keeper replies that the item is "one for $1".

The man gives the shop keeper "$3 for 600". What did the man buy for his newly painted house?

- 1of 1 vote
Generate all Kaprekar Number (refer Wiki for Kaprekar number's definition) from 1 to 999999.

I gave a brute force approach of generating all number in the range and checking if it is Kaprekar or not.

- 3of 3 votes
Given three points in a 2D plane with their (x, y) coordinates say if the origin lies inside the triangle formed by the three points.