Presorting - How to Succeed in Algorithms


Presorting - How to Succeed in Algorithms

How to Succeed in Algorithms Interview Series


  • two pointers: -> <- or <- ->
  • when order doesn’t matter: min, max, or, and

Presorting

  • Longest Arithmetic Progression of sorted array
    • starting point: 3 values, fix the middle value
    • simplify the question to find if there exist three elements in Arithmetic Progression or not
    • DP + two pointers: fix middle, <- middle ->
  • LeetCode 891 - Sum of Subsequence Widths
    • presort
    public int sumSubseqWidths(int[] A) {
    int MOD = 1_000_000_007;
    int N = A.length;
    Arrays.sort(A);
    long[] pow2 = new long[N];
    pow2[0] = 1;
    for (int i = 1; i < N; ++i)
      pow2[i] = pow2[i - 1] * 2 % MOD;
    long ans = 0;
    for (int i = 0; i < N; ++i)
      ans = (ans + (pow2[i] - pow2[N - 1 - i]) * A[i]) % MOD;
    return (int) ans;
    }

Presorting with custom comparator

  • then reorder
  • LeetCode 406 - Queue Reconstruction by Height
    • People are only counting (in their k-value) taller or equal-height others standing in front of them. So a smallest person is completely irrelevant for all taller ones.
    • starting point: tallest
    public int[][] reconstructQueue(int[][] people) {
    // pick up the tallest guy first
    // when insert the next tall guy, just need to insert him into kth position
    // repeat until all people are inserted into list
    Arrays.sort(people, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[0] != o2[0] ? -o1[0] + o2[0] : o1[1] - o2[1];
      }
    });
    List<int[]> res = new LinkedList<>();
    for (int[] cur : people) {
      if (cur[1] >= res.size())
        res.add(cur);
      else
        res.add(cur[1], cur);
    }
    return res.toArray(new int[people.length][]);
    }

Presorting with index

// a[1..Lo-1] zeroes (red)
// a[Lo..Mid-1] ones (white)
// a[Mid..Hi] unknown
// a[Hi+1..N] twos (blue)
// http://www.zrzahid.com/dutch-national-flag-dnf-problem-3-way-partitioning/
static void sort012(int a[], int arr_size)
{
    int lo = 0;
    int hi = arr_size - 1;
    int mid = 0,temp=0;
    while (mid <= hi)
    {
        switch (a[mid])
        {
        case 0:
        {
            swap(a, lo, mid);
            lo++;
            mid++;
            break;
        }
        case 1:
            mid++;
            break;
        case 2:
        {
            swap(a, mid, high);
            hi--;
            break;
        }
        }
    }
}

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)