l*********r
发帖数: 674 | 1 如果是沿着grid走的话，每一步奇偶性都会变一下。这样robot只要比enemy晚一步出门
就可以直接遍历所有room了。
不知道对面走允不允许，比如说enemy在(1,2)的时候robot start from (1,1）下一步
他们互换位置。
了. |
|
o******e
发帖数: 81 | 2
网站的用户访问日志，找出最popular的长度为3的访问序列
案好像很笨拙的样子。
比如
abcd
efgh
ijkl
输出：abcdhlkjiefg
我就是用最naive的每层4个loop的方法输出的。写完后我告诉interviewer code有bug
，对层数要分奇偶处理，他也不care，就问了test case就完了。 |
|
l*********r
发帖数: 674 | 3 面了个湾区的startup，没想到问了一堆brain teaser，分特阿.
都是经典题：
第一题是3个开关3个灯那个，
第二题是60mile的圈子，第一圈均速30，问第二圈多少才能均速60。
第三题是100盏灯，开始全灭，第一个人switch 1的倍数的灯，第二个人switch 2的倍
数，第3个人switch 3的倍数。。。第100个人switch 第100盏灯，问最后几盏亮的（就
是看约数的奇偶性）。
第四题，一杯牛奶一杯咖啡，牛奶舀一勺倒进咖啡，然后咖啡杯舀一勺倒进牛奶，问牛
奶里的咖啡多还是咖啡里的牛奶多（一样多）。
最后才问了个技术的：一个data storage file system，用什么数据结构比较好，容易
扩展，比如在存储不够的情况下，我都没太明白他说的什么意思，既然提到storage
data structure, 那就随便提一下B+ Tree，没想到他说就是等我说这个notion看我知
不知道，ft |
|
i******s
发帖数: 301 | 4 每个人根据自己看到前面所有人戴绿色帽子的奇偶来报。比如如果有奇数个绿帽，就报
红色；偶数就报绿色。
一开始，最后一个人如果报绿色，表示剩下n-1个人中有偶数个绿帽，所以当轮到倒数
第二个人时，如果他看到前面只有奇数个绿帽，那么他知道他自己戴的是绿帽，反之，
他戴的是红帽。倒数第三个人听到倒数第二个答案时，可以知道所剩绿帽总数是奇是偶
，可以根据之前的判断方法来推断出自己的帽子颜色。
所以这种方法至少能让n-1个人活下来，第一个报的看RP. |
|
a*********0
发帖数: 2727 | 5 来自主题: JobHunting版 - 一道G家题 我发现序列奇偶个数要分开考虑？
比如
1 2 3 5 6《-----A[mid]是3， value-mid=(1+6)/2=3, A[mid]==value-mid, 向右找
1 3 4 5 《-----A[mid]是3， value-mid=(1+5)/2=3, A[mid]==value-mid, 却向左找
这题太恶心啦
in |
|
a********m
发帖数: 15480 | 6 来自主题: JobHunting版 - 一道G家题 折半找是不是缺数就可以了。不管个数奇偶。 |
|
w******g
发帖数: 313 | 7 随到1，2，3，4就看奇偶，随到5重新扔，这样概率是1/2.三个一组就生成1/8的概率发
生器。
！！ |
|
d*******d
发帖数: 2050 | 8 这个问题要考虑分治后每个subproblem的奇偶问题.
你自己再研究研究,不行我再贴code |
|
r*******g
发帖数: 1335 | 9 这种题现场做很难做到bugfree啊，知道思路了就是这个奇偶问题都要把人弄死。。。 |
|
f*******t
发帖数: 7549 | 10 我还专门研究过，程序运行是以下步骤：
start: a b c 1 2 3
swap: a b 1 c 2 3
shift first half: [a b 1] c 2 3 -> a 1 b c 2 3
shift second half: a 1 [b c 2 3] -> a 1 b 2 c 3
done
dino这程序太牛了，完美解决奇偶性的问题 |
|
|
g**********y
发帖数: 14569 | 12 第四题是说只交换1，2，而其它不变。那个用奇偶性可以证明，应该是不可能。 |
|
|
c***p
发帖数: 221 | 14 如果 (s-x)%2 ＝＝ 1，继续走， 即i++；直到超过x, 而且走过的距离s 与x 同奇偶。 |
|
|
w****x
发帖数: 2483 | 16
溢出那题是不是可以把传入的unsigned int 转成double, 然后两个double相加, 然后
和UNSIGNED_INT_MAX比较
或者通过除2并判断奇偶得情况绕弯来做 |
|
k*******r
发帖数: 355 | 17 求两个sorted array合并后的median这题，我知道网上有答案可以在log(min(m,n))时间复杂度内做完，就是不断比较两个array各自的中位数缩小范围，但具体写代码也太琐碎了吧。
主要是数组元素为奇数和偶数时，中位数定义不同，对一短一长两个数组，就得分别考虑奇奇，奇偶，偶奇，偶偶4种情况，每种里面比较中位数大小又是3种可能....
有没有比较clean的代码，在30行代码左右能搞定这题的。（我觉得太长的代码，白板也很难写对阿） |
|
|
t****t
发帖数: 6806 | 19 这个解法写得这么复杂是为了数1的个数用的(就近相加-->无进位干扰). 数奇偶的话直
接折半就可以了, 比这个快一点点. |
|
r*****e
发帖数: 792 | 20 cup150里面有这道题啊，就是D&C的思想，虽然那个答案看起来
有点不太对劲。我是觉得奇偶的情况好像没有考虑，code自己没写，
觉得太麻烦。做好投降的准备了，呵呵。 |
|
r*****e
发帖数: 792 | 21 其实奇偶是一个意思，不用分开考虑。
第一次反转是半个现在partition的长度，
第二次就是前面不动部分的长度，
第三次就是后面不动部分的长度。
终于写了一下这个的code，算是nlogn的解法搞定了。 |
|
r*****e
发帖数: 792 | 22 前一段讨论过啊，nlogn的算法不算太难，不用考虑奇偶。 |
|
K*****n
发帖数: 65 | 23 1)设计hang-man游戏。（跟非死不可对过去的那家）
要考虑扩展性。
2）类似vector >, 写hasnext(), getnext(),handle size=0
3) 把黑名单从总部服务器可靠地发送到全球各地的服务器；
4）有正负数的数组，找最大连续和；
然后找最大连续乘积（考虑：零，负数的个数是奇偶的情况）
电面是写句子单词翻转。 |
|
z*****o
发帖数: 37 | 24 6. Count the Ones of an integer;
9. Even parity function;
这两个好像属于一个题吧？
为什么会问这两个呢？
计算出1的个数，然后 %2 除以2 取余数 不就 知道 奇偶了吗？
另， 是不是我理解错了？Even parity function; 不是计算 1的个数问题吗？？？？
谢谢 |
|
l*****a
发帖数: 14598 | 25 这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分 |
|
l*****a
发帖数: 14598 | 26 这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分 |
|
w********s
发帖数: 1570 | 27 第一题还可以用来测试奇偶吧
n & (n - 1) == n - 1
n & (n - 1) == n - 2
-1 |
|
y****n
发帖数: 743 | 28 O(n), 不知道有没有bug。
头尾两个index，头部发现偶数就与尾部发现奇数对换。直到头尾的index接触。
此时，奇偶的顺序已经调整完毕，需要恢复原来数据顺序。
从发现第一个偶数的位置与碰触点之间的数据反转。
从碰触点到尾部最后一个奇数位置之间的数据反转。
至此，原数据顺序恢复完毕。
public static void Swap(int[] arr, int index1, int index2)
{
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static int[] SortOddEven(int[] arr)
{
int indexOdd = 0;
int indexEven = arr.Length - 1;
int firstEven = 0;
while ((firstEven < arr.Length)&&(arr[firstEven] % 2 == 1))
firstEven ++;
int lastOdd = arr.Length - 1;
w... 阅读全帖 |
|
Y**Y
发帖数: 66 | 29 回错主题了，有另外一贴double link list奇偶排序的。原帖删了。
数组的这个想出了一个nlogn的in place方法
1. 每两个数一组，每组内变成odd/even order，最后一组可以小一些。
2. Repeat: 上次的每两组合并, 前组后面的even numbers和后组前面的odd numbers换
位。直到合成一组。
Complexity: O(2)*n/2+O(4)*n/4+ ...+ O(n) = nlogn
长度不同的组换位：
For example, swap {1...m} with {m+1 ... n} assuming m>n.
swap {1 ... n} with {m+1 ... m+n},
then the problem is reduced to swap {n+1 ...m} and {m+1...m+n}
Complexity: f(m+n) = O(n)+f(m) = O(m+n) |
|
d**********x
发帖数: 4083 | 30 正数大于等于1的都乘起来，负数小于等于-1的乘起来，视奇偶性drop掉最大的那个呗
当然还要考虑下各种边界情况 |
|
g*******s
发帖数: 2963 | 31 function signature已经定义好的不算额外。 比如楼上说的奇偶分布是符合条件的，
不过不能解决两个str长度不一样的情况。 |
|
b****g
发帖数: 192 | 32 第一题是求a^b乘方吗？
因为有bar(a, b / 2) * bar(a, b / 2)存在，所以复杂度不是O(lgb)。其实就是O(b)
吧？
所以回答第三问时，这就是要改进的地方，return bar(a, b / 2)的平方
还可以再加几个特殊情况，比如：
if(a!=0 && b==0) return 1;（原来的未考虑a==0）
if(a==0 && b!=0) return 0;
还可以考虑溢出：
int tmp = bar(a,b/2);
if(tmp > INT_MAX/tmp) //overflow
也可以用long long记录所有中间结果改进。
最重要的是没考虑负数吧？
if(b<0) return 1/bar(a,b);
if(a<0 && b>0) 看b是奇偶在return正负bar(a,b) |
|
n*******1
发帖数: 145 | 33 来自主题: JobHunting版 - G新鲜面经 1.2 奇偶区分有几个高点 然后从高到低填满高点 剩下的点全排列即可 奇数点的时候
注意特殊情况 （最大值是最后一个高点 第二大值可以不在高点而在数组最后） 无需
暴力解法 |
|
c*******0
发帖数: 2 | 34 有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。 |
|
c*******0
发帖数: 2 | 35 有一个暴力的方法 不知道对不对？
根据输入构造两张图： 朋友图 和 敌人图 两张图 每条边的值都是1.
对于每一个查询(a, b)，相当于分别对朋友图 和 敌人图 做BFS。
具体就是，
如果能在朋友图中，从a遍历到b那就是朋友关系。
否则，遍历敌人图。遍历的敌人图的时候区分一下距离的奇偶，如果是偶数距离找到了
b那就是朋友，如果在奇数距离找到了b那就什么关系也不是吧？（敌人的朋友 和 朋友
的敌人 好像没什么关系吧）
否则，a和b没关系。
时间应该是N 空间也是N
菜B拍脑门想出来的 没怎么细琢磨 还请大牛指点。 |
|
x****g
发帖数: 1512 | 36 没问题.
本题的关键就是从后往前看到第一个0开始的点是个断点.
无论那个0开头自己解释自己还是跟它前面的那个走,(不可能跟后面走)
都不影响0开头的后面的那个是个起始字节这个结论.
所以就变成了奇偶问题了. |
|
p********n
发帖数: 165 | 37 先排序就得nlogn
然后再比较奇偶 n
所以总体还是O(nlogn) |
|
l*********b
发帖数: 65 | 38 其实不用奇偶吧 只要两两比较数字 把不满足要求的 和下一个数字对调 就好啦。
比如 7,8 。7的位置应该是大数， 但是它又比8小 所以就和8调换 这样变成 8,7。 就
一定满足啦 因为8肯定是因为比7大才被调换的 所以一定也比7前面的数字大。
说得不太清楚 试一下就好啦。 |
|
c*****o
发帖数: 1702 | 39 硬来一项项加应该能解。就只能n分奇偶，然后一项一项算。
N odd, only break at least (N+1)/2 will have a chance to get all the key for
rest of the box. The first term will be (N+1)/2 / CN (N+1)/2
N even, at least N/2, the first term will be 1/CN N/2 |
|
y*****e
发帖数: 712 | 40 谢谢lz分享，祝拿到onsite。
第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
overflow的话因为return type是double, 还需要特别考虑吗？
第二题多线程怎么答呢？用synchronized行吗？ |
|
w*****1
发帖数: 6807 | 41 多谢，已经google过了，确实要再check一下奇偶就可以了 |
|
l****c
发帖数: 782 | 42 二楼的是正解啊，DFS＋cut branch和BFS都可以，但是BFS可以省空间。
不知道bottom up 的DP转移方程怎么写，要注意奇偶性？ |
|
c*****n
发帖数: 83 | 43 第一次接触这种题目，觉得很有意思。
本质是 2^i 次的分解, 即将 n = n1 + n2 s.t. |n1 - n2| == 0, or 1.
e.g 4 = 2 + 2, 5 = 3 + 2, 6 = 3 + 3, 7 = 4 + 3 = (2 + 2) + 3.
前面已经给出 n = 2, 3 时的解法。以此作用基础，按上述分解即可推出任意 n > 3
的解法。感觉这样的解法应该可以以数学归纳法来推证为最优的。有兴趣的朋友可以证
明一下。
以 n = 5 为例来说明我的解法。五个位置记作 {A, B, C, D, E}. n = 5 = 3 + 2 即
是按 %2 = 0 or 1 分成两个子集 {A,C,E} and {B, D}. 可以分别检验子集 (注意子集
的检验次序是先小后大)。
对于子集 {B, D}，是 n = 2 的情况，按照 n = 2 集合为 {A',B'}时的解法是 (B',B'
). 第一步 Map to "n = 5" 的位置是 "D". 若没有找到，到了第二步要注意了，原来
在 {B, D} 的，已经转移到 {A, C, E}, 但是当 第一步 "D... 阅读全帖 |
|
D*****r
发帖数: 133 | 44 有硬件背景， 和一些系统底层开发的经历， 可能和一般的纯软件面试有点不太一样。
Recruiter说要找背景相近的人面试。没有碰到印度人面试官
1。 面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
2。 算数据流最近N个数的平均值。 接着分别讨论整型溢出的情况和浮点数精度丢失的
问题。
3。 实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
4。 A） 写函数实现32位数的位异或操作 （算奇偶校验位）
B） 模拟普通电梯的运行，实现一个电梯控制器
5。 有一个分布式系统，提供一个返回64位数的服务。有两个要求： 1。所返回的数是
唯一的。 2。所返回的是一个近似递增序列。如何实现使得要求1必须满足，要求2不严
格要求，但越接近越好。同时对用户的响应延迟要越短越好。 |
|
k******n
发帖数: 184 | 45
要把数字和符号的逻辑隔离开， 你这样会让代码很麻烦， 尤其遇到了多个减号还要判
断奇偶。 当然我不确定你会怎么实现， 我的直觉是如此。 |
|
发帖数: 1 | 46 这个不要merge吧。分成奇偶两个loop就没dependency了：
for(int i = 0; i < nums.length-1; i+=2)
if(nums[i] > nums[i+1])
//swap nums[i] and nums[i+1]
for(int i = 1; i < nums.length-1; i+=2)
if(nums[i] < nums[i+1])
//swap nums[i] and nums[i+1] |
|
h******k
发帖数: 810 | 47 另外，存二进制，奇偶/加减一/除二/整除四的运算都很简单。 |
|
|
G******e
发帖数: 9567 | 49 【 以下文字转载自 Joke 讨论区 】
发信人: xtxtxttchris (chris), 信区: Joke
标 题: 上海知名小学入学标准~哈南```可能工作后的你都不懂
发信站: BBS 未名空间站 (Mon Jun 6 12:12:45 2011, 美东)
语文：
56个汉语拼音中掌握47个;
800-1000个识字量，会诵读，读报，古诗词(光背没用，老师随便点一个字要读得出)。
数学：
20以内完形填空加减法，如：2+?+9=20;可以是应用题，如：教室里一共30个孩子，出
去10个，又来16个，现在还有几个
数字瞬间记忆，比如一下子读十几个数字，看你记住几个。
英语：
52个字母(因为26个大小写嘛);
认知200个常用单词(1星标准);
看图片或单词读单词;
50个常用句型，如一般和特殊疑问句;
1分钟英语自我介绍(语速80/min，赶上VOA special速度啦)，并允许拓展提问，如Why
、How等。
上海重点小学入学面试题
1、一组数字，找出其中规律，并填写完整：1 2 3 4 6()12
2、一组小朋友玩老鹰捉小鸡，有一位扮演老鹰，一位做母鸡，还有8个做小... 阅读全帖 |
|
s******m
发帖数: 2310 | 50 don't understand what's the school there for if kids know all this before
they start schooling.
【 以下文字转载自 Joke 讨论区 】
发信人: xtxtxttchris (chris), 信区: Joke
标 题: 上海知名小学入学标准~哈南```可能工作后的你都不懂
发信站: BBS 未名空间站 (Mon Jun 6 12:12:45 2011, 美东)
语文：
56个汉语拼音中掌握47个;
800-1000个识字量，会诵读，读报，古诗词(光背没用，老师随便点一个字要读得出)。
数学：
20以内完形填空加减法，如：2+?+9=20;可以是应用题，如：教室里一共30个孩子，出
去10个，又来16个，现在还有几个
数字瞬间记忆，比如一下子读十几个数字，看你记住几个。
英语：
52个字母(因为26个大小写嘛);
认知200个常用单词(1星标准);
看图片或单词读单词;
50个常用句型，如一般和特殊疑问句;
1分钟英语自我介绍(语速80/min，赶上VOA special速度啦)，并允许... 阅读全帖 |
|
