This week we will continue the discussion on arrays and spatial structures we had during out previous meetup.

  1. 4SUM Question: Given an array of integers a[] and a target sum T, find four indices (p, q, r and s) such that ap + aq + ar + as = T. Return all the four indices in an array.
    • int[] FourSum(int a[], int T)

    We discussed a solution involving, generating all pairs of numbers and storing it in a HashSet of size n2. Now, apply the 2SUM solution to this at a cost of O(n2). There was open question: If the input array was 1,2,3,4 and target was 11, you should return “no solution”.
    Based on the algorithm above, we would create the pairs set as 3,4,5,6,7 and then proceed to provide an answer of 4+7 ( 1+3+3+4) or 5+6 ( 2 3 2 4). In both cases you are considering one item twice. How do we solve for this?

  2. Find Duplicate: Given an array of integers a[] of size (n+1), and every number is between 1 and n. This means that there would be at least one duplicate integer. Find it.Followup Question: How will you solve if you don’t have enough space to store the entire array in memory (throws out the O(n) space) solution. And the array is immutable (so O(1) space solution is also out).
  3. Find Missing: Given a large data set of numbers, find a number that does not exist in the array. The array may be fairly large, with millions of numbers and the data set could be of a large range. Assume 64 bit ints for the initial problem.
    1. What if the data is “user-ids”, and your goal is to check if a user-id is already present.
    2. How would the algorithm differ if you were to model this as a test? boolean isPresent(userId)?
    3. How would your algorithm change, if you were okay with wrong answer sometimes as in isPresent returns false when it is definitely not present, but may occasionally return true, when the element may not be present.Think Bloom Filters.
    4. Can you apply the bloom filters to the Find Duplicate question?
  4. Find Smallest Missing: In an unsorted array with only positive numbers, find the smallest missing number.
    Input: 9, 5, 4, 7, 2, 1, 8, 0.
    Output: 3
  5. Equitable Distribution: There are home-made chocolates of varying sizes, and there are two kids who want to share the chocolates in such a way that they both get as close to equal (by weight) share as possible. You are given the weight of each piece in an integer array, divide this array in two parts such that the difference between the sum of each array is minimized.
    1. Assume that a solution exists where you can divide them in to two equal halves. Find one of the solutions.
    2. What if no solution exists for equality, find a solution that provides the closest sums.
    3. What if there were K kids?