evi
BAN USER- 1of 1 vote
AnswersAssume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor.
- evi in United States
As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21...
so the pair sequence is:
[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ...
Write a function to output the first n pairs of this sequence.
void Outputpairs(int n)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Define two slots: A and B.
Assume N persons are numbered as 1 to N.
Steps are like this:
put #1 into slot A, #2 into slot B.
If Knows(A, B) == 1, means A knows B, so the person #1 can be removed from slot A, because #1 is not possible to be celebrity; else eliminate #2 in slot B, because it means A does not know B, so B is not possible to be celebrity.
Then put #3 into the empty slot.
Every round of comparison will remove the person either in slot A or B.
After N round of comparison, the one remaining in Slot A or B is the possible celebrity.
Call Knows() between the remaining guy and any other person, to check whether the remaining one is truly the celebrity.
Time complexity is N to 2N, thus O(N)
@Viraj
the statement
if (k%10 == 0) return;
is to handle the case k == 1 in the very beginning. Because when k == 1, only need to go from 1 to 9 not from 0 - 9.
The codes can be written like this as well:
#include<iostream>
using namespace std;
void outputCore(long long v, int N){
if(v > N) return;
int upper = (v == 1 ? 9 : 10);
for(int i = 0; i < upper && v <= N; ++i){
cout << v << endl;
outputCore(v*10, N);
++v;
}
}
int main(){
outputCore(1, 520);
return 0;
}
A very good recursion question.
- evi March 07, 2015Yep, it's a dfs problem.
Use two maps, one map to record the match between each char in pattern and each string segment in target string s; one map to record the inverse. C++
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
class Solution{
public:
bool JudgePattern(string pattern, string s){
if(pattern.empty()) return s.empty();
if(s.empty()) return emptyOrSingleLetter(pattern);
unordered_map<char, string> psmap;
unordered_map<string, char> spmap;
return judgeCore(pattern, 0, s, 0, psmap, spmap);
}
private:
bool judgeCore(string pattern, int t, string s, int p, unordered_map<char, string> &psmap, unordered_map<string, char> &spmap){
int plen = pattern.length(); int slen = s.length();
if(t == plen && p == slen) return true;
if(t == plen || p == slen) return false;
if(psmap.find(pattern[t]) != psmap.end()){
if(p+psmap[pattern[t]].length() > slen) return false;
string tmpstr = s.substr(p, psmap[pattern[t]].length());
if(tmpstr == psmap[pattern[t]])
return judgeCore(pattern, t+1, s, p+psmap[pattern[t]].length(), psmap, spmap);
}else{
for(int q = p+1; q <= slen; ++q){
string subs = s.substr(p, q-p);
if(spmap.find(subs) == spmap.end()){
spmap[subs] = pattern[t];
psmap[pattern[t]] = subs;
if(judgeCore(pattern, t+1, s, q, psmap, spmap))
return true;
psmap.erase(psmap.find(pattern[t]));
spmap.erase(spmap.find(subs));
}
}
}
return false;
}
bool emptyOrSingleLetter(string pattern){
if(pattern.empty()) return true;
for(int i = 1; i < pattern.length(); ++i){
if(pattern[i] != pattern[0]) return false;
}
return true;
}
};
int main(){
Solution sln;
cout << sln.JudgePattern("aaa", "") << endl;
cout << sln.JudgePattern("aba", "red") << endl;
cout << sln.JudgePattern("aabb", "xyzxyzabab") << endl;
cout << sln.JudgePattern("aabb", "xyzxyzab") << endl;
cout << sln.JudgePattern("fbcf", "xyzdoxyz") << endl;
return 0;
}
What raghu means, is calculating out the right, down of each cell in pre-processing, not inside the loop. your code is O(n^4).
Besides right and down, I think also left and up is needed. So each cell will have four values. These four values can be calculated out in four O(N^2) process.
Then traverse all cells from left to right, up to down.
Foreach cell c
int len = Min(c.right, c.down)
for(i = 0; i < len; ++i){
check whether the square using c as left top point and border length = i exists.
}
It's not dynamic programming. Time complexity is bigger than O(N^2) but smaller than O(N^3)
- evi February 07, 2015My idea is same as Jie
c++ code:
#include<iostream>
using namespace std;
void swap(int A[], int i, int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
void AdjustAtoB(int A[], int B[], int n){
if(n <= 1) return;
int zeroInd = 0, tmp = 0, i, j;
for(i = 0; i < n; ++i)
if(A[i] == 0) zeroInd = i;
for(i = 0; i < n; ++i){
if(A[i] != B[i] && B[i] != 0){
for(j = 0; j < n; ++j){
if(A[j] == B[i]){
tmp = j;
break;
}
}
if(A[i] != 0){
swap(A, zeroInd, i);
cout << "For A" << i << ": swap A[" << zeroInd << "](" << A[zeroInd] << ") with A[" << i << "](" << A[i] << ");" << endl;
}
swap(A, i, tmp);
cout << "For A" << i << ": swap A[" << i << "](" << A[i] << ") with A[" << tmp << "](" << A[tmp] << ");" << endl;
zeroInd = tmp;
}
}
}
int main(){
int A[] = {1, 0, 2, 5, 3, 4};
int B[] = {3, 0, 1, 2, 5, 4};
int size = sizeof(A)/sizeof(int);
AdjustAtoB(A, B, size);
int i = 0;
cout << "------B------" << endl;
for(i = 0; i < size; cout << B[i++] << ' ');
cout << endl;
cout << "------A------" << endl;
for(i = 0; i < size; cout << A[i++] << ' ');
cout << endl;
return 0;
}
The solution is really brilliant! But if size of array is very big, like 2147483647, this solution can break because of int over flow.
I use -a[i]-1 instead of division so over flow can be avoided. The sub loop is used to go through the "cycle" in which values are replaced by successors.
worst case time 2n, so O(n). c++ code:
#include<iostream>
using namespace std;
void wap(int A[], int n){
if(n <= 1) return;
int i, tmpV, ind, tmp;
for(i = 0; i < n; ++i){
if(A[i] >= 0 && A[i] != i){
tmpV = A[i];
ind = i;
while(A[ind] != i){
tmp = A[ind];
A[ind] = (-A[A[ind]] - 1);
ind = tmp;
}
A[ind] = (-tmpV - 1);
}
}
for(i = 0; i < n; A[i] = -(A[i]+1), ++i);
}
int main(){
int A[] = {2, 4, 3, 0, 1};
wap(A, sizeof(A)/sizeof(int));
for(int i = 0; i < sizeof(A)/sizeof(int); ++i)
cout << A[i] << ' ';
cout << endl;
return 0;
}
Iterative way, use Time O(n) and Space O(n), with C++
#include<iostream>
#include<string.h>
using namespace std;
int GetHeight(int A[], int n){
if(n <= 1) return 0;
int height[n];
memset(height, 0, sizeof(height));
int v, h, maxH = 0;
for(int i = 0; i < n; ++i){
v = A[i]; h = 0;
while(v >= 0){
if(height[v] > 0){ h+= (height[v] + 1); break; }
else ++h;
v = A[v];
}
height[i] = h;
maxH = max(h, maxH);
}
return maxH;
}
int main(){
int A[] = {3, 3, 3, -1, 2};
cout << GetHeight(A, sizeof(A)/sizeof(int)) << endl;
return 0;
}
If the string can contain duplicate letters, as @CT replies, we can never deduct the original string by random triplet.
Considering string S = "aaaabaaa", the triplet will always be one of the four types: "aab", "aba", "baa", "aaa".
With these four type of triplets we cannot know the real position of 'b' in S, so S will never be deducted.
If there is an extra condition that S does not contain duplicate letters. We can solve it with graph, for a triplet "abc", add a->b, b->c, a->c into the graph.
(Assume the length of S is N)
During constructing the graph, the node whose out-degree first reaches N-1 is the first letter of S, then find the node whose out-degree reaches N-2 first to find the second letter, etc..
One solution, as others already stated, is sorting all three and then use three pointers.
- evi May 22, 2015Assuming array A has M elements, array B has N elements, C has K elements. So above solution has time complexity O(MlogM + NlogN + KlogK)
I came up with another solution, this solution is efficient only when the elements in A, B, C are within a small range, like [0, 1000].
This solution works like this: we define a map<int, tuple<bool, bool, bool> >. tuple<bool, bool, bool> is to record one value's appearance in the three arrays. eg. map[89] = <1, 0, 1> means 89 appears in A, C, but not in B.
Then go through A, B, C to fill the map.
Last step, use two index p, q, to form a window, go through keys from 0-1000, find the smallest window range [p, q], which contains at least one appearance of A, B and C.
Time complexity, O(M + N + K + 1000), where "1000" is the range of values [0, 1000].