Reading...
Play button
Play button
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;
7 Cards in this Set
- Front
- Back
|
how do you find the k smallest items in an unsorted array in O(n) worst case time?
|
use median of median algorithm to find kth item in linear time. make another pass through the array to get all the items smaller than the kth item
|
|
|
how would you maintain the median for a stream of numbers?
|
use a min heap to keep track of all the larger elements and a max heap to keep track of all the smaller elements, maintain the heaps so their size difference differs by <= 1
|
|
|
enumerate the permutations of a string
|
this can be done recursively by inserting the last character into all possible positions for each permutation of the previous characters
|
|
|
given a magazine and a desired message, determine whether the message can be made by cutting out words from the magazine
|
create a hash table with words in the message as keys and values are the number of occurrences of the word in the message
do a pass through the magazine checking whether each word is in the table and decrementing if so, if the table has <=0 for all values then the message can be constructed |
|
|
a sorted array has been rotated, find the minimum element
|
do a binary search for the point where the last element jumps down to the first element
do this by checking the mid point against the ends (one of the ends will have the right relative magnitude i.e. the right most should be greater or the leftmost should be smaller) whichever end point is not correct means the biggest element is in that half of the array |
|
|
print all valid combinations of n pairs of parentheses
|
the key insight is using recursion and what unit to recurse on (individual parens rather than pairs of parens)
use recursion at the individual parentheses level by keeping track of how many left parens and right parens can be used. e.g. a left paren can be followed by all the possible permutations of strings that have n-1 left parens and n right parens, a right paren can be printed as long as the number of right parens is greater than the number of left parens |
|
|
given two sorted arrays A and B where the A has len(B) extra cells at the end, merge the two arrays
|
do merge sort's merge backwards
|
