Dissect a square into similar rectangles with sides in the ratio of 2 to
1 such that no two rectangles are the same size. A solution with nine rectangles
is known.
Tuesday, September 15, 2009
Permutations
How many ways can four points be arranged in the plane so that the
six distances between pairs of points take on only two different values?
Many crypto doorknob locks use doors with five buttons numbered
from 1 to 5. Legal combinations allow the buttons to be pushed in specific
order either singly or in pairs without pushing any button more than once.
Thus [(12), (34)] = [(21), (34)]; [(1), (3)]; and [(2), (13), (4)] are legal combinations
while [(1), (14)]; [(134)]; and [(13), (14)] are not.
(a) How many legal combinations are there?
(b) If a sixth button were added, how many legal combinations would
there be?
six distances between pairs of points take on only two different values?
Many crypto doorknob locks use doors with five buttons numbered
from 1 to 5. Legal combinations allow the buttons to be pushed in specific
order either singly or in pairs without pushing any button more than once.
Thus [(12), (34)] = [(21), (34)]; [(1), (3)]; and [(2), (13), (4)] are legal combinations
while [(1), (14)]; [(134)]; and [(13), (14)] are not.
(a) How many legal combinations are there?
(b) If a sixth button were added, how many legal combinations would
there be?
Cointainers again
You have a 37-pint container full of a refreshing drink. N thirsty customers
arrive, one having an 11-pint container and another having a 2Npint
container. How will you most efficiently measure out 1 pint of drink
for each customer to drink in turn and end up with N pints in the 11-pint
container and 37-2N pints in the 37-pint container if
(a) N = 3;
(b) N = 5?
arrive, one having an 11-pint container and another having a 2Npint
container. How will you most efficiently measure out 1 pint of drink
for each customer to drink in turn and end up with N pints in the 11-pint
container and 37-2N pints in the 37-pint container if
(a) N = 3;
(b) N = 5?
Nine single-digit numbers
Find nine single-digit numbers other than (1, 2, 3, ..., and 9) with a sum
of 45 and a product of 9! = 362,880.
of 45 and a product of 9! = 362,880.
Number:)
My regular racquetball opponent has a license plate whose three-digit
part has the following property. Divide the number by 3, reverse the digits
of the result, subtract 1 and you produce the original number. What is
the number and what is the next greater number (possibly with more than
three digits) having this property?
part has the following property. Divide the number by 3, reverse the digits
of the result, subtract 1 and you produce the original number. What is
the number and what is the next greater number (possibly with more than
three digits) having this property?
Cointainers
You have containers that hold 15 pints, 10 pints, and 6 pints. The 15-
pint container starts out full, and the other two start out empty: (15, 0,
0). Through transferring liquid among the containers, measure exactly two
pints for yourself to drink and end up with 8 pints in the 10-pint container
and 5 pints in the 6-pint container. Find the most efficient solution.
pint container starts out full, and the other two start out empty: (15, 0,
0). Through transferring liquid among the containers, measure exactly two
pints for yourself to drink and end up with 8 pints in the 10-pint container
and 5 pints in the 6-pint container. Find the most efficient solution.
Friday, September 11, 2009
Shaastra 2009 puzzles
1. Consider the way the numbers 0,1,2,5,6,8,9 appear on a 7 led display. Place
these numbers in a 3X3 matrix such that the sum of the numbers in the first two
rows gives the number in the third row and if the paper on which this is written is
inverted, the sum still works. In other words, the inverted second and inverted third
row add up to give the inverted first row.
2. Mike, Steve, Dilbert, Charlie and Stuart gathered in a farm house at the outskirts
of the city to divide the loot and plan the next robbery. However, they came to
know that it could be dangerous for them to venture into the roads that night. Since
they were anyway going to stay, they decided to sleep and discuss the next day.
Mike woke up at night. He casually inspected the items and among other things,
notices a huge sack of gold coins. He wanted to get his share right then. So he
divided the coins into five sets, but one coin was left. He added the extra coin to
one set and hid that for himself. He went back to sleep.
Steve woke up (without knowing what had happened) after Mike. His attention also
was drawn to the sack. He divided the rest of the gold coins evenly into five sets,
but one coin was left. He added the extra coin to one set and hid that for himself.
He went back to sleep.
Dilbert woke up (without knowing what had happened) after Steve. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
Charlie woke up (without knowing what had happened) after Dilbert. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
Stuart woke up (without knowing what had happened) after Charlie. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
When they all awoke in the morning, they determined to divide the rest of the gold
coins evenly into 5 sets. Each of them got a set. Again one coin was left. How they
resolved the fate of the last gold coin is a story in itself. But can you find out the
number of gold coins each person got so far?
3. Grandpa Willard says he knows how to make the best applesauce in town. So
he's down at the Half-Off Dale's Deli telling his pals about it, and pretty soon there's
a big argument over which apples and which ingredients make the best applesauce.
At one point Dale had to ask them to be quiet as they were scaring off the other
customers. So, using the following clues, see if you can which apples and which key
ingredients go with which grandpa.
The ingredients that begin with a capital letter are varieties of apples (eg: Yellow
Transparent, Gravenstein) and the others are flavors (eg: lemon, cinnamon).
- Cooper hates Northern Spy apples and horseradish.
- Neither Smith nor Ted would allow lemon in his applesauce.
- McGee uses twice as many apples as John Willard.
- Neither Dick nor Cooper likes almond.
- Neil and Cooper can't stand Granny Smith apples.
- The one using almond extract, not Rod or McGee, uses 1 lb. apples.
- Grandpa John uses 0.5 lb. more apples than Grandpa Frandsen.
- The grandpa using 2.5 lbs. does not care for cinnamon.
- The one using three teaspoons of horse radish also uses Northern Spy apples.
- The grandpa using brown sugar (2 c) uses 1.5 lbs more apples than the one using
Granny Smith apples.
- Ted and Cooper both disdain Yellow Transparents.
- Neil likes Northern Spy apples. He uses three times as many as the one who uses
almond extract.
- Delicious apples and brown sugar go together, claims Rod.
- Grandpa Smith uses 4 oz. of flavoring with his Gravenstein sauce, 3 oz. more than
Ted.
(Hint: There are only 5 grandpas present, including Grandpa Willard.)
4. A square birthday cake measures 12 inches by 12 inches and is 6 inches high.
Three children wish to share the cake equally. But simply dividing the cake into
three pieces isn't good enough; the cake has chocolate frosting on all sides except
the bottom, and each child wants to have the same amount of chocolate frosting as
well as the same amount of cake. Since there is a rose made of icing in the center
of the top of the cake, and the birthday boy wants the entire rose, no cut may pass
through or touch where the rose is. How will you divide the cake?
5.An alien ship has invaded earth and has taken humans as prisoners. They are put
in numerous circular cells suspended by some mechanism. The cell is being filled by
a poisonous gas which will kill them slowly, but surely. The wall of the cell, which is
a cylinder, has four push buttons placed symmetrically. the push buttons have two
states ,"on" or "off". But the occupants would not come to know, by any means,
what state the push button is presently in. The prisoners would be free if the push
buttons are all in the same state, i.e. all "on" or all "off". The prisoners are allowed
to press any button any number of times in a bid to get free. But the problem is
after every wrong "try", the wall of the cell will spin for 30 seconds and come to a
halt. This ensures the prisoners have no way of telling which buttons they tried. A
"try" consists of 1,2,3 or all four of the buttons being pushed simultaneously. When
a button is pushed, its state changes, i.e. on becomes off and vice versa. Tell
whether they will be able to get out of the cell within 5 minutes (the time within
which the deadly gas will surely kill everyone). Support your answer with suitable
explanation.
these numbers in a 3X3 matrix such that the sum of the numbers in the first two
rows gives the number in the third row and if the paper on which this is written is
inverted, the sum still works. In other words, the inverted second and inverted third
row add up to give the inverted first row.
2. Mike, Steve, Dilbert, Charlie and Stuart gathered in a farm house at the outskirts
of the city to divide the loot and plan the next robbery. However, they came to
know that it could be dangerous for them to venture into the roads that night. Since
they were anyway going to stay, they decided to sleep and discuss the next day.
Mike woke up at night. He casually inspected the items and among other things,
notices a huge sack of gold coins. He wanted to get his share right then. So he
divided the coins into five sets, but one coin was left. He added the extra coin to
one set and hid that for himself. He went back to sleep.
Steve woke up (without knowing what had happened) after Mike. His attention also
was drawn to the sack. He divided the rest of the gold coins evenly into five sets,
but one coin was left. He added the extra coin to one set and hid that for himself.
He went back to sleep.
Dilbert woke up (without knowing what had happened) after Steve. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
Charlie woke up (without knowing what had happened) after Dilbert. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
Stuart woke up (without knowing what had happened) after Charlie. His attention
also was drawn to the sack. He divided the rest of the gold coins evenly into five
sets, but one coin was left. He added the extra coin to one set and hid that for
himself. He went back to sleep.
When they all awoke in the morning, they determined to divide the rest of the gold
coins evenly into 5 sets. Each of them got a set. Again one coin was left. How they
resolved the fate of the last gold coin is a story in itself. But can you find out the
number of gold coins each person got so far?
3. Grandpa Willard says he knows how to make the best applesauce in town. So
he's down at the Half-Off Dale's Deli telling his pals about it, and pretty soon there's
a big argument over which apples and which ingredients make the best applesauce.
At one point Dale had to ask them to be quiet as they were scaring off the other
customers. So, using the following clues, see if you can which apples and which key
ingredients go with which grandpa.
The ingredients that begin with a capital letter are varieties of apples (eg: Yellow
Transparent, Gravenstein) and the others are flavors (eg: lemon, cinnamon).
- Cooper hates Northern Spy apples and horseradish.
- Neither Smith nor Ted would allow lemon in his applesauce.
- McGee uses twice as many apples as John Willard.
- Neither Dick nor Cooper likes almond.
- Neil and Cooper can't stand Granny Smith apples.
- The one using almond extract, not Rod or McGee, uses 1 lb. apples.
- Grandpa John uses 0.5 lb. more apples than Grandpa Frandsen.
- The grandpa using 2.5 lbs. does not care for cinnamon.
- The one using three teaspoons of horse radish also uses Northern Spy apples.
- The grandpa using brown sugar (2 c) uses 1.5 lbs more apples than the one using
Granny Smith apples.
- Ted and Cooper both disdain Yellow Transparents.
- Neil likes Northern Spy apples. He uses three times as many as the one who uses
almond extract.
- Delicious apples and brown sugar go together, claims Rod.
- Grandpa Smith uses 4 oz. of flavoring with his Gravenstein sauce, 3 oz. more than
Ted.
(Hint: There are only 5 grandpas present, including Grandpa Willard.)
4. A square birthday cake measures 12 inches by 12 inches and is 6 inches high.
Three children wish to share the cake equally. But simply dividing the cake into
three pieces isn't good enough; the cake has chocolate frosting on all sides except
the bottom, and each child wants to have the same amount of chocolate frosting as
well as the same amount of cake. Since there is a rose made of icing in the center
of the top of the cake, and the birthday boy wants the entire rose, no cut may pass
through or touch where the rose is. How will you divide the cake?
5.An alien ship has invaded earth and has taken humans as prisoners. They are put
in numerous circular cells suspended by some mechanism. The cell is being filled by
a poisonous gas which will kill them slowly, but surely. The wall of the cell, which is
a cylinder, has four push buttons placed symmetrically. the push buttons have two
states ,"on" or "off". But the occupants would not come to know, by any means,
what state the push button is presently in. The prisoners would be free if the push
buttons are all in the same state, i.e. all "on" or all "off". The prisoners are allowed
to press any button any number of times in a bid to get free. But the problem is
after every wrong "try", the wall of the cell will spin for 30 seconds and come to a
halt. This ensures the prisoners have no way of telling which buttons they tried. A
"try" consists of 1,2,3 or all four of the buttons being pushed simultaneously. When
a button is pushed, its state changes, i.e. on becomes off and vice versa. Tell
whether they will be able to get out of the cell within 5 minutes (the time within
which the deadly gas will surely kill everyone). Support your answer with suitable
explanation.
AlgorithmhtiroglA
1...Find the K'th Maximum Element in a Binary Search Tree . Do it in O(log N).
2...Find a two-line program to output the Nth Fibonacci number.
3...Given text, count the words inside.
you are reminded ".", ",", "?" could also be separator, plus number like "123,456,789.012" where '.'/',' not considered as separator...
The question is more about requirement and definition.
E.g. how many words in the string below?
"ab $2,300.58?2,,300.58 123?.235"
4...Find the longest palindromic substring in a string.
5...Given a n*m matrix having numbers such that each row and each column sorted. Now print the numbers in present in the matrix in sorted order.
6...Given a binary tree, prove that it is a BST(Binary search tree), without using inorder traversal either recursively or iteratively..?
7...Given an n*n matrix A. Each row of the matrix and each column of the matrix is sorted.
Given a number S, you are required to find S in the matrix( report k, l such that A[k,l] = S) or conclude S is not in A.
How can you solve it in O(n)?
8...A String as given as input in the form of Hex Decimal format and you need to print the ASCII format.
9...Print a binary tree in zig zag way... that is:
......a.........
....b....c.......
..d...e...f...g..
.h.i.j.k.l.m.n.o.
should be printed as a-c-b-d-e-f-g-o-n-m-l-k-j-i-h
what data structure will u use for that?
10...Write a function to reverse a line(i.e "How are you" will become "you are How")
11...give you two strings, one source string, one pattern string, check if they are totally match. The pattern string could include '?' which can replace one character. The pattern string could also include '*' which can replace multiple (0-n) characters. For example,
1. src = "abcde", pattern = "ab?de", return true.
2. src = "abcde", pattern = "a*d?", return true.
3. src = "abcde", pattern = "*fg", return false.
12...Given an integer n. Create an array of elements between 1..n in random order in the array. The probability of choosing a number for any position in the array should be the same.
13...How to identify bits that alternate 1 and 0. Ex: 101010, 10101, 01010, 01.
15...You have a random 5 function. Generate a random 7 function using this random 5 function with equal probability
2...Find a two-line program to output the Nth Fibonacci number.
3...Given text, count the words inside.
you are reminded ".", ",", "?" could also be separator, plus number like "123,456,789.012" where '.'/',' not considered as separator...
The question is more about requirement and definition.
E.g. how many words in the string below?
"ab $2,300.58?2,,300.58 123?.235"
4...Find the longest palindromic substring in a string.
5...Given a n*m matrix having numbers such that each row and each column sorted. Now print the numbers in present in the matrix in sorted order.
6...Given a binary tree, prove that it is a BST(Binary search tree), without using inorder traversal either recursively or iteratively..?
7...Given an n*n matrix A. Each row of the matrix and each column of the matrix is sorted.
Given a number S, you are required to find S in the matrix( report k, l such that A[k,l] = S) or conclude S is not in A.
How can you solve it in O(n)?
8...A String as given as input in the form of Hex Decimal format and you need to print the ASCII format.
9...Print a binary tree in zig zag way... that is:
......a.........
....b....c.......
..d...e...f...g..
.h.i.j.k.l.m.n.o.
should be printed as a-c-b-d-e-f-g-o-n-m-l-k-j-i-h
what data structure will u use for that?
10...Write a function to reverse a line(i.e "How are you" will become "you are How")
11...give you two strings, one source string, one pattern string, check if they are totally match. The pattern string could include '?' which can replace one character. The pattern string could also include '*' which can replace multiple (0-n) characters. For example,
1. src = "abcde", pattern = "ab?de", return true.
2. src = "abcde", pattern = "a*d?", return true.
3. src = "abcde", pattern = "*fg", return false.
12...Given an integer n. Create an array of elements between 1..n in random order in the array. The probability of choosing a number for any position in the array should be the same.
13...How to identify bits that alternate 1 and 0. Ex: 101010, 10101, 01010, 01.
15...You have a random 5 function. Generate a random 7 function using this random 5 function with equal probability
Arrays!!!
1...Having an int array, which size is infinite (no way to find out), how do you do a binary search?
2...Given an int array and an int value. Find all pairs in array that add up to value.
3...Given an array of size n, you have n-1 integers in the array, and one of the n elements is a duplicate, find an efficient method of finding the duplicate.
4...Given a sorted array and a value, determine the first pair of numbers from that array which sums up to the given value.
5...Given two Arrays, there is intersection of elements in these two arrays. So now find all the elements which are common in both these arrays.
Suppose there is an element '#' repeated 2 times in both the arrays, then in the output we need to show two '#'s
6...How to efficiently find most frequent element in an array.?
7...Given an array of integers,Print the integers whose appearance are in odd times.
Need not worry abt order while printing the output.
Need Algorithm in o(n) time complexity.
Need efficient space complexity.
8...Given an integer array {1, -20, 29, 9, 1, 100, ..., 29), please return the index of the first non-repetitive element in the array.
9...Given a set S of n distinct numbers and a positive integer k <= n. Determine the k numbers in S that are closest to the median of S. Find an O(n) algorithm
10...Given 2 sorted arrays of n elements A,B. Find the k-th smallest element in the union of A and B in O(log k) time. You can assume that there are no duplicate elements
11...How do you perform binary search on a rotated sorted array?
eg., 75, 77, 85, 91, 10, 19, 26, 29, 33,45, 67
12...Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times.
13...Given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array.complexity should be in o(n).
14...Find the k max elements in an array of n
15...Find the sum of the most common element in a array .
16...Find a median of two sorted integer arrays.
17...Write a function that takes in an array of integers and outputs the number of ways you can combine those integers to obtain a sum of 15.
Example: for [10,5,3,2], output = 2.
18...Given an array of integers, write a function that returns the difference between the largest even integer and the smallest odd integer.
Sample input: [17 6 13 31 2 8 23]
Correct sample output: –5 (= 8 – 13)
19...I have an array that contains integers 1...n.
I remove 2 elements from that array, shuffle it and give it to a function you will write.
Find the 2 elements i removed.
2...Given an int array and an int value. Find all pairs in array that add up to value.
3...Given an array of size n, you have n-1 integers in the array, and one of the n elements is a duplicate, find an efficient method of finding the duplicate.
4...Given a sorted array and a value, determine the first pair of numbers from that array which sums up to the given value.
5...Given two Arrays, there is intersection of elements in these two arrays. So now find all the elements which are common in both these arrays.
Suppose there is an element '#' repeated 2 times in both the arrays, then in the output we need to show two '#'s
6...How to efficiently find most frequent element in an array.?
7...Given an array of integers,Print the integers whose appearance are in odd times.
Need not worry abt order while printing the output.
Need Algorithm in o(n) time complexity.
Need efficient space complexity.
8...Given an integer array {1, -20, 29, 9, 1, 100, ..., 29), please return the index of the first non-repetitive element in the array.
9...Given a set S of n distinct numbers and a positive integer k <= n. Determine the k numbers in S that are closest to the median of S. Find an O(n) algorithm
10...Given 2 sorted arrays of n elements A,B. Find the k-th smallest element in the union of A and B in O(log k) time. You can assume that there are no duplicate elements
11...How do you perform binary search on a rotated sorted array?
eg., 75, 77, 85, 91, 10, 19, 26, 29, 33,45, 67
12...Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times.
13...Given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array.complexity should be in o(n).
14...Find the k max elements in an array of n
15...Find the sum of the most common element in a array .
16...Find a median of two sorted integer arrays.
17...Write a function that takes in an array of integers and outputs the number of ways you can combine those integers to obtain a sum of 15.
Example: for [10,5,3,2], output = 2.
18...Given an array of integers, write a function that returns the difference between the largest even integer and the smallest odd integer.
Sample input: [17 6 13 31 2 8 23]
Correct sample output: –5 (= 8 – 13)
19...I have an array that contains integers 1...n.
I remove 2 elements from that array, shuffle it and give it to a function you will write.
Find the 2 elements i removed.
Subscribe to:
Posts (Atom)