Google面试题汇总

Google面试题汇总



BST 的 add, find 和 delete 函数
定义一个 BST，然后写 insert 或者 add 方法.就着上面的结构，怎样确定一棵树是不是 BST. 然
后他打了两个例子，让说这个算法是怎么跑的
第五轮是给一个 BST，可以有 duplicate values，找出出现次数最多的 value，还问了一个把
aabbbcc 压缩成 a*2b*3c*2，再解压缩，原来的字符串里可能也有数字和*
determine if a node is in a BST
BTS, 先写了一个 recursive，5 分钟搞定，然后让我写一个不是 recursive 的
build a BST from an array
大数据的查找问题；BST 和 Hash Table 的适用场合以及性能比较；实现任意一个字符串向
float 数的转变。
given one BST, find the Kth minimum value
构建特殊堆 A rooted binary tree with keys in its nodes has the binary search tree property (BST
property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys
in its right subtree are larger than its own key. It has the heap property if, for every node, the keys
of its children are all smaller than its own key. You are given a set of n binary tree nodes that each
contain an integer i and an integer j. No two i values are equal and no two j values are equal. We
must assemble the nodes into a single binary tree where the i values obey the BST property and
the j values obey the heap property. If you pay attention only to the second key in each node, the
tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a
binary search tree.Descri

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

完全没必要的。我之后精简了 code，他觉得好多了。不过我觉得我的表现他应该不
是特别满意吧，毕竟一开始代码不简洁也不高效。之后他问我如果一直这样循环下去，会有
什么后果。我就说 cpu 一直飞速运行，直到内存溢出，因为内存是不可能存储下所有因子的。
他接着问有没有什么方法让循环持续时间更长，找到更多的质数。我说那就把这些因子分块
写到硬盘上，然后每次遍历所有因子的时候按一个 block 一个 block 的来。他说能不能写下
code，我就纳闷，不就加一个 for 循环么。我直接加了个 for each 语句。他看了下，说不高

效，这样每次检查一个数是不是质数，都会遍历所有的 block，disk io 开销太大。我没听懂
意思，以为说我写 for each 的时候需要预先载入所有的 block，我连忙说不是的，这些 block
是链表形式链接的，把 for each 语句改成了链表形式的遍历。他还是不满意，毕竟我没抓住
重点。他说你应该把函数接口变下，输入的数据不应该是一个数，而是一个 block 的数。我
恍然大悟，然后连忙接过话，说这个学过，本质就是编译器课里对嵌套循环的优化嘛，把多
层循环分块，提高 data locality。然后解释说我以为他是让我在降低 time complexity 上再下
功夫，没想到是让我注重算法复杂度里常数因子的开销啊。他虽然表示同意，但是感觉这个
人也许是年纪大的关系，没第一个人活泼，语气很低沉，给我感觉我的表现有些糟糕。
第一个题是 10 进制转换成 26 进制，只让说怎么实现，不让实现，除法，然后取余数，然
后反向输出，接着有问了如果测试，这里就有点 tricky 了，因为 26 进制，所以应该按照两
位 两位的来乘以 26 来输出 原始数据， 既然让说怎么测试了，我顺便也把测 efficiency 说
了一下，本来以为说完就要立马 code 了
十进制十八进制转换，十八进制加法