jiangok2006
BAN USER- 0of 0 votes
AnswersGiven N matrix production (A1*A2*A3...*AN), different matrix can have different dimensions but they satisfy the production requirement. For example, A1 is 2x3, then A2 can be 3x4 but not 5x2. When a 3x2 matrix products a 2x4 matrix, the total number of number production required is 24. How to reduce the total number of number production when calculating (A1*A2*A3...*AN)?
- jiangok2006 in United States| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersThere are 4 types of coins (25 cent, 10 cent, 5 cent and 1 cent). Given a number, return the minimum number of coins whose sum equals to this number. What about the 4 types of coins changes to (25, 10, 6, 1)? Write code.
- jiangok2006 in United States| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersGiven N matrix production (A1*A2*A3...*AN), different matrix can have different dimensions but they satisfy the production requirement. For example, A1 is 2x3, then A2 can be 3x4 but not 5x2. When a 3x2 matrix products a 2x4 matrix, the total number of number production required is 24. How to reduce the total number of number production when calculating (A1*A2*A3...*AN)?
- jiangok2006 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersdesign a data structure for caching the result of "int getSmallestBiggerPrime(int)" so that the client side can reduce the trips to the server as much as possible. There are some examples in format of input->output: 1->1, 2->2, 3->3, 4->5, 5->5, 6->7, 7->7, 8->11, 9->11...
- jiangok2006 in United States
The interviewer did not say whether to use Least Recently Used (LRU) or Most Recently Used (MRU). But he gave a requirement using an example, suppose the user inputs 6 and gets 7 last time, the next time when he inputs 7, there should be no server trip to get 7 as the result.| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersUse iteration to find the common ancestor of two nodes on a BST.
- jiangok2006 in United States| Report Duplicate | Flag | PURGE
Coding - 0of 0 votes
AnswersGiven a line, adjust this line to the page width.
- jiangok2006 in United States
For example, given "Dog is cute" (length of chars is 11) and the page width is 15, adjust the line to "Dog is cute". The extra spaces should be distributed as much even as possible. Assume there is no space before the first word or after the last word.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 1of 1 vote
AnswersGiven preorder traversal array of a BST, recontruct the BST.
- jiangok2006 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 2 votes
AnswersGiven API:
- jiangok2006 in United States
int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 0of 0 votes
AnswersInput a string and a pattern having . and *
- jiangok2006
Output: whether the string fully matches the pattern
. match any char, * means matching 0 or more times.
Example:
input "a", "." => match
input "abc", ".*" => match
input "abcd", "a.*d" => match| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersInput:
- jiangok2006
Either an object array having integer, string and boolean, like
{"abc", "ab,c", 10, true, false}
Or a hash table like
{"a1":"abc","t":true,"e":123}
Output:
If object array, output
"abc"
10
true
If hash, output
"a1":"abc"
"t" : true
"e" : 123| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
Assume input is 11010
c0: count of 0 counted from beginning.
c1: count of 1 counted from beginning.
c0': if current element is 0, then c0'=c0-1, otherwise c0'=c0.
c1': if current element is 1, then c1'=c1-1, otherwise c1'=c1.
(c0,c1) c1-c0 (c0',c1') c1'-c0'
1 (0,1) 1 (0,0) 0
1 (0,2) 2 (0,1) 1
0 (1,2) 1 (0,2) 2
1 (1,3) 2 (1,2) 1
0 (2,3) 1 (1,3) 2
if for i and j (j>i), c1[j]-c0[j] = c1'[i]-c0'[i], then a subsequence of equal 0's and 1's is found from i to j. For example, (1,4),(2,3)....
int f(int* a, int n)
{
Hash<int,int> h = new Hash<int, int>();
int c0=0;
int c1=0;
int max=INT_MIN;
for(int i=0;i<n;++i)
{
if(a[i]==0)
c0++;
else
c1++;
int diff = c1-c0;
if(h.ContainKey(diff))
{
int len=i-h[diff]+1;
if(len>max)
{
max=len;
}
}
if(a[i]==0)
{
diff++;
}
else
{
diff--;
}
if(!h.ContainKey(diff)
{
h.Add(diff, i);
}
}
return max;
}
Like
- jiangok2006 July 19, 2012It seems that there is some misconceptions.
1) the original question did not ask for time complexity of O(n) at all. It just asked going through once.
2) the bit vector way is not O(n) (n is the number of array element). Instead, it is O(m) where m is max-min. m has nothing to do with n and maybe m>>n.
void f()
{
//parse input, create table
int n = 0;
int* a = null;
char** table = null;
scanf("%d\n", &n);
a = new int[n];
table = new (char*)[n];
for(int i=0;i<n;++i)
{
table[i]=new char[n+1];
}
scanf("%d %d %d\n", &a[0], &a[1], &a[2]);
for(int i=0;i<n;++i)
{
scanf("%s\n", table[i]);
}
//find minimum
//double loop, look up table
for(int i=0;i<n-1;++i)
{
for(int j=i+1;j<n;++j)
{
if(a[i]>a[j] && table[i][j]=='y')
{
swap(a[i],a[j]);
}
}
}
printf("%d %d %d\n", a[0], a[1], a[2]);
for(int i=0;i<n;++i)
{
delete[] table[i];
}
delete[] table;
delete[] a;
}
get the biggest three (may <3) and the smallest three (may <3). The max product is the max of any of the three numbers taken from these 6 numbers (may <6). There are at most 20 combinations of these (at most) 6 numbers. This avoids convoluted code to handling different cases.
- jiangok2006 July 18, 2012sort
- jiangok2006 July 18, 2012void main()
{
Node *r, *a, *b; // r is the root of the tree. a and b are the two nodes to find.
... // construct tree having r as root
bool fa, fb; // fa: found a, fb: found b.
fa = fb = false;
f1(r,a,b,&fa,&fb);
}
void f1(Node *r, Node *a, Node *b, bool *fa, bool *fb)
{
if(r==null || a==null || b==null)
return false;
if(r==a)
{
*fa = true;
}
if(r==b)
{
*fb = true;
}
bool fa1, fb1;
fa1 = fb1 = false;
f1(r->left, a, b, &fa1, &fb1);
*fa |= fa1;
*fb |= fb1;
if(!*fa || !*fb) // if a or b is not found, search right child.
{
fa1 = fb1 = false;
f2(r->right, a, b, &fa1, &fb1);
*fa |= fa1;
*fb |= fb1;
}
if(*fa && *fb) // if found both a and b, print r.
{
print(r);
}
}
ok.
- jiangok2006 July 17, 2012Like
- jiangok2006 July 17, 2012The solutions using n! do not handle repeating char cases elegantly. Below solution does not use n! and handle repeating char cases. The permutation is very time consuming. Hope to see more elegant solution.
int f(char* a, int st, int end)
{
if(st>end) return 0;
int r = 0;
for(int i=st+1; i<=end; ++i)
{
if(a[st]>a[i])
{
swap(a[i], a[st]);
r += perm(a, st+1, end);
swap(a[i], a[st]);
}
}
r += f(a, st+1, end);
return r;
}
int perm(char* a, int st, int end) // permutation
{
int r=1; // start from 1 to consider the existing one.
for(int i=st+1;i<=end;++i)
{
if(a[st]!=a[i])
{
swap(a[st],a[i]);
r += perm(a, st+1, end);
swap(a[st],a[i]);
}
}
return r;
}
The question is wrong. You cannot use preorder and postorder array to distinguish below two full trees.
1
/ \
1 1
/ \
1 1
1
/ \
1 1
/ \
1 1
QuickSort should work. I doubt there is O(n) solution.
- jiangok2006 July 14, 2012// n is the size of the heap array
// a is the min heap array.
void f(int* a, int n)
{
int k = n;
int i = 0;
while(i<k)
{
if(LeftExists(i, k) && a[i]==a[Left(i)])
{
Remove(a, Left(i), n);
k--;
}
else if(RightExists(i, k) && a[i]==a[Right(i)])
{
Remove(a, Right(i), n);
k--;
}
else if(LeftExists(i,k) && RightExists(i,k) && a[Left(i)]==a[Right(i)])
{
Remove(a, Right(i), n);
i++;
k--;
}
else
{
i++;
}
}
}
void Remove(int* a, int i, int n)
{
a[i] = a[n-1];
// if the new node value is bigger than its children, heapify down.
while(true)
{
if(LeftExits(i,n) && a[i]>a[Left(i)])
{
swap(a[i], a[Left(i)];
i=Left(i);
}
else if(RightExists(i,n) && a[i]>a[Right(i)])
{
swap(a[i], a[Right(i)]);
i=Right(i);
}
else
{
break;
}
}
// if the new node value is smaller than its parent, heapify up.
while(true)
{
if(i!=0 && a[i]<a[Parent(i)])
{
swap(a[i], a[Parent(i)];
i=Parent(i);
}
else
{
break;
}
}
}
int Left(int i)
{
return (i+1)*2-1;
}
int Right(int i)
{
return Left(i)+1;
}
int Parent(int i)
{
if(i==0) return -1;
return floor((i+1)/2)-1;
}
bool LeftExists(int i, int n)
{
return Left(i)<n;
}
bool RightExists(int i, int n)
{
return Right(i)<n;
}
Another solution -
It is redundant to pass in an array from 1-n, so the main function f() just takes n and k.
void f(int n, int k)
{
int *a = new int[k]; // for print the combinations
f1(n, k, 1, a, 0)
}
void f1(int n, int k, int min, int* buf, int cur)
{
if(n==0 && k==0)
{
print(buf, cur); // print the combination from 0 to cur.
return;
}
if(k>0)
{
for(int i=min; i<n+1;++i)
{
buf[cur]=i;
f1(n-i, k-1, i+1, buf, cur+1);
}
}
}
bool f(char* s1, char* s2, char* s3)
{
if(*s1 == '\0' && *s2 == '\0' && *s3 == '\0')
{
return true;
}
if (*s3 == '\0')
{
return false;
}
if (*s1 == '\0' && *s2 == '\0')
{
return false;
}
return ((*s1==*s3 && f(s1+1, s2, s3+1)) ||
(*s2==*s3 && f(s1, s2+1, s3+1)));
}
like except that str?++ should be ++str?.
I thought this problem is permutation but it is not.
Like
- jiangok2006 July 08, 2012use sliding window
- jiangok2006 June 28, 2012Like
- jiangok2006 June 24, 2012n1 does not include '\0'
char* add (char* a1, int n1, char* a2, int n2)
{
if (n1 < n2)
{
return add (a2, n2, a1, n1);
}
char *s = new char[n1+2]; // 2: 1 for '\0', 1 for the possible carrier.
int ca = 0;
for (int i=n1; i>-1; i--)
{
int t = atoi(a1[n1]) + (n1-i) > n2 ? 0 : atoi(a2[i-n1+n2]) + ca;
s[n1-i] = t%10;
ca = t/10;
}
if (ca != 0)
{
s[n1+1] = ca;
s[n1+2] = '\0';
len = n1+1;
}
else
{
s[n1+1] = '\0';
len = n1;
}
revert (s, len);
return s;
}
void revert (char * s; int len)
{
int i=0, j=len;
while (i<j)
{
swap(s[i++], s[j--]);
}
}
enum OperatorType
{
Invalid,
Add,
Substract,
Multiply,
Divide
}
input: "5 + 3 * ( 6 - 4 )"
the result is f (exp, 0, 17); // 17 include '\0'
int f (char* exp, int st, int end)
{
int a = INT_MAX;
int b = INT_MAX;
OperatorType op = Invalid;
for (int i=st; i<end+1;)
{
if (IsNum (exp[i]))
{
if (op == Invalid)
{
SetOperand (&a, exp[i]);
}
else
{
SetOperand (&b, exp[i]);
}
i++;
}
else (IsOperator (exp[i]))
{
SetOperator (&op, exp[i]); // translate exp[i] to operator
i++;
}
else (IsLeftBracket (exp[i]))
{
int rightBracketPos = FindRightBracket (exp, i+2, end);
int sub = f (exp, i+2, rightBracketPos-2); // +2, -2 is to skip the space and the current bracket
if (op == Invalid)
{
a = sub;
}
else
{
b = sub;
}
i += rightBracketPos - i + 1; // go to the next space
}
else if (IsSpace (exp[i]) || exp[i] == '\0')
{
if (b != INT_MAX)
{
a = Compute (a, b, op);
b = INT_MAX;
op = Invalid;
}
i++;
}
}
return a;
}
void SetOperand (int *a, int e)
{
if (*a == INT_MAX)
{
*a = e;
}
else
{
*a = (*a) * 10 + e;
}
}
enum EDirec
{
RIGHT = 0,
LEFT
}
void f(Node* r)
{
Stack s;
EDirec d = RIGHT;
int cLevel = 1;
int cNextLevel = 0;
if (!r) return;
s.push(r);
while (!s.empty)
{
Node *cur = q.pop();
if (cLevel == 0)
{
cLevel = cNextLevel;
cNextLevel = 0;
d = ~d;
}
if(d == Right)
{
if(cur->left)
{
s.push(cur->left);
cNextLevel++;
}
if(cur->right)
{
s.push(cur->right);
cNextLevel++;
}
}
else
{
// reverse enqueue
}
cLevel--;
}
}
bool f(s, p)
{
if(!P)
return false;
if(s==null)
return (p=="*");
p1=p;
s1=s;
while(p[p1])
{
if(s[s1]==null)
return p[p1]=='*' && p1==p.len-1;
if(p[p1]=='?')
{
s1++;
p1++;
}
else if(p[p1]=='*')
{
if(p1==p.len-1)
return true;
else
if(s[s1+1]==p[p1+1])
return f(s.sub(s1+1),p.sub(p1+1)) || f(s.sub(s1+1), p.sub(p1));
else
return f(s.sub(s1+1),p.sub(p1));
}
else
{
if(s[s1]==p[p1])
{
s1++;
p1++;
}
else
{
return false;
}
}
}
return s[s1]=='\0';
}
main()
{
print(r);
}
void print(NODE* r)
{
if(r==null)
{
return;
}
print(r);
int sl=sum(r->l);
int sr=sum(r->r);
if(sl>sr)
print(s->l);
else
print(s->r);
}
int sum(NODE* n)
{
if(n==null)
return 0;
int sl=sum(n->l);
int sr=sum(n->r);
if(sl>sr)
return n.value+sl;
else
return n.value+sr;
}
f(A)={A}
f(B)={B}
f(C)={C}
f(A,B)={AB, BA}=A*f(B)+B*f(A)
f(A,C)={AC,CA}=A*f(C)+C*f(A)
f(B,C)={BC,CB}=B*f(c)+C*f(B)
f(A,B,C)=A*f(B,C)+B*f(A,C)+C*f(A,B)
=A*(B*f(C)+C*f(B)) + B*(A*f(C)+C*f(A)) + C(A*f(B)+B*f(A))
void f(arr s)
{
foreach x in s
print({x}, {s-x})
}
void print(arr S1, arr S2)
{
if(S1.len==k)
print(S1);
else
foreach x in S2
print(S1+x, S2-x);
}
input a line, a pattern
output true if matched word >0.4, false otherwise
int wordCount=0;
foreach lineword in the line
{
wordCount++;
int matchCount=0;
foreach patternword in the pattern
{
if lineword==patternword
{
matchCount++;
break;
}
}
}
return matchCount/wordCount>0.4;
assume the number of 1 is n, a number uses a byte (8bit).
edge cases and error handling is ignored.
f(int n)
{
int[] nums=new int[n];
for(int i=0;i<n;++i)
{
nums[i]=1<<i;
}
print(Sum(nums));
for(int i=n-1;i>-1;--i)
{
for(int j=1;j<8-n+1;++j)
{
nums[i]<<j;
print(Sum(nums));
}
}
}
suppose the matrix is m*n and the function f() is to get the paths count from the left bottom corner to the right upper corner. edge case and error handling is ignored.
f(int m, int n)
{
if(m==1 || n==1)
{
return 1;
}
else
{
return f(m-1,n)+f(m,n-1);
}
}
The best case is 11: the first 10 race determine the 1st place (say 1st is A and potential 2nd is B) and sort the horses inside each group. The 11 race sorts B with the rest 8 in A's group. If B is slower than at least 4 horses in A's group, then the rest 5 fastest horses are determined.
- jiangok2006 July 19, 2012What's the worst case? My answer is 25.
10 races determine the 1st place. 1 race for 2nd, 2 races for 3nd, 3 races for 4nd... (10+1+2+3+4+5=25)