贾乃亮：还我一个美好的明天 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>bagua - 娱乐八卦

贾乃亮：还我一个美好的明天

贾乃亮：还我一个美好的明天# bagua - 娱乐八卦

w*l2018-01-07 08:01

1 楼

刚面完，感觉一般，估计挂了....
寒暄，文件里上的project,接下来算法：
find majority element in an array. 我说用hash table，但是空间效率
低，我自己说了个constant space的idea, 写code。写完问我怎么extend
to最一般的情况, 我说了自己的idea, 然后说什么时间不够了，就不用写代码了，
他理解啥的.....

h*e2018-01-07 08:01

2 楼

圈里圈外都是李小璐出轨的文章，各路英雄好汉都在心疼贾乃亮。我默默看着天空，突
然不习惯莫斯科的温度给我带来的寒冷。
曾经有人说，贾乃亮的爱过于卑微。一个过于卑微的爱情在水深的娱乐圈，想要一起慢
慢变老，那就是痴人说梦。
你是不是也有一个曾经爱你卑微如尘土的人？
你是不是任性的以为他永远不会离开你，可以永远包容你的小任性。
女孩子可以在自己男人面前任性，男人也可以在自己女人面前卑微。但是高高在上的人
，像女王般把自己的男人当成佣人一般看待，那就不是爱了。
我始终相信，爱是相互的，不是一方迁就，一方肆无忌惮的践踏对方的尊严。
能被一个人卑微着爱着是一件何其幸运的事情。
卑微并不是他应该做的，而是他愿意为了爱甘愿放下身段迎合你，让你开心。
所以，身边有一个卑微爱着你的人，你是否可以好好换位思考一番，也让他感受到你对
他的在意。别让一腔柔情渐渐疲惫。我们都不是无所不能的神，可以让你在我心窝子捅
一刀，我还能微笑的说，没关系，我就是犯贱。
呵，没有人喜欢找虐。
好吧，我可以大度点，允许你虐我身体，但你给我带绿帽子，啧啧，我还能委曲求全？
马蓉出轨，王宝强为了维护权利，维护男人的自尊，站出来公开马蓉和宋喆的龌蹉行为
，最后宋喆赔了夫人又折兵，锒铛入狱。马蓉没了王宝强这颗摇钱树，日子也没见到有
做王太太那般舒心，现在不就成了过街老鼠人人喊打？想当初王宝强又何尝不是在痛苦
的边缘苦苦挣扎？娱乐圈还真是扎心，先是马蓉打头炮出轨震惊娱乐圈，紧接而上的就
是白百何出轨风波，呵呵，常在河边走，哪有不湿鞋？苍蝇不叮无缝的蛋，你在那里苍
白无力的靠公关团队来洗白，也依旧逃不过网友的火眼睛睛翻出来的蛛丝马迹。
2018贾乃亮最大的愿望估计是希望这个社会还他一个美好的明天吧。
好事不出门，坏事传千里。
娱乐圈一个事多的地方！

b*v2018-01-07 08:01

3 楼

你的constant space的idea是什么呀

。
extend
写代码了，
.....

【在 w****l 的大作中提到】

: 刚面完，感觉一般，估计挂了....
: 寒暄，文件里上的project,接下来算法：
: find majority element in an array. 我说用hash table，但是空间效率
: 低，我自己说了个constant space的idea, 写code。写完问我怎么extend
: to最一般的情况, 我说了自己的idea, 然后说什么时间不够了，就不用写代码了，
: 他理解啥的.....

s*y2018-01-07 08:01

4 楼

想红想疯了123456789

f*42018-01-07 08:01

5 楼

同问

s*y2018-01-07 08:01

6 楼

想红想疯了123456789

w*l2018-01-07 08:01

7 楼

就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
就记下来了。不是本人原始想法，本人是菜鸟级的).

【在 b******v 的大作中提到】

: 你的constant space的idea是什么呀
:
: 。
: extend
: 写代码了，
: .....

a*n2018-01-07 08:01

8 楼

曹雪芹写书将真事隐
李小璐出轨把假奶亮

f*42018-01-07 08:01

9 楼

可他只要知道那个数是majority啊，只要碰到相同ele vote++就好了啊
还有，啥叫最一般的情况啊？
谢谢

