I could see myself with that "deer in the headlights" look. (note to self.. don't apply to Google)
does anyone have answers to question #7 to #9?
Question #7) How many 0's are at the end of N!
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Question #7) How many 0's are at the end of N!
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Originally posted by: sjgmoney
Originally posted by: AStar617
I just had an image in my head of Google's offices... chock full of Rain Men who can answer all those questions instantly but can't make a can of soup
Or get laid.
Soup? Laid? Now you're just making words up aren't you?
ViviTheMage
Lifer
I'm not sure if I get this one. The resulting array should have size len(S1)+len(S2)+len(S3) right? Then can't we just use mergesort on the indexes and then swap integer<->word to create the array?
i.e. what's the catch?
Answer to Question #7) There are NO 0's at the end of N. N is a letter and doesn't have any numbers after it!
I just had my first phone technical interview with google for a Software Engineering position in the Brazil office.
I got one of them completely and got 2/3 of the other two. Do you guys think I have a chance?
I got one of them completely and got 2/3 of the other two. Do you guys think I have a chance?
Update people!
I've passed the first phone technical interview and will be atending an interview on site here in Brazil!
Acording to the recruiter there should be two on-site interviews if I am to be hired. Wish me luck folks!
I've passed the first phone technical interview and will be atending an interview on site here in Brazil!
Acording to the recruiter there should be two on-site interviews if I am to be hired. Wish me luck folks!
Congrats, and good luck!
My solution to the general problem of trying to find the median among N machines having N integers each is similiar to the solution Google gave you for just two machines:
Sort the integers on each machine so they are in order.
From each machine, get the highest and the lowest integer (i.e. the first and the last).
Sort the collection of high and lows into a single list.
Now repeat the following (n^2 -n) / 2 times:
From your master list, take the lowest low, tell the machine that provided it to remove it from its list, and to provide it next lowest number. Take the highest high, tell the machine that provided it to remove it from its list and to provide its next highest number.
Take the new low and and the new high number and insert them into your master list such that it is still ordered.
/repeat
You will be left with exactly a total of n integers-- get them from each machine, and find the median among those n integers.
Another solution:
Suppose you already have the solution for problem #1 (merging k infinite, sorted streams into a single sorted stream).
Have each machine sort their integers, and then treat each machine's list as a stream. Using your solution to problem #1, create a single sorted stream.
If n is odd, your median will simply be the (n^2 + 1 ) /2 'th element.
If n is even, your median will be the average of the (n^2)/2 and (n^2)/2 + 1 elements.
Got my google interview next week, so found these questions.
Here are my versions of what I think could be right.
------------------------------------------------------------------------------------------------------------------
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm
to merge the k streams into a new stream (also in sorted order).
ANS: Take first element in each of the 'k' streams and identify the smallest among these. Stick this one (if there are more
than 1 with the same value pick the one from the stream with the smallest id) at the next slot in the merged list. This
should be possible in O(k). Repeat this till all elements are exhausted. If a stream has been exhausted dont consider it in
any more comparisons. Total time complexity O(k.n). Generally k would be small compared to 'n', so this will scale reasonably
well. Of course if k=n then you have hit the worst case. ;-)
BTW this is a typical database question. Look up any database design book and you will see what I mean. They use this
extensively in merge-sort for 'join' operations in databases.
------------------------------------------------------------------------------------------------------------------
Question #2) Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk,
and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires
40gb.
ANS: Ok, now it totally depends on how huge the number of 'key->value' pairs are present.
If number of 'key->value' pairs is small enough to fit completely in memory and the number of queries i.e. one is expected to
make a lot of 'key' queries then it makes sense to just use a hash. With a hash solution all that you need to do is store the
mappings in memory. If you want persistence write it to disk sequentially and next time when the queries are to be make read
all the pages into memory. Obviously this solution will work only if the number of queries to follow are so huge that it will
offset the intial cost of reading the pages one by one from disk into memory. Also important to note is that if on the disk
you write the pages in continguous sectors the reads will be fast (only transfer time and no seek & rotation latency for the
disk head). So this solution will be good if the size is small. Read in this case will be O(1) and no disk access at all.
However most likely what the interviewer is trying to test is the other case where the number of key->value pairs is so huge
that it wont fit in memory completely. Again this is a classic database problem. The idea here is to use B+ trees. So with a
B+ tree you are creating a 'n' way tree where 'n' is the minimum number of records in one node of the B+ tree. Look up any
book for how B+ trees are implemented. Since B+ trees are balanced a look up is just log N to base 'n'. In practice the look
up just takes 3 to 4 disk accesses.
------------------------------------------------------------------------------------------------------------------
Question #3) Given N computers networked together, with each computer storing N integers, describe a procedure for finding
the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2
integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the
computers storing the integers.
Ok I really dont know if my solution for this one is good enough. Also I am going to assume that it is possible to overwrite
the values on the machines. Then all that you need to do is sort them as a whole using the free computer. This can be done in
O(N.logN). Then go to the middle computer and pick the middle element for the answer.
Obvious problems I see:
1. Assumption is too hard. May be the numbers are read only.
2. Sorting is expensive. May be theres a better solution.
------------------------------------------------------------------------------------------------------------------
Question #4) Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for
term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the
corresponding element of S1.
S1 to S2 is easy. This is just like the atoi function. Except that we have a radix of 26 and not 10.
unsigned int S1toS2(char *str)
{
unsigned int value = 0;
for (int i=0;str='\0';i++)
{
value = value*26 + (str-'a'+1);
}
return value;
}
Assumptions:
1. str is a legitamate string i.e. has only characters from a-z.
2. The corresponding value will be something that can be stored in an 'int' i.e. 0 < value < 2^32
3. As from the previous line -> no negative numbers allowed.
S2 to S1 is also easy. Just he opposite though.
char* S2toS1(int value)
{
char *str = malloc(sizeof(char)*(MAXVALUE+1)); // Assume we know the maximum number of characters required
if (str == null) return null;
for (int i=0;value>0;i++)
{
int t = value%26;
value = value/26;
str = t+'a'-1;
str[i+1] = '\0'; // I am lazy, you can move this out of the loop
}
strrev(str); // Reverse the string.
return str;
}
------------------------------------------------------------------------------------------------------------------
Question #5) Given a binary tree with the following constraints:
a) A node has either both a left and right child OR no children
b) The right child of a node is either a leaf or NULL
// Call this function initially as -
// node *newRoot = invert(root,null);
// Assumption: root is non-null
node* invert(node *me, node *parent)
{
node *newRoot = null;
if (me->lchild != null)
{
newRoot = invert(me->lchild,me);
}
// Switch the position of the nodes
if (parent != null)
{
// Only for the original root the parent will be null
me->rchild = parent->rchild;
parent->lchild = null;
}
me->lchild = parent;
// For the last node newRoot will be null
if (newRoot == null)
{
newRoot = me;
}
return newRoot;
}
------------------------------------------------------------------------------------------------------------------
Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the
square than to the edge of the square.
I am not sure about this but here is my approach:
1. Consider only the triangle formed by the center of the square and one side of the square (say right side).
The locus of points which are equidistant from the side and the center would be
sqrt(x^2 + y^2) = 1/2 - x (assume that the center of the square is at (0,0) then side is the line x=1/2)
So this gives the equation for this side of the square (so this is y^2+4x=1).
Similarly we can derive for the other sides too. I am guessing it will be
x^2+4y=1
x^2-4y=1
and y^2-4x=1.
So we have the 4 curves(parabolae) which can be joined to give the final set of points.
I dont really like this because it does not sound very simple or intuitive. I am wondering how I would have solved something
like this on the spot. ;-)
------------------------------------------------------------------------------------------------------------------
Question #7) How many 0's are at the end of N!
To do this you just need to see some examples. Say N = 100
for 0's you just need to catch the number of 5's. Since number of 2's will always be greater than number of 5's - each 5 will
result in a 0.
So if N=100
100/5 = 20
20/5 = 4
4/5 = 0
Sum = 24...
So just do this for any other N.
------------------------------------------------------------------------------------------------------------------
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given
3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si
represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our
array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm
for an arbitrary number of search terms.
hint: think of the brute force algorithm first
... brute force is rather intuitive... dont feel like typing it out...
------------------------------------------------------------------------------------------------------------------
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Ok, all that you need for this is a modified version of stack (could be implemented as link list) but with an additional
pointer for every node + 1 global pointer.
So here is how a NODE will look:
struct node
{
int value;
int *next; //Next node in the stack
int *nextMin; //Next node in the stack which had the smallest value
};
and a global int *min which points to the smallest number in the stack.
So here is how the operations would look for an input like:
push 4, push 3, MIN, push 5, pop, MIN
Initially stack: NULL (min=null)
push 4: NULL,4:NULL (min=pointer to node with value 4)
push 3: NULL,4:NULL,3:1 (min= pointer to node with value 3)
MIN: just return the value of min pointer
push 5: NULL,4:NULL,3:1,5:NULL (min still points to value 3)
pop: Just remove 5 (no need to adjust min pointer because anyway the pointer from 5 in NULL)
Had the pop been before we pushed 5 - we need to pop 3 but adjust the min pointer to the node 4.
Here are my versions of what I think could be right.
------------------------------------------------------------------------------------------------------------------
Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm
to merge the k streams into a new stream (also in sorted order).
ANS: Take first element in each of the 'k' streams and identify the smallest among these. Stick this one (if there are more
than 1 with the same value pick the one from the stream with the smallest id) at the next slot in the merged list. This
should be possible in O(k). Repeat this till all elements are exhausted. If a stream has been exhausted dont consider it in
any more comparisons. Total time complexity O(k.n). Generally k would be small compared to 'n', so this will scale reasonably
well. Of course if k=n then you have hit the worst case. ;-)
BTW this is a typical database question. Look up any database design book and you will see what I mean. They use this
extensively in merge-sort for 'join' operations in databases.
------------------------------------------------------------------------------------------------------------------
Question #2) Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk,
and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires
40gb.
ANS: Ok, now it totally depends on how huge the number of 'key->value' pairs are present.
If number of 'key->value' pairs is small enough to fit completely in memory and the number of queries i.e. one is expected to
make a lot of 'key' queries then it makes sense to just use a hash. With a hash solution all that you need to do is store the
mappings in memory. If you want persistence write it to disk sequentially and next time when the queries are to be make read
all the pages into memory. Obviously this solution will work only if the number of queries to follow are so huge that it will
offset the intial cost of reading the pages one by one from disk into memory. Also important to note is that if on the disk
you write the pages in continguous sectors the reads will be fast (only transfer time and no seek & rotation latency for the
disk head). So this solution will be good if the size is small. Read in this case will be O(1) and no disk access at all.
However most likely what the interviewer is trying to test is the other case where the number of key->value pairs is so huge
that it wont fit in memory completely. Again this is a classic database problem. The idea here is to use B+ trees. So with a
B+ tree you are creating a 'n' way tree where 'n' is the minimum number of records in one node of the B+ tree. Look up any
book for how B+ trees are implemented. Since B+ trees are balanced a look up is just log N to base 'n'. In practice the look
up just takes 3 to 4 disk accesses.
------------------------------------------------------------------------------------------------------------------
Question #3) Given N computers networked together, with each computer storing N integers, describe a procedure for finding
the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2
integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the
computers storing the integers.
Ok I really dont know if my solution for this one is good enough. Also I am going to assume that it is possible to overwrite
the values on the machines. Then all that you need to do is sort them as a whole using the free computer. This can be done in
O(N.logN). Then go to the middle computer and pick the middle element for the answer.
Obvious problems I see:
1. Assumption is too hard. May be the numbers are read only.
2. Sorting is expensive. May be theres a better solution.
------------------------------------------------------------------------------------------------------------------
Question #4) Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for
term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the
corresponding element of S1.
S1 to S2 is easy. This is just like the atoi function. Except that we have a radix of 26 and not 10.
unsigned int S1toS2(char *str)
{
unsigned int value = 0;
for (int i=0;str='\0';i++)
{
value = value*26 + (str-'a'+1);
}
return value;
}
Assumptions:
1. str is a legitamate string i.e. has only characters from a-z.
2. The corresponding value will be something that can be stored in an 'int' i.e. 0 < value < 2^32
3. As from the previous line -> no negative numbers allowed.
S2 to S1 is also easy. Just he opposite though.
char* S2toS1(int value)
{
char *str = malloc(sizeof(char)*(MAXVALUE+1)); // Assume we know the maximum number of characters required
if (str == null) return null;
for (int i=0;value>0;i++)
{
int t = value%26;
value = value/26;
str = t+'a'-1;
str[i+1] = '\0'; // I am lazy, you can move this out of the loop
}
strrev(str); // Reverse the string.
return str;
}
------------------------------------------------------------------------------------------------------------------
Question #5) Given a binary tree with the following constraints:
a) A node has either both a left and right child OR no children
b) The right child of a node is either a leaf or NULL
// Call this function initially as -
// node *newRoot = invert(root,null);
// Assumption: root is non-null
node* invert(node *me, node *parent)
{
node *newRoot = null;
if (me->lchild != null)
{
newRoot = invert(me->lchild,me);
}
// Switch the position of the nodes
if (parent != null)
{
// Only for the original root the parent will be null
me->rchild = parent->rchild;
parent->lchild = null;
}
me->lchild = parent;
// For the last node newRoot will be null
if (newRoot == null)
{
newRoot = me;
}
return newRoot;
}
------------------------------------------------------------------------------------------------------------------
Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the
square than to the edge of the square.
I am not sure about this but here is my approach:
1. Consider only the triangle formed by the center of the square and one side of the square (say right side).
The locus of points which are equidistant from the side and the center would be
sqrt(x^2 + y^2) = 1/2 - x (assume that the center of the square is at (0,0) then side is the line x=1/2)
So this gives the equation for this side of the square (so this is y^2+4x=1).
Similarly we can derive for the other sides too. I am guessing it will be
x^2+4y=1
x^2-4y=1
and y^2-4x=1.
So we have the 4 curves(parabolae) which can be joined to give the final set of points.
I dont really like this because it does not sound very simple or intuitive. I am wondering how I would have solved something
like this on the spot. ;-)
------------------------------------------------------------------------------------------------------------------
Question #7) How many 0's are at the end of N!
To do this you just need to see some examples. Say N = 100
for 0's you just need to catch the number of 5's. Since number of 2's will always be greater than number of 5's - each 5 will
result in a 0.
So if N=100
100/5 = 20
20/5 = 4
4/5 = 0
Sum = 24...
So just do this for any other N.
------------------------------------------------------------------------------------------------------------------
Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given
3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si
represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our
array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm
for an arbitrary number of search terms.
hint: think of the brute force algorithm first
... brute force is rather intuitive... dont feel like typing it out...
------------------------------------------------------------------------------------------------------------------
Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time
Ok, all that you need for this is a modified version of stack (could be implemented as link list) but with an additional
pointer for every node + 1 global pointer.
So here is how a NODE will look:
struct node
{
int value;
int *next; //Next node in the stack
int *nextMin; //Next node in the stack which had the smallest value
};
and a global int *min which points to the smallest number in the stack.
So here is how the operations would look for an input like:
push 4, push 3, MIN, push 5, pop, MIN
Initially stack: NULL (min=null)
push 4: NULL,4:NULL (min=pointer to node with value 4)
push 3: NULL,4:NULL,3:1 (min= pointer to node with value 3)
MIN: just return the value of min pointer
push 5: NULL,4:NULL,3:1,5:NULL (min still points to value 3)
pop: Just remove 5 (no need to adjust min pointer because anyway the pointer from 5 in NULL)
Had the pop been before we pushed 5 - we need to pop 3 but adjust the min pointer to the node 4.
wow first time reading some google interview questions. I didn't read all 12 pages, but I was wondering how much time do they give you to answer these questions? 2 hours? In the very few programming courses I took at UC Irvine, there were like maybe 3 or 4 questions on a 1 hour midterm. 5 or 6 questions on a 2 hour final. Even if I knew how to develop the algorithms, but had to answer ALL of those questions on page 1, it'll probably take me half a day. Ofcourse, no way in hell I would know how answer those questions.
So I had an interview @ google a few months ago. I had a couple of the questions mentioned but the one in particular I haven't seen the "correct" (as given to me) answer for was this. It helped, because they gave it to me as a 2 part question.
1) Determine the median of a set of N numbers on 1 machine
2) Determine the median of a set of M*N number partitioned equally amongst M machines.
For the first part, you can do better than N log N. Think of what a median means ... the middlemost number. So you can imagine you're given an array with N numbers, and after your operation you have an array, but in the N/2 location the "middlemost" number is there. This algorithm, where after each iteration you have a particular single place set with the correct value is similar to quicksort. So you pick a random index, and partition the array based on that digit. The difference is instead of recursively calling quicksort on both sides of the array, you call on the range that encompasses the median-index.
Analysis of Running Time:
So the running time will be of the form T(N) = N + T(N/2). The N factor is because partitioning can be done in linear time. The T(N/2) factor is because at each step you *roughly* reduce the set in half. If you expand this, you'll get N + N/2 + N/4 + ... which is bounded by O(N).
2) Run 1) on each of the M computers. This can be done in parallel, so it'll take N time. Next, on the master machine take the M median numbers, and figure out the middlemost of all of those (note that this is not the median of all the numbers, it's just an indicator). Now go back to the M machines and query "how many numbers do you have in your set that are greater than X" where X is the median you just figured out. If these numbers add up to N/2, you're done. So now you know if the median is smaller or larger than this number, and you should also know how many numbers are between the median & X. <Here I'm drawing a blank on how I got to the next step ... I had the interview in February. So I apologize if you've read this far, and are disappointed>. So at this point, I said now you do this same operation, but on the subrange you computed. The interview agreed, but then said "you dont need to, you can just compute the K-th element where K is the difference between X & the median . How do you compute the K-th element" so I told him the answer to that problem and we just continued with the interview (BTW, the K-th element is the same as 1) above, just replace the N/2 index with K). The brought me back for a second round (and eventually gave me an offer) so I guess this answer was/is good enough.
1) Determine the median of a set of N numbers on 1 machine
2) Determine the median of a set of M*N number partitioned equally amongst M machines.
For the first part, you can do better than N log N. Think of what a median means ... the middlemost number. So you can imagine you're given an array with N numbers, and after your operation you have an array, but in the N/2 location the "middlemost" number is there. This algorithm, where after each iteration you have a particular single place set with the correct value is similar to quicksort. So you pick a random index, and partition the array based on that digit. The difference is instead of recursively calling quicksort on both sides of the array, you call on the range that encompasses the median-index.
Analysis of Running Time:
So the running time will be of the form T(N) = N + T(N/2). The N factor is because partitioning can be done in linear time. The T(N/2) factor is because at each step you *roughly* reduce the set in half. If you expand this, you'll get N + N/2 + N/4 + ... which is bounded by O(N).
2) Run 1) on each of the M computers. This can be done in parallel, so it'll take N time. Next, on the master machine take the M median numbers, and figure out the middlemost of all of those (note that this is not the median of all the numbers, it's just an indicator). Now go back to the M machines and query "how many numbers do you have in your set that are greater than X" where X is the median you just figured out. If these numbers add up to N/2, you're done. So now you know if the median is smaller or larger than this number, and you should also know how many numbers are between the median & X. <Here I'm drawing a blank on how I got to the next step ... I had the interview in February. So I apologize if you've read this far, and are disappointed>. So at this point, I said now you do this same operation, but on the subrange you computed. The interview agreed, but then said "you dont need to, you can just compute the K-th element where K is the difference between X & the median . How do you compute the K-th element" so I told him the answer to that problem and we just continued with the interview (BTW, the K-th element is the same as 1) above, just replace the N/2 index with K). The brought me back for a second round (and eventually gave me an offer) so I guess this answer was/is good enough.
Originally posted by: DAGTA
Originally posted by: EKKC
i doubt people in google knows how to answer this.
which makes me mad why they test you in a job interview, that's just plain stupid.
good thing before i landed my current job last august, i been to 3 interviews and none of them tested me (they all gave me offers too, batting 1.000
I don't. Google has and continues to make a point of hiring the best people that can find. That is how they are able to make such amazing software. The technology behind their massive server farms is incredible.
QFT... some of those problems are quite hard. For inifinite streams question, I don't think there is a totally efficient way of solving that, but if you were given an infinite stream to merge the streams in, then you could append the streams with a counter for the number of hits to a stream where the number is the index of the stream.
Otherwise, this is a very simple Turing machine (if you assume the current streams are already in order). If it isn't in order it is just a little more complex (meaning the output stream has to be in able to be traversed in both directions or that you have to have multiple/infinite output strings one with the final output). I am going to print out these problems and see if I can solve them. Google is very tough to get in to though.
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 25K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes Discussion Threads
- Started by Tigerick
- Replies: 21K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
-
Facebook
Twitter