i***e
发帖数: 452 | 1
still work. scan the array twice, and do xor twice. time complexity and
space complexity doesn't change. |
|
g*********s
发帖数: 1782 | 2 1 2 3 3. how does xor work? |
|
c********1
发帖数: 161 | 3
用bitwise xor 或者是 加减乘除就能做到，不用临时char |
|
g*********s
发帖数: 1782 | 4 xor
x = x^y
y = x^y
x = x^y |
|
g*********s
发帖数: 1782 | 5 that's a problem. so xor is better. |
|
|
g**e
发帖数: 6127 | 7 use xor. O(n) time, O(1) space |
|
m**q
发帖数: 189 | 8 Or use partition, also O(n).
xor is easier in this case. |
|
g**********y
发帖数: 14569 | 9 Bit B 把数组分两组，M，D应该分属两边。然后就归化成用XOR找一个miss/duplicate
数。 |
|
m********l
发帖数: 4394 | 10 不能用XOR?
helloworld
^aaaaaaaaaa
delete any zero.
^aaaaaaaaaa
...
helloworld
^eeeeeeeeee
delete any zero.
^eeeeeeeeee |
|
m********l
发帖数: 4394 | 11
XOR两次
没仔细读.. 不准用新空间
不过他问题也没说好
output跟string1是同个空间吗?
helloworld 是要变成 hlloworl
多了个d |
|
c*********t
发帖数: 2921 | 12 对下面的问题有些疑问：
1. 如果0出现奇数次呢?
用xor, 那么0就是这个出现奇次的数，这个跟具体的那个数的值好像没有关系吧。
2.一个字符串，找出first unique的character(hash)
这个题到底问的是什么？能否给个例子？ |
|
g**e
发帖数: 6127 | 13 来自主题: JobHunting版 - 一个电面题 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
当然如果这个数是0，那就只能vote了 |
|
d*******d
发帖数: 2050 | 14 来自主题: JobHunting版 - 一个电面题 如果是0的话,也不用vote,最后xor结果就是0阿. |
|
O*2
发帖数: 178 | 15 来自主题: JobHunting版 - 一个电面题 如果没有出现奇数次的数，那么总数应该是偶数，如果有的话且xor结果为零，
那么这个数就应该是零 |
|
|
g**********y
发帖数: 14569 | 17 3 3 3 3想起来比较抽象，{3，2}就可以。
按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。 |
|
i*******n
发帖数: 114 | 18 nvidia interview experience
location:
NVIDIA
San Thomas Expressway, Santa Clara
duration
2 hours, 1PM to 3PM
2 interviewers, each for 1 hour
------------------------------------------
cdj
xor eax, edx
sub eax, edx
问我这段代码干嘛。就是算负数的补码(Two's Complement)，正数没变化
logic puzzle,
4 fuses, each fuse burns out in 40 minutes, create a fuse that can burn
in
20 minutes. slightly flawed problem. Because when you burn the fuse from
two
ends, it is not exactly 20 minutes. (Two combustion points are
certainly
faste... 阅读全帖 |
|
|
c****p
发帖数: 6474 | 20 are mathematical methods possible?
1. max - min == n - 1; // not able to deal with duplicates.
2. check with sum(a[i]) and sum(a[i]^2); // any possible exceptions?
3. xor; // easy to get a false positive.
combine 1 & 2 together might be feasible but not sure whether they work for
all the corner cases.
sequence.
space |
|
v*****k
发帖数: 7798 | 21 只有一个出现一次的还是可以有好多?只有一个的话xor就好了？好多的话上hash？ |
|
|
|
v*****k
发帖数: 7798 | 24 只有一个出现一次的还是可以有好多?只有一个的话xor就好了？好多的话上hash？ |
|
|
|
Y**B
发帖数: 144 | 27 怎么 XOR?
比如 5,5,2,2,3,4,4, 找出 3 |
|
|
B******5
发帖数: 4676 | 29 需要知道都是哪些数吧，不如1到100有一个是偶数次 |
|
S**********e
发帖数: 62 | 30 Could you elaborate on how to do this? I was not able to figure it out. |
|
q****x
发帖数: 7404 | 31 听说变态的Amazon要人念code，总结了一个。
这里面叹号和圆括号单词音节有点长，也有点绕口。我个人倾向用bang和round
bracket。但bang似乎不常见。
! exclamation mark, bang
" double quote
# pound, sharp
$ dollar
% percent
& ampersand, reference
' single quote
( left/opening parenthesis/round bracket
) right/closing
[ left/opening bracket/square bracket
] right/closing
{ left/opening brace/curly bracket
} right/closing
< less
> greater
* star
+ plus
, comma
- dash, minus
. dot
/ slash
\ back... 阅读全帖 |
|
|
a*****n
发帖数: 158 | 33 刚开始问了现在做的项目，C++h和Java有什么不同，题目到是简单，一个数组，一个数
出现奇数次，其他出现偶数次，找出来这个数。当然是XOR操作了，有问如果有2个基数
次怎么办？当时想了半天还想用BIT OPERATION解决，他说BIT OPERATION不可能（事后
我想了，还是可以的。）我就说用HASHMAP数数，然后又要求不需要占空间，我说那只
有BRUTAL FORCE了。。。。他又问如果数组是排序的怎么做，SIGH，忘了应该先排序。
然后给了算法，要求写CODE。CODE写完要求读，结果惨了，大括号、中括号不知道怎样
讲？？反正读的听乱的，然后他给了个TEST CASE，又问如何测试，我就简单描述了一
下几个CASE。后来又问如果QA拒拮你的BUG FIX怎么办，我说没碰到这种CASE，如果碰
到。BLAH, BLAH。然后结束，过2天受到剧信。
这几天信心受到打击，好在我还有份鸡肋工。圣诞好好休息了。。。祝大家早日受到理
想OFFER。。。 |
|
a****o
发帖数: 15 | 34 Here is my thought for the first problem.
Assume the variable is m.
Then m = m xor 3
and |
|
w***c
发帖数: 8 | 35 我唯一能想到的只有brute-force,但提交上去总是超时，不知各位大牛有没有好的思路
，谢谢了。 |
|
b*****c
发帖数: 1103 | 36 你没打过比赛？既然理论超时还提交。。。
真正的是logN的，而且必须不能用python,最好c,java |
|
|
|
b******g
发帖数: 1721 | 39 for the second, transform the presentation from a bit vector to an integer, and then run the first algorithm.
For the xor operation, does that require the N should be equal to 2^m or just any integer number? |
|
t****y
发帖数: 27 | 40 For the second question, do XOR with 1..N bit by bit should be fine
the |
|
P***P
发帖数: 1387 | 41 上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是不
是跟generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有没有空位
子，提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时候用
hash, time complexity多少.
他让我讲讲h... 阅读全帖 |
|
m*****a
发帖数: 636 | 42 心理素质好，google使用得当。
祝马上有好消息
上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是
不是跟
generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有
没有空位子，
提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他
怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时
候用
... 阅读全帖 |
|
|
y*****n
发帖数: 243 | 44 啊我懂了。。是说2个文件对应位置上的byte相同。只有一个位置上byte不同。然后找
出来。还是需要2个server通信的。应该用binary search,先在各自那边xor1个然后比
较是否相同。然后各自server上XOR 2个再比较..然后是xor4个然后xor2^n个。直到找
到2个结果不一样。就说明byte在2^(n-1)到2^n的区间內。再从那个区间开始search。 |
|
y*****n
发帖数: 243 | 45 啊我懂了。。是说2个文件对应位置上的byte相同。只有一个位置上byte不同。然后找
出来。还是需要2个server通信的。应该用binary search,先在各自那边xor1个然后比
较是否相同。然后各自server上XOR 2个再比较..然后是xor4个然后xor2^n个。直到找
到2个结果不一样。就说明byte在2^(n-1)到2^n的区间內。再从那个区间开始search。 |
|
g*****e
发帖数: 282 | 46 这里xor足够了。
btw，大家面试时讨论hash function，我想SHA1这种digital sign算法是不是通吃呢，
除了perf比较贵？ |
|
d******i
发帖数: 76 | 47 我说的是把position传过去，然后对另外一个server上两个positions之间的bytes XOR
,我没说传送两个positions之间的byte |
|
b***u
发帖数: 12010 | 48 a^b=c
=>
a^c=b
^为xor
太土了。 |
|
s******n
发帖数: 3946 | 49 来自主题: JobHunting版 - 问一到题目 xor计算和，and计算carrier并且<<1，循环直到carrier为0
a - b = a + (~b + 1) |
|
|
