支持毕业生获得绿卡的请愿链接 - 未名空间MITBBS历史存档

支持毕业生获得绿卡的请愿链接# EB23 - 劳工卡

l*n2013-02-05 08:02

1 楼

据说这里很灵，刚电面了g，周五还有一次，特来求bless，保佑顺利拿到onsite。先报下鸡肋的面经，准备了挺长时间，没想到考个这么
简单的题目，这是准备据人么？好郁闷阿
本来约好2：00的，不过Interviewer晚了15分钟，然后他问我知道面试的流程么？我说
之前也面过几次，都是先谈简历，然后基础知识问答，最后techinical question。他
说，好的，我们直接跳到techinical question吧。
题目是面试官口述的，就是给一个排好序的数组，降序，再给一个value，返回这个数
组中等于value的个数，
俺先写了个最简单的方法，O(N)复杂度，然后面试官问，能improve么，我说有种方法
可以对于general case减少比较次数，就是一旦找到a[i]==value以后，继续比较a[i]
后面的值，一旦a[k]！=value时就可以return了。
接着面试官问，还能Improve么，我说用binary search找a[i]==value，不过worst
case时还是O(N)，其他更好的还没想到，面试官说binary search 已经good enough了
，写吧。
写完以后，面试官没说啥，直接就一下题，和google map有关的，基本就是考图论的几
个经典shortest path算法，口述以后，就问还有别的问题么？
我问了几个无关痛痒的问题以后就over了，不多不少45分钟，现在好担心为啥出这么简
单的题目，难道本来就没想让我过么？

k*o2013-02-05 08:02

2 楼

http://wh.gov/Vr3B

s*y2013-02-05 08:02

3 楼

bless/

c*72013-02-05 08:02

4 楼

The page you're looking for is currently unavailable to view？

g*u2013-02-05 08:02

5 楼

bless...

k*b2013-02-05 08:02

6 楼

网址太长了，帮楼主截短一下
http://goo.gl/xtZxE

c*12013-02-05 08:02

7 楼

楼主，我觉得这道题可以做到 O（lg N）, 用两边binary search，两次都不是找
target的value，而是找与这连续几个value交接的joining points，第一次binary
search找比他大的最小数和value的joining point，第二次找比value小的最大数的
point，然后返回这两个point的index，就可以知道value的个数了。代码不难写，就是
简单的binary search稍加改进就可以。

c*22013-02-05 08:02

8 楼

要求的签名数量要10万了？以前也这么高么？

【在 k***o 的大作中提到】

: http://wh.gov/Vr3B

l*n2013-02-05 08:02

9 楼

各有优劣吧，你这个方法在重复的值很多的情况比我的好，在一般情况下（数组很长，
重复的value不多的时候），我只用一次binary search就行了，你还得两次。这题没有
最optimal的做法，都是要基于数组的distribution的，我当时问了interviewer了，他
说distribution是随机的，什么情况都有可能。

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

: 楼主，我觉得这道题可以做到 O（lg N）, 用两边binary search，两次都不是找
: target的value，而是找与这连续几个value交接的joining points，第一次binary
: search找比他大的最小数和value的joining point，第二次找比value小的最大数的
: point，然后返回这两个point的index，就可以知道value的个数了。代码不难写，就是
: 简单的binary search稍加改进就可以。

k*b2013-02-05 08:02

10 楼

最早好像只要5000，后来提到25000，现在变成10万了

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

: 要求的签名数量要10万了？以前也这么高么？

c*12013-02-05 08:02

11 楼

对，不过单从O-notation 上面分析最差的case，O(lg N) * 2 显然优于 O（N），不过
作为面试，我觉得应该都说道，看具体问题。

d*g2013-02-05 08:02

12 楼

和流氓玩游戏，规则都是流氓制定的

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

: 要求的签名数量要10万了？以前也这么高么？

x*l2013-02-05 08:02

13 楼

bless

题目是面试官口述的，就是给一个排好序的数组，降序，再给一个value，返回这个数
组中等于value的个数，
俺先写了个最简单的方法，O(N)复杂度，然后面试官问，能improve么，我说有种方法
可以对于general case减少比较次数，就是一旦找到a[i]==value以后，继续比较a[i]
后面的值，一旦a[k]！=value时就可以return了。
接着面试官问，还能Improve么，我说用binary search找a[i]==value，不过worst
case时还是O(N)，其他更好的还没想到，面试官说binary search 已经good enough了
，写吧。
写完以后，面试官没说啥，直接就一下题，和google map有关的，基本就是考图论的几
个经典shortest path算法，口述以后，就问还有别的问题么？
我问了几个无关痛痒的问题以后就over了，不多不少45分钟，现在好担心为啥出这么简
单的题目，难道本来就没想让我过么？

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

