/**Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
- 646 on November 23, 2010 | Report Duplicate */
/**For me, it is easier to think of the P-th smallest element
and then use K = N*N-P
For example we have a 4*4 matrix:
1 10 19 20
2 22 30 40
21 30 40 50
39 40 50 60
The numbers are trivial, but the orders and the positions are important.
[0,0] is the smallest.
Ignore the boundary case for now. Every element has two definite directions:
going right or down, which results a larger number.
It is simpler than Dajikstra, we only need to keep the unvisited frontier
elements in a priority queue. Every time we pop an element, mark it visited,
and immediately push in its two neighbors, i.e. right and down neighbors.
*/
/**In C++, the default priorit_queue is a max heap, especially when less-than
is defined.
*/
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <array>
using namespace std;
template <typename T>
class Solution{
typedef tuple<T, int, int> Element;
class ElementMore{
public:
bool operator() (const Element& lhs, const Element& rhs) const{
return get<0>(lhs) > get<0>(rhs);
}
};//class ElementLess
public:
T getSmallRank(vector<vector<T>> const& matrix, int const k){
if (matrix.empty()) return 0;
int const N = matrix.size();
if (N != matrix[0].size()) return 0;//not a square matrix
if (k < 1 || k > N*N) return 0;
//k is the desired rank to return
vector<vector<T>> visitFlag;
visitFlag.resize(matrix.size());
for(auto it = visitFlag.begin(); it != visitFlag.end(); ++it) it->resize(matrix.size());
//init visitFlag to all 0. label 1 for visited
Element element = make_tuple(matrix[0][0], 0, 0);//<value, row, col>
priority_queue<Element, vector<Element>, ElementMore> frontier;
frontier.push(element);
visitFlag[0][0] = 1;
for(int rank = 1; rank < k; ++rank){
element = frontier.top(); frontier.pop();
int const row = get<1>(element);
int const col = get<2>(element);
if (col + 1 < N && !visitFlag[row][col+1]){//element has a right neighbor
frontier.push(make_tuple(matrix[row][col+1],row,col+1));
visitFlag[row][col+1] = 1;
}//right neighbor
if (row + 1 < N && !visitFlag[row+1][col]){//has a down neighbor
frontier.push(make_tuple(matrix[row+1][col],row+1,col));
visitFlag[row+1][col] = 1;
}//down neighbor
}//for rank
return get<0>(frontier.top());
}//getSmallRankP
T getBigRank(vector<vector<T>> const& matrix, int const k){
return getSmallRank(matrix, matrix.size()*matrix.size()-k+1);
}
};
int main(){
cout<<"HEllo"<<endl;
array<int, 4> a = {1 , 10, 19, 20};
array<int, 4> b = {2 , 22, 30, 40};
array<int ,4> c = {21, 33, 40, 50};
array<int, 4> d = {39, 40, 51, 60};
//ranks: 1 ,2, 3, 4, 5, 6, 7
//elements: 1 ,2, 10, 19, 20, 21,22
//and rank 15 is 51
//and rank 16 is 60
vector<vector<int>> matrix;
matrix.resize(4);
matrix[0].assign(a.begin(),a.end());
matrix[1].assign(b.begin(),b.end());
matrix[2].assign(c.begin(),c.end());
matrix[3].assign(d.begin(),d.end());
Solution<int> s;
for(int ii = 1; ii <=7; ++ii){
auto result = s.getSmallRank(matrix,ii);
cout<<result<<endl;
}
cout<< s.getSmallRank(matrix, 15)<<endl<<endl;
cout<< s.getSmallRank(matrix, 16)<<endl<<endl;
cout<< s.getBigRank(matrix, 2)<<endl<<endl;
}
Tuesday, November 13, 2012
Kth Largest element of a sorted matrix
Interleave strings
The best way is to use dynamic programing. Here is an example: The two short strings are b="daba" and a="cbaa", and the long string is "dabacbaa". They are indexed 1 strings. We start from the last elements.
we find out that [4,4] is true.
Link to the C++ code
- Step1. Both a[4] and b[4] matches the element c[8], so the true/false grid [4,4] depends on its two neighbors, [4,3] and [3,4].
- Step2. For grid[4,3], a[4] matches c[7], so dependency goes up to [3,3].
- For grid[3,4], both a[3] and b[4] matches c[7], so dependency goes to two neighbors:[2,4] and [3,3]
- Step3. For grid[3,3], b[3] matches c[6], so go left to [3,2]
- For gird [2,4], a[2] matches c[6], so go up to [1,4]
- Step4. For grid[3,2], no matches to c[5], halt (mark false)
- For grid[1,4], a[1] matches c[5], go up to [0,4]
- Step5-9. [0,4]->[0,3]->[0,2]->[0,1]->[0,0]
we find out that [4,4] is true.
Link to the C++ code
/**Update 12/01/2012. This solution is not correct.
85 Answers
Three strings say A,B,C are given to you. Check weather 3rd string is
interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
- learn on August 27, 2012 in United States | Report Duplicate
*/
/**Hints from the comments.
Simple case: pointers to A,B,C are pA,pB,pC. Compare pA (or pB) agains
pC, if matches, ++pA (or ++pB) if none of pA or pB matches, return false
Duplication case: if pA and pB points to the same character, we call it
a conflict. The conflict character is pushed into a FIFO queue, and do
both ++pA and ++pB. When a non-conflict character appears, register it,
pA, for example. Keep searching until pA does not match the next character,
then you HAVE TO consider the conflict queue before using pB.
The queue should have a higher priority than pA/pB, since the queue stores
elemenens BEFORE the pointers.
When the queue is not empty, the match process switching between pA and pB
are forbidden. Since if pA is in process, the queue equivalently stores
elements BEFORE current pB, so skipping the queue directly to pB
is not allowed.
*/
#include <string>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class Solution{
public:
bool isInterleave(string const& A, string const& B, string const& C){
if (C.length()!= A.length() + B.length()) return false;
deque<int> conflict_que;
int conflict_flag = 0;
for(int aii = 0, bii = 0, cii = 0; cii < C.length(); ++cii){
if (!conflict_que.empty() && conflict_que.front() == C[cii]){
conflict_que.pop_front();
continue;
}//conflict_que has a match
if (A[aii] == B[bii]){
if (A[aii] == C[cii]){
++aii; ++bii; conflict_flag = 0;
conflict_que.push_back(A[aii]);
continue;
} else return false;//A==B, but no match for C
} else if (A[aii] == C[cii]){
if (!conflict_que.empty() && conflict_flag == 2) return false;
//attemp to jump over conflict_que from B
++aii; conflict_flag = 1;
continue;
} else if (B[bii] == C[cii]){
if (!conflict_que.empty() && conflict_flag == 1) return false;
++bii; conflict_flag = 2;
continue;
} else return false;//no match at all, check queue
}//for cii
return true;
}//isInterleave
};
int main(){
cout<< "Hello"<<endl;
string A("aaa");
string B("abc");
string C("aabcaa");
Solution s;
bool result = s.isInterleave(A,B,C);
cout << result <<endl;
A = "abcd"; B ="xyz"; C = "axybczd";
result = s.isInterleave(A,B,C);
cout<< result <<endl;
return 0;
}
Monday, November 12, 2012
The longest consecutive sequence
/**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;
}
}
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;
}
};
Subscribe to:
Posts (Atom)