2.17 GOOGLE ONSITE 跪经 求分

题目都很常规啊

http://stackoverflow.com/questions/6979276/select-random-value-not-in-array

kinggarden2001 发表于 2016-2-27 12:22
概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。

概率那题是不是要先把list 遍历一遍把数存进hash. 这样免得每次生成随机数之后，还得花O(n)去判断那个数是否在list中？

概率那题应该是用二分来解得，因为一般来讲N会给的极大，K应该是个合理的数字。
可以考虑把每一个禁止的数都从右边填上相应的数，比如N = 4，list= {1,3}，数组就应该是{2,4,X,X}，那么随机生成[0,N - k)范围的数，然后output对应位置的数即可。
因为又不可能将每一位的具体数字求出来，所以我现在只想到了用二分 + 二分的O(lgNlgK)的解法。第二个二分用来计算<=该值得list中的数有多少个

longest substring at most K distinct char 楼主这题的优化是怎么做的没太明白。如果你只记录最后一个出现这个char的序号，如果出现这种情况怎么办？
1112223 k＝2

夜辉冥 发表于 2016-3-23 01:30
longest substring at most K distinct char 楼主这题的优化是怎么做的没太明白。如果你只记录最后一个出现 ...

LRU的size不超过k的时候，慢指针不用动，快指针往前走，减一减就是substring长度
快指针走到3的时候，更新完LRU size会超过2，这个时候慢指针指到LRU头结点存的idx，再删掉LRU头

论坛匿名用户 发表于 2016-2-27 17:10
从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去

第三题 array是空 需要跳过去， 如果mid 的value的空， 那么该往左移动index， 直到找到第一个不是空的， 与target比较大小， 如果小于target， left = mid+1, 大于target， right = index-1, 当然也有特殊情况， 如果index == left 了 并且是空，应该直接设为left ＝ mid ＋ 1， 但是 这样的running time 在最差情况下 是O(n)吧。

论坛匿名用户 发表于 2016-2-27 17:10
从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去

另外 空的位置 是随机的么， 还是连在 一块的？

adiggo 发表于 2016-3-25 14:58
第三题 array是空 需要跳过去， 如果mid 的value的空， 那么该往左移动index， 直到找到第一个不是空的， ...

感觉这道题，就是讨论，最后复杂度还是O(n)

3, binary search， 就是注意下如果是mid=empty, 先search右边， 找不到再search左右；如果是mid>=target, search左边；如果是mid<target, search右边找不到的话，return mid