~~~~~~~~问个G家的题~~~~~~~~~~~ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

~~~~~~~~问个G家的题~~~~~~~~~~~

~~~~~~~~问个G家的题~~~~~~~~~~~# JobHunting - 待字闺中

G*F2011-05-16 07:05

1 楼

前两天跟风入了个Instant pot
无水炖鸡，比砂锅炖的香多了
小米粉蒸排骨，惊艳，比普通高压锅蒸的香软糯
杂粮粥，不比普通高压锅差
方便极了，晚上定时，早上有粥喝；早上把肉放进去，中午晚上一锅香香的肉就有了，
根本不用管
现在已经离不开这锅了。。。只后悔没有早入

g*i2011-05-16 07:05

2 楼

给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
部顺序不能
变)。

h*y2011-05-16 07:05

3 楼

我也觉得这个锅做的粥和米饭特别香，但我老公不喜欢这个锅做的米饭，他喜欢干的米
饭。

【在 G*F 的大作中提到】

: 前两天跟风入了个Instant pot
: 无水炖鸡，比砂锅炖的香多了
: 小米粉蒸排骨，惊艳，比普通高压锅蒸的香软糯
: 杂粮粥，不比普通高压锅差
: 方便极了，晚上定时，早上有粥喝；早上把肉放进去，中午晚上一锅香香的肉就有了，
: 根本不用管
: 现在已经离不开这锅了。。。只后悔没有早入

i*e2011-05-16 07:05

4 楼

3 way partition，思路跟 dutch national flag problem 一样。
三个指针遍历，有三种情况， <0, ==0, >0，然后根据情况进行 swapping。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*******i 的大作中提到】

: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。

S*A2011-05-16 07:05

5 楼

这个锅可以烧干的米饭啊，就是调节一下水的多少就行了。
我就是喜欢干点才用这个锅的。
你用什么锅烧更干的米饭？

【在 h********y 的大作中提到】

: 我也觉得这个锅做的粥和米饭特别香，但我老公不喜欢这个锅做的米饭，他喜欢干的米
: 饭。

g*i2011-05-16 07:05

6 楼

如何保证负数内部和正数内部还是原来的顺序？
Dutch national flag problem是不区分元素顺序的
这是stackoverflow上的讨论：
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ

l*r2011-05-16 07:05

7 楼

无水炖鸡怎么做？

【在 G*F 的大作中提到】

f*w2011-05-16 07:05

8 楼

同问我也觉得3partition 好像不能保证顺序

G*F2011-05-16 07:05

9 楼

鸡切大块，用料酒，酱油，姜，五香粉，香油，泡发香菇，拌好放一个小时
胡萝卜，土豆切大块垫锅底，腌好的鸡肉铺在上面
最后再撒点盐
选poultry挡，好像是25分钟就做好了

【在 l*****r 的大作中提到】

: 无水炖鸡怎么做？

i*e2011-05-16 07:05

10 楼

恩，说得对，的确不能保证保持原有顺序。
那这样呢，假设三个 index 为 lo, mid, hi，并且同时满足以下条件：
A[i] < 0, All i < lo
A[j] == 0, i <= j < mid
A[k] > 0, mid <= k < hi
当 A[hi] 与 A[mid] 交换了之后，就把 A[mid+1] 到 A[hi-1] 往上移一步，再把原
来的 A[hi] 插入 A[mid+1] 的位置就好。这样能保证原有顺序。
至于最坏情况的复杂度呢，是否 O(N^2) 还有待验证。也有可能 amortized O(N) run
time.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*******i 的大作中提到】

: 如何保证负数内部和正数内部还是原来的顺序？
: Dutch national flag problem是不区分元素顺序的
: 这是stackoverflow上的讨论：
: http://stackoverflow.com/questions/5347616/how-to-sort-an-integ

l*r2011-05-16 07:05

11 楼

一点水都不用加？太神奇了。

【在 G*F 的大作中提到】

: 鸡切大块，用料酒，酱油，姜，五香粉，香油，泡发香菇，拌好放一个小时
: 胡萝卜，土豆切大块垫锅底，腌好的鸡肉铺在上面
: 最后再撒点盐
: 选poultry挡，好像是25分钟就做好了

b*r2011-05-16 07:05

12 楼

partition by 0 and then partition by 1
It scans twice.
Dutch flag sort is not stable. The other way is american flag sort, but it
takes two scans as well.

【在 g*******i 的大作中提到】

: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。

x*i2011-05-16 07:05

13 楼

鸡就直接放那个大锅里面，不是用碗装鸡放里面蒸？

【在 G*F 的大作中提到】

g*i2011-05-16 07:05

14 楼

