|
Question 1: Finding singletons among duplicates
Given an input array of n integers, where all but one integer shows up twice in the array, write an algorithm that - given the input array - will return the integer which shows up only once.
Give an O(n^2) solution with O(1) space complexity (a)
Give an O(n log n) solution with O(1) space complexity (b)
Give an O(n) solution with O(n) space complexity (c)
Give an O(n) solution with O(1) space complexity (d)
Give an O(n) solution with O(1) space complexity using only MULTIPLY and DIVIDE (e)
Question 2: Fixed sized subset sum
Given an input array of n integers and a target number x, write an algorithm that - given the input array - will return whether (and which) any two numbers in the input array add up to x.
Give an O(n^2) solution with O(1) space complexity (f)
Give an O(n log n) solution with O(1) space complexity (g)
Give an O(n) solution with O(n) space complexity (h)
Now -- given the same input array, write an algorithm that - given the input array - will return whether (and which) any three numbers in the input array add up to x.
Give an O(n^2 log n) solution with O(1) space complexity (i)
Give an O(n^2) solution with O(n) space complexity (j)
Now -- given the same input and some integer m, write an algorithm that - given the input array - will return whether (and which) any m numbers in the input array add up to x.
Give an O(n^(m-1)) solution with O(n) space complexity (k)
Now -- for the special case of m = 4
Give an O(n^2) solution with O(n^2) space complexity (l)
Solutions
a. For each of n numbers, check if it exists elsewhere in the length n list: n*n. Uses no additional space besides pointers.
b. Sort the list in constant space with a pivot algorithm (quicksort, etc) that's O(n log n) bounded. Check for duplicates afterwards by sweeping in O(n) time. Uses no additional space.
c. Put each number into a HashSet. If the number is already in the HashSet, mark it as existing twice. In the end, only one number will not be marked. HashSet takes O(n) space to make (amortizing expands it), but the sweep operation only takes O(n) time.
d. Huffman Code. Since integers take constant bitspace, bitwise xor every number in the array together. The result will be the number that's missing.
e. I have no bloody clue.
f. For each of the n numbers, run through the size n list and check if the pairs of numbers sum to the target. n*n = n^2 time but constant space.
g. Sort it first. Keep pointers to the smallest and largest items in the array. If the smallest+largest is equal to the target, return. If the smallest+largest is larger than the target, decriment the pointer from the largest to the second largest item. If the smallest+largest is smaller than the target, increment the pointer from the smallest to the second smallest. Repeat. The pointers will eventually converge in O(n) time - so time bound is due to sorting in O(n log n).
h. Another Hash based algorithm. Create a HashMap type repository with target-arrayvalues. Find if those values match up with the actual array values.
i, j, and k) For the array newTargets = Target-ArrayValues, note that if any 2 numbers add up to a number in newTargets, then we have the 3 numbers that add up to the target. Thus we have reduced the problem with 3 items to n problems each with 2 items. The complexity is simply n*Problem(2). Thus for m levels, we find that the complexity is O(n * n * ... * n *Problem(2)) where the n's occur m-2 times.
l) Create a new array which is all possible sums of pairs of numbers in the inital array, called sumItems. Note that if any 2 items in sumItems add up to the target, then the problem is solved. It takes n^2 time to generate sumItems, and n^2 time w/ n^2 space to check whether any 2 items in sumItems add up to the target (using a Hash method). Thus the overall complexity is n^2 bound with n^2 space bound.
|
