这个zhuzhupets - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

这个zhuzhupets

这个zhuzhupets# pets - 心有所宠

b*62010-04-06 07:04

1 楼

感觉面的不是很好啊。和我准备的方向有点偏差。。。估计悲剧的面儿大。无所谓了，
实力不济啊
本人 ee ms 对算法数据结构不是很了解，最近一直恶补，效果不佳 ^_^
印度女 2pm to 2:50pm
介绍一个你最喜欢的project，什么数据结构，什么难点，什么公司的项目。。。。
你熟悉c吗？还是c++？
我说c
她问：解释一下class in c++ （貌似我说的是c。。。。）
橘子苹果 mix
1-100 找一个数找两个数
100球，一个分量不同，几次能找出来
两个sorted的数组，怎么找相同的数
我给了一个算法nlogn,他要n+n
我说用merge
他说两个数组大小不同，不用merge
我无语。。
哪位说一下解法
一个非等概率的硬币来决定足球比赛开赛，要公平，怎么办
让我问问题
整个下来磕磕绊绊，估计悲剧了。
回报一下本版，然后继续努力了，bless 各位

g*s2010-04-06 07:04

2 楼

9月9日，安徽蚌埠，一家酒店正在举办一场婚礼，突然巨大的顶棚钢化玻璃从天而降，
主持人吓懵，现场两名亲友被砸伤，一人当场被砸晕，目前已送往医院救治。
婚礼现场，人们都在为这对新人祝福，司仪正在深情款款的讲述着新郎和新娘的经历，
还有父母的养育之恩，忽然从正上方砸下一块巨大的玻璃，疑似楼顶的玻璃，由于冲击
力大，一人当场被砸晕，现已经送到医院救治，但是对此酒店还没有给出满意的回复。
有的网友调侃婚礼当天，祸从天降，这是吉兆还是什么，不过碎碎平安，也许是老天也
恭贺你们，给你们送来一份大礼。
回归正传，从天而降的玻璃终究是酒店的安保出现问题，酒店应该是需要负责的。
这种问题出现在婚礼的时候，本来大家都开开心心的，忽然间出现这样的情况，还有人
因此进了医院，放在谁身上都是不开心的吧。
新郎和新娘也不知道会不会受此影响导致婚礼变动。
结婚还是要选择在一个环境安全氛围相对好一点的地点，一方面省去自己的精力也是对
各位来宾负责。
进医院的人应该也会首先和婚礼的人沟通吧，赔偿事宜应该也是要等酒店查出具体原因
才能确定的。
但是新人的祝福还是不能少的，就当是好事多磨，岁岁平安吧！

d*i2010-04-06 07:04

3 楼

好多种阿
大家给猫买哪种?
单耗子本身四处跑得还是带那些附件的?

a*n2010-04-06 07:04

4 楼

Bless~
貌似这个问题在BB很pop...
橘子苹果 mix

m*u2010-04-06 07:04

5 楼

不用带附件吧。反正那个猪自己的动静就很大，叫着跑来跑去，猫很喜欢揍他。我在考
虑那个wheel或者ball，大概猫也会喜欢。

n*y2010-04-06 07:04

6 楼

linear scan 就可以了，跟merge sort一个道理，只要两个指针。为什么说不可以？
投两次，看先出现 HT or TH, P(HT)=P(TH)

y*u2010-04-06 07:04

7 楼

被你们天天说，俺也动心了，米线妈不愧是购物专家。AMAZON上有没有？

【在 m**u 的大作中提到】

: 不用带附件吧。反正那个猪自己的动静就很大，叫着跑来跑去，猫很喜欢揍他。我在考
: 虑那个wheel或者ball，大概猫也会喜欢。

c*t2010-04-06 07:04

8 楼

不对啊，投两次，设H概率a,T概率b， a+b=1，HT和TH为胜利
先投的第一次胜利：2ab
后投的第一次胜利：（1-2ab）×2ab
不相等啊

【在 n*****y 的大作中提到】

: linear scan 就可以了，跟merge sort一个道理，只要两个指针。为什么说不可以？
: 投两次，看先出现 HT or TH, P(HT)=P(TH)

m*u2010-04-06 07:04

9 楼

有，不过贵阿。walmart网上有，可以选在local店自己取，不要邮费。target也免邮费
。用包子爸的话说，我就是一个败家子购物狂...

【在 y*********u 的大作中提到】

