Happy New Year - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Piebridge - 鹊桥

Happy New Year

Happy New Year# Piebridge - 鹊桥

s*m2011-01-01 08:01

1 楼

给你一个数组，range［1，n］inclusive，然后说如果有个n＋1的数组的话这里面有没
有重复？为什么？
pigeon hole principle
然后followup：怎么找到那个重复的数字？有可能有多个重复
继续followup；如果说不让你交换数字，即不能排序怎么办？可以用空间
继续followup：如果说没有空间怎么办？
这里用到了pigeon hole principle，二分查找
不懂最后一个followup，怎么用二分啊
--------------追加----------
这是别处看来的面经，
--pigeon hole principle，二分查找-- 是面试官的提示
----别人的回复，但我没看懂---
第二轮第二题不用空间，是直接加起来arrray么。
恩，差不多吧，就是只要找到一个重复的就可以了所以用pigeon hole+二分每次能去掉
一半的范围

d*02011-01-01 08:01

2 楼

想请教一下班内的资深人士关于新房查验出来一些毛病的检修问题。
最近马上要close escrow，之前inspection的时候出了一个报告，里面提到一些问题，
貌似不是大问题，但是还是想和各位来确认一下。
第一个是空调部分：
Damaged relay wire at one compressor. Flashing at the freon line is not
sealed at the piping.
第二部分是窗户：
Broken/loose spring noted on the window frame. This is a possible safety
concern as the spring holds the window in the open position.
第三个是浴室部分：
Tub Faucet Stopper is disconnected.
主要是这三个，想请教一下这三个问题如果修起来大概需要多少钱？尤其是第三个，指
的是浴缸的放水有问题吗？
还有就是哪位有不错的handyman可推荐吗？
不胜感激。

y*l2011-01-01 08:01

3 楼

A New Year Day
yourpal
such a lonely day
is a day
I cannot miss you more
The whole world is so quiet
that I may die away
wherever you go
I want to go with you
whenever you die
I want to die with you
hand me and take me away
the loneliest day in my life
I cannot stand being without you
Want you to want me
need you to need me
love you to love me
the loneliest day in my life

c*e2011-01-01 08:01

4 楼

你确定是二分查找？
如果其他数字都出现一次，某个数字出现两次，那可以用bitwise operation啊

c*g2011-01-01 08:01

5 楼

bless.

a*52011-01-01 08:01

6 楼

可能不止一个重复，不能这样做

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

: 你确定是二分查找？
: 如果其他数字都出现一次，某个数字出现两次，那可以用bitwise operation啊

s*l2011-01-01 08:01

7 楼

如果有重复 2分不好用吧还是要o(n)吧
比如1 2 2 2 2 2

r*g2011-01-01 08:01

8 楼

觉得再咋地也得O(n)吧
任意数组求是否重复, 基于比较的最优复杂度是O(nlog(n))
这里有了取值限制在[1, n] 可以优化到O(n)

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

: 给你一个数组，range［1，n］inclusive，然后说如果有个n＋1的数组的话这里面有没
: 有重复？为什么？
: pigeon hole principle
: 然后followup：怎么找到那个重复的数字？有可能有多个重复
: 继续followup；如果说不让你交换数字，即不能排序怎么办？可以用空间
: 继续followup：如果说没有空间怎么办？
: 这里用到了pigeon hole principle，二分查找
: 不懂最后一个followup，怎么用二分啊
: --------------追加----------
: 这是别处看来的面经，