This week’s session is headlined by Arun. We will cover a few questions based on Array data structure. This is work in progress, question may change before they are announced in the meetup.

  1. 2SUM Problem: Given an array of integers a[] and a target sum T, find two indices (i and j) such that a[i] + a[j] adds up to T. Return both the indices
    int[] TwoSum(int a[], int T)
    Easy: O(n2)
    Easy-Moderate: O(n log n)
    Moderate: O(n), Can use extra space.
  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. Note: There may be more than one duplicate, return any of them. A number may appear more than twice.
    Easy: O(n2) time, O(1) space
    Moderate: O(n) time, O(n) space.
    Moderate-Hard: O(n) time, O(1) space, if you can make the array mutable.
  3. Find in Rotated Sorted Array: Given an array of integers a[] that is sorted, and then cut into two parts (LEFT and RIGHT). The array is now spliced back RIGHT and LEFT. So a will look like 4 5 6 7 0 1 2.
    • Find the smallest element in the array?
    • Find the largest element in the array?
    • Find the kth largest element in the array?
    • Find the index of a given element in the array?
      Easy: O(n)
      Easy-Moderate: O( log n)
  4. Filling Water: Assume you are given a bar graph chart, where the width of each bar 1 unit, and the height is provided in an array of ints. If you “flood” the graph now, calculate the total water that will be retained in the shape.
    Example: If the input is : Given [0,1,0,2,1,0,1,3,2,1,2,1]. It represents, a bar of 0 height at 0th location, 1 in 1st location, 0 in 2nd location and so on. If you flood the graph with water, you will have 1 unit between 1st and 3rd bars, 4 units between 3rd and 7th bars, 1 unit between 8 and 10th bars. So net output is 6
    water-bar-graphEasy: O(n2) time, O(1) space
    Moderate-Hard: O(n) time, O(n) space
  5. Combined Median: Given two sorted arrays, a[] and b[] of size n,
    • Find the median of the combined array.
    • Find the kth element of the combined array.

    Easy: O(n)
    Moderate: O( log (n) )