Google 不甘心的跪经

10月底面的Google onsite，
第一轮三姐，问题是常见的给字典，再给词语前缀，然后返回所有是该前缀的词语，用Trie加DFS做出
第二轮白人小哥，一开始问了一道至今不懂的问题，好像是给一个vector<uint8_t> nums, 然后又给一个256位的vector<int> counts，遍历nums，然后

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
白人小哥，第一题，判断括号是否合法，秒做，第二题，两个array表示两个整数，相加，秒做，第三题很有意思，给一个逻辑运算树，问最少翻转几个运算符可以翻转最终结果，例如，(True && False) || (False || True)，结果是true，若想翻转成false，最少翻转一次(第三个||翻转成为&&)，没写code，讨论下来应该分情况讨论然后recursive做


跪在第二轮，白人大叔，题目是部分sort，即sort数组中一半的元素，例如{9, 1, 8, 3, 0} sort成{0, 1, 9, 3, 8}，本来用quick sort 加个条件解决即可，但是大叔硬是要我用C++的template，语法忘记，结果卡了三十分钟，大叔也一直不给提示，心态爆炸，最后算法也没用对，面到四十分钟大叔就说有事先走了，真的是不甘心，之前onsite也有一些轮答得不是很好，但没有这么差过，竟然完跪在最后加面一轮。

比较两个 bst 只需要比较两个的 preorder 一样。

因为知道 preorder，inorder 就已经确定（BST），然后根据 preorder 和 inorder 就可以还原出一棵 binary tree。

小A要当码农 发表于 2016-12-1 04:19
梁神 这个题的idea是不是先对原数组做partition,求得第K大的元素M，然后双指针，比M小的放数组左边，比M ...

嗯我感觉应该是用quick sort变体，比如在找数组的最后一个数，然后双指针遍历数组，找到比这个数小的数k1个，比这个数大的数k2个，如果k1等于(k - 1)，就找到了这个数，k1大于(k - 1)，在比这个数小的数里找第k个，k1大于(k - 1)，在比这个数大的数里找第(k - 1 - k1)个，应该和你的想法一样，毕竟庄神

hwu2498 发表于 2016-11-23 13:38
稀疏矩阵我觉得就用嵌套hashtable就能解决吧？因为如果是十字链表你也得是 doublely-linkedlist吧，这样你 ...

补充一下，这道问题还需要写将矩阵整行整列设为某个值的函数，你说得好像也有道理。。 这里需要用到两个hash，hash(row, hash(col, val)), hash(col, hash(row, val))，时间复杂度是一样，不过因为要从两个里面都插入或者删除，代码应该还是十字链表应该要简洁一些

请问一下第三题， in order 的比较方法我有一点疑问？比如 root(1).right(3) 和 root(3).left(1)的in order是一样的，但是树的结构不一样，这种是不是就不适用了？ 楼主能解释一下iterator是怎么写的嘛，我只想到递归判断两课树是否相等的写法，不过没有用到BST的性质。

一半sort 不应该是 0 1 3 吗

zyoppy008 发表于 2016-11-22 16:52
一半sort 不应该是 0 1 3 吗

哦哦 两个也可以

luffy_zc 发表于 2016-11-22 15:22
请问一下第三题， in order 的比较方法我有一点疑问？比如 root(1).right(3) 和 root(3).left(1)的in order ...

同想知道iterator是怎么写的、、、

luffy_zc 发表于 2016-11-22 15:22
请问一下第三题， in order 的比较方法我有一点疑问？比如 root(1).right(3) 和 root(3).left(1)的in order ...

Inorder 输出的数组是排序好的，因为是BST所以肯定可以比较。后面的iterator大叔加了两个条件，一个是知道最小那个数的node，另一个是每个node有个parent，这样就很简单了，implement next与hasnext

lyc1994 发表于 2016-11-22 22:39
并没有明年，要去google只能以后跳槽了sigh...

对啊-.-...那就跳槽咯~~~.