s*****i
发帖数: 355 | 1 预处理100K个矩阵，记录每个矩阵0和1的个数，用这个签名作为key保存在hashmap里面
然后找出与要查找的矩阵签名相同的，然后挨个比。因为都是0和1，用XOR应该比较快 |
|
s**********h
发帖数: 19 | 2 第一题为什么不能用XOR,最后结果是0就是相等... |
|
|
t****t
发帖数: 6806 | 4 其实大家说的求和, 求平方和, 求XOR都是一个意思, 就是用一个hash function或者说
signature, 只是这里要求invariant to element order
普通的signature很常见的, 比如说CRC32, MD5之类, 不是invariant to element
order, 可以做一些诸如验证下载是否正确的事情. 这是一个快速的方法, 特别是正确
序列的signature已知的情况. 它不能保证检测正确, 但是它能保证检测错误, 在随机
错误的情况下, 检测正确的成功率也很高.
我觉得你要能答出这些, 就差不多了. 关键是given random error pattern, it has
high probability of successful. 如果是人为forged error pattern, 那么再另说. |
|
|
|
l*y
发帖数: 21010 | 7 第一道题难道不是这个数组中只有一个重复奇数次的数，让你找到它？xor所有元素就可
以了 |
|
l*y
发帖数: 21010 | 8 第一道题难道不是这个数组中只有一个重复奇数次的数，让你找到它？xor所有元素就可
以了 |
|
|
r****o
发帖数: 1950 | 10 我也想问这个问题，
不知道能不能整数部分和小数部分 分别XOR. |
|
|
c***g
发帖数: 472 | 12 一个unsorted的array, 包含1 - n的没有重复的整数
如果已经知道有n-1个, 只有一个missing, 怎么做, 这个加起来和xor就行了
如果已经知道只有n-2个, 只有两个missing, 怎么做, 1 到 n加起来, 算差, 1 到n的
平方, 加起来, 算差, 然后解方程.
这中间有人提到1到n的平方算和的时候会有overflow的问题, 怎么解决? 可以不可以
先算i的平方, 然后减去array[i]的平方, i从1到n求和, 这样就没有overflow了吧
如果已经知道有n-3个, 只有三个missing, 怎么做, 还是这样求三次方的和了再解方程
么?
还有别的办法么? |
|
|
|
r****o
发帖数: 1950 | 15 hi, Teves99, 问一下，如果一个数组里面装的是double，还能用XOR这种办法吗？ |
|
|
w******1
发帖数: 520 | 17 字符串AB 和AB XOR 之后， 是O 啊， 没问题吧 |
|
t**g
发帖数: 1164 | 18 Given an array of integers where some numbers repeat 1 time, some numbers
repeat 2 times and only one number repeats 3 times, how do you find the
number that repeat 3 times. Using hash was not allowed.
有人说可以用XOR，可是我不是很明白
谁能解释下，谢谢！ |
|
t**g
发帖数: 1164 | 19 careercup上的
大侠们只给出了xor的提示
没留下其它线索
所以来这边问问 |
|
r***e
发帖数: 486 | 20 面试的时候遇到的，有一组bit arrays, 有一个target bit array, 怎样判断那一组里
面有没有一种组合的XOR等于target的那个。 |
|
y**i
发帖数: 1112 | 21 怎么有点像一组数里面找两个数的和等于一个给定的数那道题？
只不过那个可以用hashtable，用sum-A[i]在hashtable里查找，这个等价的位操作该是
怎样的？xor倒是sum without carry，就是怎么实现对应减法不借位 |
|
y**i
发帖数: 1112 | 22 好像还是xor哦，那么就可以用sum^A[i]在hashtable里查找了 |
|
g*****u
发帖数: 298 | 23 人家没说是两个array XOR成target array哦
可能是3个，4个甚至全部呢。 |
|
y**i
发帖数: 1112 | 24 那就每次插入到hash表的时候把自己以及自己和hash表中的每个元素的xor都插入进去
，总可以了吧 |
|
y**i
发帖数: 1112 | 25 hash表比较倒只要一次平均时间O(1)，空间复杂度是高了点，构造的时候如果要考虑与
之前的元素取xor，时间也会上去，成为N^2，这个方法最适合找2个的组合，空间复杂
度O(N)，时间复杂度O(N) |
|
|
z*****j
发帖数: 6 | 27 1) char * ptr = “Hello”;
sizeof(ptr) = ?
a. 1
b. 4
c. 5
d. 6
2) char obj[10][20][30];
sizeof(obj) = ?
a. 6000
b. 600
c. 60
d. 1
3) char c = 127; c = c + 10;
Which of the following is true?
a. c > 0
b. c = 0
c c < 0
d .c >= 0
4) double a = 5/10*2.0;
a = ?
a. 0
b. 0.25
c. 1
d. 0.05
5) int a = 2|1; //Bitwise OR operation
a = ?
a. 0
b. 1
c. 2
d. 3
6) int a = 3^1; //Bitwise XOR operation
a = ?
a. 0
b. 1
c. 2
d. 3
7) #include
int main()
{
int a = 5;
{int a = 6;cout<
return 0;
}
Wha |
|
m*****g
发帖数: 226 | 28 这方法最大的问题是要你找重复出现的n个
一下子就死悄悄了 |
|
d*******n
发帖数: 369 | 29 swap a and b using XOR (no the third variable). The following function is
correct? Explain
swap(int *a, int *b)
{
*a ^= *b ^= *a ^= *b;
}
I found that if I write it as follows, it's correct
*a ^= *b;
*b ^= *a;
*a ^= *b;
but *a ^= *b ^= *a ^= *b is wrong but why? explain in detail |
|
w******e
发帖数: 81 | 30 看起来像是 *a^=*b^=*a^=*b在具体运算时第一个*a的值跟第二个*a的值没有同时
update。第一个*a应该是保留了初始值，第二个*a=*a^*b，之后*b换成*a的初始值，这
样最后一次*a^*b实际是两个相同的数xor，结果为0. |
|
a*d
发帖数: 47 | 31 If #1 problem is changed to array of N-1 element, then we can use bit XOR
operation to find the missing number. |
|
Z*****Z
发帖数: 723 | 32 举例：1到7的数组，现在5和6missing，1和2duplicate，也就是说：
1,1,2,2,3,4,7
做XOR的结果相当于3，4,7做抑或，结果为0。
这个方法甚至于对1个missing1个duplicate的也不work，举例：
1到6的数组，6 missing 1 duplicate，也就是说
1,1,2,3,4,5
做抑或的结果还是0
除非我对你这里做抑或的理解有误 |
|
Z*****Z
发帖数: 723 | 33 1面：
1、introduce yourself
2、why amazon
3、BST和Hashtable的比较，有什么区别
4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
，2个都提了一下，就跳过了）
5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
存，我用了个list，被指出这样影响复杂度。
2面：
1、一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。问
了3种解法。
解法1：XOR。问复杂度，O（N）
解法2：hashtable。问hashtable 的size。（N-1）/2+1。他说对，同时N/2+1也是对的
，为什么？答：因为N永远为奇数。
解法3：sorting，复杂度
2、详细比较ArrayList和LinkedList的实现，优缺点。
3、设计parking lot。（这个不是OOD问题）
3.1 只有1个valet，这个系统如 |
|
s*****n
发帖数: 956 | 34 发个帖子，也许对大家有用。大牛看了别笑话。
1. 找数组中出现奇数次的一个整数
n*n 2层循环 做了一次
sort 后一层循环 做了一次，
他一定要n time的。 我说要不弄另外一个大数组用index记数好了。他说太大了，
不好。然后问我会哪些data structures.我说blah blash， hash。
问我会不会用hash做,我就说那就数hit次数吧。 然后问 hashtable, hashmap，
有啥区别。 我说一个syn, 一个non-syn， 我不记得哪个是哪个了， 我不怎么用这2个
东西。 问我用哪个。 我说这个就用Non-syn吧，反正不是multiple-threading。他没
表态。 我对吗？
其实昨天我看到这个题目了，可惜没时间去看一下答案。 原来xor一下就完了，
tnnd。
2. 斐波纳切数列，
递归做了一次。 问有什么问题吗？ 我说可能stack overflow。 那怎么办？ 我说可以
用循环。然后集里哇啦想了下用循环做了一次。
3. 会web service吗？
不会
4. 会Unix吗？
很久没用了
5 |
|
z***9
发帖数: 696 | 35 找数组中出现奇数次的一个整数-->
xor all the data in the array. the result is the one you are looking for, O(
n) |
|
F*****n
发帖数: 1552 | 36 出现奇数次的整数只能有一个吧，不然xor没有用。 |
|
s*****n
发帖数: 956 | 37 比如 1 1 4 4 4 2 2 5 5
4 出现了奇数次， 其他 1 2 5 都出现了偶数次. 要求你找出 4 来。
如果出现奇数次的整数有且只有一个。 那么XOR是最好的方法。
如果有多个这样的整数，可能就要想别的办法了。 hash什么的。 |
|
|
y*c
发帖数: 904 | 39 深表同意。至少准备3个月。我觉得程度就是小trick(XOR, slow, fast pointers)要全
部了解，经典解法(recursion，DP, divide conquer)全部掌握，基本数据结构滚瓜烂
熟（stack simulating queue, various tree traversal, hash）就可以面试了。从电
面到onsite一个月，所以时间可以缩短到2个月准备（需要很dedicated），
programming pearl + 做一下题可以搞定电面。 |
|
|
i**********b
发帖数: 77 | 41 1）为什么 new 出来的object 不能用free。 malloc出来的object不能用delete。
我说了constructor，destructor 的原因.他们还问有没有其他原因。假设不涉及资源
分配问题。
2）SQL alias是用来干嘛的。不会，乱答的
3)为什么assign operator 不能自己assign 给自己。没打上来
4）算法题： 一个array里找唯一一个duplicated integer
5）abstract class, pure virtual function. why use them
两个老印，一男一女。女的极度tough. 我还在一边说一边想呢。她居然challenge我说
"now what?!" 算法题我给了两个解法。一个sort，binary search，另一个bitwise
XOR。那个男的让我用个例子go through 一下。我马上就快说完了。那女的居然说“we
are running out of time".其实才不到45分钟。而且我就差一句了。 剩下的15分钟
我可以问问题。真没礼貌。 不知道bloomberg的人 |
|
|
j***u
发帖数: 16 | 43 这个bitwise xor 只适合 连续 array 吧. 对非连续 的无效.
最好还是先排序, 然后找, 反正duplicated integer是前后相邻的 |
|
N*D
发帖数: 3641 | 44 use XOR
int dup = a[0];
for (int i=1; i<=N; i++) {
dup = dup ^ i ^ a[i];
}
return dup; |
|
p******r
发帖数: 2999 | 45 q1: 用xor运算
q2: return !(n & (n - 1));
share |
|
r******e
发帖数: 80 | 46 how does the Q1 use the xor ? Can you explain more? Thanks a lot. |
|
d**e
发帖数: 6098 | 47 如果要快过binary search...这里要先sort再search，所以是O(n log n)吧
比它快，就要O(n)，用xor了…… |
|
x****9
发帖数: 24 | 48 背景：ECE的MS, 过了online assessment智力题，约电面
电面：一共不到40分钟，只有一个面试官，应该是老印，不过没什么口音，听的比较清楚
首先behavior，where do you hear Bloomberg, why Bloomberg, why this position
然后介绍自己project，面试官问project中用了什么data structure，问的比较细
然后让我比较Link List 和 Array的优缺点，怎么优化Link List的random access比较
慢的缺点
然后是两个算法题，第一个问题找数组中第二大的元素，我先说遍历两遍第一遍找最大
第二遍找第二大，然后又说可以先排序再输出，他问排序的效率多少，我说看算法要么
O（N2）要么O（NLogN），他问那种好，我说第一种只用O（N），他问第一种一遍行不
，我想了想说行只要俩变量就行，然后他让给出大概的代码，pseudo code也成，我就
大概看了看然后直接跟他说代码，要考虑输入如果是0个元素或者只有1个元素输出-1，
否则遍历数组然后输出
第二题是经典0-N少一个数找出这... 阅读全帖 |
|
l*****a
发帖数: 14598 | 49 1)
Use XOR if u know the scope of the numbers. |
|
e*****e
发帖数: 1275 | 50 地球人都知道如果只有一个整数咋办。XOR~~~~~
如果是n个整数出现奇数次,怎么搞？ |
|