: 被你们天天说，俺也动心了，米线妈不愧是购物专家。AMAZON上有没有？

r*g2010-04-06 07:04

10 楼

连续投两次，看结果，两次一样（TT or HH)从新再投两次。 P(TH)=ba=P(HT)=ab. TH
甲队开
球，HT乙对开球，对两队公平。

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

: 不对啊，投两次，设H概率a,T概率b， a+b=1，HT和TH为胜利
: 先投的第一次胜利：2ab
: 后投的第一次胜利：（1-2ab）×2ab
: 不相等啊

y*u2010-04-06 07:04

11 楼

amazon 比TARGET贵呀？

【在 m**u 的大作中提到】

: 有，不过贵阿。walmart网上有，可以选在local店自己取，不要邮费。target也免邮费
: 。用包子爸的话说，我就是一个败家子购物狂...

r*g2010-04-06 07:04

12 楼

by the way, 橘子苹果mix具体题目是什么？

d*i2010-04-06 07:04

13 楼

哦我就是说的wheel and ball...
那个耗子跑得快么?如果不快，以前买过一些电动的玩具，行动太迟缓，饕默根本不屑
去抓。。。

【在 m**u 的大作中提到】

: 不用带附件吧。反正那个猪自己的动静就很大，叫着跑来跑去，猫很喜欢揍他。我在考
: 虑那个wheel或者ball，大概猫也会喜欢。

c*t2010-04-06 07:04

14 楼

3盒子3标签：橘子，苹果，mix，全贴错位，最少拿一个出来能知道所有正确的标签位置
另问：100个球是知道轻重的吧，其实不知道轻重也是5次，但不知道具体原理，谁知道
解说一下

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

: by the way, 橘子苹果mix具体题目是什么？

m*u2010-04-06 07:04

15 楼

不算特别快，毕竟太快了小孩不好追，不过也不算迟钝。但是拍一巴掌嚷嚷一声，对猫
还是有吸引力的。

【在 d***i 的大作中提到】

: 哦我就是说的wheel and ball...
: 那个耗子跑得快么?如果不快，以前买过一些电动的玩具，行动太迟缓，饕默根本不屑
: 去抓。。。

r*g2010-04-06 07:04

16 楼

33 33 34 秤一次，如果这两堆一样那么剩下34，不一样剩33
剩33， 11 11 11 称第二次
3 3 5 称第三次，剩3个（再需一次）或者5个
剩5， 2 2 1 最多两次，
剩34， 11 11 12 同理，最多也是5次
这个题有通解，假设N个球，那么worst case最少是ceil(log3(N)).对不？

位置

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

: 3盒子3标签：橘子，苹果，mix，全贴错位，最少拿一个出来能知道所有正确的标签位置
: 另问：100个球是知道轻重的吧，其实不知道轻重也是5次，但不知道具体原理，谁知道
: 解说一下

m*u2010-04-06 07:04

17 楼

因为老缺货，所以amazon经常就剩些很贵的卖家了。

【在 y*********u 的大作中提到】

: amazon 比TARGET贵呀？

r*g2010-04-06 07:04

18 楼

是问最少拿几个能知道所有正确标签么？为什么最少一个？

位置

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

A*R2010-04-06 07:04

19 楼

cannot compare with you guys. just order a 48" cat tree for my two cats.
current ones are only 30" tall.

i*e2010-04-06 07:04

20 楼

这是 finding intersection of two sorted arrays 呀。At most 2n comparisons is
enough.
http://www.ihas1337code.com/2010/03/here-is-phone-screening-question-from.html
>>两个sorted的数组，怎么找相同的数
我给了一个算法nlogn,他要n+n
我说用merge
他说两个数组大小不同，不用merge
我无语。。
哪位说一下解法
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 感觉面的不是很好啊。和我准备的方向有点偏差。。。估计悲剧的面儿大。无所谓了，
: 实力不济啊
: 本人 ee ms 对算法数据结构不是很了解，最近一直恶补，效果不佳 ^_^
: 印度女 2pm to 2:50pm
: 介绍一个你最喜欢的project，什么数据结构，什么难点，什么公司的项目。。。。
: 你熟悉c吗？还是c++？
: 我说c
: 她问：解释一下class in c++ （貌似我说的是c。。。。）
: 橘子苹果 mix
: 1-100 找一个数找两个数

b*62010-04-06 07:04

21 楼

学到了
高手啊。。。
不明白为什么说merge 不行呢？

