Saturday, February 23, 2013

[LeetCode] Longest Consecutive Sequence, Solution


Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
» Solve this problem

[Thoughts]
Since it requires O(n) solution, normal sort won't be work here. Hash probably is the best choice.
3 Steps:
1. create the hashmap to hold <num, index>
2. scan the num vector from left to right, for each num
               i, check whether num -1 is in the map  (loop)
              ii, check whether num+1 is in the map  (loop)
3. track the sequence length during scanning.

[Code]
1:       int longestConsecutive(vector<int> &num) {  
2:            unordered_map<int, int> hashmap;            
3:            for(int i =0; i< num.size(); i++)  
4:            {  
5:                 hashmap[num[i]] = i;  
6:            }  
7:            vector<int> visited(num.size(), 0);  
8:            int maxV = INT_MIN;  
9:            for(int i =0; i< num.size(); i++)  
10:            {  
11:                 if(visited[i]==1) continue;  
12:                 visited[i]=1;  
13:                 int len = 1;  
14:                 int index = num[i]-1;  
15:                 while(hashmap.find(index) != hashmap.end())  
16:                 {  
17:                      visited[hashmap[index]] =1;  
18:                      index--;  
19:                      len++;  
20:                 }  
21:                 index = num[i]+1;  
22:                 while(hashmap.find(index) != hashmap.end())  
23:                 {  
24:                      visited[hashmap[index]] =1;  
25:                      index++;  
26:                      len++;  
27:                 }  
28:                 if(len > maxV)  
29:                      maxV = len;  
30:            }  
31:            return maxV;  
32:       }  



Update 08/23/2014
Interesting discussion in the comments:) I haven't visited my blog for quite long time.

For each num, define D[num] as the longest consecutive sequence from k to num,  0<k<num

So D[num] = D[num-1] +1   if num-1 in the map
                  =0                      if num-1  not in the map

But unfortunately, the unordered_map doesn't keep any order of sequence. It's hard to do the DP via a loop.

Here can use Memorization to optimize the code. Since for each fresh node, it only visits once. It is O(n) code.

And in the code , the second 'for' loop and the third 'for' loop could be merged together, but here keep them separated for readability.

1:       int longestConsecutive(vector<int> &num) {  
2:            unordered_map<int, int> hashmap;  
3:            vector<int> length(num.size(),0);  
4:            for(int i =0; i< num.size(); i++)  
5:            {  
6:                 hashmap[num[i]]=i;  
7:            }  
8:            for(int i =0; i< num.size(); i++)  
9:            {  
10:                 // skip the node, which already calculate the length  
11:                 if(length[i] > 0) continue;                 
12:                 length[i] = consecutiveLength(num[i], hashmap, length);  
13:            }  
14:            int maxV = INT_MIN;  
15:            for(int i =0; i< num.size(); i++)  
16:            {  
17:                 maxV = length[i]>maxV?length[i]:maxV;  
18:            }  
19:            return maxV;  
20:       }  
21:       int consecutiveLength(int num, unordered_map<int, int>& hashmap, vector<int>& length)  
22:       {  
23:            if(hashmap.find(num) == hashmap.end()) return 0;  
24:            int index = hashmap[num];  
25:            // skip the node, which already calculate the length  
26:            if(length[index] > 0) return length[index];  
27:            else  
28:            {  
29:                 // hit each fresh node only once  
30:                 length[index] = consecutiveLength(num - 1, hashmap, length) + 1;  
31:                 return length[index];  
32:            }  
33:       }  




Friday, February 22, 2013

[LeetCode] Sum Root to Leaf Numbers, Solution


Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
» Solve this problem


[Thoughts]
Recursion. Similar as [LeetCode] Binary Tree Maximum Path Sum Solution, the difference here is only adding a track variable to sum all the paths.

[Code]
1:       int sumNumbers(TreeNode *root) {  
2:            int sum=0, path =0;            
3:            GenerateSum(root, sum, path);  
4:            return sum;  
5:       }  
6:       void GenerateSum(TreeNode *root, int& sum, int path)  
7:       {  
8:            if(root == NULL) return;      
9:            path = path*10 +root->val;  
10:            if(root->left == NULL && root->right == NULL)  
11:            {  
12:                 sum+=path;  
13:                 return;  
14:            }  
15:            GenerateSum(root->left, sum, path);  
16:            GenerateSum(root->right, sum, path);  
17:       }  