partition by 0怎么保持顺序呢
能说具体点么

it

【在 b**********r 的大作中提到】

: partition by 0 and then partition by 1
: It scans twice.
: Dutch flag sort is not stable. The other way is american flag sort, but it
: takes two scans as well.

s*l2011-05-16 07:05

15 楼

有谁有好的菜谱么？我家买了一年半了，还没拆包。。而且当时还给我们寄了俩，结果
人家客服说另外那个寄回来运费太贵，你们就留着吧。。现在俩都在地下室闲置。。

f*42011-05-16 07:05

16 楼

x1 x2 x3 y1 z1 y2 x4 y3 z2 z3
xi<0; yi=0; z1>0
i指向x3， j指向x4
交换y2,x4
交换z1,x4
交换y1,x4
i指向x4, j指向y3
partition 0之后可以用i+1到数组结尾调用partition 1(如果数组是整数的话)
可能是O(n^2)

【在 g*******i 的大作中提到】

: partition by 0怎么保持顺序呢
: 能说具体点么
:
: it

G*F2011-05-16 07:05

17 楼

不用，鸡肉自己会出水。实在不放心，或想喝点汤底子可以加点点水

【在 l*****r 的大作中提到】

: 一点水都不用加？太神奇了。

d*l2011-05-16 07:05

18 楼

这个如果小于零的全在最后，大于零的全在最前，应该就是最朴素的O(n^2)，跟插入排
序的过程有点像

【在 f****4 的大作中提到】

: x1 x2 x3 y1 z1 y2 x4 y3 z2 z3
: xi<0; yi=0; z1>0
: i指向x3， j指向x4
: 交换y2,x4
: 交换z1,x4
: 交换y1,x4
: i指向x4, j指向y3
: partition 0之后可以用i+1到数组结尾调用partition 1(如果数组是整数的话)
: 可能是O(n^2)

G*F2011-05-16 07:05

19 楼

如果你拆了包就不会问这个问题了，我买的里面有毛毛妈图文并茂的中文菜谱。。。

【在 s****l 的大作中提到】

: 有谁有好的菜谱么？我家买了一年半了，还没拆包。。而且当时还给我们寄了俩，结果
: 人家客服说另外那个寄回来运费太贵，你们就留着吧。。现在俩都在地下室闲置。。

i*e2011-05-16 07:05

20 楼

不好意思，我之前的解答没考虑到还要对 ==0 的也进行数组移位。虽然 DNF 可以改进
来保持顺序，但由于数组移位的关系，复杂度肯定是 O(N^2)。那还不如用 insertion
sort. 感觉不可能会有 O(N) 的 in-place partition 并且保证顺序。唯一一个办法就
是用链表，那就能保证 O(N)。
我在网上找了找，应该就是这题啊，题目也没要求要保持顺序：
http://www.glassdoor.com/Interview/Partition-an-array-in-such-w
还有，另一点是这题也曾在 Programming pearls 出现过。在 Column 11 的第 11 条
练习题。这个 3-way partition 可是应用于 quicksort 里的。可以在网上搜 3-way
quicksort partition。quicksort 也不是 stable sort。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

G*F2011-05-16 07:05

21 楼

直接放那个大锅里是炖，用碗装鸡放里面是蒸，都可以。我是直接放那个大锅炖。

【在 x*****i 的大作中提到】

: 鸡就直接放那个大锅里面，不是用碗装鸡放里面蒸？

s*k2011-05-16 07:05

22 楼

similar to bubble sort.
only difference is swap 相邻两个元素
if ( a[j] > a[j+1] && a[j]*a[j+1] <= 0)

【在 g*******i 的大作中提到】

: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。

s*y2011-05-16 07:05

23 楼

我买的里面什么菜谱都没有。＠＠

【在 G*F 的大作中提到】

: 如果你拆了包就不会问这个问题了，我买的里面有毛毛妈图文并茂的中文菜谱。。。

g*i2011-05-16 07:05

24 楼

我有一个思路，是不是可以用类似于MergeSort的方法递归达到O(nlogn)
合并相邻的两个处理过的数列比如
x1,x2,x3,y,y,z1,z2,z3, 和 X1,X2,Y,Z1,Z2 (xi<0,y==0,z>0)
（1）反转z1到X2
（2）反转X1到X2，反转z1到z3
(3) 移动X1,X2到x3后，移动z1,z2,z3到Z1前，当中元素改为y==0
大家觉得有什么问题么？

t*32011-05-16 07:05

25 楼

same here

【在 s*****y 的大作中提到】

: 我买的里面什么菜谱都没有。＠＠

g*s2011-05-16 07:05

26 楼

