n******r
发帖数: 1247 | 1 可以的
先对array求和，找出两个missing number的和,设为M
则必然一个小于M/2,一个大于M/2
对array里所有
对array里所有>M/2的数xor，再和{floor[M/2]+1,...,N}xor得到第二个数 |
|
s*****r
发帖数: 773 | 2 请问是不是find duplication和missing 的方法都是一样的
有n个数 range 是 [1, N-1]，只有一个是duplication， 比如，N=4, {1，2，3，3}
方法:
1 数组全部加起来，和减去 1到N-1的和；
2 数组全部XOR， 然后依次XOR 1到 N-1；
3 二分法；
有 n-1 个数 range 是 [1, N]，只有一个missing， 比如，N=4, {1，2，3}
方法:
1 全部 1到N，加起来，和减去数组的和；
2 数组全部XOR， 然后依次XOR 1到 N；
3 二分法； |
|
w*****e
发帖数: 721 | 3 XOR: exclusive or.
for example:
1001 xor 1100 = 0101
(different bit => 1 , same bit => 0)
1 xor 1 =0
1 xor 0 =1 |
|
g*******9
发帖数: 2 | 4 个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M， 直到小于
100 KB 才开始一个一个的XOR |
|
g*******9
发帖数: 2 | 5 个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M， 直到小于
100 KB 才开始一个一个的XOR |
|
o****o
发帖数: 1398 | 6 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
作有帮助
Ans: a = a ^ 0x000000F0;
2. 交换第i与第j位
这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
考虑比较好：
（1）如果第i位和第j位相同，不用换
（2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
Ans:
//Assume i,j start from 0
int exchange(int a, int i, int j) {
if( ((a>>i)&1) != ((a>>j)&1) ) {
a = a ^ ((1<
}
return a;
}
3. Turn off the rightmost 1-bit
Ans: x = x & (x-1)... 阅读全帖 |
|
h*******e
发帖数: 1377 | 7 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
都可以用xor阿， xor真是用途多哦。 |
|
h*******e
发帖数: 1377 | 8 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
都可以用xor阿， xor真是用途多哦。 |
|
f*********s
发帖数: 34 | 9
Smart!!!
Basically the first loop XOR every number exactly once,
second loop XOR again to every number, which made odd number XOR twice, and
even number XOR odd times.
It turned one Even number problem into one Odd number problem. |
|
t*******r
发帖数: 22634 | 10 我觉得不严格的形象表述那个属性（形象联系 XOR 和 < 号），
就是看那张彩色的 Cayley Table 的图。
bitwise-XOR 对于自然数序列的 Caley Table 实际上是基本 XOR 矩阵
0 1
1 0
逐次在不同的位 bits 上递归叠加。（上面有人提到过这个）。
（其实这个就是 bitwise-XOR 的定义）。
（另外由于这个叠加不会出现进位，所以这个叠加跟加法也是一回事）。
而比较大小的 < 号，其实也是从最高位（最高递归层）到最低位（最低递归层）
的逐次比较。
这样从那张图上递归地看：
（1）最高位比该数的最高位小的数，在长边的排列组合都会出现。
（2）最高位和该数一样的。大家统统一起剥掉最高位，然后递归到（1）。
所以不严格的概念表示，比该数小的那些数都会出现。
彩图在这里：
'^
L |
|
|
y**i
发帖数: 1112 | 12 我只知道只有一个数repeat 1 time的或者missing 1 number的情况，用XOR计算所有这
些数以及reference：1-N，所剩的结果就是要找的数了，因为相同的数XOR等于0，0
XOR 任何数等于那个数本身。其他的情况应该怎么解？难道都要去解方程？ |
|
Z*****Z
发帖数: 723 | 13 不太明白，duplicate的元素做XOR肯定是0。所以，对原数组所有元素做XOR相当于对原
数组所有unique元素做XOR。
为什么结果一定不为0，为什么根据为1的某位，能把duplicate分到2组去？ |
|
g**********y
发帖数: 14569 | 14 要是连续的话，是可以这样，
一遍扫描，可以知道：min, max, XOR(array), sum(array)
假设a出现2次，b出现3次
XOR(array) ^ XOR(min..max) = a
sum(array) - sum(min..max) = a + 2b
别的都是一次或者三次的话，那么令 |
|
g*******s
发帖数: 490 | 15 对于一个missing number的题目，用xor是最好解法
比如，1，2，3，5，missing number is 4
(0^1^2^3^4^5) ^ (1^2^3^5) = 4
xor 1-n的数，再xor array里面的数给你那个唯一的missing number
但是这招对于2个或以上missing number行不通
所以我们回到addition to find missing number的路上来
sum(1-n) - sum(elements in array) 也可以给你唯一的missing number (potential
overflow problem)
把那个方法generalize到>1个missing number
a1=sum(1-n) - sum(elements in array), a1是missing number的和
a2=sum(1 squre-n squre) - sum (elements squre in array)， a2是missing number
的平方和
假设两个missing number是x, y
x+y=a1
x... 阅读全帖 |
|
g***s
发帖数: 3811 | 16 assume a and b are 64 bits int
c = 0xFFFFFFFF = -1;
c + 1 = 0
a-b = a + (-b) = a + (c xor b - c) = a + (c xor b - (c+1) ) + 1 =
a + (c xor b) + 1 |
|
g**u
发帖数: 583 | 17
In fact, I think xor can still work if we have 2 number appearing odd times.
after xor the entire array, we will find the first non zero bit of the
result, then we will partition the original array into 2 groups with the
first group with that bit to be 0, the second group with that bit to be 1,
we then do xor trick within each group, the left over is the number appears
odd times....
not sure for multiple(>2) number missing though.... |
|
S**I
发帖数: 15689 | 18 ☆─────────────────────────────────────☆
coconut001 (coconut001) 于 (Sat Apr 16 20:51:09 2011, 美东) 提到:
我是这周三面试的，周四回来歇了两天，压跟就没有心情来版上询问。我总共面了6个
人，5个
leader（真的各个title都是leader or senior leader，我就纳闷，M家木有engineer
吗？）和一
个PM。 问题比较简单，
实现strcmp，
实现malloc and free，讨论memory leak怎么解决，以及memory fragment问题
pointer问题（这个问的很杂，比如什么指针存的是一个已经out of scope的address之
后会发生
什么之类的，具体记不清楚了）
multi-processor相关问题，比如multi-processor的机器实现lock要怎么做，我好像说
了memory
bus之类的，中断这时候不起作用了。
Open question（这个问题我用数学模型解释，以至于面我的人以为我是Math的。。。
。。。... 阅读全帖 |
|
c****p
发帖数: 6474 | 19 3.简单起见，一个格子被直接按中导致的0-1翻转称为主翻转，和它同行同列的翻转导致
的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
或。
4.对于给定图案中的任意一点x,y，可以把它所在的行和列的所有元素相异或。对于M+N
为偶的，若结果为1，则说明该点被按过；对于M+N为奇数的，若结果为0，则说明该点被
按过。
举个例子（我自己写的一个生成图案的函数）
A是图案，D是被按过的键，也即我们要找的解
>> [A,D] = gen_pad(4,4,.2)
A =
1 0 0 1
1 0 0 1
1 1 1 1
0 0 1 0
D =
0 1 0 0
0 1 0 0
0 0 1 0
0 0 0 0
假设解为S矩阵，我们要求出S=D
假设左上角元素为A[1,1]，则
S[1,1]=xor(A[1,... 阅读全帖 |
|
p*****2
发帖数: 21240 | 20
我写了一个练练。
def findDup(l):
xor=0
for i in l:
xor^=i
checker=1
while not (xor & checker):
checker<<=1
ans=[0,0]
for i in l:
if i&checker:
ans[0]^=i
else:
ans[1]^=i
return ans
l=[1,1,2,2,3,3,4,5]
print findDup(l) |
|
z***m
发帖数: 1602 | 21 x = x xor y
y = x xor y
x = x xor y
对吗？ |
|
A*********c
发帖数: 430 | 22 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。 |
|
A*********c
发帖数: 430 | 23 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。 |
|
l*******n
发帖数: 101 | 24 1. since it asks for a binary way. maybe use robin karp? as for the hashing,
just xor all the elements in str and when u move forward the window in the
file, xor the first element at the front, which will cancel out the first
element, then xor the next element and so on.. |
|
b*********s
发帖数: 115 | 25 昨天onsite完的，趁还记得上来写一下，面的不好，求bless。
一轮店面
第一题判断一个string的开头第一个字母是不是大写，两行代码就能写完，没有任何陷
阱。第二题让我用Java（因为我本来用python）写判断binary tree是不是bst。两个题
都很简单，然后还让我说一下自己做过的最challenging的一个project，整个面试不到
二十分钟就说问完了问我还有没有问题，我连忙问他为什么这么快是不是我什么地方做
错了他不愿继续问下去。答曰他在G工作七年多面了不下一百人，十分清楚哪些人去
onsite不是在浪费他们engineer的时间，觉得我没有问题。。。
过了一周果然hr说去onsite，由于我所在的城市有G的office，所以去那里面，早上三
轮然后吃午餐，下午再两轮，一共五轮
第一轮
给一个矩阵，每个格子上有三种可能，空房，阻碍物或者是保安，阻碍物不能进，空房
四个方向都能进，要写代码给每个空房标记其离最近的保安的距离，比如
000
BGG
B00
B表示障碍物，G表示保安，0表示空房，应该标记为
211
BGG
B11
我说扫一遍矩阵，然后遇到每个G就bf... 阅读全帖 |
|
f******h
发帖数: 45 | 26 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
h*******t
发帖数: 2679 | 27 #include
#include
using namespace std;
char XOR(string s)
{
char result = 0;
for(int i = 0; i
result ^= s[i];
return result;
}
int main()
{
char targetXOR = XOR("pto");
string dict[]={"hello", "world", "pot", "opt"};
char result = 0;
for (int i = 0; i
{
result = XOR(dict[i]) ^ targetXOR;
if(!result)
cout << dict[i] <
}
delete dict;
return 0;
} |
|
d******v
发帖数: 801 | 28 好像不对，假设数组｛A, B, C, D, E, E} = {00, 01, 10, 11, E, E}。
1）xor all = 00 ^ E ^ E = 00 当E为任何值都成立
2）or all = 11 | E | E = 11 当E为任何值都成立
3）所以(xor all) xor (or all) = 11 当E为任何值都成立 |
|
m*****k
发帖数: 18 | 29 1. 扫一遍数组，XOR所有Unique number一次，得一数x
2. XOR 原数组所有数，再XOR x，返回此结果便是
O(n) time, O(n) space |
|
t*******r
发帖数: 22634 | 30 但是另一方面，我觉得那个 XOR 不像是碰巧的。。。XOR 好像有个特性产生不重复序
列，这个跟二进制几进制无关，是 XOR 的内在属性（dudo, let's make a "flip"）。
。。
现在没时间，等俺有空再想想。。。 |
|
t*******r
发帖数: 22634 | 31 我刚才又想到 XOR 有两个等价的表示：（1）XOR 的 binary 表示，
（2）XOR 的集合论表示。。。如果再联系上自然数也存在的集合论
表示。。。这个是不是能顺理成章的引出/想出？。。。
again，俺还在 brainstorming 的原始社会阶段。。。老板总是
喊我回 cube 码 code 的说。。。 |
|
t*******r
发帖数: 22634 | 32 我是 xor 两次，c 是第一次 xor，后面对 c 做 xor，实际上是两次。。。我承认我在
matrix tool 里都懒得多敲字。。。
不过这个矩阵的高维看起来意义不大，因为重复 pattern。。。重复 pattern 是因为
三维中间的那些点，投影不落在数轴上。。。 |
|
|
b*****9
发帖数: 8922 | 34 ☆─────────────────────────────────────☆
wonderlich (左岸，遁去) 于 (Sun Aug 1 19:31:25 2010, 美东) 提到:
（1）理发不仅仅便宜，而且是理得不错。
（2）早餐。
☆─────────────────────────────────────☆
miragedeva (砸锅卖铁养马甲) 于 (Sun Aug 1 19:38:47 2010, 美东) 提到:
同意。每次我回国，第一次理发的时候，理发师都会很不屑的问，你这个头上次在哪里
理的？
☆─────────────────────────────────────☆
salvinorin (salvinorin粉丝) 于 (Sun Aug 1 21:37:30 2010, 美东) 提到:
这就是国内最吸引你们的啊？好有追求。
☆─────────────────────────────────────☆
wonderlich (左岸，遁去) 于 (Sun Aug 1 21:44:01 2010, 美东) 提到... 阅读全帖 |
|
p****s
发帖数: 3184 | 35
The XOR solution already assumes a sequential scan.
So I don't know what's new in your claim.
It is clear that "to locate it" is completely different from
"to find what the value is".
For the latter one, O(1) space-complexity and O(N) time-complexity
given an array of N elements. That is, the XOR solution did it.
For the former one, O(N) time-complexity is trivial, but there is no
way you can get O(1) space-complexity. The XOR solution fails.
But I believe the interviewer was thinking about t |
|
w***g
发帖数: 5958 | 36 2. 任何一个二进制数跟自己的xor都是0
二进制数的xor是可以交换的
任何二进制数和0xor后还是它自己。所以答案是所有的数求xor，最后得到的就是单
个的那一个。复杂度为O(N)
这个东西我也是想了一会儿才想出来的。要是面试的话估计也挂了。 |
|
c*a
发帖数: 806 | 37 wrong board? should be asking math?
a xor k = c
c xor k = a
k = a xor c? |
|
x****u
发帖数: 44466 | 38 你不要太激动，我也是在研究这个细节。
我在VC上编译你这个程序得到的汇编也一样，说明这个行为普遍存在，不管符合不符合
语法，在多线程的全局变量前一定要加上volatile防止编译器自作主张cache值。
这个是没有volatile的
00321002 in al,dx
00321003 and esp,0FFFFFFF8h
unsigned int x=0;
00321006 xor eax,eax
global_var = 1;
for (long long i=0; i<10000000000L; i++) {
00321008 xor edx,edx
0032100A mov dword ptr [global_var (323378h)],1
00321014 xor ecx,ecx
00321016 add edx,1
00321019 adc ecx,0
0032101C cmp |
|
h*******3
发帖数: 3775 | 39 这几个问题是有关汇编语言移动光标的问题，大家能不能看看我做的对吗？
谢谢啦。
Write some code to do the following (assume 80x25 monochrome display, page 0
.)
Each part of this problem is independent of the other parts.
a)Move the cursor to the upper left corner of the screen.
mov ah,2 ;move cursor functin
xor bh,bh ;page 0
mov dx,0000h ;row 0,column 0
int 10h ;move cursor
b)Locate the cursor and move it to the top of the current column.
mov ah,3 ;get cursor location
xor bh,bh ;page 0
mov dh,0 ;top of current ... 阅读全帖 |
|
y**c
发帖数: 6307 | 40 我有一个程序计算CRC码，需要求任意2项或者以上的合并项，
比如，计算2项的合并：
void printCRCComb2(itemType *CRC, int n)
{
for(int i = 0; i < n; ++i){
for(int j = i+1; j < n; ++j){
itemType tmp = XOR(CRC[i],CRC[j]);
printCRC(&tmp,1);
}
}
}
}
但是如果计算3项，就有3个loop:
for(int i = 0; i < n; ++i){
for(int j = i+1; j < n; ++j){
itemType tmp1 = XOR(CRC[i],CRC[j]);
for(int k = j+1; k < n; ++k){
itemType tmp2 = XOR(tmp1,CRC[k]);
...
}
}
}
如果更多项，loop就更多了，容易出错，程序也不通用。有... 阅读全帖 |
|
q*c
发帖数: 9453 | 41 int X = 2
int Y = 3
X = X xor y
Y= X xor y
X = X xor y
经典面试题， 当年一个 principle 面试我，要我交换两个变量（用无脑的方法）。
这样的羞辱哥怎么能接收？马上就用这个把他跪了。 |
|
t********t
发帖数: 5415 | 42 co,s:out_logic
这个是啥？
co,s:out std_logic吧
另外为啥不直接用结构描述写呢？
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity fulladder is
port(
a,b,cin:in std_logic;
co,s:out std_logic);
end fulladder;
architecture structure of fulladder is
begin
s <= (a xor b) xor cin;
co <= (a and b) or ((a xor b) and cin);
end structure; |
|
c****n
发帖数: 21367 | 43 非常感谢 //thx & bow
已知 X,Y,Z 都是 i.i.d. 的均匀分布随机变量
取值范围都是{0,1}^n，也就是n个bit的二进制向量
令 A = X XOR Z, B = Y XOR Z （XOR是按位异或运算）
问1: A和B相互独立么？
问2: 如果 Z 的分布为任意分布，只是和X,Y相互独立，A和B相互独立么？ |
|
p*****k
发帖数: 318 | 44 just to be clear, everyone during the noon would present
her own guess. only one of them needs to be correct.
one way is to exploit the XOR operation. consider n=2 case
(one guesses the same character as the one she sees and
the other guesses the opposite to what she sees)
so consider (XOR sum of all numbers seen) XOR (own number)
here everyone is pre-assigned a character, which converts
to a number from 0 and n-1, before the whole process |
|
h**********g
发帖数: 3962 | 45 一下是图灵官网的描述。我觉得他在密码学方面的贡献是很重要的一部分。
Yao spent a year as a Professor in the Computer Science Division of the
University of California, Berkeley, and subsequently returned to Stanford as
a full Professor in 1982. During the early 1980’s, Yao produced a number
of papers which had a lasting impact on the foundations of cryptography,
computer security, computational complexity and randomized computation. This
work was significant not only for results obtained, but also for the
introduction of problems,... 阅读全帖 |
|
m*****f
发帖数: 1243 | 46 no need to sort, just xor the array and then xor 1 to n, done |
|
k***e
发帖数: 556 | 47 上次发了一题，没人理，继续。这两题都是来自职业杯。
1。Given a set of n points, find the line that intersects the most number of
points
想不出有比n^2更好的办法
2。Given n integers, find two of them that has max xor result
如果假定a xor b takes time len(a)+len(b)), then the naive way will take time
n^2 * avglen
my idea: first align all the numbers to same length, say it is x, then
distribute by most significant bit, as 1, 0, to two array one and zero. we
will keep dividing one into oneone, onezero, zero into zerozero, zeroone.
then to ac |
|
j**7
发帖数: 59 | 48 我只道 Array of integers 是个老题，不过有个问题问大家：
Hash table 和 XOR 那个快？有没有人试过？
XOR 的 bit operation 有没有办法并行计算？
Array of integers, all integers appear even times except one, find the one
appears odd times |
|
c*****y
发帖数: 90 | 49 实际上分组是虚的，并没有重新排序呀。真正的操作是当indexOf1这一位是1的时候与
temp1进行XOR,而当indexOf1这一位是0，与temp2进行XOR。以你的例
子:temp1=N1^N3^N3=N1,temp2=N2^N4^N4=N2。这样结果就出来了。
},
N1 |
|
k*******s
发帖数: 134 | 50 第二题就是给每一个文件checksum一下就好了。最基本的checksum的算法就是把文件的
每个word XOR.但是这样不是很精确，比如word order不一样就检查不出来。 复杂一点
的比如CRC算法,时间长一些，但是更精确。最后把XOR的值相等的文件分组就好了。 |
|