[LeetCode] Word Ladder II, Solution


Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note:
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
» Solve this problem

[Thoughts]
解法一,递归
1. 首先生成不同字符串之间的跳转函数(Func[A][B] means how many char need changed if A transfer to B),比如{"a", "b", "c"}
      a        b       c
a    0        1       1
b    1        0       1
c    1        1        0
2. 有了转移方程之后,直接递归就好了。

在实现中,由于unordered_set不支持[]操作,所以我额外拷贝到vector里面来做(没有使用hash),浪费了多余的时间。可以过小数据,但是过不了大数据。

1:  int DiffDict[1000][1000];  
2:  int visited[1000];  
3:  void findtran(string& start, string& end, vector<string> &dict, int curIndex,  
4:  int step, int& min, vector<vector<string>>& result, vector<string>& candidate)  
5:  {  
6:       if(start == end)  
7:       {  
8:            if(step < min)  
9:            {  
10:                 min = step;  
11:                 result.clear();  
12:                 result.push_back(candidate);  
13:            }  
14:            else if(step == min)  
15:            {  
16:                 result.push_back(candidate);  
17:            }       
18:            return;  
19:       }  
20:       for(int i =1; i< dict.size(); i++)  
21:       {  
22:            if(visited[i] ==1 || DiffDict[curIndex][i] !=1)  
23:                 continue;  
24:            visited[i] =1;  
25:            candidate.push_back(dict[i]);  
26:            findtran(dict[i], end, dict, i, step+1, min, result, candidate);  
27:            candidate.pop_back();  
28:            visited[i] =0;  
29:       }  
30:  }  
31:  vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
32:       vector<vector<string>> result;  
33:       assert(dict.size() < 1000);  
34:       vector<string> dictV;  
35:       //copy data to vector since unordered_set not support []  
36:       for(unordered_set<string>::iterator it = dict.begin(); it!=dict.end(); ++it)  
37:       {  
38:            dictV.push_back(*it);  
39:       }  
40:       //add start as head  
41:       vector<string>::iterator it = std::find(dictV.begin(), dictV.end(),start);  
42:       if(it!= dictV.end())  
43:       {  
44:            dictV.erase(it);  
45:       }  
46:       dictV.insert(dictV.begin(),start);  
47:       visited[0] =1;  
48:       //add end as tail  
49:       it = std::find(dictV.begin(), dictV.end(),end);  
50:       if(it!= dictV.end())  
51:       {  
52:            dictV.erase(it);  
53:       }  
54:       dictV.push_back(end);  
55:       //preprocess trans metrics  
56:       for(int i=0; i<dictV.size(); i++)  
57:       {  
58:            for(int j=i; j<dictV.size(); j++)  
59:            {  
60:                 int diff=0;  
61:                 for(int k=0; k< it->size(); k++)  
62:                 {  
63:                      if(dictV[i][k] != dictV[j][k]) diff++;  
64:                 }  
65:                 DiffDict[i][j] = diff;  
66:                 DiffDict[j][i] = diff;  
67:            }  
68:       }  
69:       int step =0;  
70:       int min = INT_MAX;  
71:       vector<string> candidate;  
72:       candidate.push_back(start);  
73:       findtran(start, end, dictV, 0,step, min, result, candidate);  
74:       return result;  
75:  }  


考虑到题目已经提示了应该使用unordered_set来做,应该有基于hash的解法。

Thursday, February 21, 2013

[LeetCode] Valid Palindrome, Solution


Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
» Solve this problem

[Thoughts]
Two pointer. From both sides to middle.


