Refdash 面经

eiei39 发表于 2017-8-6 19:19
第一题返回最大值的index，第一遍找最大值，第二遍如果从保存了所有最大值的index中随机返回一个，那space ...

查到了这个问题。
one pass 和 two passes 都给了方法:
https://stackoverflow.com/questi ... ability-of-1-number

kafkagre 发表于 2017-8-5 08:06
dead end leaf 的意思是这个BST不能有duplicate的node是吧？

就是返回不能继续添加子节点的叶子节点。
比如说
           4
       2        5
          3
这个3就是一个dead leaf..

eiei39 发表于 2017-8-6 19:19
第一题返回最大值的index，第一遍找最大值，第二遍如果从保存了所有最大值的index中随机返回一个，那space ...

one pass： 用 Reservoir sampling LC398的简化。
Two pass:
第一遍统计最大值的个数。记做Counts
int ithMax = rand(1,Counts)//生成1～Counts的随机数
第二遍：找到ithMax个最大值，返回index

能问下面试官名字嘛

我也面了，其中一道是减squre number能否赢的题，另一道是给一个数组,  arr = [3, 4, 2, 3, 0, 3, 1, 2, 1], and a startIndex.
当你在index i 的时候， 你可以左跳或又跳arr[i] 的距离，问你是否可以到达值0的位置。

请问第二题用dp怎么做的？

感谢楼主分享，同问第二题是怎么做的

FightForTomo 发表于 2017-8-7 14:07
就是返回不能继续添加子节点的叶子节点。
比如说
           4

这题中序遍历用recursive可能好写一点。

话说楼主当时二面是些啥题？

lavender41 发表于 2017-12-11 02:31
这题中序遍历用recursive可能好写一点。

求看代码，我至今没想明白。