since we dont care the stablility of 0, so, we can use the 0 to adjust.
if the (number of 0) / (number of array) is a constant level, it can be
solved by O(n).
assum number of 0 is k
1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
(n)
2. check if number of position < number of negative. pick smaller one to do
3-5. assume we choose positive number.
3. scan from end, non-0 number;
4. swap k position number with 0s
5. compact 0, go to 4, util all positive numbers are moved to the end.
6. compact 0 with negtive numbers.
e.g.
9 -3 0 2 -7 -1 5 -4 3 0 -6
1. -> 9 -3 2 -7 -1 5 -4 3 -6 0 0
-> 9 -3 2 -7 -1 0 -4 0 -6 5 3
-> 9 -3 2 -7 -1 0 -4 0 -6 5 3
-> 9 -3 2 -7 -1 -4 -6 0 0 5 3
-> 0 -3 0 -7 -1 -4 -6 9 2 5 3
-> -3 -7 -1 -4 -6 0 0 9 2 5 3

l*r2011-05-16 07:05

27 楼

maomaoma果然是instant pot的托儿！

【在 G*F 的大作中提到】

: 如果你拆了包就不会问这个问题了，我买的里面有毛毛妈图文并茂的中文菜谱。。。

g*e2011-05-16 07:05

28 楼

mark

O
do

【在 g***s 的大作中提到】

: since we dont care the stablility of 0, so, we can use the 0 to adjust.
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n).
: assum number of 0 is k
: 1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
: (n)
: 2. check if number of position < number of negative. pick smaller one to do
: 3-5. assume we choose positive number.
: 3. scan from end, non-0 number;
: 4. swap k position number with 0s

m*h2011-05-16 07:05

29 楼

是啊。我更喜欢。爱厨

maomaoma果然是instant pot的托儿！

【在 l*****r 的大作中提到】

: maomaoma果然是instant pot的托儿！

f*42011-05-16 07:05

30 楼

这个方法好
if the (number of 0) / (number of array) is a constant level, it can be
solved by O(n)么？
是不是你这里假设如果 (number of 0) = (length of array)/k , k>=1是constant
value？
如果前面的假设理解对的话，(number of 0) / (length of array) -> 0的话还是O(n^
2)?
考虑数组 2n+1长度
n个大于零的数在前 0 n个小于零的数在后面
每次只能移动1个大于零的数到数组后部，需要移动n个小于零的数

O
do

【在 g***s 的大作中提到】

S*A2011-05-16 07:05

31 楼

我的也没有中文菜谱，就是说明书上有示范讲解
食物每项如何用。

t*g2011-05-16 07:05

32 楼

Is this O(n)? The "compact 0" is not constant time.

O
do

【在 g***s 的大作中提到】

W*e2011-05-16 07:05

33 楼

Instant pot难道不是高压锅么？
为啥还跟普通高压锅比较？
有啥不一样的地方？

【在 G*F 的大作中提到】

g*s2011-05-16 07:05

34 楼

Yes. e.g. there is no 0.
otherwise, maybe we can use in-place merge which is used in stl
stable_sort().

n^

【在 f****4 的大作中提到】

: 这个方法好
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n)么？
: 是不是你这里假设如果 (number of 0) = (length of array)/k , k>=1是constant
: value？
: 如果前面的假设理解对的话，(number of 0) / (length of array) -> 0的话还是O(n^
: 2)?
: 考虑数组 2n+1长度
: n个大于零的数在前 0 n个小于零的数在后面
: 每次只能移动1个大于零的数到数组后部，需要移动n个小于零的数

S*A2011-05-16 07:05

35 楼

里面有压力和温度感应器和一个8位单片机控制。
最大的区别在于，电高压锅在压东西的时候不会
一直冒气，这样不用经常看着。味道也不会散发
到整个屋子都是。用的水也少些。在高压状态，
锅里面的水是不沸腾的。
主要区别是这个，还有电高压锅有不同的程序，
根据压力和温度做适当的反应，比较“智能”些。
可以设置好然后就不管了。普通高压锅要经常看着。

【在 W*******e 的大作中提到】

: Instant pot难道不是高压锅么？
: 为啥还跟普通高压锅比较？
: 有啥不一样的地方？

g*s2011-05-16 07:05

36 楼

Compact 0 is O(n). Just like in-place delete.
We only need to do n/k times. based on my assumption, it is a const.

【在 t******g 的大作中提到】

: Is this O(n)? The "compact 0" is not constant time.
:
: O
: do

f*r2011-05-16 07:05

37 楼

求菜谱

【在 G*F 的大作中提到】

t*g2011-05-16 07:05

38 楼

