l****u
发帖数: 46 | 1 1.
Write a boolean function for determining if an integer is palindrome.
2.
Given three linked list of integers, all sorted. Find the first shared
integer in all three. What is the time complexity? |
D*********y
发帖数: 876 | 2 说说我的想法：
第一题我在A家面试的时候也遇到了
假设原来的数是num，定义a=num, b=0
每次取a&1也就是a的最右边一位，b=b<<1+(a&1)
a = a>>1;
那么b就是num的inverse bit的结果
return ( num-b==0 )
第二题我的想法是
从三个linked list的开头往后遍历
如果三个数相等，返回结果
如果不相等，最小的那个数->next，继续比较
总之就是比较当前最小的那个数和其他两个数是否相等
complexity是O(n1+n2+n3), n1, n2,n3是三个linked list的长度 |
C***y
发帖数: 2546 | 3 1. 这个palindrome是指decimal还是binary representation的？
2. 除了用了size = 3 的heap来merge，还有更好的办法？
【在 l****u 的大作中提到】
: 1.
: Write a boolean function for determining if an integer is palindrome.
: 2.
: Given three linked list of integers, all sorted. Find the first shared
: integer in all three. What is the time complexity?
|
D*********y
发帖数: 876 | 4 我在Amazon面的时候问过面试官
palindrome指的是decimal还是binary
他说是binary
其实decimal方法也一样的
【在 C***y 的大作中提到】
: 1. 这个palindrome是指decimal还是binary representation的？
: 2. 除了用了size = 3 的heap来merge，还有更好的办法？
|
C***y
发帖数: 2546 | 5 binary的
用reverse比较好吧
logN复杂度，N=bit数
decimal的，
a 原来的
b reverse之后的
int b = 0
while(a){
b = b*10 + a%10;
a /= 10;
}
【在 D*********y 的大作中提到】
: 我在Amazon面的时候问过面试官
: palindrome指的是decimal还是binary
: 他说是binary
: 其实decimal方法也一样的
|
D*********y
发帖数: 876 | 6 b = b*10 + a%10 ?
【在 C***y 的大作中提到】
: binary的
: 用reverse比较好吧
: logN复杂度，N=bit数
: decimal的，
: a 原来的
: b reverse之后的
: int b = 0
: while(a){
: b = b*10 + a%10;
: a /= 10;
|
C***y
发帖数: 2546 | 7 谢谢更正
写快了，呵呵
【在 D*********y 的大作中提到】
: b = b*10 + a%10 ?
|
l*****a
发帖数: 14598 | 8 两种可能
32123
3223
你都cover了吗？
【在 D*********y 的大作中提到】
: 说说我的想法：
: 第一题我在A家面试的时候也遇到了
: 假设原来的数是num，定义a=num, b=0
: 每次取a&1也就是a的最右边一位，b=b<<1+(a&1)
: a = a>>1;
: 那么b就是num的inverse bit的结果
: return ( num-b==0 )
: 第二题我的想法是
: 从三个linked list的开头往后遍历
: 如果三个数相等，返回结果
|
e*****e
发帖数: 1275 | 9 她的方法是直接算出那个数的palindrome
而不是一个数位一个数位滴比较。。。所以你的special case 不需要考虑吧？
【在 l*****a 的大作中提到】
: 两种可能
: 32123
: 3223
: 你都cover了吗？
|
l*****a
发帖数: 14598 | 10 不好意思，没细看
但显然她的慢了一半。。
【在 e*****e 的大作中提到】
: 她的方法是直接算出那个数的palindrome
: 而不是一个数位一个数位滴比较。。。所以你的special case 不需要考虑吧？
|
s*****y
发帖数: 897 | 11 Why it is logN?
【在 C***y 的大作中提到】
: binary的
: 用reverse比较好吧
: logN复杂度，N=bit数
: decimal的，
: a 原来的
: b reverse之后的
: int b = 0
: while(a){
: b = b*10 + a%10;
: a /= 10;
|
C***y
发帖数: 2546 | 12 bit reverse
http://stackoverflow.com/questions/746171/best-algorithm-for-bi
om-msb-lsb-to-lsb-msb-in-c
【在 s*****y 的大作中提到】
: Why it is logN?
|
