能有人详细讲一下这两道google的面试题吗? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

能有人详细讲一下这两道google的面试题吗?

能有人详细讲一下这两道google的面试题吗?# Programming - 葵花宝典

s*e2006-12-31 08:12

1 楼

The first one: Write the code using an optimization algriothm to calcuate
the
intersection and union of two sets. (30 mins)
The second one: Write the code for an algriothm to transfrom the index in
excel to the number, and write a class to call this function without
declearing an object. for example: "A, B, C,....AB,AC,..BA,BB,....AAA,AAB,..
."
, transform to "1,2,3,.....", and also transform back.(30 mins)

r*g2006-12-31 08:12

2 楼

g*g2006-12-31 08:12

3 楼

sort two sets individually, merge
O(mlogm) + O(nlogn)
..
base 26 radix, no difference from converting back/forward binary to integer
just change 2 to 26

【在 s*********e 的大作中提到】

: The first one: Write the code using an optimization algriothm to calcuate
: the
: intersection and union of two sets. (30 mins)
: The second one: Write the code for an algriothm to transfrom the index in
: excel to the number, and write a class to call this function without
: declearing an object. for example: "A, B, C,....AB,AC,..BA,BB,....AAA,AAB,..
: ."
: , transform to "1,2,3,.....", and also transform back.(30 mins)

r*g2006-12-31 08:12

4 楼

1.two ways:
(1) hash.
(2)sort first.
Two array A and B, Let array C to store the intersection of A and B
after sorting A and B.Let m be the size of A, n be the size of B.
i=0,j=0;
while(i{
if(A[i]< B[j]) i++;
if(A[i]>B[j]) j++;
else
{
add A[i] to C;
i++;j++;
}
}
then the union is A-C+B;
Time complexity maximum(O(mlogm),O(nlogn))
2.this is 26-based numbers. You should convert between 10-based numbers and
26-based numbers. Simulation is ok.
to call

p*u2006-12-31 08:12

5 楼

yes, static method should be what they asked for.

c*z2006-12-31 08:12

6 楼

for question two, how about make the function static and just
call in this way:
object:func()?

【在 r********g 的大作中提到】

: 1.two ways:
: (1) hash.
: (2)sort first.
: Two array A and B, Let array C to store the intersection of A and B
: after sorting A and B.Let m be the size of A, n be the size of B.
: i=0,j=0;
: while(i: {
: if(A[i]< B[j]) i++;
: if(A[i]>B[j]) j++;