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'=c01, otherwise c0'=c0.
c1': if current element is 1, then c1'=c11, otherwise c1'=c1.
(c0,c1) c1c0 (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 = c1c0;
if(h.ContainKey(diff))
{
int len=ih[diff]+1;
if(len>max)
{
max=len;
}
}
if(a[i]==0)
{
diff++;
}
else
{
diff;
}
if(!h.ContainKey(diff)
{
h.Add(diff, i);
}
}
return max;
}

jiangok2006
July 19, 2012 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 maxmin. 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<n1;++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;
}

jiangok2006
July 18, 2012 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);
}
}

jiangok2006
July 17, 2012 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;
}

jiangok2006
July 16, 2012 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

jiangok2006
July 15, 2012 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[n1];
// 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)*21;
}
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;
}

jiangok2006
July 14, 2012 Another solution 
It is redundant to pass in an array from 1n, 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(ni, k1, i+1, buf, cur+1);
}
}
}

jiangok2006
July 13, 2012 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)));
}

jiangok2006
July 12, 2012 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]) + (n1i) > n2 ? 0 : atoi(a2[in1+n2]) + ca;
s[n1i] = 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]);
}
}

jiangok2006
June 23, 2012 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, rightBracketPos2); // +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;
}
}

jiangok2006
June 23, 2012 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;
}
}

jiangok2006
June 23, 2012 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.len1;
if(p[p1]=='?')
{
s1++;
p1++;
}
else if(p[p1]=='*')
{
if(p1==p.len1)
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';
}

jiangok2006
October 16, 2010 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;
}

jiangok2006
October 16, 2010 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}, {sx})
}
void print(arr S1, arr S2)
{
if(S1.len==k)
print(S1);
else
foreach x in S2
print(S1+x, S2x);
}

jiangok2006
October 04, 2010 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;

jiangok2006
October 03, 2010 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=n1;i>1;i)
{
for(int j=1;j<8n+1;++j)
{
nums[i]<<j;
print(Sum(nums));
}
}
}

jiangok2006
October 02, 2010 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(m1,n)+f(m,n1);
}
}
Open Chat in New Window
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)