Question

link

Bucket sort is mainly useful when input is uniformly distributed over a range. For example:

Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do we sort the numbers efficiently.

Solution

1) Create n empty buckets (Or lists).

2) Insert each arr[i] into bucket[n*array[i]]

3) Sort individual buckets using insertion sort.

4) Concatenate all sorted buckets.

Steps 1 and 2 clearly take O(n) time. Step 4 also takes O(n) time.

The main step to analyze is step 3. This step also takes O(n) time on average if all numbers are uniformly distributed. Final time complexity: O(n).

Relationship with other sorting algorithms

There’s a algorithm within the bucket. Now if we use bucket sort itself as the sorting function, this becomes a radix sort.

If we set the bucket size as 2, then this becomes a quick sort (with potentially poor pivot choices).

Code

C++ code from G4G

void bucketSort(float arr[], int n) {
    // 1) Create n empty buckets
    vector<float> b[n];

    // 2) Put array elements in different buckets
    for (int i=0; i<n; i++)
    {
       int bi = n*arr[i]; // Index in bucket
       b[bi].push_back(arr[i]);
    }

    // 3) Sort individual buckets
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
          arr[index++] = b[i][j];
}

Question

link

Problem: Get maximum binary Gap.

For example, 9’s binary form is 1001, the gap is 2.

Solution

This question is a good practise of binary operations.

Code

writen by me

private int solution(int num) {
    int max = 0;
    int boundary = -1;
    for (int i = 0; i < 32; i++) {
        int t = num & 1;
        num = num >> 1;
        if (t == 1) {
            if (boundary == -1) {
                boundary = i;
            } else {
                max = Math.max(max, i - boundary - 1);
                boundary = i;
            }
        }
    }
    return max;
}

Question

link

Quicksort is a divide and conquer algorithm. It first divides a large list into two smaller sub-lists and then recursively sort the two sub-lists. If we want to sort an array without any extra space, Quicksort is a good option. On average, time complexity is O(n log(n)).

Solution

This question is not easy. Practise more!

Code

