c**y
发帖数: 172 | 1 1.写一个enque和deque是multi-thread safe
2.复制一个link list。每一个元素有val和两个指针next和random，next是指向下一个
,random是指向任何可能的元素（有可能是当前元素本身，形成一个loop）
3.m个集合，从每一个集合取出一个元素，组成一个数组a，其中a[i](i = 0,...,m-1)
来自集合i。求所有可能a的总数。已知每个集合内部没有重复元素。不同集合可以有重
复，比如数值10可以出现在集合0和集合m-1，但是不影响结果。
例如m=2。集合0={0,1}集合1={0,2}，然后a有4中可能的组合{0,0}，{0,2}，{1,0}，{1
,2}。 | x*********w
发帖数: 533 | 2
{1
看到第二题我就吐了
【在 c**y 的大作中提到】
: 1.写一个enque和deque是multi-thread safe
: 2.复制一个link list。每一个元素有val和两个指针next和random，next是指向下一个
: ,random是指向任何可能的元素（有可能是当前元素本身，形成一个loop）
: 3.m个集合，从每一个集合取出一个元素，组成一个数组a，其中a[i](i = 0,...,m-1)
: 来自集合i。求所有可能a的总数。已知每个集合内部没有重复元素。不同集合可以有重
: 复，比如数值10可以出现在集合0和集合m-1，但是不影响结果。
: 例如m=2。集合0={0,1}集合1={0,2}，然后a有4中可能的组合{0,0}，{0,2}，{1,0}，{1
: ,2}。
| A***o
发帖数: 358 | 3 因为经典？
【在 x*********w 的大作中提到】
:
: {1
: 看到第二题我就吐了
| A***o
发帖数: 358 | 4 第一个要求lock free 吗？
{1
【在 c**y 的大作中提到】
: 1.写一个enque和deque是multi-thread safe
: 2.复制一个link list。每一个元素有val和两个指针next和random，next是指向下一个
: ,random是指向任何可能的元素（有可能是当前元素本身，形成一个loop）
: 3.m个集合，从每一个集合取出一个元素，组成一个数组a，其中a[i](i = 0,...,m-1)
: 来自集合i。求所有可能a的总数。已知每个集合内部没有重复元素。不同集合可以有重
: 复，比如数值10可以出现在集合0和集合m-1，但是不影响结果。
: 例如m=2。集合0={0,1}集合1={0,2}，然后a有4中可能的组合{0,0}，{0,2}，{1,0}，{1
: ,2}。
| s*****r
发帖数: 43070 | 5 lookup table，由老node找新node
【在 x*********w 的大作中提到】
:
: {1
: 看到第二题我就吐了
| g*******s
发帖数: 2963 | 6 我心中的痛啊。。。。不会又是google吧？
【在 x*********w 的大作中提到】
:
: {1
: 看到第二题我就吐了
| c**y
发帖数: 172 | | l**f
发帖数: 14 | 8 3有什么好的办法去掉重复的结果？比如集合0={0,1,2}集合1={0,2,3}，只留一个{0,2}
传hash进递归函数? | c**y
发帖数: 172 | 9 不用担心重复的结果。介绍问题的时候就担心这个说的不清楚。就你给的集合，返回结
果是
{0,0}，{0,2}，{0,3}，{1,0}，{1,2}，{1,3}，{2,0}，{2,2}，{2,3}。因为位置信息
是有意义的，所以{0,2}和{2,0}不同。（如果实在需要去掉，可以每个组合sort一下，
然后比较，但是在这里是不需要的）。
2}
【在 l**f 的大作中提到】
: 3有什么好的办法去掉重复的结果？比如集合0={0,1,2}集合1={0,2,3}，只留一个{0,2}
: 传hash进递归函数?
| c**y
发帖数: 172 | 10 第3题想到直观的解法是：每一个组合等价一个数组w，里面有m个元素。其中w[i]（i=0
,1,...m-1)是在集合i中相应元素的索引index。这样只要对于每个集合i，把其中所有
元素都输出一次，就输出了所有结果。下面是pseudo code。
let denote the original m sets by vector > sets.
vector getCombination(vector > &sets, int set_idx, vector
curr_comb)
{
for (int i = 0; i < sets[set_idx].size(); i++) {
vector ret_comb;
ret_comb = curr_comb;
ret_comb.push_back(sets[set_idx][j]);
if (set_idx == 0) {
// process the final combination here
return ret_comb;
} else {
return getCombination(sets, set_idx - 1, ret_comb);
}
}
}
// in caller function
vector v;
getCombination(sets, m - 1, v); |
|
