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 | | 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
: .
|
|
