a********a
发帖数: 219 | 1 还愿谢恩。回答一周问题，算法，design，都算。不保证答对，不保证回答。但是肯定
会详细解释为什么。以及思路。想问的把问题贴此贴上即可。 |
H*M
发帖数: 1268 | 2 你在哪个公司上班? 可否帮版友们推荐?
【在 a********a 的大作中提到】
: 还愿谢恩。回答一周问题，算法，design，都算。不保证答对，不保证回答。但是肯定
: 会详细解释为什么。以及思路。想问的把问题贴此贴上即可。
|
a********a
发帖数: 219 | 3 第一个问题和算法无关。。。。第二个我没有机会推荐别人。
【在 H*M 的大作中提到】
: 你在哪个公司上班? 可否帮版友们推荐?
|
g*****u
发帖数: 298 | 4 楼主讲一下这个题吧
一个停车场有n个位子，停了n-1辆车，这n-1辆车要从一开始的排列次序变成要求的顺
序，只能用多余的那个位子。 |
m******9
发帖数: 968 | 5 我有2个题目：
一个是关于traffic light的design，这个题目出现过了好多次了，不过每个人的答案
可能不太一样，楼主你是怎么回答的？谢谢 |
a********a
发帖数: 219 | 6 这个题本质上是mapping问题，就是source->target mapping
解决maping，需要从两个方向入手，一个是source->target,一个是target->source
我们先看target->source, input:120354, empty space:0, target012345
如果从target入手，我们需要找到空位所需要的车，也就是2,
102354，然后继续
012354
然后发现0已经在0了，这意味着有seperate cycle,需要打破cycle,
512304
512340
012345
因为source的定位必须要iterate,也就是o(n)复杂度，总共n^2，显然不能接受。
所以要考虑source->target
对于任何一辆车，他的目标位置可以random access到。也就是o(1),另外我们发现一辆
车一旦进
入他的目标位置，再没有任何理由把它挪开，所以我们的算法可以是从头往后遍历，一
旦发现一辆车
不在他该在的位置，就调整到他的target，这个复杂度是o(1),总体是o(n)，可以接受。
以上面为例：
120354
【在 g*****u 的大作中提到】
: 楼主讲一下这个题吧
: 一个停车场有n个位子，停了n-1辆车，这n-1辆车要从一开始的排列次序变成要求的顺
: 序，只能用多余的那个位子。
|
b******g
发帖数: 1721 | 7 nice. thanks.
【在 a********a 的大作中提到】
: 这个题本质上是mapping问题，就是source->target mapping
: 解决maping，需要从两个方向入手，一个是source->target,一个是target->source
: 我们先看target->source, input:120354, empty space:0, target012345
: 如果从target入手，我们需要找到空位所需要的车，也就是2,
: 102354，然后继续
: 012354
: 然后发现0已经在0了，这意味着有seperate cycle,需要打破cycle,
: 512304
: 512340
: 012345
|
b******g
发帖数: 1721 | 8 问问题：
Write a program to find depth of binary search tree without using recursion?
多谢。 |
r****o
发帖数: 1950 | 9 我想问道经典的题，虽然这个版上可能讨论过了，但是我还是没弄太明白。
有一个array全部由正整数构成，元素个数为2n，如何将其分成2个subarray(元素各n个
)，使得subarray的元素和最接近。
多谢先。
【在 a********a 的大作中提到】
: 还愿谢恩。回答一周问题，算法，design，都算。不保证答对，不保证回答。但是肯定
: 会详细解释为什么。以及思路。想问的把问题贴此贴上即可。
|
s*****i
发帖数: 355 | 10 你这第二种是o(n)？
【在 a********a 的大作中提到】
: 这个题本质上是mapping问题，就是source->target mapping
: 解决maping，需要从两个方向入手，一个是source->target,一个是target->source
: 我们先看target->source, input:120354, empty space:0, target012345
: 如果从target入手，我们需要找到空位所需要的车，也就是2,
: 102354，然后继续
: 012354
: 然后发现0已经在0了，这意味着有seperate cycle,需要打破cycle,
: 512304
: 512340
: 012345
|
|
|
s*****i
发帖数: 355 | 11 wiki DFS
recursion?
【在 b******g 的大作中提到】
: 问问题：
: Write a program to find depth of binary search tree without using recursion?
: 多谢。
|
s*****i
发帖数: 355 | 12 sort the integer array. then use greedy algorithm, starting from the largest
number. o(n)
【在 r****o 的大作中提到】
: 我想问道经典的题，虽然这个版上可能讨论过了，但是我还是没弄太明白。
: 有一个array全部由正整数构成，元素个数为2n，如何将其分成2个subarray(元素各n个
: )，使得subarray的元素和最接近。
: 多谢先。
|
g*******y
发帖数: 1930 | 13 greedy doesn't work
in fact, this one is NPC
largest
【在 s*****i 的大作中提到】
: sort the integer array. then use greedy algorithm, starting from the largest
: number. o(n)
|
p****o
发帖数: 46 | 14 不明白，这第二部分ｓｏｕｒｃｅ ｔｏ ｔａｒｇｅｔ怎么做的，为什么
是O(n).假设ｓｏｕｒｃｅ 是５４３２１０，
【在 a********a 的大作中提到】
: 这个题本质上是mapping问题，就是source->target mapping
: 解决maping，需要从两个方向入手，一个是source->target,一个是target->source
: 我们先看target->source, input:120354, empty space:0, target012345
: 如果从target入手，我们需要找到空位所需要的车，也就是2,
: 102354，然后继续
: 012354
: 然后发现0已经在0了，这意味着有seperate cycle,需要打破cycle,
: 512304
: 512340
: 012345
|
b******g
发帖数: 1721 | 15 DFS 还是recursion啊。
【在 s*****i 的大作中提到】
: wiki DFS
:
: recursion?
|
a********a
发帖数: 219 | 16 大家的问题已经偏离我的本意了。我想的是有一些问题网上不常见的，大家找不到合适
答案的，我可以来解答一下，不管对错，至少给人一些思路。但是大家来问的都是网上
的常见题，google就可以轻松找到无数答案，这样就没有什么意义了。我不认为我会比
那些人答的更好。
【在 m******9 的大作中提到】
: 我有2个题目：
: 一个是关于traffic light的design，这个题目出现过了好多次了，不过每个人的答案
: 可能不太一样，楼主你是怎么回答的？谢谢
|
a********a
发帖数: 219 | 17 你既然说已经有人讨论过了，那问我还有什么意义呢？
任何bi-partition/sub-set都是NPC问题。但是NPC并不一定很难解，受到其他限制，
NPC很容易转化成polinomial问题。这个题的关键是sum.我们需要找到的是所有可能的
子集总和，然后就可以找到最小difference。显然是一个dp题。
解dp题，第一就是状态定义：
状态： bool state[pos][number][sum];
这个状态的第一位指的是在前面pos个元素的集合里。
第二位指的是选择多少个元素，在前面pos个里面。
第三位指的是这些元素的和的可能性。
结果指的是是否这个组合可以达到。
初始值是false, state[0][0][0] = true;
递推公式是state[pos][number][sum] = state[pos - 1][number][sum] | state[pos
- 1][number - 1][sum - source[pos - 1]];
寻找结果是
int sum = accumulate(source.begin(), source.end(), 0);
【在 r****o 的大作中提到】
: 我想问道经典的题，虽然这个版上可能讨论过了，但是我还是没弄太明白。
: 有一个array全部由正整数构成，元素个数为2n，如何将其分成2个subarray(元素各n个
: )，使得subarray的元素和最接近。
: 多谢先。
|
s*****r
发帖数: 773 | 18 请麻烦一并讲讲elevator system 和file system的设计的主要point
【在 a********a 的大作中提到】
: 还愿谢恩。回答一周问题，算法，design，都算。不保证答对，不保证回答。但是肯定
: 会详细解释为什么。以及思路。想问的把问题贴此贴上即可。
|
a********a
发帖数: 219 | 19 前面说了，这些都是经典题，网上随便一搜答案都大把，我怎么可能答的比别人好。。
。。
【在 s*****r 的大作中提到】
: 请麻烦一并讲讲elevator system 和file system的设计的主要point
|
s*****i
发帖数: 355 | 20 you are right. it's not the optimal solution. this is np
【在 g*******y 的大作中提到】
: greedy doesn't work
: in fact, this one is NPC
:
: largest
|
