w*t
2 楼
a 一部分面试题：
1，算表盘时针，分针，秒针的角度
2, sql
3，设计hotel reservation system
4, bar raiser question:
有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
cost最小。
5. 旋转print matrix
6. 很大一组set，每个set里包含若干个string,
比如 ,,
第一个set和第三个set没有关系（一个是水果，一个是颜色）虽然都包含orange，第
一个set和第二个set有关联（都是水果），应该是一类。若何把这些set分类。
其他题目都跟做过的项目或他们自己的项目有关.
感觉面试有时候也有运气成分，第四个问题是个老印，很aggressive,不容多想，不停地push下面的问题。第六个还是老印，4,5十分钟面试出出进进四五趟，动不动就把我一个人晾到哪儿，刚开始看见这题以为是 natural language processing,他说不是，说了好几趟思路都不对他的路，时间快过半了他才举了几个例子，我才大致弄清楚大致怎么个回事。他举得例子是大概是如果两个set有相同string,但是一个set只有几个string,另一个set有几十上百个string，这两个set是同一类的可能性就没有了，我才理解到他要的是看看common string 在两个不同的set中占得比重怎么样，如果到了一定的 threshold 才算同类，理解到他的要点每一会儿时间就到了，code没有完成好。
总之点儿相当的背，只能怪自己运气不好，move on
1，算表盘时针，分针，秒针的角度
2, sql
3，设计hotel reservation system
4, bar raiser question:
有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
cost最小。
5. 旋转print matrix
6. 很大一组set，每个set里包含若干个string,
比如
第一个set和第三个set没有关系（一个是水果，一个是颜色）虽然都包含orange，第
一个set和第二个set有关联（都是水果），应该是一类。若何把这些set分类。
其他题目都跟做过的项目或他们自己的项目有关.
感觉面试有时候也有运气成分，第四个问题是个老印，很aggressive,不容多想，不停地push下面的问题。第六个还是老印，4,5十分钟面试出出进进四五趟，动不动就把我一个人晾到哪儿，刚开始看见这题以为是 natural language processing,他说不是，说了好几趟思路都不对他的路，时间快过半了他才举了几个例子，我才大致弄清楚大致怎么个回事。他举得例子是大概是如果两个set有相同string,但是一个set只有几个string,另一个set有几十上百个string，这两个set是同一类的可能性就没有了，我才理解到他要的是看看common string 在两个不同的set中占得比重怎么样，如果到了一定的 threshold 才算同类，理解到他的要点每一会儿时间就到了，code没有完成好。
总之点儿相当的背，只能怪自己运气不好，move on
s*z
3 楼
新闻来源: 联合新闻网 于January 25, 2011 18:21:01
一项最新研究宣称，建立蒙古帝国的成吉思汗，打遍欧亚杀人无数，让许多土地因居民
死光了而变回树
林，相当于减少逾七亿公吨的碳排放量，被封「史上最环保的入侵者」。
英国每日邮报报导，这项美国史丹佛大学卡内基学院全球生态系科学家发表的报告，比
较并计算历史上
大量人口死亡的事件的造成的碳排放量改变，包括欧洲黑死病、中国明朝灭亡、美洲大
陆开发等。
研究发现，成吉思汗于13世纪率领蒙古铁骑杀遍欧，
造成约四千万人丧生，使人类开垦的部分地区因居民遭大量屠杀而恢复至森林的植被景
观，这些植物吸
收二氧化碳，让大气中减少了七亿公吨二氧化碳，相当于全球消耗石油一年造成的碳排
放量。
这种「减排」手段没有人会认同，但学者指出，成吉思汗的作为可能是史上第一次人类
造成的「全球冷
化」。
所有历史上人类大量死亡的事件，都有森林景观广泛回复的共同点。主持研究的科学家
茱莉亚·彭格烈
兹（Julia Pongratz）说：「许多人认为18世纪工业革命时期，人类大量燃烧石油和煤
矿，是人类首
度影响气候，其实这是个误解。」
彭格烈兹说，成吉思汗的战争规模既广且远，植被回复的时间也相对较充裕及广泛，因
此减少碳排放量
居历史之冠。她强调，成吉思汗仍会被史家认为是杀戳君主而非环保君主，这项研究只
是提供传统气候
变迁研究的另类思考方式。
一项最新研究宣称，建立蒙古帝国的成吉思汗，打遍欧亚杀人无数，让许多土地因居民
死光了而变回树
林，相当于减少逾七亿公吨的碳排放量，被封「史上最环保的入侵者」。
英国每日邮报报导，这项美国史丹佛大学卡内基学院全球生态系科学家发表的报告，比
较并计算历史上
大量人口死亡的事件的造成的碳排放量改变，包括欧洲黑死病、中国明朝灭亡、美洲大
陆开发等。
研究发现，成吉思汗于13世纪率领蒙古铁骑杀遍欧，
造成约四千万人丧生，使人类开垦的部分地区因居民遭大量屠杀而恢复至森林的植被景
观，这些植物吸
收二氧化碳，让大气中减少了七亿公吨二氧化碳，相当于全球消耗石油一年造成的碳排
放量。
这种「减排」手段没有人会认同，但学者指出，成吉思汗的作为可能是史上第一次人类
造成的「全球冷
化」。
所有历史上人类大量死亡的事件，都有森林景观广泛回复的共同点。主持研究的科学家
茱莉亚·彭格烈
兹（Julia Pongratz）说：「许多人认为18世纪工业革命时期，人类大量燃烧石油和煤
矿，是人类首
度影响气候，其实这是个误解。」
彭格烈兹说，成吉思汗的战争规模既广且远，植被回复的时间也相对较充裕及广泛，因
此减少碳排放量
居历史之冠。她强调，成吉思汗仍会被史家认为是杀戳君主而非环保君主，这项研究只
是提供传统气候
变迁研究的另类思考方式。
c*r
4 楼
【在 c*****r 的大作中提到】
: 靠谱吗?元芳们你们怎么看?
g*e
5 楼
第四题是NPC吧，用DP写状态方程可解，比较麻烦
第六题还是得遍历所有元素，按元素给当前set分类。问题是题目有没有给一个这样的
类型可以让我们判断的？给定一个元素，返回这个元素所有可能的分类。比如给orange
，返回水果，颜色。这样就可以用voting system做了。遍历一个set下来，投票最高的
那个就是该set的分类。
>,
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
第六题还是得遍历所有元素，按元素给当前set分类。问题是题目有没有给一个这样的
类型可以让我们判断的？给定一个元素，返回这个元素所有可能的分类。比如给orange
，返回水果，颜色。这样就可以用voting system做了。遍历一个set下来，投票最高的
那个就是该set的分类。
>,
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
f*8
6 楼
北京就一个豆汁？
w*t
7 楼
我在原帖中加了解释
orange
【在 g**e 的大作中提到】
: 第四题是NPC吧，用DP写状态方程可解，比较麻烦
: 第六题还是得遍历所有元素，按元素给当前set分类。问题是题目有没有给一个这样的
: 类型可以让我们判断的？给定一个元素，返回这个元素所有可能的分类。比如给orange
: ，返回水果，颜色。这样就可以用voting system做了。遍历一个set下来，投票最高的
: 那个就是该set的分类。
:
: >,
orange
【在 g**e 的大作中提到】
: 第四题是NPC吧，用DP写状态方程可解，比较麻烦
: 第六题还是得遍历所有元素，按元素给当前set分类。问题是题目有没有给一个这样的
: 类型可以让我们判断的？给定一个元素，返回这个元素所有可能的分类。比如给orange
: ，返回水果，颜色。这样就可以用voting system做了。遍历一个set下来，投票最高的
: 那个就是该set的分类。
:
: >,
c*r
8 楼
一城一食
不过豆汁确实冷门,不具代表性~
【在 f*****8 的大作中提到】
: 北京就一个豆汁？
不过豆汁确实冷门,不具代表性~
【在 f*****8 的大作中提到】
: 北京就一个豆汁？
g*x
9 楼
每个cage之间的distance怎么得到？是有个数组存放相邻cage之间的距离么？还是说
cage1和cage2之间的距离为2-1=1？
【在 w*********t 的大作中提到】
: 我在原帖中加了解释
:
: orange
cage1和cage2之间的距离为2-1=1？
【在 w*********t 的大作中提到】
: 我在原帖中加了解释
:
: orange
c*g
10 楼
豆汁 超级难喝阿
哈尔滨的挺靠谱的，不过那个得莫力炖鱼其实源于方正县，算哈尔滨的也行。还有齐齐
哈尔和佳木斯的就是典型的东北菜，包括长春的，在东北那个城市都可以有阿。
哈尔滨还有的特色的就是俄罗斯美食。
【在 c*****r 的大作中提到】
: 一城一食
: 不过豆汁确实冷门,不具代表性~
哈尔滨的挺靠谱的，不过那个得莫力炖鱼其实源于方正县，算哈尔滨的也行。还有齐齐
哈尔和佳木斯的就是典型的东北菜，包括长春的，在东北那个城市都可以有阿。
哈尔滨还有的特色的就是俄罗斯美食。
【在 c*****r 的大作中提到】
: 一城一食
: 不过豆汁确实冷门,不具代表性~
w*t
11 楼
distance就是array element之间的差 a[1] a[3]的distance是 2
【在 g*****x 的大作中提到】
: 每个cage之间的distance怎么得到？是有个数组存放相邻cage之间的距离么？还是说
: cage1和cage2之间的距离为2-1=1？
【在 g*****x 的大作中提到】
: 每个cage之间的distance怎么得到？是有个数组存放相邻cage之间的距离么？还是说
: cage1和cage2之间的距离为2-1=1？
j*a
12 楼
去年在上海吃了一份清炖蟹粉狮子头，怀念至今。58元一个，放在个小盅子里，点的时
候觉得贵，回想起来超值啊。
【在 c*****r 的大作中提到】
: 靠谱吗?元芳们你们怎么看?
候觉得贵，回想起来超值啊。
【在 c*****r 的大作中提到】
: 靠谱吗?元芳们你们怎么看?
c*m
13 楼
是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
kmeans.是NPC，kmeans能给近似解。
kmeans.是NPC，kmeans能给近似解。
c*r
14 楼
确实好吃,馋我啊.不过这个是淮扬菜,蟹壳黄其实也不是正宗上海特色吧.
【在 j*******a 的大作中提到】
: 去年在上海吃了一份清炖蟹粉狮子头，怀念至今。58元一个，放在个小盅子里，点的时
: 候觉得贵，回想起来超值啊。
【在 j*******a 的大作中提到】
: 去年在上海吃了一份清炖蟹粉狮子头，怀念至今。58元一个，放在个小盅子里，点的时
: 候觉得贵，回想起来超值啊。
w*t
15 楼
应该是吧，一个array,一个pipe管array的一部分，一个array从中间某个地方分开成两
部分，一个pipe管一部分
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
部分，一个pipe管一部分
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
c*r
16 楼
东北菜炖好了很好吃,白菜豆腐都很好吃.:)
【在 c*******g 的大作中提到】
: 豆汁 超级难喝阿
: 哈尔滨的挺靠谱的，不过那个得莫力炖鱼其实源于方正县，算哈尔滨的也行。还有齐齐
: 哈尔和佳木斯的就是典型的东北菜，包括长春的，在东北那个城市都可以有阿。
: 哈尔滨还有的特色的就是俄罗斯美食。
【在 c*******g 的大作中提到】
: 豆汁 超级难喝阿
: 哈尔滨的挺靠谱的，不过那个得莫力炖鱼其实源于方正县，算哈尔滨的也行。还有齐齐
: 哈尔和佳木斯的就是典型的东北菜，包括长春的，在东北那个城市都可以有阿。
: 哈尔滨还有的特色的就是俄罗斯美食。
g*x
17 楼
是有些像weighted k-means，可是你算出sum of cost within group，还是不知道如何
update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
C*s
18 楼
大人，此事背后一定有一个天大的秘密
【在 c*****r 的大作中提到】
【在 c*****r 的大作中提到】
y*k
19 楼
没看出来怎么NPC了。两个水管位置有C（n，2）种取法，水管位置固定后怎么送水是显
然的
位置
【在 g*****x 的大作中提到】
: 是有些像weighted k-means，可是你算出sum of cost within group，还是不知道如何
: update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
然的
位置
【在 g*****x 的大作中提到】
: 是有些像weighted k-means，可是你算出sum of cost within group，还是不知道如何
: update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
b*e
20 楼
There seems to be a linear solution to #4.
First look at the case where there's only 1 pipe. The most naive way of
doing it is O(n^2): for each of the n positions, compute the cost. Each
cost computation take O(n), which yields O(n^2) for n iterations.
However, we observe that whenever we move from position i to postion
i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
(roughly) the same as Sum[i+2..n]. This makes it linear. So
essentially, the pipe should split the array to two halfs whose sums are
equal.
The case of 2 pipe, although seems much more complicated, is in fact
similar. We need to test each n possible split positions. For each
each position i, we can identify the pipe in the first half to be at i1,
where Sum[0..i1] is roughly half of the Sum[0..i]; similar for the
second half. With some careful programming, I believe this can be O(n).
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
First look at the case where there's only 1 pipe. The most naive way of
doing it is O(n^2): for each of the n positions, compute the cost. Each
cost computation take O(n), which yields O(n^2) for n iterations.
However, we observe that whenever we move from position i to postion
i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
(roughly) the same as Sum[i+2..n]. This makes it linear. So
essentially, the pipe should split the array to two halfs whose sums are
equal.
The case of 2 pipe, although seems much more complicated, is in fact
similar. We need to test each n possible split positions. For each
each position i, we can identify the pipe in the first half to be at i1,
where Sum[0..i1] is roughly half of the Sum[0..i]; similar for the
second half. With some careful programming, I believe this can be O(n).
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
g*x
21 楼
it's O(n^3), how can you make it O(n)?
【在 b***e 的大作中提到】
: There seems to be a linear solution to #4.
: First look at the case where there's only 1 pipe. The most naive way of
: doing it is O(n^2): for each of the n positions, compute the cost. Each
: cost computation take O(n), which yields O(n^2) for n iterations.
: However, we observe that whenever we move from position i to postion
: i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
: That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
: (roughly) the same as Sum[i+2..n]. This makes it linear. So
: essentially, the pipe should split the array to two halfs whose sums are
: equal.
【在 b***e 的大作中提到】
: There seems to be a linear solution to #4.
: First look at the case where there's only 1 pipe. The most naive way of
: doing it is O(n^2): for each of the n positions, compute the cost. Each
: cost computation take O(n), which yields O(n^2) for n iterations.
: However, we observe that whenever we move from position i to postion
: i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
: That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
: (roughly) the same as Sum[i+2..n]. This makes it linear. So
: essentially, the pipe should split the array to two halfs whose sums are
: equal.
g*y
22 楼
总结一下：
1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
这个二分可以解，O(logn), 但是所有位置求和要O(n)
2. 两个水管，就是要找位置t:
(1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
(2) t = (x+y)/2
解法：二分找t
对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
t > (x+y)/2, 说明t该左移 (减小)
t < (x+y)/2, 说明t该右移 (增加)
【在 b***e 的大作中提到】
: There seems to be a linear solution to #4.
: First look at the case where there's only 1 pipe. The most naive way of
: doing it is O(n^2): for each of the n positions, compute the cost. Each
: cost computation take O(n), which yields O(n^2) for n iterations.
: However, we observe that whenever we move from position i to postion
: i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
: That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
: (roughly) the same as Sum[i+2..n]. This makes it linear. So
: essentially, the pipe should split the array to two halfs whose sums are
: equal.
1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
这个二分可以解，O(logn), 但是所有位置求和要O(n)
2. 两个水管，就是要找位置t:
(1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
(2) t = (x+y)/2
解法：二分找t
对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
t > (x+y)/2, 说明t该左移 (减小)
t < (x+y)/2, 说明t该右移 (增加)
【在 b***e 的大作中提到】
: There seems to be a linear solution to #4.
: First look at the case where there's only 1 pipe. The most naive way of
: doing it is O(n^2): for each of the n positions, compute the cost. Each
: cost computation take O(n), which yields O(n^2) for n iterations.
: However, we observe that whenever we move from position i to postion
: i+1, we in fact add to the cost Sum[0..i-1], and save cost Sum[i+2..n].
: That's to say, the pipe needs to be move to some i, where Sum[0..i-1] is
: (roughly) the same as Sum[i+2..n]. This makes it linear. So
: essentially, the pipe should split the array to two halfs whose sums are
: equal.
g*s
23 楼
In your description, in 1, it is O(n log n), isn't it?
In 2, how can you use log(n) to find the x,y?
for pipe=1, the answer is the weighted median, it is O(n).
Then for pipe=2, the total time can be O(nlogn) using weighted median +
binary search.
【在 g**********y 的大作中提到】
: 总结一下：
: 1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
: 这个二分可以解，O(logn), 但是所有位置求和要O(n)
: 2. 两个水管，就是要找位置t:
: (1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
: (2) t = (x+y)/2
: 解法：二分找t
: 对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
: t > (x+y)/2, 说明t该左移 (减小)
: t < (x+y)/2, 说明t该右移 (增加)
In 2, how can you use log(n) to find the x,y?
for pipe=1, the answer is the weighted median, it is O(n).
Then for pipe=2, the total time can be O(nlogn) using weighted median +
binary search.
【在 g**********y 的大作中提到】
: 总结一下：
: 1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
: 这个二分可以解，O(logn), 但是所有位置求和要O(n)
: 2. 两个水管，就是要找位置t:
: (1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
: (2) t = (x+y)/2
: 解法：二分找t
: 对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
: t > (x+y)/2, 说明t该左移 (减小)
: t < (x+y)/2, 说明t该右移 (增加)
g*y
24 楼
in 1, it is O(n)累加 + O(logn)二分
in 2, it is same way to find x between 1 .. t, y between t .. n
累加是一次性的计算，O(n)
后面的二分，总计应该是 O(logn^2)
所以 O(n) + O(logn^2) ~ O(n)
【在 g***s 的大作中提到】
: In your description, in 1, it is O(n log n), isn't it?
: In 2, how can you use log(n) to find the x,y?
: for pipe=1, the answer is the weighted median, it is O(n).
: Then for pipe=2, the total time can be O(nlogn) using weighted median +
: binary search.
in 2, it is same way to find x between 1 .. t, y between t .. n
累加是一次性的计算，O(n)
后面的二分，总计应该是 O(logn^2)
所以 O(n) + O(logn^2) ~ O(n)
【在 g***s 的大作中提到】
: In your description, in 1, it is O(n log n), isn't it?
: In 2, how can you use log(n) to find the x,y?
: for pipe=1, the answer is the weighted median, it is O(n).
: Then for pipe=2, the total time can be O(nlogn) using weighted median +
: binary search.
g*e
25 楼
this is not right even for pipe=1, your algorithm yields O(nlogn) for p=1
【在 g**********y 的大作中提到】
: in 1, it is O(n)累加 + O(logn)二分
: in 2, it is same way to find x between 1 .. t, y between t .. n
: 累加是一次性的计算，O(n)
: 后面的二分，总计应该是 O(logn^2)
: 所以 O(n) + O(logn^2) ~ O(n)
【在 g**********y 的大作中提到】
: in 1, it is O(n)累加 + O(logn)二分
: in 2, it is same way to find x between 1 .. t, y between t .. n
: 累加是一次性的计算，O(n)
: 后面的二分，总计应该是 O(logn^2)
: 所以 O(n) + O(logn^2) ~ O(n)
g*s
26 楼
I understand know. it is correct.
To be clear, for the algo,
for both 1 and 2, we have to get sum(i) using DP since for each binary
split, you needs to know the sum(i,j)
【在 g**********y 的大作中提到】
: in 1, it is O(n)累加 + O(logn)二分
: in 2, it is same way to find x between 1 .. t, y between t .. n
: 累加是一次性的计算，O(n)
: 后面的二分，总计应该是 O(logn^2)
: 所以 O(n) + O(logn^2) ~ O(n)
To be clear, for the algo,
for both 1 and 2, we have to get sum(i) using DP since for each binary
split, you needs to know the sum(i,j)
【在 g**********y 的大作中提到】
: in 1, it is O(n)累加 + O(logn)二分
: in 2, it is same way to find x between 1 .. t, y between t .. n
: 累加是一次性的计算，O(n)
: 后面的二分，总计应该是 O(logn^2)
: 所以 O(n) + O(logn^2) ~ O(n)
g*y
27 楼
right, sum(i,j) = sum(j) - sum(i)
【在 g***s 的大作中提到】
: I understand know. it is correct.
: To be clear, for the algo,
: for both 1 and 2, we have to get sum(i) using DP since for each binary
: split, you needs to know the sum(i,j)
【在 g***s 的大作中提到】
: I understand know. it is correct.
: To be clear, for the algo,
: for both 1 and 2, we have to get sum(i) using DP since for each binary
: split, you needs to know the sum(i,j)
g*e
28 楼
I don't think so. It still can be done in O(n) using DP though. I firstly
thought it wrong.
sum(i,j) = sum( w[k]*(j-k+1) ) for all i<=k<=j
sum(i,j) = sum(i,j-1) + t[i,j]
where sum(i,j) is the total cost of [i,j] to place pipe at j, and t[i,j]=w[i
]+...+w[j], w[i] is the cost of position i if a pipe is placed at i
【在 g**********y 的大作中提到】
: right, sum(i,j) = sum(j) - sum(i)
thought it wrong.
sum(i,j) = sum( w[k]*(j-k+1) ) for all i<=k<=j
sum(i,j) = sum(i,j-1) + t[i,j]
where sum(i,j) is the total cost of [i,j] to place pipe at j, and t[i,j]=w[i
]+...+w[j], w[i] is the cost of position i if a pipe is placed at i
【在 g**********y 的大作中提到】
: right, sum(i,j) = sum(j) - sum(i)
g*s
29 楼
sum(i) = sum of the weight of 1..i
sum(i,j) = sum( w[k] ) for all i<=k<=j
in fact, the idea is same as weighted median. check blaze's post.
firstly
t[i,j]=w[i
【在 g**e 的大作中提到】
: I don't think so. It still can be done in O(n) using DP though. I firstly
: thought it wrong.
: sum(i,j) = sum( w[k]*(j-k+1) ) for all i<=k<=j
: sum(i,j) = sum(i,j-1) + t[i,j]
: where sum(i,j) is the total cost of [i,j] to place pipe at j, and t[i,j]=w[i
: ]+...+w[j], w[i] is the cost of position i if a pipe is placed at i
sum(i,j) = sum( w[k] ) for all i<=k<=j
in fact, the idea is same as weighted median. check blaze's post.
firstly
t[i,j]=w[i
【在 g**e 的大作中提到】
: I don't think so. It still can be done in O(n) using DP though. I firstly
: thought it wrong.
: sum(i,j) = sum( w[k]*(j-k+1) ) for all i<=k<=j
: sum(i,j) = sum(i,j-1) + t[i,j]
: where sum(i,j) is the total cost of [i,j] to place pipe at j, and t[i,j]=w[i
: ]+...+w[j], w[i] is the cost of position i if a pipe is placed at i
g*y
30 楼
grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
g*e
31 楼
是不是我题意没理解清楚， 比如下面的数组 1 2 3 4 5， pipe放在3，
total cost = 1*3 + 2*2 + 3*1 + 4*2 + 5*3 = 33
是不是这样？
【在 g***s 的大作中提到】
: sum(i) = sum of the weight of 1..i
: sum(i,j) = sum( w[k] ) for all i<=k<=j
: in fact, the idea is same as weighted median. check blaze's post.
:
: firstly
: t[i,j]=w[i
total cost = 1*3 + 2*2 + 3*1 + 4*2 + 5*3 = 33
是不是这样？
【在 g***s 的大作中提到】
: sum(i) = sum of the weight of 1..i
: sum(i,j) = sum( w[k] ) for all i<=k<=j
: in fact, the idea is same as weighted median. check blaze's post.
:
: firstly
: t[i,j]=w[i
g*s
32 楼
I was wrong, so i deleted it.
for one pipe, it is correct.
but we still need to use binary search + weighted median to solve 2-pipes
problem.
【在 g**********y 的大作中提到】
: grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
for one pipe, it is correct.
but we still need to use binary search + weighted median to solve 2-pipes
problem.
【在 g**********y 的大作中提到】
: grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
d*l
33 楼
我也觉得，如果一个pipe的话正确无疑，但两个pipe情况下正确性不那么显然，虽然我
也觉得这很可能是对的。如果这个正确，是否能推广到更普遍的情况呢？比如3个、4个
pipe？
【在 g**********y 的大作中提到】
: grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
也觉得这很可能是对的。如果这个正确，是否能推广到更普遍的情况呢？比如3个、4个
pipe？
【在 g**********y 的大作中提到】
: grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
g*s
34 楼
pipe=3
cost = 1*2 + 2*1 + 4*1 + 5*2 = 18
weighted median is 4,
pipe =4
cost = 1*3 + 2*2 + 3*1 + 5*1= 15
【在 g**e 的大作中提到】
: 是不是我题意没理解清楚， 比如下面的数组 1 2 3 4 5， pipe放在3，
: total cost = 1*3 + 2*2 + 3*1 + 4*2 + 5*3 = 33
: 是不是这样？
cost = 1*2 + 2*1 + 4*1 + 5*2 = 18
weighted median is 4,
pipe =4
cost = 1*3 + 2*2 + 3*1 + 5*1= 15
【在 g**e 的大作中提到】
: 是不是我题意没理解清楚， 比如下面的数组 1 2 3 4 5， pipe放在3，
: total cost = 1*3 + 2*2 + 3*1 + 4*2 + 5*3 = 33
: 是不是这样？
b*e
35 楼
Actually, 1 pipe, we can do it in O(N), 2N, actually.
For 2 pipes, we can do it in O(N), too, 3N actually, just scan the array
from beginning, and the end.
For 2 pipes, we can do it in O(N), too, 3N actually, just scan the array
from beginning, and the end.
M*u
36 楼
a公司这么多年，来来回回来就是这些题。。。
>,
停地push下面的问题。第六个还是老印，4,5十分钟面试出出进进四五趟，动不动就把
我一个人晾到哪儿，刚开始看见这题以为是 natural language processing,他说不是
，说了好几趟思路都不对他的路，时:
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
>,
停地push下面的问题。第六个还是老印，4,5十分钟面试出出进进四五趟，动不动就把
我一个人晾到哪儿，刚开始看见这题以为是 natural language processing,他说不是
，说了好几趟思路都不对他的路，时:
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
g*e
37 楼
可是题目是“pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供
水的cost是 (distance to that cage)*那个cage动物的用水量”
按照你这么算，pipe位置没有cost，不符合题意啊
【在 g***s 的大作中提到】
: pipe=3
: cost = 1*2 + 2*1 + 4*1 + 5*2 = 18
: weighted median is 4,
: pipe =4
: cost = 1*3 + 2*2 + 3*1 + 5*1= 15
水的cost是 (distance to that cage)*那个cage动物的用水量”
按照你这么算，pipe位置没有cost，不符合题意啊
【在 g***s 的大作中提到】
: pipe=3
: cost = 1*2 + 2*1 + 4*1 + 5*2 = 18
: weighted median is 4,
: pipe =4
: cost = 1*3 + 2*2 + 3*1 + 5*1= 15
g*s
38 楼
ohh... that's correct. :)
so, the answer could not be weight median.
but should be one of (weight median - 1, weight median, weight median + 1)
【在 g**e 的大作中提到】
: 可是题目是“pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供
: 水的cost是 (distance to that cage)*那个cage动物的用水量”
: 按照你这么算，pipe位置没有cost，不符合题意啊
so, the answer could not be weight median.
but should be one of (weight median - 1, weight median, weight median + 1)
【在 g**e 的大作中提到】
: 可是题目是“pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供
: 水的cost是 (distance to that cage)*那个cage动物的用水量”
: 按照你这么算，pipe位置没有cost，不符合题意啊
d*l
39 楼
刚开始我也想错了。。那这个题意有点不和谐了，不过一个pipe还是应该能O(n)的。两
个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
【在 g***s 的大作中提到】
: ohh... that's correct. :)
: so, the answer could not be weight median.
: but should be one of (weight median - 1, weight median, weight median + 1)
个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
【在 g***s 的大作中提到】
: ohh... that's correct. :)
: so, the answer could not be weight median.
: but should be one of (weight median - 1, weight median, weight median + 1)
g*e
40 楼
i变化的时候，找到新的j，不是O(1)吧
【在 d*******l 的大作中提到】
: 刚开始我也想错了。。那这个题意有点不和谐了，不过一个pipe还是应该能O(n)的。两
: 个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
: 开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
: 然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
: 退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
【在 d*******l 的大作中提到】
: 刚开始我也想错了。。那这个题意有点不和谐了，不过一个pipe还是应该能O(n)的。两
: 个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
: 开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
: 然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
: 退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
d*l
41 楼
你刚才的方法为什么是错的？一时想不出很直接的反例啊
【在 g***s 的大作中提到】
: I was wrong, so i deleted it.
: for one pipe, it is correct.
: but we still need to use binary search + weighted median to solve 2-pipes
: problem.
【在 g***s 的大作中提到】
: I was wrong, so i deleted it.
: for one pipe, it is correct.
: but we still need to use binary search + weighted median to solve 2-pipes
: problem.
d*l
42 楼
目前我假设随着i变大，j的最优位置不会减小。
如果真是这样，那j对应一个i的时候可能不是O(1)的，但由于整体上只走一遍，最后还
是O(n)。
【在 g**e 的大作中提到】
: i变化的时候，找到新的j，不是O(1)吧
如果真是这样，那j对应一个i的时候可能不是O(1)的，但由于整体上只走一遍，最后还
是O(n)。
【在 g**e 的大作中提到】
: i变化的时候，找到新的j，不是O(1)吧
g*s
43 楼
1 50 50 0 3 1 104
【在 d*******l 的大作中提到】
: 你刚才的方法为什么是错的？一时想不出很直接的反例啊
【在 d*******l 的大作中提到】
: 你刚才的方法为什么是错的？一时想不出很直接的反例啊
b*8
44 楼
#4如果距离就是数组下标差，那给本Cage和相邻的Cage供水代价是一样的？很不合理呀
。这类问题一定要先搞清楚准确定义，不然难度上谬以千里了。
。这类问题一定要先搞清楚准确定义，不然难度上谬以千里了。
b*e
45 楼
This is obviously correct. Just one scan is OK. Set split point j at 1
in the beginning. Let pipe 1 at i = 0 and pipe 2 at k where Sum[j..n] =
Sum[1..n] / 2.
Then we need to loop j from 1 to n, in each step we (maybe) increase i and
k such that the following invariant hold:
1. Sum[0..i] = Sum[0..j] / 2
2. Sum[k..n] = Sum[j..n] / 2
【在 d*******l 的大作中提到】
: 刚开始我也想错了。。那这个题意有点不和谐了，不过一个pipe还是应该能O(n)的。两
: 个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
: 开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
: 然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
: 退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
in the beginning. Let pipe 1 at i = 0 and pipe 2 at k where Sum[j..n] =
Sum[1..n] / 2.
Then we need to loop j from 1 to n, in each step we (maybe) increase i and
k such that the following invariant hold:
1. Sum[0..i] = Sum[0..j] / 2
2. Sum[k..n] = Sum[j..n] / 2
【在 d*******l 的大作中提到】
: 刚开始我也想错了。。那这个题意有点不和谐了，不过一个pipe还是应该能O(n)的。两
: 个pipe的情况，我现在想到一个可能的办法。假设pipe1，pipe2的位置是i，j。
: 开始的时候i=1，然后找到相应的最优的j，这个是O(n)的。
: 然后i递增，j也递增。这里的假设是，随着pipe1向右推移，pipe2的最优位置是不会回
: 退的。如果假设是正确的，那似乎可以在i，j都走完一遍之后就出结果。O(n)
b*e
46 楼
Seems this generalizes to any k pipes, yielding a complexity of O(n*k):
From the position of the first pipe p1, all the position of other pipes
can be determined by:
* p2 is at the point where Sum[0..p1] = Sum[p1..p2]
* for i = 3..k, p_{i+1} - p_i = p2 - p1
So still only one scan.
【在 d*******l 的大作中提到】
: 我也觉得，如果一个pipe的话正确无疑，但两个pipe情况下正确性不那么显然，虽然我
: 也觉得这很可能是对的。如果这个正确，是否能推广到更普遍的情况呢？比如3个、4个
: pipe？
From the position of the first pipe p1, all the position of other pipes
can be determined by:
* p2 is at the point where Sum[0..p1] = Sum[p1..p2]
* for i = 3..k, p_{i+1} - p_i = p2 - p1
So still only one scan.
【在 d*******l 的大作中提到】
: 我也觉得，如果一个pipe的话正确无疑，但两个pipe情况下正确性不那么显然，虽然我
: 也觉得这很可能是对的。如果这个正确，是否能推广到更普遍的情况呢？比如3个、4个
: pipe？
b*e
47 楼
I'm unclear about the bin search in last step. Bin search requires fixed
upper and lower bound. Yours are moving. So in theory it might even not
terminate.
【在 g**********y 的大作中提到】
: 总结一下：
: 1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
: 这个二分可以解，O(logn), 但是所有位置求和要O(n)
: 2. 两个水管，就是要找位置t:
: (1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
: (2) t = (x+y)/2
: 解法：二分找t
: 对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
: t > (x+y)/2, 说明t该左移 (减小)
: t < (x+y)/2, 说明t该右移 (增加)
upper and lower bound. Yours are moving. So in theory it might even not
terminate.
【在 g**********y 的大作中提到】
: 总结一下：
: 1. 一个水管的情况，解法就是找到k, 使a[1]+...+a[k] ~ a[k+1] + ... a[n],
: 这个二分可以解，O(logn), 但是所有位置求和要O(n)
: 2. 两个水管，就是要找位置t:
: (1) a[1] ... a[t] 由 水管1在位置x提供; a[t+1] ... a[n]由水管2在位置y提供
: (2) t = (x+y)/2
: 解法：二分找t
: 对于任何一个假设值t, 我们都可以O(logn)找出相应的x, y
: t > (x+y)/2, 说明t该左移 (减小)
: t < (x+y)/2, 说明t该右移 (增加)
g*s
48 楼
你这就是weighted median再weighted median。
我开始也猜这个，但后来发现不对，所有把自己的帖子删了。（即使是当前点贡献是0
用这个方法也不
能推广到pipe>1)
因为这题比较怪，当前位置跟距离为1的位置的贡献是一样的.所以，对pipe=1,我们用
Weighted
median，但要稍微做一些修改。求到了以后，设为m。
我们需要在m-1，m,m-1进行选择
if sum(m-2) < sum(m+1,n) then t = m-1;
else if sum(m-1) < sum(m+2,n) 的值 t = m;
else t = m+1
所以,pipe=1可以O(n).
再用二分，两边分别用这个思路做，就是gloomyturkey描述的那样。也就可以O(n)完成。
1
=
and
【在 b***e 的大作中提到】
: This is obviously correct. Just one scan is OK. Set split point j at 1
: in the beginning. Let pipe 1 at i = 0 and pipe 2 at k where Sum[j..n] =
: Sum[1..n] / 2.
: Then we need to loop j from 1 to n, in each step we (maybe) increase i and
: k such that the following invariant hold:
: 1. Sum[0..i] = Sum[0..j] / 2
: 2. Sum[k..n] = Sum[j..n] / 2
我开始也猜这个，但后来发现不对，所有把自己的帖子删了。（即使是当前点贡献是0
用这个方法也不
能推广到pipe>1)
因为这题比较怪，当前位置跟距离为1的位置的贡献是一样的.所以，对pipe=1,我们用
Weighted
median，但要稍微做一些修改。求到了以后，设为m。
我们需要在m-1，m,m-1进行选择
if sum(m-2) < sum(m+1,n) then t = m-1;
else if sum(m-1) < sum(m+2,n) 的值 t = m;
else t = m+1
所以,pipe=1可以O(n).
再用二分，两边分别用这个思路做，就是gloomyturkey描述的那样。也就可以O(n)完成。
1
=
and
【在 b***e 的大作中提到】
: This is obviously correct. Just one scan is OK. Set split point j at 1
: in the beginning. Let pipe 1 at i = 0 and pipe 2 at k where Sum[j..n] =
: Sum[1..n] / 2.
: Then we need to loop j from 1 to n, in each step we (maybe) increase i and
: k such that the following invariant hold:
: 1. Sum[0..i] = Sum[0..j] / 2
: 2. Sum[k..n] = Sum[j..n] / 2
b*e
49 楼
Didn't get it. In my terminology:
For each k (the split point), I can always get the accurate position of
i (pipe 1 position) and j (pipe 2 position) in constant time, right?
More detailed, when k -> k+1:
* i -> i or i+1
* j -> j or j+1
This is just one scan.
Also, I cannot justify the bin-search algorithm, as I said in a previous
post. It is not obvious why it is correct (or why it should even stop).
0
置
【在 g***s 的大作中提到】
: 你这就是weighted median再weighted median。
: 我开始也猜这个，但后来发现不对，所有把自己的帖子删了。（即使是当前点贡献是0
: 用这个方法也不
: 能推广到pipe>1)
: 因为这题比较怪，当前位置跟距离为1的位置的贡献是一样的.所以，对pipe=1,我们用
: Weighted
: median，但要稍微做一些修改。求到了以后，设为m。
: 我们需要在m-1，m,m-1进行选择
: if sum(m-2) < sum(m+1,n) then t = m-1;
: else if sum(m-1) < sum(m+2,n) 的值 t = m;
For each k (the split point), I can always get the accurate position of
i (pipe 1 position) and j (pipe 2 position) in constant time, right?
More detailed, when k -> k+1:
* i -> i or i+1
* j -> j or j+1
This is just one scan.
Also, I cannot justify the bin-search algorithm, as I said in a previous
post. It is not obvious why it is correct (or why it should even stop).
0
置
【在 g***s 的大作中提到】
: 你这就是weighted median再weighted median。
: 我开始也猜这个，但后来发现不对，所有把自己的帖子删了。（即使是当前点贡献是0
: 用这个方法也不
: 能推广到pipe>1)
: 因为这题比较怪，当前位置跟距离为1的位置的贡献是一样的.所以，对pipe=1,我们用
: Weighted
: median，但要稍微做一些修改。求到了以后，设为m。
: 我们需要在m-1，m,m-1进行选择
: if sum(m-2) < sum(m+1,n) then t = m-1;
: else if sum(m-1) < sum(m+2,n) 的值 t = m;
g*s
50 楼
i->i or i+1 is incorrect
2 2 1 1 1 1 100 100 ......
k = 6, i = ?
k = 7, i = ？
of
previous
stop).
【在 b***e 的大作中提到】
: Didn't get it. In my terminology:
: For each k (the split point), I can always get the accurate position of
: i (pipe 1 position) and j (pipe 2 position) in constant time, right?
: More detailed, when k -> k+1:
: * i -> i or i+1
: * j -> j or j+1
: This is just one scan.
: Also, I cannot justify the bin-search algorithm, as I said in a previous
: post. It is not obvious why it is correct (or why it should even stop).
:
2 2 1 1 1 1 100 100 ......
k = 6, i = ?
k = 7, i = ？
of
previous
stop).
【在 b***e 的大作中提到】
: Didn't get it. In my terminology:
: For each k (the split point), I can always get the accurate position of
: i (pipe 1 position) and j (pipe 2 position) in constant time, right?
: More detailed, when k -> k+1:
: * i -> i or i+1
: * j -> j or j+1
: This is just one scan.
: Also, I cannot justify the bin-search algorithm, as I said in a previous
: post. It is not obvious why it is correct (or why it should even stop).
:
b*e
51 楼
1. Sure, that wasn't all correct. But still, i, j grows to one
direction, and will never go back. Might not be plus one, but it's
guaranteed to be one pass, O(n). Still not seeing why you say it's
being wrong.
2. In fact, assuming the original array is A, it's pretty easy to see
that we can DP to compute B, where B[i] is the optimal with 1 pipe for
A[i..n]. This is O(n). Computer for the other direction, O(n) too.
The algorithm I described is just a better version of this bidirectional
DP with less space complexity.
3. My k-pipe is not all correct as well, but I believe it's the
direction.
4. I see the O(n*log(n)) bin-search correct, but not the
O(log(n)*log(n)) one being correct.
【在 g***s 的大作中提到】
: i->i or i+1 is incorrect
: 2 2 1 1 1 1 100 100 ......
: k = 6, i = ?
: k = 7, i = ？
:
: of
: previous
: stop).
direction, and will never go back. Might not be plus one, but it's
guaranteed to be one pass, O(n). Still not seeing why you say it's
being wrong.
2. In fact, assuming the original array is A, it's pretty easy to see
that we can DP to compute B, where B[i] is the optimal with 1 pipe for
A[i..n]. This is O(n). Computer for the other direction, O(n) too.
The algorithm I described is just a better version of this bidirectional
DP with less space complexity.
3. My k-pipe is not all correct as well, but I believe it's the
direction.
4. I see the O(n*log(n)) bin-search correct, but not the
O(log(n)*log(n)) one being correct.
【在 g***s 的大作中提到】
: i->i or i+1 is incorrect
: 2 2 1 1 1 1 100 100 ......
: k = 6, i = ?
: k = 7, i = ？
:
: of
: previous
: stop).
c*t
52 楼
5. 旋转print matrix
这道题问的是什么？
是给定一个矩阵，按照旋转的顺序把elements打印出来？
还是要自己生成一个旋转矩阵，然后按照行打印处理？
谢谢！
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
这道题问的是什么？
是给定一个矩阵，按照旋转的顺序把elements打印出来？
还是要自己生成一个旋转矩阵，然后按照行打印处理？
谢谢！
【在 w*********t 的大作中提到】
: a 一部分面试题：
: 1，算表盘时针，分针，秒针的角度
: 2, sql
: 3，设计hotel reservation system
: 4, bar raiser question:
: 有一 行 animal cages ，每个cage的动物的用水量为数组,有两个pipe给所有动物
: 供水，pipe给当前cage的cost 是 这个cage动物的用水量，给其他cage的动物供水的
: cost是 (distance to that cage)*那个cage动物的用水量， 求两个pipe供水的位置使
: cost最小。
: 5. 旋转print matrix
g*s
53 楼
Your idea is correct. and gloomyturkey gave the detail based on your
idea.
for 1, now, it is correct. Another mehtod gloomyturkey gave is: after we
get sum(i) using O(N), we can also use binary search to find the i and
j. (find the max x, let sum(x) - sum(x+3,n)<0). return x+2.
for 2, i cannot understand how to using DP to get in O(n)
for 3, 2 pipe has only one split point, so, the choice is O(n). but for
pipe is 3, with two split points, is difficult to be solved in O(n).
for 4, f(x) = sum(x) - sum(x+3,n) > 0
BTW:
A little more you need to polish for pipe = 1 is: sum(i) = sum(n)/2
since the question is a little different, a counter sample:
for pipe = 1
10 10 x y 11 10
The answer is alway 4 no matter the value of x, y. e.g. x=1000, y=1 and
x=1, y=1000. using sum(i) = sum(n) / 2 will get different i.
idea.
for 1, now, it is correct. Another mehtod gloomyturkey gave is: after we
get sum(i) using O(N), we can also use binary search to find the i and
j. (find the max x, let sum(x) - sum(x+3,n)<0). return x+2.
for 2, i cannot understand how to using DP to get in O(n)
for 3, 2 pipe has only one split point, so, the choice is O(n). but for
pipe is 3, with two split points, is difficult to be solved in O(n).
for 4, f(x) = sum(x) - sum(x+3,n) > 0
BTW:
A little more you need to polish for pipe = 1 is: sum(i) = sum(n)/2
since the question is a little different, a counter sample:
for pipe = 1
10 10 x y 11 10
The answer is alway 4 no matter the value of x, y. e.g. x=1000, y=1 and
x=1, y=1000. using sum(i) = sum(n) / 2 will get different i.
b*e
54 楼
I am still confused on 4. Quote:
t > (x+y)/2, 说明t该左移 (减小)
t < (x+y)/2, 说明t该右移 (增加)
The implication here is non-trivial. Why is it the case that, if t > (x+y)/
2, then t should get smaller? There's needs to be a proof that the optimal
t can no longer be bigger than the current t. Why exactly is that?
t > (x+y)/2, 说明t该左移 (减小)
t < (x+y)/2, 说明t该右移 (增加)
The implication here is non-trivial. Why is it the case that, if t > (x+y)/
2, then t should get smaller? There's needs to be a proof that the optimal
t can no longer be bigger than the current t. Why exactly is that?
相关阅读