Daily Archives: June 7, 2015

Longest Consecutive Sequence

Posted on by
Reply

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Clarification

Your algorithm should run in O(n) complexity.

Solution: 建一个hash表 对每一个num[i]上下浮动寻找num[i]+1, num[i]+2, …, 和num[i]-1, num[i]-2, …是不是在表里 如果找到的话就把该数从hash表里删除避免重复查找，所以建表时间是O(n) 每个数只会被访问一次，所以时间复杂度是O(n).

public int longestConsecutive(int[] num) {
    Set<Integer> numSet = new HashSet<>();
    for (int i = 0; i < num.length; i++) {
        numSet.add(num[i]);
    }
    int maxLength = 0;
    for (int i = 0; i < num.length; i++) {
        if (numSet.contains(num[i])) {
            int length = 1;
            int curr = num[i] - 1 ;
            while (numSet.contains(curr)) {
                numSet.remove(curr);
                length++;
                curr--;
            }
            curr = num[i] + 1;
            while (numSet.contains(curr)) {
                numSet.remove(curr);
                length++;
                curr++;
            }
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    return maxLength;
}
FacebookTwitterGoogle+Share

Rehashing

Posted on by
Reply

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4

<code>[null, 21, 14, null]
       ↓    ↓
       9   null
       ↓
      null
</code>

The hash function is:

<code>int hashcode(int key, int capacity) {
    return key % capacity;
}
</code>

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.

rehashing this hash table, double the capacity, you will get:

size=3, capacity=8

<code>index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]
</code>

Given the original hash table, return the new hash table after rehashing .

Example

Given [null, 21->9->null, 14->null, null],

return [null, 9->null, null, null, null, 21->null, 14->null, null]

Note

For negative integer in hash table, the position can be calculated as follow:

  • C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
  • Python: you can directly use -1 % 3, you will get 2 automatically.

Solution:

Note: For negative integer in hash table, the position can be calculated as follow:
if you directly calculate -4 % 3 you will get -1.
You can use function: a % b = (a % b + b) % b to make it is a non negative integer.

public ListNode[] rehashing(ListNode[] hashTable) {
    if (hashTable == null) {
        return null;
    }
    ListNode[] newHash = new ListNode[hashTable.length * 2];
    int capacity = newHash.length;
    for (int i = 0; i < hashTable.length; i++) {
        ListNode node = hashTable[i];
        while (node != null) {
            int index = mod(node.val, capacity);
            ListNode next = node.next; //need to remove the next pointer
            node.next = null;
            //if it is the first one
            if (newHash[index] == null) {
                newHash[index] = node;
            } else {
                ListNode runner = newHash[index];
                while (runner.next != null) {
                    runner = runner.next;
                }
                runner.next = node;
            }
            hashTable[i] = next; //set to its next node
            node = next;
        }
    }
    return newHash;
}

//For negative integer in hash table, the position can be calculated as follow:
//if you directly calculate -4 % 3 you will get -1.
//You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
public int mod(int A, int module) {
    return (A % module + module) % module;
}

Heapify

Posted on by
Reply

Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?

  • Heap is a data structure, which usually have three methods: push, pop and top. where “push” add a new element the heap, “pop” delete the minimum/maximum element in the heap, “top” return the minimum/maximum element.
What is heapify?
  • Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
What if there is a lot of solutions?
  • Return any of them.

Solution 1: For each of the node in the heap array, use siftup method once.

public void heapify(int[] A) {
    if (A == null || A.length <= 1) {
        return;
    }
    for (int i = 0; i < A.length; i++) {
        siftUp(A, );
    }
}

public void siftUp(int[] A, int index) {
    int parentIndex = (index - 1) / 2;
    while (parentIndex >= 0 && A[index] < A[parentIndex]) {
        swap(A, index, parentIndex);
        index = parentIndex;
        parentIndex = (index - 1) / 2;
    }
}

public void swap(int[] A, int a, int b) {
    int tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;
}

Solution 2. for A[0, …, n/2-1] non leaf nodes, call siftDown method, O(n) time complexity.

比solution1时间上更优因为可以节省最下行叶子节点的时间， 叶子节点不需要siftdown.

public void heapify(int[] A) {
    if (A == null || A.length <= 1) {
        return;
    }
    for (int i = A.length / 2 - 1; i >= 0; i--) {
        siftDown(A, i);
    }
}

public void siftDown(int[] A, int index) {
    while (index < A.length) {
        int smallest = index;
        if (index * 2 + 1 < A.length && A[index * 2 + 1] < A[smallest]) {
            smallest = index * 2 + 1;
        }
        if (index * 2 + 2 < A.length && A[index * 2 + 2] < A[smallest]) {
            smallest = index * 2 + 2;
        }
        if (smallest == index) {
            break;
        }
        swap(A, smallest, index);
        index = smallest;
    }
}

public void swap(int[] A, int a, int b) {
    int tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;
}

Hash Function

Posted on by
Reply

Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to “hash” the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode(“abcd”) = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE

= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

= 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Example

For key=”abcd” and size=100, return 78

Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

Solution: Use a helper to avoid overflow.  To calculate a*33%HASH_SIZE, instead of multiply by 33, we add a to itself 33 times. if(result+num>mod) we only add num-mod it to the result, otherwise, just need to add num to result. In this case, we are either adding or removing HASH_SIZE from the final result so it won’t overflow.

public int hashCode(char[] key, int HASH_SIZE) {
    int result = 0;
    for (int i = 0; i < key.length; i++) {
        result = helper(result, 33, HASH_SIZE);
        result += key[i];
        result %= HASH_SIZE;
    }
    return result;
}

int helper(int num, int base, int mod) {
    int result = 0;
    for (int i = 0; i < base; i++) {
        if (result + num > mod) {
            result += num - mod;
        } else {
            result += num;
        }
    }
    return result;
}