e*****e
发帖数: 1275 | 1 You are given an array containing positive integers. All the integers occur
even number of times except one. Find this special integer.
Like, 1, 4, 5, 4, 3, 1, 3, 3, 5. 3 appears 3 times.
The solution is easy, just do XOR for all of them.
But, what if n integers instead of 1 occur odd number of times, how you
gonna find them out? |
|
|
h***n
发帖数: 276 | 3 还是异或(XOR)，出现偶数次的，都消掉了(0)，出现奇数次的保留了下来，因为0^x=x |
|
l****i
发帖数: 396 | 4 保留下来的是几个出现奇数次的数的xor值，怎么把每个都找出来呢？
x |
|
r******d
发帖数: 308 | 5 把每一行转成一个二进制度的数， 看这个数是不是等于0?
不过前提是那个数组已经放在一个string 数组里面了
或者XOR每一列的所有数字， 看看哪行总是保持在0? |
|
s*******e
发帖数: 93 | 6 又说连续数组吗，然后其他都是一次吗？
比如是 1 2 2 2 3 4 5 5 6 这样，
还是完全random的，比如: 1 2 2 2 7 7 8 10
?
如果是后者，估计就是先看能不能用hash,如果不能用外部空间就先排序再一个一个扫
如果是前者，我猜是先 xor 所有数 以及 min 到 max的所有数，
然后得到出现2次的那个。
然后要找出现3次那个，把所有数加起来？这样问题是可能overflow,但是O(n)没有大量extra space一定可以找出来。 |
|
C*****n
发帖数: 1872 | 7 俺的答案：
1. bitmap
5. 3^6 - 3*(2^6) + 3
6. XOR 0xFFFFF
列组合了。。。 |
|
n*****y
发帖数: 361 | 8 学理论的吧？
你说的也对，但二楼比你解释的直观多了。
that
when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for
the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1
, the XOR result
, |
|
j*****u
发帖数: 1133 | 9 1. 除了2^N外的数都可以
2. a+b = (a XOR b) + (a AND b)<<1，递归
3. binary search, sqrt(n): min=1, max=n,循环计算mid^2直到它接近n |
|
t**********n
发帖数: 145 | 10 找工作这段时间以来常匿名浏览，在版上获益良多。不久前刚拿到A公司的Offer，特地
注册了账号，呈上面经，以感谢各位xdjm。
先说一下我的背景，国内CS硕士，毕业后在国内做了三年startup。去年10月搬家到西
雅图，11月初开始撒简历，没有什么reference，直接网投。就在投简历到A公司网站上
之后一个礼拜不到就有recruiter发来email说邀请电面。BTW，至今其他投递的简历没
有一个有音讯的，回想起来感觉很lucky，另外说明A公司直接网投是有用的。
因为自己的背景，所以apply主要是SDE/AJAX/front-end的position。其实这类
position的面经在上网还挺少的，所以希望我的面试经过可以给大家提供这方面的参考。
面的过程一共是3轮phone interview和2轮on-site，其中一次是8个session，另一次是
3个session，面的比较多，可能是因为有2个team都感兴趣的关系。
整理了一下印象比较深的问题有以下这些：
========比较Personal的一些问题========
1）简单介绍自己。每个interviewer必... 阅读全帖 |
|
s**x
发帖数: 7506 | 11 大家多多贡献吧。这里那里有好多，还是集中一下比较方便。
先从偶知道的说吧。主要集中在 algorithms and puzzles.
Q1. how to verify a binary tree is a binary search tree?
A. the trick is to have a max and min value node for the function.
Q2.25 horses problem. 25 horses, 1 track, each race can race 5 horses only,
no timer, find the top 3 horses running the fastest with min races.
A: skip as this is well known.
Q3. all the numbers in an array occur twice except one only occur once, find
the one that occurs once.
A: simply xor all the number... 阅读全帖 |
|
g**u
发帖数: 583 | 12 Q14:
why the prob is not the same? since it is a fair coin, the H and T is
interchangable.
Q15:
I do not understand it. Why not directly using Xor OXFF(1111 1111), then
all the bits 1 will be 0, all the bits 0 will be 1.
Could you please elaborate your algo? |
|
c******n
发帖数: 4965 | 13 q3 I see it all the time
bit I don't understand why XOR would work here
eg. 1 2 3 3
we look for 3. can u show me?
l |
|
b***e
发帖数: 1419 | 14 来自主题: JobHunting版 - 矩阵变换题 Yes, there is a simple solution here, which is no more than to solve a
set of linear equations.
Taking the example in OP as an example:
1. computer the xor, we get:
1 1 0
0 0 1
0 1 1
2. linearize it, top to bottom, left to right, let R be:
1 1 0 0 0 1 0 1 1
3. List all the transformations you can do, let T be:
1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1
1 0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1
4. Let T' be the transit of T, and R' be the transit of R (so R's is a
column). ... 阅读全帖 |
|
f*******4
发帖数: 1401 | 15 1. 对 就是hash
2. 我说了这个 也说了XOR 面试官说也行 但不是他想的答案。对了这个题不允许用其
他存储空间。
3. 好像不是这个意思。n是固定的。只是问在n的大小是多少时候分别怎么选。
4. 咳 这个俺真不懂了。。。
我觉得答得一般般... |
|
g*********s
发帖数: 1782 | 16
how come xor works? that one is for all but one twice, i believe. |
|
b******n
发帖数: 4509 | 17 you xor all the number and then 1-10000
用其 |
|
g*********s
发帖数: 1782 | 18 interesting solution. i see two advantages of this:
1. although it's a two-pass solution, xor is much faster than addition.
2. no overflow concerns. |
|
s********y
发帖数: 161 | 19 刚面完，回到酒店。上帝保佑明天拿到给offer。感谢祝福。签了NDA，不过以下应该也
没有泄露亚麻的技术秘密...
网络服务组
Common questions几乎每个人都会问到, why 亚麻, why web service, your
experience/work.
Phone 1 别的组的老美
两个数组求交集。如果已经排好序了，一个数组很大，一个很小怎么办。如果数组都很
大，内存放不下，怎么办。
设计扑克牌。扑克牌shuffle算法。
两个整数，需要多少步才能把一个数的二进制表达转换到另一个数的二进制表达。 （
XOR后数1）
Phone 2 本组的印裔
设计LRU Cache, 然后讨论多线程访问Cache的问题。面完后实现Cache发代码给他。
Onsite见了7个人，每个人45分钟，连轴转。上午10点半进building, 下午4点出来
Onsite 1 很Nice的老美
讨论设计web crawler， coding BFS， 讨论多线程处理crawler等。
Onsite 2 印裔
OOD机场air traffic control system.
Onsite 3 ... 阅读全帖 |
|
s********y
发帖数: 161 | 20 对
是的
这个要跟interviewer clarify, 是不允许重复访问的，否则DFS没有尽头了...
关于那两个整数转换，就是看有多少次0->1或1->0。所以把xor两个数后，就变成了经
典的在binary representation中有多少个1的问题 |
|
g***s
发帖数: 3811 | 21 c xor b = c - b since c = 0xFFFFFFFF; |
|
g***s
发帖数: 3811 | 22 if so, it is my answer:
a + (c xor b) + 1
c = 0xFFFFFFFF |
|
x**y
发帖数: 1086 | 23 找整数数组里面出现奇数次的元素那道题
如果只有一个的话可以用xor
如果有多个或者一个都没有该怎么考虑啊 |
|
r******e
发帖数: 80 | 24 use XOR, if the result is 0, then no odd integer. If the result is not 0,
then it has at least one odd integer. |
|
g***s
发帖数: 3811 | 25 give a sample :
1, 2, 3
xor = 0
0, |
|
C***y
发帖数: 2546 | 26 1. bitmap比较好，当然sort也可以做
这个有个问题就是，可能in-place remove 所用的两个指针所指的位置不能同时装入内
存，这个问题还没想好如何解决
2. 方法很多
a. 全部加起来，看缺多少，就是哪个数
b. 1xor2xor...10000，然后继续xor给的9999个数字
3.
不知道，太开放了，先说集中可能，再跟面试官交流，慢慢讨论吧
duplicate？
法得出缺了哪个数字？
code，不看GDB的trace和应用程序的log，该怎样快速诊断出可能的原因？ |
|
j***y
发帖数: 2074 | 27
bitmap不是图形格式吗？能把数组变成一个bitmap？不太懂啊。能不能给段代码的例子？
这个方法就是面试官后来跟我说的。不过他后来又说，如果是9998个数字，数值从1到
10000，缺两个，加法就貌似不行了。这种情况下，该用什么方法呢？
这个方法是个什么原理啊？xor完这19999个数字之后就能保证得出漏掉的那个数吗？
当时面试官和我说的是这种问题，第一个想法应该是不是disk IO出问题了？不过我想
，不看log，不看trace，怎么能断定是disk IO的问题？莫非去看硬盘指示灯？
因为电面表现太差，也没好意思去详细问这个问题的思路。
对了，忘了提公司的名字了，NetApp。很好的机会被我浪费了，还是弱。 |
|
|
j***y
发帖数: 2074 | 29
不明白这个xor解法的原理是什么，可以简单讲一下或给个参考文献吗？ |
|
f***g
发帖数: 214 | 30 没找到，我试着讲一下：
仍然按照Chevy的方法做
如果是一个数：
最后的结果就是 M
如果是两个数：结果就是M1 xor M2
从这个结果中挑一个bit为1的，就可以把原数组划分为两组。missing numbers分别在
这两个组中。
按照1个数的方法再分别做一遍。
据说这个思路可以扩展到3个，4个数去
有个类似的http://geeksforgeeks.org/?p=2457 |
|
|
j***y
发帖数: 2074 | 32
啊，这个重要的xor的性质我忘记了，谢谢提醒。 |
|
j***y
发帖数: 2074 | 33
知道A xor A == 0之后，明白对一个数的解法了。
嗯，现在也还明白。
详细读了链接里面的文章，终于弄懂了。多谢。
另外想再请教一下，对第一个duplicate的问题，有什么好的方法吗？ |
|
r*****e
发帖数: 792 | 34 怎么扩展到3个呢？如果缺的数字是2，4，6的话，
xor的结果就是0了。没有任何bit有1了。 |
|
t****o
发帖数: 31 | 35 如果数组中没有重复integer的话，可以用XOR判断。 |
|
e*****e
发帖数: 1275 | 36 题目是不时错了？是两次而不是三次？
两次就XOR |
|
M*****e
发帖数: 568 | 37 这个变量名已经说得很明确了，
ones就是所有出现过一次的，所以每次更新用xor （注意后面去除了三次的）。
twos就是出现过两次的，更新的意思就是如果当前数b[i]在ones中存在, b[i]&ones，
就加到twos里面。
three就是一次和两次都出现过的，所以要从ones和twos中每次去除, & not_threes |
|
Z**********4
发帖数: 528 | 38 问简历
如何测试一个DVD player
第二题
int x=20; int y=35;
x=y+++x++;
y=++y+++x;
问之后x 和y 是多少
第三题
怎样交换两个数而不用temp （XOR）
哎。。简历被问得SB了。。 |
|
s*****y
发帖数: 897 | 39 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
|
|
s*****y
发帖数: 897 | 41 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
|
|
|
M7
发帖数: 219 | 44 就说xor应该可以吧？
数学上这个符号叫hat |
|
l*********r
发帖数: 674 | 45 ft, 大家说法都不一样啊。下次如果问到我还是直接说xor算了。 |
|
g***s
发帖数: 3811 | 46 Xor
请问帽子的题目有人能贴一下solution吗？
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite |
|
f****4
发帖数: 1359 | 47 我给interviewer问到过用temp交换和用XOR交换哪个效率高的问题
被告知，编译器对temp交换有优化：两个变量的指针，入stack，后出stack |
|
c**y
发帖数: 172 | 48 XOR only works for int, long and char (unsigned and signed).
For other types, temp is the way to go. |
|
g**u
发帖数: 583 | 49 攒RP, 发第二轮Amazon面经
一开始是 interviewer自我介绍3分钟，对方介绍自己组的project,讲的巨快。 自己手
机信号不好，没听明白， 就不时“hum”表示依然在听，没掉线。
接着开始做题，题目是非常经典的:
在一个数组中，有的数字出现基数次，有的出现偶数次，写程序找出出现基数次的方法.
脑袋不知为何短路， 没有说 xor 的方法，直接就上了hash_map,
， 然后设置sum=0,通过sum的值来确定出现基数次的元素； 然后讨论如果输入里面所
有的元素都出现偶数次怎么办， 接着讨论hash table 的设计考虑的因素，然后被要求设计一个 差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃.....然后被要求电话里面读code实现......
接着是OOD, 就是经典的设计card的问题， 说了一通，基本上和career cup查不多； 被要求实现shuffle cards的算法；
然后interviwer开始变要求, 如果要支持不同的游戏规则怎么办，答strateg... 阅读全帖 |
|
g*********s
发帖数: 1782 | 50 xor doesn't work if two numbers appear odd times.
法.
求设计一个
差的hash function, 肯定没听错，的确是设计一个差的hash function, 自己一顿瞎侃
.....然
后被要求电话里面读code实现......
被要求实
现shuffle cards的算法； |
|