=
，觉得挺好，

【在 w****l 的大作中提到】

: 就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
: array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
: vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
: 就记下来了。不是本人原始想法，本人是菜鸟级的).

f*62018-01-07 08:01

10 楼

is this for summer intern or full-time position?
Good luck!

w*l2018-01-07 08:01

11 楼

majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
vote变
量。

【在 f****4 的大作中提到】

: 可他只要知道那个数是majority啊，只要碰到相同ele vote++就好了啊
: 还有，啥叫最一般的情况啊？
: 谢谢
:
: =
: ，觉得挺好，

w*l2018-01-07 08:01

12 楼

New Graduate Full Time Position, Mountain View

【在 f******6 的大作中提到】

: is this for summer intern or full-time position?
: Good luck!

b*v2018-01-07 08:01

13 楼

这样的话，要扫描很多次吧？

=
，觉得挺好，

【在 w****l 的大作中提到】

w*l2018-01-07 08:01

14 楼

一次就够了....

【在 b******v 的大作中提到】

: 这样的话，要扫描很多次吧？
:
: =
: ，觉得挺好，

b*v2018-01-07 08:01

15 楼

你第一次的扫描只是对array[0] vote吧
难道不要对array[1]...array[n-1]也做一次vote吗？

【在 w****l 的大作中提到】

: 一次就够了....

w*l2018-01-07 08:01

16 楼

如果这么理解的话那就是多次扫描了，我个人认为constant time可以得到array[i]],
所以整个数
组就是依次扫描了，难道是多次扫描？不理解中....请指教....

【在 b******v 的大作中提到】

: 你第一次的扫描只是对array[0] vote吧
: 难道不要对array[1]...array[n-1]也做一次vote吗？

f*42018-01-07 08:01

17 楼

哦，我把majority理解错了
可那样的话，还是只需要统计每个ele的出现次数啊，最后扫描出现次数大于n/2的就是
；这样的话对n/k的也能不做修改直接实现啊（只要比较出现次数大于n/k的就好了）
bless

【在 w****l 的大作中提到】

: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。

d*82018-01-07 08:01

18 楼

不用的呀，当vote变零的时候你也要更新Element然后重置vote为一

【在 b******v 的大作中提到】

: 你第一次的扫描只是对array[0] vote吧
: 难道不要对array[1]...array[n-1]也做一次vote吗？

c*t2018-01-07 08:01

19 楼

如果 ele > n/2 楼主的方法可行。如果是n/k, 搂主能不能讲讲两个votes 的方法。

l*42018-01-07 08:01

20 楼

co-ask

【在 c********t 的大作中提到】

: 如果 ele > n/2 楼主的方法可行。如果是n/k, 搂主能不能讲讲两个votes 的方法。

f*e2018-01-07 08:01

21 楼

how to do that?

【在 w****l 的大作中提到】

: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。

a*92018-01-07 08:01

22 楼

lz的做法只用到constant space, 扫描一次就够了,
如果统计每个数出现的次数就不是constant space了

【在 f****4 的大作中提到】

: 哦，我把majority理解错了
: 可那样的话，还是只需要统计每个ele的出现次数啊，最后扫描出现次数大于n/2的就是
: ；这样的话对n/k的也能不做修改直接实现啊（只要比较出现次数大于n/k的就好了）
: bless

a*92018-01-07 08:01

23 楼

make clear一件事，大于n/k的majority也是只有一个数么？并且所有的数都不超过n/k
吗？

【在 w****l 的大作中提到】

: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。

w*l2018-01-07 08:01

24 楼

不是这个意思，有可能有两个，比如k=3,那么就是要找出现频率超过n/3的数，至于
其他数是不是
也都小于这个数，不清楚....所以我一时没想出什么解法来...sigh.....估计是挂面了
....

/k

【在 a***9 的大作中提到】

: make clear一件事，大于n/k的majority也是只有一个数么？并且所有的数都不超过n/k
: 吗？

a*92018-01-07 08:01

25 楼

这个code测试了么是到vote=0的时候往后就换成后面一个element吧

=
，觉得挺好，

【在 w****l 的大作中提到】

