y*****2
发帖数: 22 | 1 第一题的印象有点模糊了。。大概是给一个数组，然后有一些数是重复的，然后找到重
复最多的那个数，比如说 int input[]={3,7,4,3,6,1,3,6}，重复最多的数是3，这些3
的index分别是0 3 6，那么要求程序以相等的概率返回这3个index,
int computeIndex(int[] input);
33.3% return 0
33.3% return 3
33.3% return 6
当时因为叙述的比较绕，所以光题目就理解了半天，最后在他的提示下找到答案：先扫
第一遍，找到出现最多的那个数（比如3），然后写个random函数, 再扫第二遍，每次
遇到3就调用这个Random函数，若Random返回值大于一个阈值就返回当前的index。比如
这个函数可以是
bool ran(int size){
if(random()*size<1)
return true;
return false;
}
叙述的不好，见谅！有问题请提问~
第二题是leetcode原题，Permutation，我用递归做完之后，又让分析算法复杂度，并
问了我在输入在多大的时候算法会崩，递归到多深会崩什么的，然后我扯到了操作系统
的堆栈大小什么的，感觉他不是很满意
第二天就收到了拒信——thanks from facebook.
祝大家好运 | d********e
发帖数: 239 | 2 第一题，为啥不是直接生成一个1到3直接的一个随机数n，然后再扫描一遍，碰到第n个
3就返回index?
些3
【在 y*****2 的大作中提到】
: 第一题的印象有点模糊了。。大概是给一个数组，然后有一些数是重复的，然后找到重
: 复最多的那个数，比如说 int input[]={3,7,4,3,6,1,3,6}，重复最多的数是3，这些3
: 的index分别是0 3 6，那么要求程序以相等的概率返回这3个index,
: int computeIndex(int[] input);
: 33.3% return 0
: 33.3% return 3
: 33.3% return 6
: 当时因为叙述的比较绕，所以光题目就理解了半天，最后在他的提示下找到答案：先扫
: 第一遍，找到出现最多的那个数（比如3），然后写个random函数, 再扫第二遍，每次
: 遇到3就调用这个Random函数，若Random返回值大于一个阈值就返回当前的index。比如
| y*****2
发帖数: 22 | 3 恩，这样做更好！
【在 d********e 的大作中提到】
: 第一题，为啥不是直接生成一个1到3直接的一个随机数n，然后再扫描一遍，碰到第n个
: 3就返回index?
:
: 些3
| l******6
发帖数: 340 | 4 The first problem , I guess the key is you don't know how many 3 are there
in the array and the interviewer want you traverse the array only once
int ret;
int occur = 0;
for(int i = 0 ; i < input . length ; i++)
{
if(input[i] == 3)
{
occur ++;
if(rand()%occur == 0)
ret = i;
}
}
return ret;
and if it is not known which number occurs most times
int ret = 0;
int maxOccur = 0;
int num;
unordered_map occurMap;
unordered_map randomPickMap;
for(int i = 0 ; i < input . length ; i ++)
{
num = input[i];
if(occurMap.count(num))
occurMap[num] += 1;
else
occurMap[num] = 1;
if(rand() % occurMap[num] == 0)
randomPickMap[num] = i;
if(occurMap[num] > maxOccur)
{
maxOccur = occurMap[num];
ret = randomPickMap[num];
}
}
return ret; | d********e
发帖数: 239 | 5 第一个程序有个小错误，return ret?
第二个程序 ret = maxOccur;？or ret = i?
如果不知道出现最多的数是哪个，怎么也得扫两遍吧，要不ret可能记录的是别的数的
index吧
【在 l******6 的大作中提到】
: The first problem , I guess the key is you don't know how many 3 are there
: in the array and the interviewer want you traverse the array only once
: int ret;
: int occur = 0;
: for(int i = 0 ; i < input . length ; i++)
: {
: if(input[i] == 3)
: {
: occur ++;
: if(rand()%occur == 0)
| l******6
发帖数: 340 | 6 Sorry I corrected it.
The reason why I think it is allow to traverse the array once is this may be
a super long array or it is streaming data. The problem is like shuffle
streaming data.
Program 2 I corrected it
【在 d********e 的大作中提到】
: 第一个程序有个小错误，return ret?
: 第二个程序 ret = maxOccur;？or ret = i?
: 如果不知道出现最多的数是哪个，怎么也得扫两遍吧，要不ret可能记录的是别的数的
: index吧
| p**o
发帖数: 3409 | 7 # Q1
import random
def compute_index (input):
counter = {}
for i, x in enumerate(input):
counter.setdefault(x, []).append(i)
indices = max(counter.itervalues(), key=len)
return random.choice(indices)
>>> compute_index([3,7,4,3,6,1,3,6]) | x*********1
发帖数: 23 | 8 能不能解释下rand()/occur?
【在 l******6 的大作中提到】
: The first problem , I guess the key is you don't know how many 3 are there
: in the array and the interviewer want you traverse the array only once
: int ret;
: int occur = 0;
: for(int i = 0 ; i < input . length ; i++)
: {
: if(input[i] == 3)
: {
: occur ++;
: if(rand()%occur == 0)
| l******6
发帖数: 340 | 9
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
random shuffle with special case that leaves only one element
【在 x*********1 的大作中提到】
: 能不能解释下rand()/occur?
|
|
