zigzag打印矩阵
e.g.
input:
a b c
d e f
g h i
output:
adbceghfi
Answer: just simulate the move
1)start at i=1, j=1
2)move down once(i++) OR move right if you are at the bottom side
3)move in north east direction until you are reached top or right side
4)move right once if you are at top side OR move down once if you are at right side
5)move in south west direction until you are reached bottom or left side
6)go to step2 if you are still in the range
void print(vector<string>&matrix){
int row=matrix.size();
int col=matrix[0].length();
int i=0,j=0;
do{
cout<<matrix[i][j]<<" ";
if(i<row-1)
i++;
else if(j<col-1)
j++;
else//already finished printing
break;
//NE(north east) direction
while(i>0&&j<col-1){
cout<<matrix[i][j]<<" ";
i--;j++;
}
cout<<matrix[i][j]<<" ";
if(i==0&&j<col-1)
j++;
else
i++;
while(i<row-1&&j>0){//SW direction
cout<<matrix[i][j]<<" ";
i++;j--;
}
}while(i<=row-1&&j<=col-1);
cout<<endl;
}
Thursday, December 4, 2014
Count Inversions in an array - use merge sort
观察归并排序——合并数列(1，3，5)与(2，4)的时候：
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：
//从归并排序到数列的逆序数对
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) //a[i] 前面的数 a[j] 后面的数
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
//a[j]和前面每一个数都能组成逆序数对
g_nCount += m - i + 1;
}
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
void MergeSort(int a[], int n)
{
int *p = new int[n];
mergesort(a, 0, n - 1, p);
}
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：
//从归并排序到数列的逆序数对
#include <stdio.h>
int g_nCount;
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n) //a[i] 前面的数 a[j] 后面的数
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
//a[j]和前面每一个数都能组成逆序数对
g_nCount += m - i + 1;
}
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
void MergeSort(int a[], int n)
{
int *p = new int[n];
mergesort(a, 0, n - 1, p);
}
Wednesday, December 3, 2014
Interview Question - use kmp
Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
Find the length of the shortest palindrome that you can create from S by applying the above transformation.
Answer:
Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.
prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.
int getPalindrome(string s) {
int n = s.size();
vector<int> p(2*n+1,0);
string current = s + '$';
for (int i = 0; i < n; i++) {
current += s[n - 1 - i];
}
p[0] = 0;
for (int i = 1; i < 2 * n + 1; i++) {
int j = p[i - 1];
while (j > 0 && current[j] != current[i])
j = p[j - 1];
j += current[i] == current[j];
p[i] = j;
}
return 2 *n - p[2 * n];//returns the length of the palindrome formed
}
Find the length of the shortest palindrome that you can create from S by applying the above transformation.
Answer:
Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.
prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.
int getPalindrome(string s) {
int n = s.size();
vector<int> p(2*n+1,0);
string current = s + '$';
for (int i = 0; i < n; i++) {
current += s[n - 1 - i];
}
p[0] = 0;
for (int i = 1; i < 2 * n + 1; i++) {
int j = p[i - 1];
while (j > 0 && current[j] != current[i])
j = p[j - 1];
j += current[i] == current[j];
p[i] = j;
}
return 2 *n - p[2 * n];//returns the length of the palindrome formed
}
Word Ladder
int ladderLength(string start, string end, unordered_set<string> &dict) {
int ret = 0;
if (start == end)
return ret;
unordered_set<string> added;
queue<string> que;
int lev1 = 1;
int lev2 = 0;
que.push(start);
added.insert(start);
while (!que.empty()) {
string s = que.front();
que.pop();
--lev1;
for (int i = 0; i < s.length(); ++i) {
char before=s[i];
for (int j = 0; j < 26; ++j) {
s[i] = 'a' + j;
if (s == end)
return ret + 2;
if (dict.find(s) != dict.end()
&& added.find(s) == added.end()) {
que.push(s);
added.insert(s);
++lev2;
}
}
s[i]=before;
}
if (lev1 == 0) {
++ret;
lev1 = lev2;
lev2 = 0;
}
}
return 0;
}
//another flavor, by annikim
int ladderLength(string start, string end, unordered_set<string> &dict) {
queue<pair<string,int>> que;
que.push(make_pair(start,1));
while(!que.empty()){
pair<string,int> front=que.front();que.pop();
string word=front.first;
for(int i=0;i<word.length();i++){
char before=word[i];
for(char c='a';c<='z';c++){
word[i]=c;
if(word==end) return front.second+1;
if(dict.find(word)!=dict.end()){
que.push(make_pair(word,front.second+1));
dict.erase(word);
}
}
word[i]=before;
}
}
return 0;
}
int ret = 0;
if (start == end)
return ret;
unordered_set<string> added;
queue<string> que;
int lev1 = 1;
int lev2 = 0;
que.push(start);
added.insert(start);
while (!que.empty()) {
string s = que.front();
que.pop();
--lev1;
for (int i = 0; i < s.length(); ++i) {
char before=s[i];
for (int j = 0; j < 26; ++j) {
s[i] = 'a' + j;
if (s == end)
return ret + 2;
if (dict.find(s) != dict.end()
&& added.find(s) == added.end()) {
que.push(s);
added.insert(s);
++lev2;
}
}
s[i]=before;
}
if (lev1 == 0) {
++ret;
lev1 = lev2;
lev2 = 0;
}
}
return 0;
}
//another flavor, by annikim
int ladderLength(string start, string end, unordered_set<string> &dict) {
queue<pair<string,int>> que;
que.push(make_pair(start,1));
while(!que.empty()){
pair<string,int> front=que.front();que.pop();
string word=front.first;
for(int i=0;i<word.length();i++){
char before=word[i];
for(char c='a';c<='z';c++){
word[i]=c;
if(word==end) return front.second+1;
if(dict.find(word)!=dict.end()){
que.push(make_pair(word,front.second+1));
dict.erase(word);
}
}
word[i]=before;
}
}
return 0;
}
Binary Tree Level Order Traversal
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > ret;
if (!root) return ret;
TreeNode*pointer=root;
queue<TreeNode*> aQueue;
aQueue.push(pointer);
vector<int> temp;
int curlevel=1,nextlevel=0;
while(!aQueue.empty())
{
curlevel--;
pointer=aQueue.front();
aQueue.pop();
temp.push_back(pointer->val);
if (pointer->left)
{aQueue.push(pointer->left); nextlevel++;}
if (pointer->right)
{aQueue.push(pointer->right); nextlevel++;}
if (curlevel==0)
{
ret.push_back(temp);
temp.clear();
curlevel=nextlevel;
nextlevel=0;
}
}
return ret;
}
//another flavor, using NULL mark, by anniekim
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (!node)
{
res.push_back(level);
level.clear();
if (q.empty()) break; // end
q.push(NULL);
}
else
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
//another flavor
vector<vector<int> > levelOrder(TreeNode *root) {
if (!root) return vector<vector<int> >();
TreeNode*pointer=root;
queue<TreeNode*> currentLevel, nextLevel;
currentLevel.push(pointer);
vector<vector<int> > ret;
while(!currentLevel.empty()||!nextLevel.empty())
{
vector<int> temp1,temp2;
while(!currentLevel.empty())
{
pointer=currentLevel.front();
currentLevel.pop();
temp1.push_back(pointer->val);
if (pointer->left)
nextLevel.push(pointer->left);
if (pointer->right)
nextLevel.push(pointer->right);
}
while(!nextLevel.empty())
{
pointer=nextLevel.front();
nextLevel.pop();
temp2.push_back(pointer->val);
if (pointer->left)
currentLevel.push(pointer->left);
if (pointer->right)
currentLevel.push(pointer->right);
}
ret.push_back(temp1);
if(temp2.size()>0)
ret.push_back(temp2);
}
return ret;
}
vector<vector<int> > ret;
if (!root) return ret;
TreeNode*pointer=root;
queue<TreeNode*> aQueue;
aQueue.push(pointer);
vector<int> temp;
int curlevel=1,nextlevel=0;
while(!aQueue.empty())
{
curlevel--;
pointer=aQueue.front();
aQueue.pop();
temp.push_back(pointer->val);
if (pointer->left)
{aQueue.push(pointer->left); nextlevel++;}
if (pointer->right)
{aQueue.push(pointer->right); nextlevel++;}
if (curlevel==0)
{
ret.push_back(temp);
temp.clear();
curlevel=nextlevel;
nextlevel=0;
}
}
return ret;
}
//another flavor, using NULL mark, by anniekim
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (!node)
{
res.push_back(level);
level.clear();
if (q.empty()) break; // end
q.push(NULL);
}
else
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
//another flavor
vector<vector<int> > levelOrder(TreeNode *root) {
if (!root) return vector<vector<int> >();
TreeNode*pointer=root;
queue<TreeNode*> currentLevel, nextLevel;
currentLevel.push(pointer);
vector<vector<int> > ret;
while(!currentLevel.empty()||!nextLevel.empty())
{
vector<int> temp1,temp2;
while(!currentLevel.empty())
{
pointer=currentLevel.front();
currentLevel.pop();
temp1.push_back(pointer->val);
if (pointer->left)
nextLevel.push(pointer->left);
if (pointer->right)
nextLevel.push(pointer->right);
}
while(!nextLevel.empty())
{
pointer=nextLevel.front();
nextLevel.pop();
temp2.push_back(pointer->val);
if (pointer->left)
currentLevel.push(pointer->left);
if (pointer->right)
currentLevel.push(pointer->right);
}
ret.push_back(temp1);
if(temp2.size()>0)
ret.push_back(temp2);
}
return ret;
}
Surrounded Regions
from codeganker
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的'O'是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法， 把所有边缘上的'O'都替换成另一个字符，比如'#'。接下来我们知道除去被我们换成'#'的那些顶点，剩下的所有'O'都应该被替换成'X'，而'#' 那些最终应该是还原成'O'，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法， 因为只有是'O'才会进行，而且会被替换成'#'，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所 以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度 优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是 n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
class Solution {
public:
void solve(vector<vector<char>> & board) {
if(board.size()<=1 || board[0].size()<=1)
return;
for(int i=0;i<board[0].size();i++)
{
fill(board,0,i);
fill(board,board.size()-1,i);
}
for(int i=0;i<board.size();i++)
{
fill(board,i,0);
fill(board,i,board[0].size()-1);
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='#')
board[i][j]='O';
}
}
}
void fill(vector<vector<char>> & board, int i, int j)
{
if(board[i][j]!='O')
return;
board[i][j] = '#';
queue<int> queue;
int code = i*board[0].size()+j;
const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue.push(code);
while(!queue.empty())
{
code = queue.front();queue.pop();
int row = code/board[0].size();
int col = code%board[0].size();
for(int i=0;i<4;i++){
int currow=row+dir[i][0];
int curcol=col+dir[i][1];
if(currow>=0&&currow<board.size()&&curcol>=0&&curcol<board[0].size()){
if(board[currow][curcol]=='O'){
board[currow][curcol]='#';
queue.push(currow*board[0].size()+curcol);
}
}
}
}
}
};
//another flavor, from anniekim
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solve(BOARDTYPE &board) {
if (board.empty() || board[0].empty()) return;
int N = board.size(), M = board[0].size();
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (i == 0 || j == 0 || i == N-1 || j == M-1)
bfs(board, i, j); // you may call dfs or bfs here!
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
}
void dfs(BOARDTYPE &board, int row, int col) {
int N = board.size(), M = board[0].size();
if (row < 0 || row >= N || col < 0 || col >= M) return;
if (board[row][col] != 'O') return;
board[row][col] = 'V';
dfs(board, row+1, col);
dfs(board, row-1, col);
dfs(board, row, col+1);
dfs(board, row, col-1);
}
void bfs(BOARDTYPE &board, int row, int col) {
if (board[row][col] != 'O') return;
int N = board.size(), M = board[0].size();
queue<pair<int, int>> q;
q.push(make_pair(row, col));
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
if (i < 0 || i >= N || j < 0 || j >= M) continue;
if (board[i][j] != 'O') continue;// important to recheck!
board[i][j] = 'V';
q.push(make_pair(i-1, j));
q.push(make_pair(i+1, j));
q.push(make_pair(i, j-1));
q.push(make_pair(i, j+1));
}
}
};
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的'O'是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法， 把所有边缘上的'O'都替换成另一个字符，比如'#'。接下来我们知道除去被我们换成'#'的那些顶点，剩下的所有'O'都应该被替换成'X'，而'#' 那些最终应该是还原成'O'，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法， 因为只有是'O'才会进行，而且会被替换成'#'，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所 以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度 优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是 n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
class Solution {
public:
void solve(vector<vector<char>> & board) {
if(board.size()<=1 || board[0].size()<=1)
return;
for(int i=0;i<board[0].size();i++)
{
fill(board,0,i);
fill(board,board.size()-1,i);
}
for(int i=0;i<board.size();i++)
{
fill(board,i,0);
fill(board,i,board[0].size()-1);
}
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='#')
board[i][j]='O';
}
}
}
void fill(vector<vector<char>> & board, int i, int j)
{
if(board[i][j]!='O')
return;
board[i][j] = '#';
queue<int> queue;
int code = i*board[0].size()+j;
const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue.push(code);
while(!queue.empty())
{
code = queue.front();queue.pop();
int row = code/board[0].size();
int col = code%board[0].size();
for(int i=0;i<4;i++){
int currow=row+dir[i][0];
int curcol=col+dir[i][1];
if(currow>=0&&currow<board.size()&&curcol>=0&&curcol<board[0].size()){
if(board[currow][curcol]=='O'){
board[currow][curcol]='#';
queue.push(currow*board[0].size()+curcol);
}
}
}
}
}
};
//another flavor, from anniekim
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solve(BOARDTYPE &board) {
if (board.empty() || board[0].empty()) return;
int N = board.size(), M = board[0].size();
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (i == 0 || j == 0 || i == N-1 || j == M-1)
bfs(board, i, j); // you may call dfs or bfs here!
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
}
void dfs(BOARDTYPE &board, int row, int col) {
int N = board.size(), M = board[0].size();
if (row < 0 || row >= N || col < 0 || col >= M) return;
if (board[row][col] != 'O') return;
board[row][col] = 'V';
dfs(board, row+1, col);
dfs(board, row-1, col);
dfs(board, row, col+1);
dfs(board, row, col-1);
}
void bfs(BOARDTYPE &board, int row, int col) {
if (board[row][col] != 'O') return;
int N = board.size(), M = board[0].size();
queue<pair<int, int>> q;
q.push(make_pair(row, col));
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
if (i < 0 || i >= N || j < 0 || j >= M) continue;
if (board[i][j] != 'O') continue;// important to recheck!
board[i][j] = 'V';
q.push(make_pair(i-1, j));
q.push(make_pair(i+1, j));
q.push(make_pair(i, j-1));
q.push(make_pair(i, j+1));
}
}
};
Tuesday, December 2, 2014
Hash table vs Binary search tree
from here
Hash table and binary search tree are two fundamental data structures in CS. When would you want to use one over another one? What is the difference? This is a common interview question that I had most frequently been asked.
Well, it is not easy to answer by one or two sentences. The main difference between hash table and trees is on two aspects: Implementation details and behaviors and performance under different circumstance.
Let me start with implementation. Hash table uses hash function to assign index to input data and put data into array under corresponding index. If the size of hash table is 100, hash function can generate 0~99 to input data and store them into hash table. Theoretically, time complexity of insertion and looking-up is constant time (O(1)).
Binary search tree is implemented as the rule that all left children’s values are less than root, while all right children’s value are greater than it. If the tree is balanced, it always takes O(log(n)) time to insert a new node or look up.O(log(n)) is not as fast as constant time but rather fast. n is the total number in tree and log(n) is usually depth of tree. Notice that I mentioned if it is balanced tree, however there are sophisticated algorithm (e.g., RB tree) to maintain tree balanced.
It seems we can prefer hash table over tree, but it is not always the case. Hash table has significant drawbacks:
1. As more data input comes, there is huge probability that collision shows up (hash function maps different data to same index). There are two ways to handle collision. First is linear probing that implement hash table as array of linked list. In this case, worst time for insertion or retrieve or deletion is O(n) that all input data are mapped to same index. Besides, hash table need more space than number of input data. Second way is open addressing. It would not consume more space than input data, but at worst case insertion and retrieve is still O(n), which is extremely slow than constant time.
2. You have to know approximate size of input data before initializing hash table. Otherwise you need to resize hash table which is a very time-consuming operation. For example, your hash table size is 100 and then you want to insert the 101st element. Not only the size of hash table is enlarged to 150, all element in hash table have to be rehashed. This insertion operation takes O(n).
3. The elements stored in hash table are unsorted. In certain circumstance, we want data to be stored with sorted order, like contacts in cell phone.
However, binary search tree performs well against hash table:
1. Binary search tree never meets collision, which means binary search tree can guarantee insertion, retrieve and deletion are implemented in O(log(n)), which is hugely fast than linear time. Besides, space needed by tree is exactly same as size of input data.
2. You do not need to know size of input in advance.
3. all elements in tree are sorted that in-order traverse takes O(n) time.
OK, let me make a summary.
If you know how many data to maintain, and have enough space to store hash table and do not need data to be sorted, hash table is always good choice. Because, hash table provides constant time operation for insertion, retrieve and deletion. On the other hand, if items will be consistently added, binary search tree’s O(log(n)) operation is acceptable, comparing with rehashing operation during running time.
Besides, If you actually do not know size of input items, but after inserting, most operations are item looking up, hash table is preferred due to constant retrieve time. However, if items are continuously added or removed, tree’s O(log(n)) insertion and deletion time are more suitable in this condition.
In a word, there is no one answer that hash table or tree is better. All we need to know is pros and cons of hash table and tree in different conditions. Best decision can be made with knowledge of benefits and trade-offs of these two structures.
Hash table and binary search tree are two fundamental data structures in CS. When would you want to use one over another one? What is the difference? This is a common interview question that I had most frequently been asked.
Well, it is not easy to answer by one or two sentences. The main difference between hash table and trees is on two aspects: Implementation details and behaviors and performance under different circumstance.
Let me start with implementation. Hash table uses hash function to assign index to input data and put data into array under corresponding index. If the size of hash table is 100, hash function can generate 0~99 to input data and store them into hash table. Theoretically, time complexity of insertion and looking-up is constant time (O(1)).
Binary search tree is implemented as the rule that all left children’s values are less than root, while all right children’s value are greater than it. If the tree is balanced, it always takes O(log(n)) time to insert a new node or look up.O(log(n)) is not as fast as constant time but rather fast. n is the total number in tree and log(n) is usually depth of tree. Notice that I mentioned if it is balanced tree, however there are sophisticated algorithm (e.g., RB tree) to maintain tree balanced.
It seems we can prefer hash table over tree, but it is not always the case. Hash table has significant drawbacks:
1. As more data input comes, there is huge probability that collision shows up (hash function maps different data to same index). There are two ways to handle collision. First is linear probing that implement hash table as array of linked list. In this case, worst time for insertion or retrieve or deletion is O(n) that all input data are mapped to same index. Besides, hash table need more space than number of input data. Second way is open addressing. It would not consume more space than input data, but at worst case insertion and retrieve is still O(n), which is extremely slow than constant time.
2. You have to know approximate size of input data before initializing hash table. Otherwise you need to resize hash table which is a very time-consuming operation. For example, your hash table size is 100 and then you want to insert the 101st element. Not only the size of hash table is enlarged to 150, all element in hash table have to be rehashed. This insertion operation takes O(n).
3. The elements stored in hash table are unsorted. In certain circumstance, we want data to be stored with sorted order, like contacts in cell phone.
However, binary search tree performs well against hash table:
1. Binary search tree never meets collision, which means binary search tree can guarantee insertion, retrieve and deletion are implemented in O(log(n)), which is hugely fast than linear time. Besides, space needed by tree is exactly same as size of input data.
2. You do not need to know size of input in advance.
3. all elements in tree are sorted that in-order traverse takes O(n) time.
OK, let me make a summary.
If you know how many data to maintain, and have enough space to store hash table and do not need data to be sorted, hash table is always good choice. Because, hash table provides constant time operation for insertion, retrieve and deletion. On the other hand, if items will be consistently added, binary search tree’s O(log(n)) operation is acceptable, comparing with rehashing operation during running time.
Besides, If you actually do not know size of input items, but after inserting, most operations are item looking up, hash table is preferred due to constant retrieve time. However, if items are continuously added or removed, tree’s O(log(n)) insertion and deletion time are more suitable in this condition.
In a word, there is no one answer that hash table or tree is better. All we need to know is pros and cons of hash table and tree in different conditions. Best decision can be made with knowledge of benefits and trade-offs of these two structures.
Subscribe to:
Posts (Atom)