a*92018-01-07 08:01

26 楼

2个变量怎么整？
如果 k = 4, 就有可能有3个大于n/4的元素吧
猜测可以用k-1个vote, 增vote时不用++，用vote+=k-1，减就用--，到0时换成后面的
元素

【在 w****l 的大作中提到】

: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。

w*l2018-01-07 08:01

27 楼

测试过了，是正确的，至于扩展的版本，我还没有完全想明白......不好意思.....

【在 a***9 的大作中提到】

: 这个code测试了么是到vote=0的时候往后就换成后面一个element吧
:
: =
: ，觉得挺好，

a*92018-01-07 08:01

28 楼

问一下element的元素不更新？那如果不是arr[0]怎么找的出来啊。。可能我理解错了
你意思

【在 w****l 的大作中提到】

: 测试过了，是正确的，至于扩展的版本，我还没有完全想明白......不好意思.....

w*l2018-01-07 08:01

29 楼

我贴一下code 吧，基本版本，扩展的没想好：
#include
#include
int findMajorityElem(int array[], int n){

int maj_index =0;

int votes = 1;

for (int i = 1; i< n; i++){
if (array[i] == array[maj_index] ){
votes ++;
}else if(votes >0){
votes--;
}else{
maj_index = i;
votes = 1;
}
}

return array[maj_index];
}
//For testing purpose
int main(){
int arr[] ={1,3,3,3,1,2};

int nu

a*92018-01-07 08:01

30 楼

对的吧。你还是更新了的

【在 w****l 的大作中提到】

: 我贴一下code 吧，基本版本，扩展的没想好：
: #include
: #include
: int findMajorityElem(int array[], int n){
:
: int maj_index =0;
:
: int votes = 1;
:
: for (int i = 1; i< n; i++){

b*y2018-01-07 08:01

31 楼

Google 电面我挂了

c*t2018-01-07 08:01

32 楼

大于n/k的element, 是不是得把数组无序变有序再找，preprocess: O(nlg(n)),
search time O(n)

r*12018-01-07 08:01

33 楼

对于[3,1,2,3]这个数组，你的findMajorityElem返回值是2，应该是3.
int findMajorityElem(int array[], int n){

int maj_index =0;

int votes = 1;

for (int i = 1; i< n; i++){
if (array[i] == array[maj_index] ){
votes ++;
}else if(votes >0){
votes--;
}else{
maj_index = i;
votes = 1;
}
}

return array[maj_index];
}

b*v2018-01-07 08:01

34 楼

对，他那个算法有问题

【在 r**********1 的大作中提到】

: 对于[3,1,2,3]这个数组，你的findMajorityElem返回值是2，应该是3.
: int findMajorityElem(int array[], int n){
:
: int maj_index =0;
:
: int votes = 1;
:
: for (int i = 1; i< n; i++){
: if (array[i] == array[maj_index] ){
: votes ++;

f*42018-01-07 08:01

35 楼

如果不是还有别的条件没讲清楚的话
这个votes的办法是求不出majority的

【在 r**********1 的大作中提到】

l*42018-01-07 08:01

36 楼

I have the similar solution.
There is k-1 votes.
each time check the k-1 votes. Here is the pseudocode.
for(i = 0 to n-1)
{
flag = true;
for (j = 0 to k-1)
{
if (a[i] == vote[j])
{
count[j]+=(k-1);
flag = false;
}
if ((a[i]!= vote[j]) &&(count[j] !=0)
{
count[j]--;
}
}
if (flag)
{
for (j = 0 to k-1)
{
if (count[j] == 0)
{
cou

【在 a***9 的大作中提到】

: 2个变量怎么整？
: 如果 k = 4, 就有可能有3个大于n/4的元素吧
: 猜测可以用k-1个vote, 增vote时不用++，用vote+=k-1，减就用--，到0时换成后面的
: 元素

w*l2018-01-07 08:01

37 楼

条件是： more than n/2,不包括n/2，所以我认为那个算法还在这个条件下是work 的

b*v2018-01-07 08:01

38 楼

这样好像是可以的

【在 w****l 的大作中提到】

: 条件是： more than n/2,不包括n/2，所以我认为那个算法还在这个条件下是work 的