All possible paths for a robot moving along a NxN grid
Posted on March 26, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.
Solution
We solved the similar question here, where we had to find the count of number of paths.
[Read More]How many lockers are open after 100 passes of toggles
Posted on March 26, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?
[Read More]Two egg puzzle
Posted on March 26, 2014
(Last modified on August 7, 2020)
| 8 minutes
| Kinshuk Chandra
Problem: There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
Solution This is similar as binary search. If we have unlimited number of eggs, we only need 7 (log 100 to base 2) to find N i.
[Read More]How long does it take to remove c ‘magical’ hats from n people
Posted on March 26, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., _at least one person has a ha_t). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight.
[Read More]Get 4qt of water using a 5qt jug and a 3qt jug
Posted on March 25, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water?
NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible.
Solution: I first thought we can come up with 2qt water by filling up the 5qt jug and pouring 3qt water to the 3qt jug.
[Read More]Covering a chess board with dominos
Posted on March 25, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: There is an 8×8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible)
Solution: No, it’s not possible. Two diagonally opposite squares on a chess board are of the same color.
[Read More]Swap odd and even bits in an integer
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
Input : An integer x
Output : An integer y, which odd and even bit swapped (with 0th bit being least significant bit)
Example
Input 1: 10 = 1010 Output 1: 5 = 0101 (0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped) Input 2: 14 = 1110 Output 2: 13 = 1101 Solution
[Read More]Find missing integer in an array with only access to jth bit of element A[i]
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer.
[Read More]Count number of bits to be flipped to convert A to B
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
You are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B.
Example
Input: 73, 21 Output: 4 Representing numbers in bits : A = 1001001 B = 0010101 C = \* \*\*\* C = 4 Solution
Method 1 - Counting the bits set after XORing 2 numbers
1. Calculate XOR of A and B.
[Read More]Explain ((n & (n-1)) == 0)
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem :
Explain what the following code does: ((n & (n-1)) == 0).
Solution
When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s.
It works because a binary power of two is of the form 1000...000 and subtracting one will give you 111.
[Read More]