i**********e 发帖数: 1145 | 1 [3, 2] and [6,7]
both XOR equal to 1. |
|
n**e 发帖数: 116 | 2 Let result = XOR all the integers in both arrays
return result == 0; |
|
n**e 发帖数: 116 | 3 Let result = XOR all the integers in both arrays
return result == 0;
It does NOT work |
|
s******o 发帖数: 2233 | 4 is XOR all == 0 enough already, if there are no duplicates?
the
start |
|
H*****1 发帖数: 4815 | 5 怎么用XOR啊?
请详解,谢谢!
the
start |
|
z*********8 发帖数: 2070 | 6 好吧, 如果 XOR=0, 和相等, 平方和相等, 立方和相等, 行不? |
|
l***m 发帖数: 339 | 7 俺觉得 和相等,乘积相等应该就是最优的吧。XOR有很多特殊情况是处理不了的。比如
22222,33333。 |
|
|
|
|
|
|
c****p 发帖数: 6474 | 13 两个元素之间的xor操作是O1的,,一堆元素嘛,,,肯定不是O1的 |
|
L*****k 发帖数: 327 | 14 记得一个说法是即使大量数据做XOR,也是很快,但不知道具体到什么级别~ |
|
c****p 发帖数: 6474 | 15 有range的话可以用xor搞吧。。
或者是每个元素都是俩,有一个是一个的。。。 |
|
h*****3 发帖数: 1391 | 16 如果range,而且是n+1的元素,xor不就可以了?
要不bitmap? |
|
|
s********0 发帖数: 34 | 18 这样行不
如果要找的两个数不一样: a != b
可以转换为 2个(1...1000)的范围 + a + b
即一个数组只有两个数a, b 出现奇数次(3次),其他均为偶数次(这边为2次),找出a,b
然后按照经典XOR的方法处理 |
|
a********d 发帖数: 195 | 19 板上原来的题。xor找这两个数的抑或,找到第一个不同的位置将所有数按此位分两组
,分别异或得结果。 |
|
G******i 发帖数: 5226 | 20 ☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Nov 9 17:30:25 2011, 美东) 提到:
听说变态的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
< ... 阅读全帖 |
|
a*******y 发帖数: 1040 | 21 Given an array of 32bit unsigned integers in which every number appears
exactly twice except three of them, find those three numbers in O(n) time
using O(1) extra space. The input array is read-only. What if there are k
exceptions instead of 3? |
|
a*******y 发帖数: 1040 | 22 k是奇数怎么搞
比如k是3,set的bit是1的话,三个数在这个位置上可能是0,0,1, 也可能是1 1 1,
这个怎么搞? |
|
a*******y 发帖数: 1040 | 23 如果res1中没1了,bit为
这句不对,应该是三个0或者1,1,0,
还有一种情况就是,你都试过了所有的位置了都不行,那么就是这三个数都是一样的 |
|
|
b******8 发帖数: 27 | 25 问给一个set,比如1122334,其中只有一个数字出现奇数次,其余均为偶数次,如何找
出该数
答:xor
问,如果有两个数出现奇数次,怎么找
答:hash table
问:如何改进空间复杂度
答:先排序,再遍历一次,看相邻两数是否一样
问:有没有别的方法
答:。。。不知道了。。。 |
|
C***U 发帖数: 2406 | 26 code看这里
http://blog.sina.com.cn/s/blog_60b5450101019v71.html
思路是这样的
比如你有101和110
那么你要把都是1的那些位拿出来,因为这些为相加会进一位,需要用&
这个例子里面百位都是1,所以他们相加变成0,所以进以为。那么我们就取出100 然后
进以为得到1000
然后呢你需要把剩下那些没有加的拿出来,都是0的不用拿出来,因为相加是0,所以你
就用xor把对应位置不同的位拿出来
然后再把这两个相加就是需要求的和了,这里用到recursion。
然后很容易就能说明剩下的那个数总是越来越小,最后变成0的
所以你结束recursion的条件是小的那个是0的时候,那就返回大的那个数字 |
|
v**********r 发帖数: 40 | 27 来自主题: JobHunting版 - A家一道题 XOR啊 |
|
t********e 发帖数: 344 | 28 来自主题: JobHunting版 - A家电面题 第一题用XOR吗 |
|
k***g 发帖数: 58 | 29 来自主题: JobHunting版 - A家电面题 我在想怎么对string直接做XOR……
C++/Java编译似乎不支持,怎么转换一下? |
|
k***g 发帖数: 58 | 30 来自主题: JobHunting版 - A家电面题 恩,分别XOR所有string在同一位置的char可行
我之前在想有没有更简便的直接对string进行操作方法,似乎绕不过per char |
|
m***k 发帖数: 946 | 31 再请教一道题:
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
这题不是1-N的范围里缺一个数。我看了测试case,类似[1,2,6,7]是可能出现的。这样
就不能用“只有一个数出现奇数次”那种bit xor的办法来解了。
谁有什么好办法? |
|
h****n 发帖数: 1093 | 32 第一次:
1)如何设计系统去处理很多的user requests。
cache,load balance?
2)implement LRU(least recently used) cache.
hash+doubly linked list?
第二次:
1)1-100的整数,有一个数出现一次,其余的数出现两次。找到仅出现一次的那个数。
XOR?
2)找到输入数组中所有的pair which sum up to a given value。要求考虑数重复
出现的情况。现在发现自己的程序有bug。
two pointers?
3)hashset vs. hashtable. 不熟悉,就回答了对hash的理解。
set没有value?
总体感觉不难。对interviewers感觉比较舒服。希望能拿到onsite。 |
|
z********i 发帖数: 568 | 33 1.1)cache, load balance. 我也回答了,但被追问怎么做load balance。最后用以前
router的记忆回答说router可以load balance to a server farm according to user
IP addresses.
1.2)Yes, hash+linked list。
2.1)可能记反了,xor好像不能用。题目可能是找到仅出现两次的那个数(其余的数仅
出现一次)。
2.2)我程序的bug是不能正确处理输入为k/2, k/2, ...,k/2 where k is the target
sum.
数。 |
|
h****n 发帖数: 1093 | 34 必须是doubly linked list,否则无法在O(1)内做更新和删除操作
仅出现两次的话也一样做,因为数有范围,所以你把输入和1-100这些数做XOR,剩下的
那个数就是出现两次的数了
你这个bug是面试官指出来的么,因为2 sum题一般都是假设数都是不一样的
user
target |
|
|
U***5 发帖数: 2796 | 36 来自主题: JobHunting版 - BB 电面 第3题咋整?
弄100个bitmap,
1: 000000000....
2: 101010101....
3: 1001001001...
100: 1000...001
然后XOR?
in |
|
p*******8 发帖数: 344 | 37 1)一个数组,除了一个数只出现一次,其他都出现两次,找出这个数。经典题之一,
XOR就行了
2)很大一个文件,内存放不下,里面都是整数,有重复,求只出现一次的整数的个数
。应该是大数据吧,我就说了hash到多个小文件,保证一样的整数到同一个小文件,然
后依次读进内存用hashmap/hashset处理,面试官说如果所有数都一样,hash后还是一
个文件,我想了下想再hash一次,后来想干脆用hadoop搞,用两个job,第一个每个map
读进来,key是integer本身以及map task id,reducer负责输出这个task的unique的整
数,partioner根据integer和map id进行分配,然后第二个job把reducer设置成1个进
行合并。感觉杀鸡用牛刀了,但想不到啥其他方法
3)差不多的题,这次输出所有unique的数。我想了下先把所有一样的数hash到小文件,
如果小文件size还太大,再进行二次hash,根据文件size进行平均分配,然后处理每个
小文件,最后合并结果。
感觉2)3)答得不好,大数据以前就稍微看了下top k之类的,都是hashmap ... 阅读全帖 |
|
|
c******5 发帖数: 84 | 39 1.给定一个整数(也可以是任意位的数),已知里面有一个duplicate的digit,其余都
是unique的,问如何求出这些duplicate digit的位置,开始想要用XOR,不过后来还是
用的hashtable。
2.设计一个Stack类。 |
|
|
c***f 发帖数: 40 | 41
请问大牛, 能具体点吗,用xor 做怎么排除 1 surrounded by 0的情况呢,
time ,space 是多少呢
谢谢! |
|
f*******3 发帖数: 206 | 42 仔细读题的话能发现重复只可能有一次我觉得不管写几个算法xor是他想看到的 |
|
p*****2 发帖数: 21240 | 43
不是有followup吗?我觉得LZ那个sum作为第一个解答还可以吧?后面的followup可以
说xor呀。
follow-up: Give another algorithm for this problem. Find as many algorithms
as you can. |
|
B********t 发帖数: 147 | 44 bar raiser那个,能想到的所有的
1. 求sum
2. hash map
3. 类似 first missing positive, 不停的swap
4, xor
5, sort
还有别的么 |
|
|
p****e 发帖数: 3548 | 46 这是哪个track啊
hackerrank对代码优化要求很高,不同test case差别很大
search那个track的Arithmetic Progressions我的code死活过不了后面3个test case
但是前面的都只要0.1s |
|
a******3 发帖数: 113 | 47
Bit Manipulation
我没有什么头绪去优化。。求各位指导一下 |
|
p*****2 发帖数: 21240 | 48 话说我昨天做了median那题也没过。还没心情再花时间搞呢。 |
|
|
|