r********t
发帖数: 395 | 1 通常一个人会在黑名单里呆多久？具体每个公司的时间有小道消息吗？ |
a********1
发帖数: 750 | 2 微软大概是1年
【在 r********t 的大作中提到】
: 通常一个人会在黑名单里呆多久？具体每个公司的时间有小道消息吗？
|
g*******y
发帖数: 1930 | 3 应该没有这么长吧，我认识有人春季的on campus没面上，秋季再次on campus最后拿到
offer的
【在 a********1 的大作中提到】
: 微软大概是1年
|
a****n
发帖数: 1887 | 4 MS校园招聘是一年， 我去年被拒了， 据信里是这么写的
不过有人推荐的话， 估计可以不用管这个
社招的话， 没有记录， 也不会有时间限制
顺便说一下上次onsite的题目
1. Sudoku, 给你9x9的 sudoku的一个问题， 求他的解
这道题挂了， 说我优化不够
2. 判断一个BST 是否valid
还有一道题， 把一个number array 分成 N 份， 求最平均的方案， 不可以打乱数组顺序
例如[3, 5, 6, 2, 7, 9] 分成3份[3，5，6] [2，7] [9]
还有随机算法 |
g*******y
发帖数: 1930 | 5 我认识的人校园面试第一次是intern，第二次是full time，不知道跟这个有没有关系
，不过确实是春季那次没有拿到onsite，秋季那次拿到offer了。
sudoku那个面试写出来有些难度啊！我以前写过一个4×4的，感觉写起来挺复杂的。
【在 a****n 的大作中提到】
: MS校园招聘是一年， 我去年被拒了， 据信里是这么写的
: 不过有人推荐的话， 估计可以不用管这个
: 社招的话， 没有记录， 也不会有时间限制
: 顺便说一下上次onsite的题目
: 1. Sudoku, 给你9x9的 sudoku的一个问题， 求他的解
: 这道题挂了， 说我优化不够
: 2. 判断一个BST 是否valid
:
: 还有一道题， 把一个number array 分成 N 份， 求最平均的方案， 不可以打乱数组顺序
: 例如[3, 5, 6, 2, 7, 9] 分成3份[3，5，6] [2，7] [9]
|
a****n
发帖数: 1887 | 6 我当时写的就是最简单的DFS，加上3*9个数组判断状态
当时有两个问题我没有考虑清楚，一个是用位操作优化，用3*9个int代替3*9个数组， 第二
个是DFS的顺序
这个是我后来做的, DFS的顺序还是没有考虑（也是POJ的原题）
http://www.cnblogs.com/asuran/archive/2009/10/11/1580878.html
【在 g*******y 的大作中提到】
: 我认识的人校园面试第一次是intern，第二次是full time，不知道跟这个有没有关系
: ，不过确实是春季那次没有拿到onsite，秋季那次拿到offer了。
: sudoku那个面试写出来有些难度啊！我以前写过一个4×4的，感觉写起来挺复杂的。
|
g*******y
发帖数: 1930 | 7 看了下你的blog，好强啊！
， 第二
【在 a****n 的大作中提到】
: 我当时写的就是最简单的DFS，加上3*9个数组判断状态
: 当时有两个问题我没有考虑清楚，一个是用位操作优化，用3*9个int代替3*9个数组， 第二
: 个是DFS的顺序
: 这个是我后来做的, DFS的顺序还是没有考虑（也是POJ的原题）
: http://www.cnblogs.com/asuran/archive/2009/10/11/1580878.html
|
w********p
发帖数: 948 | 8 blog 很强，收藏。
咱以后也考虑写学习笔记贴在blog上。
， 第二
【在 a****n 的大作中提到】
: 我当时写的就是最简单的DFS，加上3*9个数组判断状态
: 当时有两个问题我没有考虑清楚，一个是用位操作优化，用3*9个int代替3*9个数组， 第二
: 个是DFS的顺序
: 这个是我后来做的, DFS的顺序还是没有考虑（也是POJ的原题）
: http://www.cnblogs.com/asuran/archive/2009/10/11/1580878.html
|
a********a
发帖数: 219 | 9 不是一般的强，简直太强了。我见过的人都没有这么强大的。我觉得这个水平去谷歌也
应该是没有问题
吧？如果这样的人都去不了，那只能说明谷歌不招人了。
【在 w********p 的大作中提到】
: blog 很强，收藏。
: 咱以后也考虑写学习笔记贴在blog上。
:
: ， 第二
|
d*********e
发帖数: 3835 | 10 what is this black list? |
|
|
k*k
发帖数: 49 | 11 还有一道题， 把一个number array 分成 N 份， 求最平均的方案， 不可以打乱数组
顺序
例如[3, 5, 6, 2, 7, 9] 分成3份[3，5，6] [2，7] [9] |
m*****f
发帖数: 1243 | 12 请问考虑DFS的顺序是不是就是记录下每个0空的avl状态， 总是从可选最少的0空开始
DFS?
， 第二
【在 a****n 的大作中提到】
: 我当时写的就是最简单的DFS，加上3*9个数组判断状态
: 当时有两个问题我没有考虑清楚，一个是用位操作优化，用3*9个int代替3*9个数组， 第二
: 个是DFS的顺序
: 这个是我后来做的, DFS的顺序还是没有考虑（也是POJ的原题）
: http://www.cnblogs.com/asuran/archive/2009/10/11/1580878.html
|
a****n
发帖数: 1887 | 13 本人水平一般，大多数题是看了题解之后才做出来的
【在 g*******y 的大作中提到】
: 看了下你的blog，好强啊！
:
: ， 第二
|
a****n
发帖数: 1887 | 14 是
【在 m*****f 的大作中提到】
: 请问考虑DFS的顺序是不是就是记录下每个0空的avl状态， 总是从可选最少的0空开始
: DFS?
:
: ， 第二
|
k***e
发帖数: 556 | 15 对array切分的那道题，感觉条件不是很全。
因为衡量k个数之间的距离，可以用max-min,也可以用Variance,结果是不一样的
此外，请问有比n^k更好的解法吗？（n^k也就是brutal force了）
组顺序
【在 a****n 的大作中提到】
: MS校园招聘是一年， 我去年被拒了， 据信里是这么写的
: 不过有人推荐的话， 估计可以不用管这个
: 社招的话， 没有记录， 也不会有时间限制
: 顺便说一下上次onsite的题目
: 1. Sudoku, 给你9x9的 sudoku的一个问题， 求他的解
: 这道题挂了， 说我优化不够
: 2. 判断一个BST 是否valid
:
: 还有一道题， 把一个number array 分成 N 份， 求最平均的方案， 不可以打乱数组顺序
: 例如[3, 5, 6, 2, 7, 9] 分成3份[3，5，6] [2，7] [9]
|
a****n
发帖数: 1887 | 16 原题是求分成N组后， 每组和记为Si, 求 Max(Si)最小的分法， 我的理解就是最平均。
【在 k***e 的大作中提到】
: 对array切分的那道题，感觉条件不是很全。
: 因为衡量k个数之间的距离，可以用max-min,也可以用Variance,结果是不一样的
: 此外，请问有比n^k更好的解法吗？（n^k也就是brutal force了）
:
: 组顺序
|
s*****r
发帖数: 773 | 17 请问原题哪儿可以看到
【在 a****n 的大作中提到】
: 本人水平一般，大多数题是看了题解之后才做出来的
|
k***e
发帖数: 556 | 18 你说的这个条件是minmax, 还可以maxmin，结果是不一样的
感觉你运气很差 ：）
均。
【在 a****n 的大作中提到】
: 原题是求分成N组后， 每组和记为Si, 求 Max(Si)最小的分法， 我的理解就是最平均。
|
a****n
发帖数: 1887 | |
a****n
发帖数: 1887 | 20 不好意思， 我没解释清楚， 原题应该是min max吧
【在 k***e 的大作中提到】
: 你说的这个条件是minmax, 还可以maxmin，结果是不一样的
: 感觉你运气很差 ：）
:
: 均。
|
|
|
b**********7
发帖数: 103 | 21 太不一般了! 平时都隐身的，看到这么牛的博客，一定要上来re一下。:>
多谢了!
【在 a****n 的大作中提到】
: 本人水平一般，大多数题是看了题解之后才做出来的
|
k***e
发帖数: 556 | 22 我提一个算法，用greedy algorithm for the min-max condition
1. make a guess of the max segment length for dividing a[i:j] into x
sections. suppose it is y, i.e, we want to answer the following question:
Q: is it possible to divide a[i:j] into x sessions with each session <= y?
To answer the question, we will use greedy algorithm. find the maximal j_0
such that: sum_{s=j}^{j_0} a[s] <= y then
f(a,i,j,y,x) = f(a,j_0+1,j,y,x-1)
Thus, we can answer Q in time n for each specific x.
2. note that: max{a[i]} <=
【在 a****n 的大作中提到】
: 原题是求分成N组后， 每组和记为Si, 求 Max(Si)最小的分法， 我的理解就是最平均。
|
a********1
发帖数: 750 | 23 onsite来算的
【在 g*******y 的大作中提到】
: 应该没有这么长吧，我认识有人春季的on campus没面上，秋季再次on campus最后拿到
: offer的
|
k*k
发帖数: 49 | 24 如果 most evenly partitioned means the smallest possible variance among sums
of partitions, 这题有 efficient 算法吗？
谢谢。
【在 k***e 的大作中提到】
: 我提一个算法，用greedy algorithm for the min-max condition
: 1. make a guess of the max segment length for dividing a[i:j] into x
: sections. suppose it is y, i.e, we want to answer the following question:
: Q: is it possible to divide a[i:j] into x sessions with each session <= y?
: To answer the question, we will use greedy algorithm. find the maximal j_0
: such that: sum_{s=j}^{j_0} a[s] <= y then
: f(a,i,j,y,x) = f(a,j_0+1,j,y,x-1)
: Thus, we can answer Q in time n for each specific x.
: 2. note that: max{a[i]} <=
|
a****n
发帖数: 1887 | 25 你太强了， 一看题就知道Binary Search, 我当时第一感觉是用DP， 后来被提示用
Binary Search...
【在 k***e 的大作中提到】
: 我提一个算法，用greedy algorithm for the min-max condition
: 1. make a guess of the max segment length for dividing a[i:j] into x
: sections. suppose it is y, i.e, we want to answer the following question:
: Q: is it possible to divide a[i:j] into x sessions with each session <= y?
: To answer the question, we will use greedy algorithm. find the maximal j_0
: such that: sum_{s=j}^{j_0} a[s] <= y then
: f(a,i,j,y,x) = f(a,j_0+1,j,y,x-1)
: Thus, we can answer Q in time n for each specific x.
: 2. note that: max{a[i]} <=
|
k***e
发帖数: 556 | 26 想了一下，好像除了brutal force就没办法了。
召唤geniusxsy 哈哈
sums
【在 k*k 的大作中提到】
: 如果 most evenly partitioned means the smallest possible variance among sums
: of partitions, 这题有 efficient 算法吗？
: 谢谢。
|
a****n
发帖数: 1887 | 27 假设min max 值为Y， 这个Y 的范围是 max{a[i]} <= y <= sum{a[i]}, 因为这个区间
是单调的， 所以可以在上面做Binary Search |
g*******y
发帖数: 1930 | 28 我还有点没睡醒，为什么binary search好？前面krone给出的复杂度是n^3*log{max{a[
n]}
n个元素的数组，分成k段的话：DP只要最多O(n^2*k)(不知道能不能再优化，但是这个
肯定是能做到的)?
先算个S[i][j] = sum{ arr[i] ... arr[j] } O(n^2)
i
r[i][j]: 在arr[0]...arr[i]这段数组，割成j段，min-max sum的值
状态方程：
r[i][j] = min{ max{ S[k+1][i] , r[k][j-1] } | for j-2<=k
类似的，min variance也可以用这个方法做啊，因为每一段的和的平均值是知道的(=total sum/k),
【在 a****n 的大作中提到】
: 你太强了， 一看题就知道Binary Search, 我当时第一感觉是用DP， 后来被提示用
: Binary Search...
|
a****n
发帖数: 1887 | 29 假设数组为int sum[N], 需要分为M段
int foo()
{
int maxv = accumulate(&num[0],&num[N],0);
int minv = *max_element(&num[0],&num[N]);
int midv;
while(minv < maxv)
{
midv = (minv + maxv)>>1;
int k = 0;
int sum = 0;
for (int i = 0; i < N; ++i)
{
sum += num[i];
if (sum > midv)
{
sum = num[i];
++k;
}
}
if (k < M) maxv = midv;
else minv = midv + 1;
|
g*******y
发帖数: 1930 | 30 wait a second, you guys assume all the numbers are positive?
if not, then minv = max{num[i]} is not a correct lower bound
【在 a****n 的大作中提到】
: 假设数组为int sum[N], 需要分为M段
: int foo()
: {
: int maxv = accumulate(&num[0],&num[N],0);
: int minv = *max_element(&num[0],&num[N]);
: int midv;
: while(minv < maxv)
: {
: midv = (minv + maxv)>>1;
: int k = 0;
|
|
|
a****n
发帖数: 1887 | 31 不好意思，题没说清楚， 我的问题。
这道题全是正数
【在 g*******y 的大作中提到】
: wait a second, you guys assume all the numbers are positive?
: if not, then minv = max{num[i]} is not a correct lower bound
|
g*******y
发帖数: 1930 | 32 汗，重要的条件漏掉了，呵呵...
【在 a****n 的大作中提到】
: 不好意思，题没说清楚， 我的问题。
: 这道题全是正数
|
a****n
发帖数: 1887 | 33 如果有负数的话， 用binary search， 验证过程复杂度会高一些
也可以开头做张表， 记录num[i] + + + num[j]的值， check循环里面直接查表 |
r********t
发帖数: 395 | 34
就是说，被拒了以后很快重新申的话，人家公司会查黑名单，如果有，就直接拒。
不过那个黑名单不是永久的，有个时限～
【在 d*********e 的大作中提到】
: what is this black list?
|
s*****d
发帖数: 43 | 35 哪位可以给详细讲讲Bi-Search的做法？觉得小羊的解才是正解。 |
k***e
发帖数: 556 | 36 han 看看我写的一封贴
为什么鄙视binary search 555
ps，complexity is n^2lg(maxa[i])
【在 s*****d 的大作中提到】
: 哪位可以给详细讲讲Bi-Search的做法？觉得小羊的解才是正解。
|
g*******y
发帖数: 1930 | 37 why asuran got an algorithm with n*log{total sum}, while you get n^2log{max}?
well, if all numbers are positive, binary search is better than my dp, but
maybe there could be some optimization of the DP solution.
【在 k***e 的大作中提到】
: han 看看我写的一封贴
: 为什么鄙视binary search 555
: ps，complexity is n^2lg(maxa[i])
|
k***e
发帖数: 556 | 38 555 I made mistake again
it should be nlog{total sum} or n(lgn + lg(max))
when negative numbers are allowed, it is very messy. i am not quite sure the
binary search works. But DP definitely works, which require nk space and n^
2k time.
max}?
【在 g*******y 的大作中提到】
: why asuran got an algorithm with n*log{total sum}, while you get n^2log{max}?
: well, if all numbers are positive, binary search is better than my dp, but
: maybe there could be some optimization of the DP solution.
|
r********t
发帖数: 395 | 39
他应该是看到一个感兴趣的题，就试着做一下，日积月累。。。
【在 s*****r 的大作中提到】
: 请问原题哪儿可以看到
|
s*****d
发帖数: 43 | 40 KRONE,
不是鄙视binary search， 而是水平有限，没有看懂，故而诚心求教。
【在 k***e 的大作中提到】
: han 看看我写的一封贴
: 为什么鄙视binary search 555
: ps，complexity is n^2lg(maxa[i])
|
