/**97 Answers
Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??*/
/**On the one go, use a map to record the beginning and ending of a sub-sequence, merge two sub-sequences to
one. The counts are determined by ending-beginning. sequence representation: [beginning, ending]
*/
#include <map>
#include <vector>
#include <array>
#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
class Solution{
public:
vector<int> getLCS(vector<int> const& s){
vector<int> beginning;//store beginnings of sub-sequences
vector<int> ending;//store endings of sub-sequences
for(int ii = 0; ii < s.size(); ++ii){
int const number = s[ii];
auto it_begin = find(beginning.begin(), beginning.end(), number+1);
auto it_end = find(ending.begin(), ending.end(), number-1);
if (it_end != ending.end() && it_begin != beginning.end()){//the number is a bridge
//sew two sub-sequences together.
int const high_seq_pos = distance(beginning.begin(), it_begin);
(*it_end) = ending[high_seq_pos];
beginning.erase(it_begin);
ending.erase(ending.begin() + high_seq_pos);
continue;
}
if (it_end != ending.end()){//can be appended after one existing sequence
++(*it_end);//should equal to number now.
continue;
}//it_end
if( it_begin != beginning.end()){//can be the new beginning of one existing sequence
--(*it_begin);//new begin should be number now
continue;
}
//init case, just insert in the number
beginning.push_back(number);
ending.push_back(number);
}//for ii
int maxLCS = 0;
int maxPos = 0;
for(int ii = 0; ii < beginning.size(); ++ii){
int const localLength = ending[ii] - beginning[ii];
if (maxLCS < localLength){
maxPos = ii;
maxLCS = localLength;
}
}
vector<int> result;
result.reserve(maxLCS);
for(int ii = beginning[maxPos]; ii <= ending[maxPos]; ++ii){
result.push_back(ii);
}
return result;
}//getLCS
};
int main(){
cout<<"Hello"<<endl;
Solution s;
array<int, 6> a = {100,3,200,1,2,4};
vector<int> r = s.getLCS(vector<int>(a.begin(),a.end()));
for(int ii = 0; ii < r.size(); ++ii){
cout << r[ii] << endl;
}
cout<<endl<<endl;
array<int, 8> b ={101, 2, 3, 104, 5, 103, 9, 102};
r = s.getLCS(vector<int>(b.begin(), b.end()));
for(int ii = 0; ii < r.size(); ++ii){
cout << r[ii] << endl;
}
cout<<endl<<endl;
array<int, 9> c ={6, 2, 8, 104, 8, 103, 9, 102,100};
r = s.getLCS(vector<int>(c.begin(), c.end()));
for(int ii = 0; ii < r.size(); ++ii){
cout << r[ii] << endl;
}
}
Monday, November 12, 2012
The longest consecutive sequence
algo: More than one third
/*105 Answers
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo
- shondik on June 27, 2012 in India | Report Duplicate
*/
/**
First step is to find the candicates. There are at most two candidates, each with more than n/3 appearance.
Like Tetris, every time you have 3 different elements in a group, you delete them all. At last, the remaining elements are the candidates with more than n/3 appearance. Due to peogen hole principle, the candicates are at least one element more than the non-candidates.
One round to find the candidates.
Second round to verify the candidates. Overall complexity O(n).
*/
#include <map>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
class Solution{
public:
vector<T> getOverOneThird(vector<T> const& element_array){
vector<T> result;
map<T, int> counter;
for(int ii = 0; ii < element_array.size(); ++ii){
if (counter.size() == 3){//level full, delete or decrement
for(auto it = counter.begin(); it != counter.end();){
if (it->second > 0){
--it->second;
++it;
}
else counter.erase(it++);
}//for it
}//if counter.size()==3
++counter[element_array[ii]];
}//for ii
//now in counter, only the candidates survived
for(auto it = counter.begin(); it != counter.end(); ++it){//init
it->second = 0;
}
for(int ii = 0; ii < element_array.size(); ++ii){//verify the candidates
for(auto it = counter.begin(); it != counter.end(); ++it){//counting
T element = it->first;
if (element_array[ii] == element) ++it->second;
}
}
for(auto it = counter.begin(); it != counter.end(); ++it){//verified
if (3 * it->second > element_array.size()) result.push_back(it->first);
}
return result;
}//getOverOneThird
};
int main(){
cout<<"Hello"<<endl;
array<int, 12> a = {1,1,1,1,1,2,2,2,2,2,3,3};
vector<int> elements(a.begin(), a.end());
Solution<int> s;
vector<int> output = s.getOverOneThird(elements);
for(int ii = 0 ; ii < output.size(); ++ii){
cout<<output[ii]<<endl;
}
}
algo unsolved: 49 car race
Unsolved:
49 race cars and no two have the same speed. Now give you 7 tracks with equal length to find the 25th fastest car. At least how many races are needed.(no time recorder)
Sunday, November 11, 2012
algo: max sum path in a tree
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
Given the below binary tree,
1
/ \
2 3
Return
6. Because you can go from 2 to 3 (via 1) and the total sum is 6
A very good test case is:
Given the below binary tree,
9
/ \
6 -3
/ \ / \
# # -6 2
/ \ / \
# # 2 #
/ \
-6 -6
/
-6
Return
Assume we knew the path for the max sum. We calculate the local maxPathSum that HAS TO include the current node. Compare this local max to the historical max value of the other nodes, and the record the new max.
The local max path must be done recursively with every node: max(maxSumPath(root->left), maxSumPath(root->right))
To find the local max, simply speaking, the path should start from a node in left subtree, go pass node(9), and end at a node in right subtree. When the pass starts from left subtree to node(9), it is a one-way-up path where I call it a single path. This single path has to be maximum when it reaches node(9). So the maxSinglePath of the left subtree is 6. Similarly, the maxSinglePath of the right subtree is 1.
When updating the maxSinglePath, there are 3 sub-cases:
case A: left subtree has a negative maxSinglePath. (returns root+right = 21)
case B: right subtree has a negative maxSinglePath. (returns root+left = 17)
case C: both subtrees have negative maxSinglePath. (returns root = 15)
15 15 15
/ \ / \ / \
-3 6 2 -7 -3 -5
So the maxSinglePath of the root is max(root+left, root+right, root)16. Because you can go from 6 to 2 (via 9, -3, 2) and the sum is 16, which is the max you can get from any two nodes. Here # means NULLAssume we knew the path for the max sum. We calculate the local maxPathSum that HAS TO include the current node. Compare this local max to the historical max value of the other nodes, and the record the new max.
The local max path must be done recursively with every node: max(maxSumPath(root->left), maxSumPath(root->right))
To find the local max, simply speaking, the path should start from a node in left subtree, go pass node(9), and end at a node in right subtree. When the pass starts from left subtree to node(9), it is a one-way-up path where I call it a single path. This single path has to be maximum when it reaches node(9). So the maxSinglePath of the left subtree is 6. Similarly, the maxSinglePath of the right subtree is 1.
When updating the maxSinglePath, there are 3 sub-cases:
case A: left subtree has a negative maxSinglePath. (returns root+right = 21)
case B: right subtree has a negative maxSinglePath. (returns root+left = 17)
case C: both subtrees have negative maxSinglePath. (returns root = 15)
15 15 15
/ \ / \ / \
-3 6 2 -7 -3 -5
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int singleDown;
maxValue = -9999;
return maxPathOverload(root, singleDown);
}
int maxPathOverload(TreeNode* root, int& singleLine){
if (!root){
singleLine = 0;
return 0;
}
int leftSingleLine = 0;
int rightSingleLine = 0;
maxPathOverload(root->left, leftSingleLine);
maxPathOverload(root->right, rightSingleLine);
vector subMaxPath;
subMaxPath.push_back(root->val);//case C
subMaxPath.push_back(root->val + leftSingleLine);//case B
subMaxPath.push_back(root->val + rightSingleLine);//case A
singleLine = *max_element(subMaxPath.begin(), subMaxPath.end());
subMaxPath.push_back(root->val + leftSingleLine + rightSingleLine);//case 1
maxValue = max(maxValue, *max_element(subMaxPath.begin(), subMaxPath.end()));
//compare the path values, which you HAVE TO include the current node
//This eleminate the zero's for null leaf's
return maxValue;
}
};
Thursday, October 25, 2012
Blog updating problem
Thanks to the Great Fire Wall, I found out that the blog can not be viewed from China... Due to the extreme inconvenience, the blog is not updated until I come back to the US...
Friday, July 13, 2012
How to compile a kernel on Ubuntu 10.04
- sudo apt-get install fakeroot kernel-wedge build-essential makedumpfile kernel-package libncurses5 libncurses5-dev
The following packages have unmet dependencies: build-essential: Depends: g++ (>= 4:4.3.1) but it is not going to be installedSolution: Update ubuntu with all packages using update manager.
- Under ~/src/linux-2.6.32, using command
$make menuconfig
- Then I add the home-brewed system call into the file bounds.c (because this file is short).
http://macboypro.wordpress.com/2009/05/15/adding-a-custom-system-call-to-the-linux-os/
http://enzam.wordpress.com/2011/03/26/how-to-add-a-system-call-in-linux-kernel-ubuntu-os/
- I forgot to use this command line below the first time:
sudo update-initramfs -c -k 2.6.32.11+drm33.2-alphaThen I got an unbootable kernel :(
Kernel Panic - not syncing: VFS: Unable to mount root fs on unknown-block(0,0)
- And I had to make a live CD and boot from CD-ROM
http://askubuntu.com/questions/41930/kernel-panic-not-syncing-vfs-unable-to-mount-root-fs-on-unknown-block0-0
Create two folders under /mnt : /mnt/dev and /mnt/proc
Start with a livecd, open a a terminal
sudo fdisk -l
sudo mount /dev/sdax /mnt
sudo mount --bind /dev /mnt/dev
sudo mount --bind /proc /mnt/proc
sudo chroot /mnt
with the new root folder, cd under /boot and find all the kernel versions.
$update-initramfs -u -k 2.6.32.59+drm33.24-alpha
$update-grub
- After boot up, use $uname to verify the booted version.
/**************END******************/
Wednesday, July 11, 2012
Subscribe to:
Posts (Atom)