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. |
|
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. |
|
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. |