[Code]
1:       bool isPalindrome(string s) {  
2:            int start = 0;  
3:            int end = s.size()-1;  
4:            std::transform(s.begin(), s.end(), s.begin(), ::tolower);  
5:            while(start<end)  
6:            {  
7:                 while(start< end && !isAlpha(s[start])) start++;  //filter non-alpha char
8:                 while(start< end && !isAlpha(s[end])) end--;  //filter non-alpha char
9:                 if(s[start]!=s[end]) break;        
10:                 start++;  
11:                 end--;  
12:            }  
13:            if(start >= end)  
14:                 return true;  
15:            else  
16:                 return false;        
17:       }  
18:       bool isAlpha(char c)  
19:       {  
20:            if(c>='a' && c<='z') return true;     
21:            if(c>='0' && c<='9') return true;  
22:            return false;  
23:       }  


Sunday, February 3, 2013

[Yahoo] Cloest palindrome number, Solution

Given an integer, print the closest number to it that is a palindrome - eg, the number "1224" would return "1221".

[Thoughts]

pseudo code: (with two examples in parentheses)

- Convert the number into string. (1224, 39999)
- take half of the string. ( "12", "399" )
- copy first half to second half in reverse order (take care of no of chars) ( "12" -> "1221", "399" -> "39993" )
- convert to number and measure the abs. difference with original number - diff1 ( |1221 - 1224| = 3, |39993-39999| = 6)
- add 1 to half string and now copy first half to second half in reverse order ( 12+1 = 13, 399 + 1 = 400, 13-> 1331, 400->40004)
- convert to number and measure the abs. difference with original number - diff2 ( |1331-1224| = 107, |40004-39999| = 5 )
- if diff1<diff2 return first number else return second number ( 1221, 40004)

Saturday, February 2, 2013

[Google] URL query with wild card

In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of any characters, how to build the
index such that such a type of query can be executed efficiently and the
contents of all correpsonding URLs can be displayed to the users? For
example, given a query http://www.*o*ve*ou.com. You man need to find iloveyou.com, itveabcu.com, etc.

[Thoughts]
use a Trie and traverse through are trie and for each * traversing to all the children of the node...

[Google] Inorder Successor in Binary Search Tree, Solution


In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.
In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.
Method 1 (Uses Parent Pointer)
In this method, we assume that every node has parent pointer.
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.
Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.
1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.
Implementation
Note that the function to find InOrder Successor is highlighted (with gray background) in below code.
1:  #include <stdio.h>  
2:  #include <stdlib.h>  
3:  /* A binary tree node has data, pointer to left child  
4:    and a pointer to right child */  
5:  struct node  
6:  {  
7:    int data;  
8:    struct node* left;  
9:    struct node* right;  
10:    struct node* parent;  
11:  };  
12:  struct node * minValue(struct node* node);  
13:  struct node * inOrderSuccessor(struct node *root, struct node *n)  
14:  {  
15:   // step 1 of the above algorithm  
16:   if( n->right != NULL )  
17:    return minValue(n->right);  
18:   // step 2 of the above algorithm  
19:   struct node *p = n->parent;  
20:   while(p != NULL && n == p->right)  
21:   {  
22:     n = p;  
23:     p = p->parent;  
24:   }  
25:   return p;  
26:  }  
27:  /* Given a non-empty binary search tree, return the minimum data   
28:    value found in that tree. Note that the entire tree does not need  
29:    to be searched. */  
30:  struct node * minValue(struct node* node) {  
31:   struct node* current = node;  
32:   /* loop down to find the leftmost leaf */  
33:   while (current->left != NULL) {  
34:    current = current->left;  
35:   }  
36:   return current;  
37:  }  
Time Complexity: O(h) where h is height of tree.


Method 2 (Don't Use Parent Pointer)
Inorder travel the tree and
1) If current visit node is target node,  mark the indicator as true.
2) If indicator is true, print the node and return.

Implementation
1:  struct node * inOrderSuccessor(struct node *n, struct node* target, bool& indicator)  
2:  {  
3:   if( n== NULL )  
4:    return NULL;  
5:   if(indicator) return n;  
6:   if(n == target) { indicator = true; return;}  
7:   node* left = inOrderSuccessor(n->left, target, indicator);  
8:   node * right =inOrderSuccessor(n->right, target, indicator);  
9:   if(left != NULL) return left;  
10:   if(right!= NULL) return right;  
11:   return NULL;  
12:  }