由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G面试题
相关主题
这些找missing number的题是不是都不能用求和做?Google电话面试题目
问道fackbook面试题问个面试题
smiley同学的面试题分类总结链接谁那有问个微软面试题
也问一个算法题问个google面试题
亚麻新鲜面经amazon一道面试题
Amazon电面题目bloomberg 店面
A家onsite,已悲剧今天又被recuiter 鄙视了,大家来教育下我吧。
麻烦2爷peking2帮个忙amazon问题求教
相关话题的讨论汇总
话题: tree话题: contains话题: binary话题: whether话题: arrays
进入JobHunting版参与讨论
1 (共1页)
i****c
发帖数: 102
1
Some questions:
1. find PI using simulation
2. design a cache (interface, implements different cache strategies)
3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
} is the same as {1,3,2}
Any O(n) approach? what if the range of the integers in the arrays are huge?
4.
if a tree can be converted to the other by only swaping the labels between s
ibling nodes, then the two trees are considered to be variants of each other
.
A database contains a lot of binary trees, given a binary tree,
1) how to decide whether the database contains the tree.

2) how to decide whether the database contains the tree or contains a varian
t of the tree.
5. find common prefix of a set of strings.
z**********g
发帖数: 209
2
抛砖引玉一下
Some questions:
1. find PI using simulation
monte carlo simulation
2. design a cache (interface, implements different cache strategies)
LRU hashtable + double linked list
3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
} is the same as {1,3,2}
Any O(n) approach?
bitmap
what if the range of the integers in the arrays are huge?
hashtable
4.
if a tree can be converted to the other by only swaping the labels between s
ibling nodes, then the two trees are considered to be variants of each other
.
A database contains a lot of binary trees, given a binary tree,
1) how to decide whether the database contains the tree.
Every tree needs to store the number of nodes, and look for the same tree
size and then preorder + inorder?
2) how to decide whether the database contains the tree or contains a varian
t of the tree.
brute force n^2, and it looks expensive ya.
5. find common prefix of a set of strings.
trie. Do we need to implement trie on white board?
Thanks.
y******5
发帖数: 43
3
3. bitmap不能处理repeated integer吧。

{1,2,3

【在 z**********g 的大作中提到】
: 抛砖引玉一下
: Some questions:
: 1. find PI using simulation
: monte carlo simulation
: 2. design a cache (interface, implements different cache strategies)
: LRU hashtable + double linked list
: 3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
: } is the same as {1,3,2}
: Any O(n) approach?
: bitmap

c******t
发帖数: 1500
4
这是 Google的 onsite面试题?
f*********i
发帖数: 197
5
都是这么难吗,太夸张了一点吧。
第一题谁能给个思路啊,monte carlo simulation好像没有说圆周率的。
第三题的思路如下
hashtable先过一遍{1,2,2,3}, 这次是往hashtable加的,hashtable的value可
以是
if(hash.get(i)!=null){
hash.put(i,hash.get(i)+1);
}
然后再过一遍(1,3,2,2)如果hash的值为0,那么就remove这个element from hash
,最后check if the hash is empty.
保证了O(n)和重复数字的问题
C***y
发帖数: 2546
6
第一题用一个【0-1】rand number generator
然后每次产生两个数,分别对应一个点的x,y坐标
如果到(0.5,0.5)的距离小于等于0.5,则计数加1
符合条件的点的个数除以总的点的个数,就是半径为0.5圆的面积
再用PI*0.5^2就可以反算出PI

hash

【在 f*********i 的大作中提到】
: 都是这么难吗,太夸张了一点吧。
: 第一题谁能给个思路啊,monte carlo simulation好像没有说圆周率的。
: 第三题的思路如下
: hashtable先过一遍{1,2,2,3}, 这次是往hashtable加的,hashtable的value可
: 以是
: if(hash.get(i)!=null){
: hash.put(i,hash.get(i)+1);
: }
: 然后再过一遍(1,3,2,2)如果hash的值为0,那么就remove这个element from hash
: ,最后check if the hash is empty.

i****c
发帖数: 102
7
如果要求O(1)空间复杂度呢?

hash

【在 f*********i 的大作中提到】
: 都是这么难吗,太夸张了一点吧。
: 第一题谁能给个思路啊,monte carlo simulation好像没有说圆周率的。
: 第三题的思路如下
: hashtable先过一遍{1,2,2,3}, 这次是往hashtable加的,hashtable的value可
: 以是
: if(hash.get(i)!=null){
: hash.put(i,hash.get(i)+1);
: }
: 然后再过一遍(1,3,2,2)如果hash的值为0,那么就remove这个element from hash
: ,最后check if the hash is empty.

i****c
发帖数: 102
8
建议半径用1,
首先默认的随机数是0到1的
其次,算距离就不用开根号了

【在 C***y 的大作中提到】
: 第一题用一个【0-1】rand number generator
: 然后每次产生两个数,分别对应一个点的x,y坐标
: 如果到(0.5,0.5)的距离小于等于0.5,则计数加1
: 符合条件的点的个数除以总的点的个数,就是半径为0.5圆的面积
: 再用PI*0.5^2就可以反算出PI
:
: hash

C***y
发帖数: 2546
9

我就是想到哪写到哪了
算四分之一个圆就可以了
从原点开始算距离

【在 i****c 的大作中提到】
: 建议半径用1,
: 首先默认的随机数是0到1的
: 其次,算距离就不用开根号了

c*****c
发帖数: 188
10
4.When store the binary tree, store (a) structure encoding (b) data, which
is a list containing the content of each internal nodes
For encoding a binary tree, see
http://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_bi
DB contains that binary tree if it has a record of the exact encoding and
data of the that tree.
DB contains a variant of the binary tree if it has a record of the exact
encoding but the permutation of the data of that tree
t****o
发帖数: 31
11
如果数组中没有重复integer的话,可以用XOR判断。

【在 i****c 的大作中提到】
: 如果要求O(1)空间复杂度呢?
:
: hash

y******5
发帖数: 43
12
{1,4} != {2,3}

【在 t****o 的大作中提到】
: 如果数组中没有重复integer的话,可以用XOR判断。
j*****n
发帖数: 1545
13
算pi 可以用 buffon's needle. 最经典的办法,
y***m
发帖数: 7027
14
3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
} is the same as {1,3,2}
Any O(n) approach? what if the range of the integers in the arrays are huge?
遍历数组求
A1/B1*A2/B2..An/Bn=1
A1-B1+A2-B2..An-bn=0
4。不懂二叉树和数据库怎么个对应关系?
5. find common prefix of a set of strings.
挨个并行移动发现有一个不同就停止,返回的就是所要?

,3
huge?
s
other

【在 i****c 的大作中提到】
: Some questions:
: 1. find PI using simulation
: 2. design a cache (interface, implements different cache strategies)
: 3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
: } is the same as {1,3,2}
: Any O(n) approach? what if the range of the integers in the arrays are huge?
: 4.
: if a tree can be converted to the other by only swaping the labels between s
: ibling nodes, then the two trees are considered to be variants of each other
: .

1 (共1页)
进入JobHunting版参与讨论
相关主题
amazon问题求教亚麻新鲜面经
问一道面世题Amazon电面题目
一个电面题A家onsite,已悲剧
问个amazon店面题麻烦2爷peking2帮个忙
这些找missing number的题是不是都不能用求和做?Google电话面试题目
问道fackbook面试题问个面试题
smiley同学的面试题分类总结链接谁那有问个微软面试题
也问一个算法题问个google面试题
相关话题的讨论汇总
话题: tree话题: contains话题: binary话题: whether话题: arrays