w*********t
发帖数: 170 | 1 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
| g**e
发帖数: 6127 | 2 第四题是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
| w*********t
发帖数: 170 | 3 我在原帖中加了解释
orange
【在 g**e 的大作中提到】
: 第四题是NPC吧，用DP写状态方程可解，比较麻烦
: 第六题还是得遍历所有元素，按元素给当前set分类。问题是题目有没有给一个这样的
: 类型可以让我们判断的？给定一个元素，返回这个元素所有可能的分类。比如给orange
: ，返回水果，颜色。这样就可以用voting system做了。遍历一个set下来，投票最高的
: 那个就是该set的分类。
:
: >,
| g*****x
发帖数: 799 | 4 每个cage之间的distance怎么得到？是有个数组存放相邻cage之间的距离么？还是说
cage1和cage2之间的距离为2-1=1？
【在 w*********t 的大作中提到】
: 我在原帖中加了解释
:
: orange
| w*********t
发帖数: 170 | 5 distance就是array element之间的差 a[1] a[3]的distance是 2
【在 g*****x 的大作中提到】
: 每个cage之间的distance怎么得到？是有个数组存放相邻cage之间的距离么？还是说
: cage1和cage2之间的距离为2-1=1？
| c****m
发帖数: 179 | 6 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
kmeans.是NPC，kmeans能给近似解。 | w*********t
发帖数: 170 | 7 应该是吧，一个array,一个pipe管array的一部分，一个array从中间某个地方分开成两
部分，一个pipe管一部分
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
| g*****x
发帖数: 799 | 8 是有些像weighted k-means，可是你算出sum of cost within group，还是不知道如何
update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
【在 c****m 的大作中提到】
: 是要把动物分成两部分，分别用一个pipe吗？ 如果是这样的话，就是weighted
: kmeans.是NPC，kmeans能给近似解。
| y**k
发帖数: 222 | 9 没看出来怎么NPC了。两个水管位置有C（n，2）种取法，水管位置固定后怎么送水是显
然的
位置
【在 g*****x 的大作中提到】
: 是有些像weighted k-means，可是你算出sum of cost within group，还是不知道如何
: update那组的中心点，即水管位置。。这并不是坐标空间，那个mean不代表中心点的位置
| b***e
发帖数: 1419 | 10 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
| | | g*****x
发帖数: 799 | 11 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.
| g**********y
发帖数: 14569 | 12 总结一下：
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
发帖数: 3811 | 13 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该右移 (增加)
| g**********y
发帖数: 14569 | 14 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.
| g**e
发帖数: 6127 | 15 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***s
发帖数: 3811 | 16 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)
| g**********y
发帖数: 14569 | 17 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**e
发帖数: 6127 | 18 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)
| g***s
发帖数: 3811 | 19 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
| g**********y
发帖数: 14569 | 20 grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。 | | | g**e
发帖数: 6127 | 21 是不是我题意没理解清楚， 比如下面的数组 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
| g***s
发帖数: 3811 | 22 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平分两次，直觉上好象是对的，需要数学证明吧。
| d*******l
发帖数: 338 | 23 我也觉得，如果一个pipe的话正确无疑，但两个pipe情况下正确性不那么显然，虽然我
也觉得这很可能是对的。如果这个正确，是否能推广到更普遍的情况呢？比如3个、4个
pipe？
【在 g**********y 的大作中提到】
: grass你说按weighted median平分两次，直觉上好象是对的，需要数学证明吧。
| g***s
发帖数: 3811 | 24 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
: 是不是这样？
| b******e
发帖数: 52 | 25 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. | M**u
发帖数: 10158 | 26 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
| g**e
发帖数: 6127 | 27 可是题目是“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
| g***s
发帖数: 3811 | 28 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，不符合题意啊
| d*******l
发帖数: 338 | 29 刚开始我也想错了。。那这个题意有点不和谐了，不过一个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)
| g**e
发帖数: 6127 | 30 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
发帖数: 338 | 31 你刚才的方法为什么是错的？一时想不出很直接的反例啊
【在 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
发帖数: 338 | 32 目前我假设随着i变大，j的最优位置不会减小。
如果真是这样，那j对应一个i的时候可能不是O(1)的，但由于整体上只走一遍，最后还
是O(n)。
【在 g**e 的大作中提到】
: i变化的时候，找到新的j，不是O(1)吧
| g***s
发帖数: 3811 | 33 1 50 50 0 3 1 104
【在 d*******l 的大作中提到】
: 你刚才的方法为什么是错的？一时想不出很直接的反例啊
| b*******8
发帖数: 37364 | 34 #4如果距离就是数组下标差，那给本Cage和相邻的Cage供水代价是一样的？很不合理呀
。这类问题一定要先搞清楚准确定义，不然难度上谬以千里了。 | b***e
发帖数: 1419 | 35 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)
| b***e
发帖数: 1419 | 36 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？
| b***e
发帖数: 1419 | 37 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该右移 (增加)
| g***s
发帖数: 3811 | 38 你这就是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
| b***e
发帖数: 1419 | 39 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;
| g***s
发帖数: 3811 | 40 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).
:
| | | b***e
发帖数: 1419 | 41 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).
| c*********t
发帖数: 2921 | 42 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
发帖数: 3811 | 43 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. | b***e
发帖数: 1419 | 44 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? |
|