What's wrong with a simple insertion sort? Treat all negatives as equal and
all positives as equals also.

S*A2011-05-16 07:05

39 楼

http://www.mitbbs.com/article_t/Food/31874293.html

【在 f*******r 的大作中提到】

: 求菜谱

g*s2011-05-16 07:05

40 楼

Time concern. in-place merge sort is better.

and

【在 t******g 的大作中提到】

: What's wrong with a simple insertion sort? Treat all negatives as equal and
: all positives as equals also.

M*a2011-05-16 07:05

41 楼

一开始的料酒酱油都不用放进去对吧？
另外你买的是6-in-1 还是最新的？

【在 G*F 的大作中提到】

: 不用，鸡肉自己会出水。实在不放心，或想喝点汤底子可以加点点水

t*g2011-05-16 07:05

42 楼

That's right. How many times do you have to compact?

【在 g***s 的大作中提到】

: Compact 0 is O(n). Just like in-place delete.
: We only need to do n/k times. based on my assumption, it is a const.

r*a2011-05-16 07:05

43 楼

slow cooker煮稀饭和炖汤会不会更好些？买在那很久了没打开

m*q2011-05-16 07:05

44 楼

学习了

0 O
do

【在 g***s 的大作中提到】

G*F2011-05-16 07:05

45 楼

当然是放进去，一开始的料酒酱油没多少，大部分被鸡肉吸收了

【在 M*****a 的大作中提到】

: 一开始的料酒酱油都不用放进去对吧？
: 另外你买的是6-in-1 还是最新的？

g*s2011-05-16 07:05

46 楼

n/k times

【在 t******g 的大作中提到】

: That's right. How many times do you have to compact?

c*e2011-05-16 07:05

47 楼

哇，啥东西，听着好好啊

【在 G*F 的大作中提到】

t*g2011-05-16 07:05

48 楼

I see. You're changing the question.
If k/n is constant, do you have to compact 0 to benefit?

【在 g***s 的大作中提到】

: n/k times

c*e2011-05-16 07:05

49 楼

朋友，请接收我的label吧。

【在 s****l 的大作中提到】

t*g2011-05-16 07:05

50 楼

I see what's going on here. If there is no requirement of in-place for this
question, then it's very simple. By requiring constant portion of 0 in the
array, you actually gain space to get over the in-place hurdle.

【在 m**q 的大作中提到】

: 学习了
:
: 0 O
: do

c*e2011-05-16 07:05

51 楼

是不是那个尖帽子一样的锅，好像哪次新闻看过。

【在 G*F 的大作中提到】

: 不用，鸡肉自己会出水。实在不放心，或想喝点汤底子可以加点点水

g*s2011-05-16 07:05

52 楼

or do you have better solution? My solution is just using the k 0s as a
extra space. I mentioned in another post, if k<be used.

【在 t******g 的大作中提到】

: I see. You're changing the question.
: If k/n is constant, do you have to compact 0 to benefit?

C*m2011-05-16 07:05

53 楼

请问无水炖鸡的recipe，谢谢！

f*42011-05-16 07:05

54 楼

能说说in-place操作，到底是怎么要求的么？
比如说，当两个数交换的时候，给不给用temp变量啊？

【在 g***s 的大作中提到】

: or do you have better solution? My solution is just using the k 0s as a
: extra space. I mentioned in another post, if k<: be used.

S*y2011-05-16 07:05

55 楼

早上放肉，是不是订时在晚上回家时烧好？太早烧，会有问题吗？
★ 发自iPhone App: ChineseWeb 7.8

g*s2011-05-16 07:05

56 楼

In-place means using O(1) space. temp is needed.

【在 f****4 的大作中提到】

: 能说说in-place操作，到底是怎么要求的么？
: 比如说，当两个数交换的时候，给不给用temp变量啊？

c*e2011-05-16 07:05

57 楼

在哪买的，多少钱，我也想买一个，但是在本地店里买好贵。

【在 G*F 的大作中提到】

f*42011-05-16 07:05

58 楼

多谢

【在 g***s 的大作中提到】

: In-place means using O(1) space. temp is needed.

S*y2011-05-16 07:05

59 楼

团购，amazon

★ 发自iPhone App: ChineseWeb 7.8

【在 c*********e 的大作中提到】

: 在哪买的，多少钱，我也想买一个，但是在本地店里买好贵。

P*s2011-05-16 07:05

60 楼

这个锅没有那么神奇，我用了一年多了
就是一个高压锅，不锈钢内胆，带慢炖功能。

P*s2011-05-16 07:05

61 楼

你说的应该是塔吉锅，尖尖的顶。

【在 c********e 的大作中提到】

: 哇，啥东西，听着好好啊