public static void quickSortRan(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int pivot = arr[low + (high - low) / 2];
    int left = low;
    int right = high;
    while (left < right) {
        while (arr[left] < pivot) {
            left++;
        }
        while (arr[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    quickSortRan(arr, low, right);
    quickSortRan(arr, left, high);
}

4 Principles

link

1. Encapsulation

2. Abstraction

3. Inheritance

4. Polymorphism

Encapsulation

The hiding of data implementation by restricting access to accessors and mutators.

Abstraction

Representation of data in which the implementation details are hidden.

For examplem, the development of classes, objects, types in terms of their interfaces and functionality, instead of their implementation details.

Abstraction is used to manage complexity (decompose complex systems into smaller components).

Inheritance

The ability to derive new classes from existing classes.

Polymorphism

Polymorphism describes a pattern in object oriented programming in which classes have different functionality while sharing a common interface.

Eg. shape object.

Read more

http://en.wikipedia.org/wiki/SOLID_(object-oriented_design)

Question

link

Given a string, find the longest substring that contains only two unique characters. For example, given “abcbbbbcccbdddadacb”, the longest substring that contains 2 unique character is “bcbbbbcccb”.

Solution

First, the most basic and naive solution, which we use 2 pointers and 1 hashset. Read thru and when seeing the 3rd different char, rebuild the hashset. Idea is from original post. This approach is not very efficient.

Second, we can use HashMap instead of HashSet, so that we keep couting how many of each char we currently got. This should do the trick well.

What if the question change from ‘2 unique chars’ to ‘N unique chars’? Use HashMap instead of HashSet. The rest of the is very similar.

Third solution I found it here. It keeps a ‘lastGroupStart’ pointer, that points to the last position where character changes. Eg. “aaaabbbbbcccc”, ‘lastGroupStart’ would pointer to the first occurance of ‘b’. When we read until c, we update the window starting point to ‘lastGroupStart’, and update ‘lastGroupStart’ to the first occurance of ‘c’.

This is a frequent question. I personally would recommend 2nd solution: using HashMap.

Code

first solution

private String solution(String input) {
    HashSet<Character> set = new HashSet<Character>();
    char[] letters = input.toCharArray();
    set.add(letters[0]);

    int start = 0;
    String longest = input.substring(0, 1);

    for (int i = 1; i < input.length(); i++) {
        if (set.add(letters[i])) {
            if (set.size() > 2) {
                // first, update the longest substring that exists before i
                if (i - start > longest.length()) {
                    longest = input.substring(start, i);
                }
                // clear and rebuild the HashSet
                set.clear();
                set.add(letters[i]);
                set.add(letters[i - 1]);
                // remove 1 char entirely from current substring
                int p = i - 1;
                while (p > 0 && letters[p] == letters[p - 1]) {
                    p--;
                }
                start = p;
            }
        }
    }
    if (input.length() - start > longest.length()) {
        longest = input.substring(start);
    }
    return longest;
}

third solution, pay attention to ‘lastGroupStart’.

// Find the first letter that is not equal to the first one, 
// or return the entire string if it consists of one type of characters
int start = 0;
int i = 1;
while (i < str.length() && str[i] == str[start])
    i++;
if (i == str.length())
    return str;

// The main algorithm
char[2] chars = {str[start], str[i]};
int lastGroupStart = 0;
while (i < str.length()) {
    if (str[i] == chars[0] || str[i] == chars[1]) {
        if (str[i] != str[i - 1])
            lastGroupStart = i;
    }
    else {
        //TODO: str.substring(start, i) is a locally maximal string; 
        //      compare it to the longest one so far
        start = lastGroupStart;
        lastGroupStart = i;
        chars[0] = str[start];
        chars[1] = str[lastGroupStart];
    }
    i++;
}
//TODO: After the loop, str.substring(start, str.length()) 
//      is also a potential solution.

Ruby/gem/bundler setup (on a new machine) has always been a hassle to me. Not only that, I’ve had some confusions about developing Octopress blog on 2 different computers.

Now that I’ve had enough failures and success, I would like write a long post to summarize it.

Install Ruby

Well first of all, we must install Ruby and Development Kit. Simply go this this page and download:

1. Ruby 1.9.3
2. DevKit for Ruby 1.9.3

Installing Ruby is straight-forward, only remember to check “Add Ruby to your PATH”. Otherwise you need to manually set the Ruby directory (eg. C:\Ruby193\bin) in System Variables Settings.

Ruby DevKit is a self-extracting archive. After extracting the files, we should initialize the DevKit like this:

cd C:/RubyDevKit
ruby dk.rb init
ruby dk.rb install

Clone octopress

clone the source branch to the local octopress folder

using HTTPS
git clone -b source https://github.com/okckd/okckd.github.io.git octopress

or using SSH
git clone -b source git@github.com:okckd/okckd.github.io.git octopress

I would recommend using SSH over HTTPS, because using HTTPS, you will need to type your username and password everytime you push.

To change from ‘HTTPS’ to ‘SSH’, follow this instruction:

git remote set-url origin git@github.com:username/repo.git

More info about HTTPS and SSH is available.

Install dependencies

Follow this instruction and install bundler and dependencies.

cd c:/github/octopress
gem install bundler
rbenv rehash    # generally optional, unless you are using rbenv
bundle install

If you see endless dependency errors here, please refer to my other post: [Ruby] Endless error with gem dependencies.

If you are confused with some concepts in Ruby, read [Ruby] RubyGems, gem, Gemfile and Bundler.

Now, start octopress

You can use either of the commands below to start octopress. I can’t remember clearly but you can simply follow this guide.

rake setup_github_pages

when prompted, enter this url: git@github.com:okckd/okckd.github.io.git

rake install

Commit your changes

You can do ‘rake generate’, then ‘rake deploy’ to deploy to master branch. If you see the “Liquid Exception: Tag xxx was not properly terminated with regexp”: do this:

The file that’s causing this problem in octopress, is category_feed.xml, inside _includes/custom. You need to replace “markdownify” for “markdownize” and it works. Now I can rest.

Do ‘git commit", “git push origin source’ to update blog source. reference

At this step, congratulations you are all set!

Last word

Setting ‘rake’ up is found to be a great hassle for many, for example, someone spent 7 hours on it.

Wish this post can help!

Overview

Two’s complement is a binary signed number representation.

Negative values are taken by subtracting the number from 2ⁿ. This is the most common method of representing signed integers on computers.

Example

So basically ‘1111 1111’ means -1, and ‘1000 0000’ means -128.

Special case

In java, minimum integer = -2147483648, which is “10000000000000000000000000000000”. If we negative this value, we still get -2147483648!

public void solve(int A) {
    System.out.println(A);
    System.out.println(Integer.toBinaryString(A));
    System.out.println(A * -1);
    System.out.println(Integer.toBinaryString(-1 * A));
    System.out.println(-A);
}

We get:

-2147483648
10000000000000000000000000000000
-2147483648
10000000000000000000000000000000
-2147483648

The following questions does not appear in NineChap, but they all worth reading.

Question List

1. Longest Substring Without Repeating Characters

2. Minimum Window Substring - very difficult

3. Scramble String

4. Recover Binary Search Tree

5. Median of Two Sorted Arrays - difficult

6. Sudoku Solver - difficult

7. Word Search

8. Simplify Path

9. Regular Expression Matching - very difficult

10. Wildcard Matching - difficult

Question

link

Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.

Eg. input = (1, 4, 45, 6, 0, 19), 51, output (4, 45, 6)

Solution

Solution 1 (the better one) is based on another question Subarray with 0 Sum. We calculate the 前缀和 of every number. Takes O(n) time.

If all input are positive, there can be a Solution 2 which is based on another question Subarray with Particular Sum. The sliding window search. It’s O(n) time as well.

Code

Solution 2 (for positive input)

int smallestSubWithSum(int arr[], int n, int x) {
    //  Initilize length of smallest subarray as n+1
     int min_len = n + 1;

     // Pick every element as starting point
     for (int start=0; start<n; start++)
     {
          // Initialize sum starting with current start
          int curr_sum = arr[start];

          // If first element itself is greater
          if (curr_sum > x) return 1;

          // Try different ending points for curremt start
          for (int end=start+1; end<n; end++)
          {
              // add last element to current sum
              curr_sum += arr[end];

              // If sum becomes more than x and length of
              // this subarray is smaller than current smallest
              // length, update the smallest length (or result)
              if (curr_sum > x && (end - start + 1) < min_len)
                 min_len = (end - start + 1);
          }
     }
     return min_len;
}

Question

link

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Eg. input = (1, 4, 20, 3, 10, 5), 33, output (20, 3, 10)

Solution

Like a sliding window. Note that input numbers are all positive (otherwise it won’t work).

Initialize a variable ‘curr_sum’ as first element. ‘curr_sum’ indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum.

1. If curr_sum exceeds the sum, then remove first.
2. If curr_sum becomes equal to sum, solution found.

O(n) time.