• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/10

Click to flip

Use LEFT and RIGHT arrow keys to navigate between flashcards;

Use UP and DOWN arrow keys to flip the card;

H to show hint;

A reads text to speech;

10 Cards in this Set

  • Front
  • Back

Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?

Join the centers of the original and the removed rectangle. It works for cuboids too! BTW, I have been getting many questions asking why a horizontal slice across the middle will not do. Please note the "any size or orientation" in the question! Don't get boxed in by the way you cut your birthday cake :) Think out of the box.

You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

1. Mark the jars with numbers 1, 2, 3, 4, and 5.

2. Take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4 and take 5 pills from jar 5.

3. Put all of them on the scale at once and take the measurement.

4. Now, subtract the measurement from 150 ( 1*10 + 2*10 + 3*10 + 4*10 + 5*10)

5. The result will give you the jar number which has contaminated pill.

If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

This is actually about getting 2 quarts in the 3 quart pail so you can pour off exactly 1 quart from the 5 quart pail, leaving 4.

The entire process:
Fill the 5 quart pail then fill the 3 quart pail from the 5 quart pail. You now have 2 quarts in the 5 quart pail. Empty the 3 quart pail and transfer the 2 quarts from the 5 quart pail to the 3 quart pail. Lastly, fill the 5 quart pail then pour off the extra quart into the 3 quart pail until it is full. What remains in the 5 quart pail is 4 quarts.

As the two jug sizes are relatively prime (i.e., have no common prime factors), you can find a pour sequence for any value between 1 and the sum of the jug sizes.

What does it mean when we say an algorhythm executes in logarithmic time?

It means that a dividing strategy similar to binary search is implemented halving the items in the target domain on each iteration.


( Log N)

What does it mean when we say an algorhythm executes in Linear time?

It means visiting every node in a one dimensional array or list.


( N )

What does it mean when we say an algorhythm executes in Linearithmic time?

For example a sort followed by a binary search. Mergesort is another example.



( N Log N )

What does it mean when we say an algorhythm executes in quadratic time?

A doubly nested for loop or visiting every item in a 2 dimensional array.


( N^2 )

What does it mean when we say an algorhythm executes in cubic time?

A triply nested for loop or visiting every item in a 3 dimensional array.


( N^3 )

What does it mean when we say an algorhythm executes in exponential time?

Having to visit each item in a one dimensional array Y times.


( N^Y )

What does it mean when we say an algorhythm executes in constant time?

Constant time effectively means you can give a constant upper bound to how long the program will take to run which isn't affected by any of the input parameters.