: 各有优劣吧，你这个方法在重复的值很多的情况比我的好，在一般情况下（数组很长，
: 重复的value不多的时候），我只用一次binary search就行了，你还得两次。这题没有
: 最optimal的做法，都是要基于数组的distribution的，我当时问了interviewer了，他
: 说distribution是随机的，什么情况都有可能。

c*22013-02-05 08:02

14 楼

白送上门的货太多，流氓要挑挑拣拣。

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

: 和流氓玩游戏，规则都是流氓制定的

l*n2013-02-05 08:02

15 楼

恩，要栽估计就栽在这上面了

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

: 对，不过单从O-notation 上面分析最差的case，O(lg N) * 2 显然优于 O（N），不过
: 作为面试，我觉得应该都说道，看具体问题。

g*e2013-02-05 08:02

16 楼

这个跟前几天贴的google面试题是一回事， sorted array找某元素的起始终止index。
你的方法是对的

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

: 对，不过单从O-notation 上面分析最差的case，O(lg N) * 2 显然优于 O（N），不过
: 作为面试，我觉得应该都说道，看具体问题。

C*l2013-02-05 08:02

17 楼

bless ...

报下鸡肋的面经，准备了挺长时间，没想到考个这么

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

: 据说这里很灵，刚电面了g，周五还有一次，特来求bless，保佑顺利拿到onsite。先报下鸡肋的面经，准备了挺长时间，没想到考个这么
: 简单的题目，这是准备据人么？好郁闷阿
: 本来约好2：00的，不过Interviewer晚了15分钟，然后他问我知道面试的流程么？我说
: 之前也面过几次，都是先谈简历，然后基础知识问答，最后techinical question。他
: 说，好的，我们直接跳到techinical question吧。
: 题目是面试官口述的，就是给一个排好序的数组，降序，再给一个value，返回这个数
: 组中等于value的个数，
: 俺先写了个最简单的方法，O(N)复杂度，然后面试官问，能improve么，我说有种方法
: 可以对于general case减少比较次数，就是一旦找到a[i]==value以后，继续比较a[i]
: 后面的值，一旦a[k]！=value时就可以return了。

l*a2013-02-05 08:02

18 楼

你准备得并不充分啊
这是很常见的题。

报下鸡肋的面
经，准备了挺长时间，没想到考个这么

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

: 据说这里很灵，刚电面了g，周五还有一次，特来求bless，保佑顺利拿到onsite。先报下鸡肋的面经，准备了挺长时间，没想到考个这么
: 简单的题目，这是准备据人么？好郁闷阿
: 本来约好2：00的，不过Interviewer晚了15分钟，然后他问我知道面试的流程么？我说
: 之前也面过几次，都是先谈简历，然后基础知识问答，最后techinical question。他
: 说，好的，我们直接跳到techinical question吧。
: 题目是面试官口述的，就是给一个排好序的数组，降序，再给一个value，返回这个数
: 组中等于value的个数，
: 俺先写了个最简单的方法，O(N)复杂度，然后面试官问，能improve么，我说有种方法
: 可以对于general case减少比较次数，就是一旦找到a[i]==value以后，继续比较a[i]
: 后面的值，一旦a[k]！=value时就可以return了。

d*l2013-02-05 08:02

19 楼

这题我也见过，基本想法是一次binary search，然后向后探查。如果元素出现次数非
常多就改进为两次binary search。不过看面试官的意思大概也在一定程度上满意了，
还是祝愿楼主取得理想的结果～

l*o2013-02-05 08:02

20 楼

bless. 同Bless一下自己。

d*22013-02-05 08:02

21 楼

bless~

M*u2013-02-05 08:02

22 楼

bless

报下鸡肋的面经，准备了挺长时间，没想到考个这么

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

: 据说这里很灵，刚电面了g，周五还有一次，特来求bless，保佑顺利拿到onsite。先报下鸡肋的面经，准备了挺长时间，没想到考个这么
: 简单的题目，这是准备据人么？好郁闷阿
: 本来约好2：00的，不过Interviewer晚了15分钟，然后他问我知道面试的流程么？我说
: 之前也面过几次，都是先谈简历，然后基础知识问答，最后techinical question。他
: 说，好的，我们直接跳到techinical question吧。
: 题目是面试官口述的，就是给一个排好序的数组，降序，再给一个value，返回这个数
: 组中等于value的个数，
: 俺先写了个最简单的方法，O(N)复杂度，然后面试官问，能improve么，我说有种方法
: 可以对于general case减少比较次数，就是一旦找到a[i]==value以后，继续比较a[i]
: 后面的值，一旦a[k]！=value时就可以return了。

S*i2013-02-05 08:02

23 楼

bless

v*r2013-02-05 08:02

24 楼

bless

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

: bless