The way I found the problem on the web:
Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
Categories
Month: June 2009
If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.
Kind of a trick question. What if the buckets only contained 1.1 cups of paint?
Since the paint is conserved we can say that if after the pouring back and fourth over N cycles (here N=1) an ammount a of paint is transfered from the red to the blue bucket then we can see that the relative ratios are:
[(X-A) Red / A Blue] in the red bucket and [A/(X-A)] in the blue bucket.
As logn as (X-A) is greater than A we have proven the above statement.
There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can’t change them. Identify each switch with its bulb.
Assumptions:
- Assuming the lights are not the newer LED bulbs that dont get warm to the touch we can assume if we leave thei light on it will get warm.
- We are powering up the box / it does not exsist before time T0. If not it is possible that the heating and cooling times will make the following simplification not work.
Two bulb Solution
{S1 S2} = {a,b} –> Starting test state – wait for an hour.
{S1 !S2} = {a,!b} –> Toggle switch states and open the door.
- Light that was constantly on should now be warm and on.
- Light that was constantly off should still be off and cold.
- Light that was on and is now off should be off and cold.
- Light that was off and is now on shoudl be on and cold.
Tests 1 and 2 uniquely identify S1, and you get S2 by process of elimination.
Three bulb Solution
- {S1 S2 S3} = {a, b, c} –> Starting test state – wait for X mins.
- {S1 S2 !S3} = {a, b, !c} –> Toggle switch and wait for Y mins.
- {S1 !S2 S3} = {a,!b, c} –> Toggle switch and pen the door.
Decoding then is
- S1. Light that was constantly on should either be ambient temperature and off or very hot and on.
- S2. Should either be heated for X+Y mins and off, or ambient and on.
- S3. Should either be heated for X-Y mins and on, or heated Y mins and off.
Four temperatures possible: Ambient, Y, X-Y, X+Y
- Ambient and off light is S1.
- Ambient and on light is S2.
- Heated (X+Y) and on is S1.
- heated (X+Y) and off it is S2.
- Heated X-Y and on is S3 and heated Y and off is S3. So the medium temperature (either Y or X-Y) is S3.
From 5 above we can collapse the temperature range to Ambient , {Y, X-Y}, X+Y. So just picking a X/Y ratio that allows for adaquade difference in heating and cooling times is all that is needed.
This is how the problem was phrased when I found it on the web.
You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
Write a function to print the Fibonacci numbers.
The fibonacci sequence is a set of numbers formed by
with seed values
This generates the numbers using the following set of rules….
So the fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…
Reverse the words in a sentence, i.e. “My name is Chris” becomes “Chris is name My.” Optimize for speed. Optimize for space.
Categories
Calculate a substring
Find a substring. Optimize for speed. Optimize for space.
Categories
Compare two strings
Compare two strings using O(n) time with constant space.
- Implement strstr() (or some other string library function).
strlen() Get length of a string. strcpy() Copy one string to another. strcat() Link together (concatenate) two strings. strcmp() Compare two strings. strchr() Find character in string. strstr() Find string in string. strlwr() Convert string to lowercase. strupr() Convert string to uppercase.
Implement an algorithm to do wild card string matching