一道Amazon intern面试题有感

austurela 发表于 2014-3-1 17:19
那lz怎么还这样呢 万一被发现了以后各公司不就不相信中国人的电面了？

准确说我不是替考，我是在旁边坐着，看着他来着~帮他搜搜资料什么的

sumingche 发表于 2014-3-2 06:22
准确说我不是替考，我是在旁边坐着，看着他来着~帮他搜搜资料什么的

I hope this could have been acceptable to Americans.

请问这题是给了一个Langford pairing 比如2,3,1,2,1,3，
然后让你求n＝3出现的位置吗？

还是给了n＝3，
你写算法生成一个Langford pairing？

vancexu 发表于 2014-3-2 17:36
请问这题是给了一个Langford pairing 比如2,3,1,2,1,3，
然后让你求n＝3出现的位置吗？

给你个n ，让你写出一个排列

北美农民 发表于 2014-3-1 08:47
这题完全acceptable嘛， amz想搞个高大上的名字唬人么。bitset也没啥， 自己弄一个a[n/32]的数组bit oper判 ...

想问一下，最后问什么要还原呢？就是最后两句话 bs.flip(i);  bs.flip(j); 小弟水平有限，希望兄弟不惜赐教
                                       

实在没看出这题有用bitset的必要啊。。

thanks for sharing

vancexu 发表于 2014-3-2 17:36
请问这题是给了一个Langford pairing 比如2,3,1,2,1,3，
然后让你求n＝3出现的位置吗？

恩恩，题目是这个意思哈~

cqx83 发表于 2014-3-29 16:23
实在没看出这题有用bitset的必要啊。。

恩恩，我觉得就普通的数组就OK，小弟有一点不明白，最后为什么要回归还原呢。就是最后两句话 bs.flip(i);  bs.flip(j)

anikin0617 发表于 2014-3-29 02:11
想问一下，最后问什么要还原呢？就是最后两句话 bs.flip(i);  bs.flip(j); 小弟水平有限，希望兄弟不惜赐 ...

Sry cannot type Chinese.

This is for going backward and recover bits if we did not find solution. I think this is also the essence of DFS: trying a possible solution, go deeper and if no solution then we go backward and try another possible solution.