i*e2010-04-06 07:04

22 楼

其实这道题的基本思路跟 merge 是一样的，也是用两个指针，两个矩阵也都排好序了
。估计你没有跟面试官沟通清楚，他以为你说的是把两个矩阵 merge 了之后再找相同
的元素。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 学到了
: 高手啊。。。
: 不明白为什么说merge 不行呢？

f*r2010-04-06 07:04

23 楼

如果不知道轻重就复杂多了

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

: 33 33 34 秤一次，如果这两堆一样那么剩下34，不一样剩33
: 剩33， 11 11 11 称第二次
: 3 3 5 称第三次，剩3个（再需一次）或者5个
: 剩5， 2 2 1 最多两次，
: 剩34， 11 11 12 同理，最多也是5次
: 这个题有通解，假设N个球，那么worst case最少是ceil(log3(N)).对不？
:
: 位置

x*92010-04-06 07:04

24 楼

两个sorted的数组，怎么找相同的数
Loop/Bineary search/hashtable/two pointer
学习了。。。
那个秤球的如果不知道哪个轻哪个重怎么弄啊。。。

z*n2010-04-06 07:04

25 楼

不知道轻重的话
第一次放两堆33的，如果平衡，那么就一次淘汰了66个，在剩下的34个里头再找；
如果不平衡，说明剩下的34个都是好球，选33个与之前天平上的某一堆换，如果还
不平衡，说明没被换下的33个里有坏球，而且此时连坏球是轻是重都已经知道了；
如果变平衡了，说明被换下的33个里头有坏球。不管怎样，两次以后都缩小到33个
了
之后依次类推，每次都分三堆，最坏次数应该是2log3(N)

两个sorted的数组，怎么找相同的数
Loop/Bineary search/hashtable/two pointer
学习了。。。
那个秤球的如果不知道哪个轻哪个重怎么弄啊。。。

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

: 两个sorted的数组，怎么找相同的数
: Loop/Bineary search/hashtable/two pointer
: 学习了。。。
: 那个秤球的如果不知道哪个轻哪个重怎么弄啊。。。

c*t2010-04-06 07:04

26 楼

不对，这是有公式的，如下
100个球可能性：100×2=200
3^N>=200 N=5
如果知道轻重是：
3^N>=100 N也=5
就像前面讨论过3次最多可以弄13个球，不知道轻重，因为：
3^3=27
27/2=13

【在 z****n 的大作中提到】

: 不知道轻重的话
: 第一次放两堆33的，如果平衡，那么就一次淘汰了66个，在剩下的34个里头再找；
: 如果不平衡，说明剩下的34个都是好球，选33个与之前天平上的某一堆换，如果还
: 不平衡，说明没被换下的33个里有坏球，而且此时连坏球是轻是重都已经知道了；
: 如果变平衡了，说明被换下的33个里头有坏球。不管怎样，两次以后都缩小到33个
: 了
: 之后依次类推，每次都分三堆，最坏次数应该是2log3(N)
:
: 两个sorted的数组，怎么找相同的数
: Loop/Bineary search/hashtable/two pointer

c*t2010-04-06 07:04

27 楼

对，但是答案就是一个，因为标签是全错位的
从mix的拿一个就能知道所有标签里面实际是什么

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

: 是问最少拿几个能知道所有正确标签么？为什么最少一个？
:
: 位置

z*n2010-04-06 07:04

28 楼

没看懂你公式。。。
不过你说3次最多可以弄13个球，那讨论的应该是固定球数后，最好情况可以多少次
吧。我说的是固定球数后，最坏情况下需要多少次

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

: 不对，这是有公式的，如下
: 100个球可能性：100×2=200
: 3^N>=200 N=5
: 如果知道轻重是：
: 3^N>=100 N也=5
: 就像前面讨论过3次最多可以弄13个球，不知道轻重，因为：
: 3^3=27
: 27/2=13

c*t2010-04-06 07:04

29 楼

是最坏，
13个球不知道轻重，3次必定能得出结果
公式就是N次必定最多能M个球：3^N>=2M
我只是知其然，不知其所以然，所以呼唤大牛来解释下，6年前高中有人讲过这题，当
时就没听懂。。。。

【在 z****n 的大作中提到】

: 没看懂你公式。。。
: 不过你说3次最多可以弄13个球，那讨论的应该是固定球数后，最好情况可以多少次
: 吧。我说的是固定球数后，最坏情况下需要多少次