胚芽米比白米好吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

胚芽米比白米好吗？

胚芽米比白米好吗？# Living

t*a2013-04-01 07:04

1 楼

编程菜鸟，面了一下CISCO.一道很简单的题。一个Sorted array A,元素是数字1~N，一
个数字丢失，如何最快的找到丢失的数字。我的算法是binary search，先比较A[(n-1)
/2]==1+(n-1)/2，相等，丢失数字在右侧，否则在左侧，递归可得O(log(N))的算法。
但interviewer说我的算法不够快，应该数0,1个数，做bit manipulation。但bit
manipulation也是O(N)的复杂度啊。哪位大侠能解释一下如何用bit manipulation达到
比O(log(N))更优的时间复杂度啊。

l*r2013-04-01 07:04

2 楼

我已经离开学校了，如何在ISI上log in?

c*i2013-04-01 07:04

3 楼

今天收到的RFE notice, 我和老婆（副申请人）RFE 要求一模一样： medical +
updated Form G-325A.
因为刚打开邮件时没有看到employment verification的字样，心里压力顿时小很多。
后来又翻出两年前交i-485申请的文件包，温习一下G-325A是什么表。一眼看到了其中
一项‘Applicant's employment last five years’, 才知道麻烦事儿可能要来。
以下是我的时间表：
EB2 PD: 8/2013
I-485 RD: 7/2015
Birth certificate RFE and RRFE: 10/2015
EB3 downgrade: 4/2016
Changed employer: 9/2016 (almost same position/field; new employer filed new
H-1B so I have not used EAD/AP card)
New RFE today.
请问各位朋友，这种情况是需要老老实实准备EVL / supplement J 同G-325A一起交上
去，还是硬着头皮只在G325A上填写上新雇主的信息，见招拆招，没要工作证明就不出
示了？
在此先拜谢大家！

l*r2013-04-01 07:04

4 楼

看到大家讨论吃的，也来问一个问题。最近朋友推荐胚芽米，说比白米更有营养。买了
一袋，吃口跟糙米差不多，没有白米的口感好。

e*i2013-04-01 07:04

5 楼

简单来说，你的算法是错的，怎么lgn法啊，看一半如何知道哪一半丢了啊？

m*22013-04-01 07:04

6 楼

没戏。除非你自己subscribe数据库，一年几千块貌似。

z*d2013-04-01 07:04

7 楼

要什么给什么。真要EVL肯定跟你要了，不会跟你遮遮掩掩的。

e*i2013-04-01 07:04

8 楼

没看到sorted不好意思！
不过觉得题目不可能是sorted！

l*r2013-04-01 07:04

9 楼

晕倒

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

: 没戏。除非你自己subscribe数据库，一年几千块貌似。

w*02013-04-01 07:04

10 楼

是不是bit manipulate位运算更tricky一些，其次更简单。

l*r2013-04-01 07:04

11 楼

我还有学校的账号和邮箱。可不可以在家查？

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

: 没戏。除非你自己subscribe数据库，一年几千块貌似。

t*a2013-04-01 07:04

12 楼

确实是sorted，如果不是sorted那就是直接XOR了，我double check了，开始我说可以
XOR,他说对这个specific question, sorted的array,该如何做。这个肯定没有听错。

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

: 没看到sorted不好意思！
: 不过觉得题目不可能是sorted！

t*n2013-04-01 07:04

13 楼

你试试呗

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

: 我还有学校的账号和邮箱。可不可以在家查？

t*a2013-04-01 07:04

14 楼

我理解他的bit manipulation就是CC 150上的5.7题。
CC150上的题是这样的
"An array A[1…n] contains all the integers from 0 to n except for one
number which is missing. In this problem, we cannot access an entire integer
in A with a single operation. The elements of A are represented in binary,
and the only operation we can use to access them is “fetch the jth bit of A
[i]”, which takes constant time. Write code to find the missing integer.
Can you do it in O(n) time?"
但interviewer没说一次只能fetch 一位bit.实在想不出来有什么比O(log(N))更快的算
法了。

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

: 是不是bit manipulate位运算更tricky一些，其次更简单。

l*r2013-04-01 07:04

15 楼

在学校的网叶上找不到地方试。

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

: 你试试呗

w*02013-04-01 07:04

16 楼

不，我的想法bit manipulation是遍历数组的每个数的最后一位，即与1'b1做与。如果
是连续的应该就会得到0，1，0，1，0，1。。。。循环，但是漏一个数字就会出现0，0
.或者是1，1.再看该数字即可，这样是不是位运算更多一些，于是就简单点？菜鸟的一
点小想法。

1)

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

: 编程菜鸟，面了一下CISCO.一道很简单的题。一个Sorted array A,元素是数字1~N，一
: 个数字丢失，如何最快的找到丢失的数字。我的算法是binary search，先比较A[(n-1)
: /2]==1+(n-1)/2，相等，丢失数字在右侧，否则在左侧，递归可得O(log(N))的算法。
: 但interviewer说我的算法不够快，应该数0,1个数，做bit manipulation。但bit
: manipulation也是O(N)的复杂度啊。哪位大侠能解释一下如何用bit manipulation达到
: 比O(log(N))更优的时间复杂度啊。

t*82013-04-01 07:04

17 楼

你只要想办法连接到学校图书馆的线路上或者学校的线路上，我以前的学校就有回家也
可以查 ISI和一些付费的杂志。
我觉得你去你们学校的图书馆网页上找找看。

t*a2013-04-01 07:04

18 楼

，0
这种算法的本质是检测是否连续出现两个奇数，或者两个偶数，但算法复杂度还是O(N)
啊，不会比O(log(N))快。感觉那个interviewer自己没想明白，一般面试题O(log(N))
基本上就是能到达的最优了。

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

: 不，我的想法bit manipulation是遍历数组的每个数的最后一位，即与1'b1做与。如果
: 是连续的应该就会得到0，1，0，1，0，1。。。。循环，但是漏一个数字就会出现0，0
: .或者是1，1.再看该数字即可，这样是不是位运算更多一些，于是就简单点？菜鸟的一
: 点小想法。
:
: 1)

l*r2013-04-01 07:04

19 楼

好的，我试试

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

: 你只要想办法连接到学校图书馆的线路上或者学校的线路上，我以前的学校就有回家也
: 可以查 ISI和一些付费的杂志。
: 我觉得你去你们学校的图书馆网页上找找看。

z*z2013-04-01 07:04

20 楼

用vpn连回学校的网络？

l*n2013-04-01 07:04

21 楼

图书馆的proxy

l*n2013-04-01 07:04

22 楼

一般来说，学校的图书馆都有proxy可以让大家在家里查文献，不过前提是你要有一个
学校的帐号。这个帐号一般就是学校邮箱。
另外，很多学校是人一走，基本上是第二天就把你的帐号删除了。不过毕竟你是刚离开
，一定还认识一些学校的同事朋友。你可以让他们想办法给你搞个vpn的代理，这样你
可以通过遥控电脑下载文章，然后再通过发邮件的方式传到你的信箱里。但是，这个方
式原则上是跟大多数学校的网络管理规范违背的，虽然说一般学校不怎么追究。

c*o2013-04-01 07:04

23 楼

找个校友帮着查

★ 发自iPhone App: ChineseWeb 7.5

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

: 我已经离开学校了，如何在ISI上log in?

p*r2013-04-01 07:04

24 楼

用学校的代理proxy吧，如果你还有账号的话。一般学校的图书馆都有介绍怎么用proxy
。