贡献一下：本版上搜集的 Google 面试题 - 未名空间精华区

贡献一下：本版上搜集的 Google 面试题 - 未名空间精华区

1. Find links/urls from one html page using C++, then how do you store those
links that you found.

2. Design a schema for actors and movies database (one actor can be act one
or
more movies and one movie has more than one actor). Search name of actor,
you
can get a list of movies and search name of movie, you can get a list of
actors. 我数据库老早以前上过一门课，现在全忘光了。:(
3. In a linked list find the nth node from the end of this list.
4. questions about interface and abstract class.

1. design a data structure, this data structure have four functions: pop,
push
, min, top. DO NOT use any stack, queue, list, array or things like this.
2. two binary trees, write a compare function to check if they are equal or
not. equal means they have the same value and same structure.

3. how do you test a calculator.

4. questions about c++, like virtual functions, etc.

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
.
step 1:
sort on each one of those N computers. takes N*N*longN time. If we consider
the
concurrency the overall time taken could be NlogN

step2:
transfer the smallest number on each of thse N computers to the spare box
and
sort them, also  need to keep the information about which computer the
number
comes from.
this takes NlogN time

step3:
after sorting, throw the smallest number out and ask that speicific computer
where the smallest number come from to get the second smallest number, then
resort the numbers on the spare computer. repeat this step untill u have
thrown out N*N/2-1 numbers out, then on the spare
computer the smallest number is the global median number

This step takes NlogN+N*N/2*longN

How to serialize and deserialize 1) a binary tree and 2) a binary graph?

1. How did you get to us ?

2. Which group are you interested in ?

3. Describw what kind of new product you have in mind for google ?

technical :

1. grid problem, how to find the number of paths leading to a character ?
A B D C A
C D A B C
B A C D B
note: any path should startng with A and path should go strictly
alphabetical order. For example, the B in the second row could have two
paths.

2. Book database(very large), how to remove duplicates ? The same book might
have several records in the database due to title misspelling or name
aliases.


- implement a fixed size cache put and get methods. and Least Recently Used
discards
- 两个排序的数组, 找出交集.

=================
Onsite Questions:
=================
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)
1. 用hash table
2. 基本相当于26进制。比如 aa=26*1+1=27, aaa=26*26*1+26*1+1=something
--------------
1. Compute the quotient and remainder of m/n, without using divisionoperator.
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change.
3. Given an array,
i) Find the longest continuous increasing subsequence.
ii) Find the longest increasing subsequence.
4. A building of 100 floors, there is a threshold N s.t. if an egg drops
from Nth floor and above it will break. If it's dropped from any floor below
, it will not break. Given 2 eggs, find this N, and minimize the number of
drops for the worse case.
5. An OO design problem. It's a problem related to his work, I am not
supposed to disclose details.
6. Design a stack. We want to push, pop, and also, retrieve the minimum
element in constant time.
7. Suppose we have N companies, and we want to eventually merge them into
one big company. How many ways are there to merge?

===============
自己提问的问题：
===============
what the search engine will be in its next step?

他们现在的pagerank基于heuristic，有没有进行利用machine learning 去学习
ranking

other questions
===============

Given a list of numbers ( fixed list) Now given any other list, how can you
efficiently find out if there is any element in the second list that is an
element of the first list (fixed list).

两个很长的string，找出它们的longest common string (连续的），要求n*log(n)时
间。

suffix tree

Read full article from 贡献一下：本版上搜集的 Google 面试题 - 未名空间精华区