请教：房子面积计算（纯技术） - 未名空间MITBBS历史存档

请教：房子面积计算（纯技术）# Living

L*e2010-09-13 07:09

1 楼

Implement a queue in which push_rear(), pop_front() and get_min() are all
constant time operations。
Copied from careercup. seemed no good solution discussed over there. 高手
share一下？thanks.

r*e2010-09-13 07:09

2 楼

因为两个人都工作，所以早晨没有多少时间。想在允许的时间内让孩子吃的好些。
儿子一般是快7点起床，起来换尿布后，放到high chair上开始吃cheerios, 吃不了多
少，好像一般是不饿，这时候大人在蒸鸡蛋羹或煎鸡蛋，好了后连哄带看iPad 能吃一
大半，然后和6oz奶。大人洗脸刷牙的时候，他自己玩玩，臭臭，最后换尿布，出门。
整个过程大约1小时10分钟。
总觉得他吃淀粉的东西少，大家有什么建议？

r*n2010-09-13 07:09

3 楼

美国的房子楼梯，走道，洗衣房计入面积吗？如果客厅是high ceiling，是两层的高度
，算多少面积？

g*s2010-09-13 07:09

4 楼

no, the commonly asked one is the stack, not the queue.
the hardness of queue is due to the fact the queue has 2 ends to take care
while the stack only have one.
it's an interesting variant of the classical one. but i don't feel there's
any good algo.

all

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

: Implement a queue in which push_rear(), pop_front() and get_min() are all
: constant time operations。
: Copied from careercup. seemed no good solution discussed over there. 高手
: share一下？thanks.

a*n2010-09-13 07:09

5 楼

几岁？
我们一岁后开始白天不怎么吃奶，但是吃饭也是猫一天狗一天，尤其早上，喝了6oz以
后基本就吃不下什么了，以前能吃个煎蛋，现在根本喂不进去，愁啊。

f*r2010-09-13 07:09

6 楼

除了车库地库。

L*e2010-09-13 07:09

7 楼

Thanks. Then what is the solution for stack? using a priority_queue?

s*l2010-09-13 07:09

8 楼

多大的娃？

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

: 因为两个人都工作，所以早晨没有多少时间。想在允许的时间内让孩子吃的好些。
: 儿子一般是快7点起床，起来换尿布后，放到high chair上开始吃cheerios, 吃不了多
: 少，好像一般是不饿，这时候大人在蒸鸡蛋羹或煎鸡蛋，好了后连哄带看iPad 能吃一
: 大半，然后和6oz奶。大人洗脸刷牙的时候，他自己玩玩，臭臭，最后换尿布，出门。
: 整个过程大约1小时10分钟。
: 总觉得他吃淀粉的东西少，大家有什么建议？

t*e2010-09-13 07:09

9 楼

凡是有地毯，hardwood floor, tile, vinyl etc.的都算，two-story living room
appracial 算一层，realtor算两层。

f*42010-09-13 07:09

10 楼

Use an extra stack to maintain the minimums.
To retrieve the current minimum, just return the top element from minimum
stack.
Each time you perform a push operation, check if the pushed element is a new
minimum. If it is, push it to the minimum stack too.
When you perform a pop operation, check if the popped element is the same as
the current minimum. If it is, pop it off the minimum stack too.

r*e2010-09-13 07:09

11 楼

回楼上两位：2岁

r*n2010-09-13 07:09

12 楼

不会吧，量了一下房子，按照你说的凡是有地毯、hardwood floor，tile，vinyle都算
，车库和房间连接处的洗衣房都加了，也只有county记录的面积的93％左右呀

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

: 凡是有地毯，hardwood floor, tile, vinyl etc.的都算，two-story living room
: appracial 算一层，realtor算两层。

D*y2010-09-13 07:09

13 楼

对
这是career cup 150题里面的一个例题
我记得programming interview那本书里也讲到了这道题

new
as

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

: Use an extra stack to maintain the minimums.
: To retrieve the current minimum, just return the top element from minimum
: stack.
: Each time you perform a push operation, check if the pushed element is a new
: minimum. If it is, push it to the minimum stack too.
: When you perform a pop operation, check if the popped element is the same as
: the current minimum. If it is, pop it off the minimum stack too.

r*e2010-09-13 07:09

14 楼

鸡蛋羹或煎蛋有没有什么办法加点什么进去就什么营养都有了？这样就吃煎蛋和奶好了
，奶他非常喜欢，一看到奶就迫不及待。

n*92010-09-13 07:09

15 楼

谁量的？

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

: 不会吧，量了一下房子，按照你说的凡是有地毯、hardwood floor，tile，vinyle都算
: ，车库和房间连接处的洗衣房都加了，也只有county记录的面积的93％左右呀

i*e2010-09-13 07:09

16 楼

这题用两个 queue 就行了。
一个 queue 来 maintain minimums，另一个 queue 来 push_rear 和 pop_front.
每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
每次 pop_front 的时候，就检查现在 pop 的元素是否与 current min 相等。如果是
的话，就从 queue 和 min queue 同时 pop.
其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
因为同样一个 data structure 就直接能应用于 finding sliding window minimum，
并且得到 O(N) 的复杂度。
Reference:
http://www.ihas1337code.com/2010/11/stack-that-supports-push-po
http://www.ihas1337code.com/2011/01/sliding-window-maximum.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

s*l2010-09-13 07:09

17 楼

2岁的daycare一般会给早饭吧，7点多的确有点早。

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

: 回楼上两位：2岁

p*e2010-09-13 07:09

18 楼

一般是沿房子外墙量，车库地下室不算。
所以，在屋内量的话，自然比标称面积少。银行请的appraiser也是这么量。

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

: 美国的房子楼梯，走道，洗衣房计入面积吗？如果客厅是high ceiling，是两层的高度
: ，算多少面积？

c*t2010-09-13 07:09

19 楼

好像不太对啊。比如 1，3，2 按描述
每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
那么到2入queue的时候，min queue里面是（1，3），2>1，所以2就直接入min queue
，变为（1，3，2），就不对了。
sliding window我没见过，就去搜了一下，好像用的是vector, 要去掉vector中所有比
新值大的的元素,而不是只比较最后的元素吧？

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

: 这题用两个 queue 就行了。
: 一个 queue 来 maintain minimums，另一个 queue 来 push_rear 和 pop_front.
: 每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
: 话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
: 每次 pop_front 的时候，就检查现在 pop 的元素是否与 current min 相等。如果是
: 的话，就从 queue 和 min queue 同时 pop.
: 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
: 因为同样一个 data structure 就直接能应用于 finding sliding window minimum，
: 并且得到 O(N) 的复杂度。
: Reference:

s*l2010-09-13 07:09

20 楼

用牛奶卧鸡蛋，牛奶里面再加点oatmeal?

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

: 鸡蛋羹或煎蛋有没有什么办法加点什么进去就什么营养都有了？这样就吃煎蛋和奶好了
: ，奶他非常喜欢，一看到奶就迫不及待。

t*m2010-09-13 07:09

21 楼

量外面。

都算

【在 n*******9 的大作中提到】

: 谁量的？

i*e2010-09-13 07:09

22 楼

是检查minqueue 的后面，不时前面。
minqueue = [1, 3], push 2 的时候，因为 3 > 2，pop 3 from back，然后再比较 1
和 2. 因为 1 <= 2，那就把 2 push 进 minqueue。这时候 minqueue = [1, 2].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

queue

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

: 好像不太对啊。比如 1，3，2 按描述
: 每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
: 话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
: 那么到2入queue的时候，min queue里面是（1，3），2>1，所以2就直接入min queue
: ，变为（1，3，2），就不对了。
: sliding window我没见过，就去搜了一下，好像用的是vector, 要去掉vector中所有比
: 新值大的的元素,而不是只比较最后的元素吧？

V*o2010-09-13 07:09

23 楼

坐上车以后在手里塞两块饼干就有淀粉了。娃在路上的时间要充分利用。

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

: 因为两个人都工作，所以早晨没有多少时间。想在允许的时间内让孩子吃的好些。
: 儿子一般是快7点起床，起来换尿布后，放到high chair上开始吃cheerios, 吃不了多
: 少，好像一般是不饿，这时候大人在蒸鸡蛋羹或煎鸡蛋，好了后连哄带看iPad 能吃一
: 大半，然后和6oz奶。大人洗脸刷牙的时候，他自己玩玩，臭臭，最后换尿布，出门。
: 整个过程大约1小时10分钟。
: 总觉得他吃淀粉的东西少，大家有什么建议？

g*s2010-09-13 07:09

24 楼

in this case how u ensure O(1)?

1

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

: 是检查minqueue 的后面，不时前面。
: minqueue = [1, 3], push 2 的时候，因为 3 > 2，pop 3 from back，然后再比较 1
: 和 2. 因为 1 <= 2，那就把 2 push 进 minqueue。这时候 minqueue = [1, 2].
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: queue

r*e2010-09-13 07:09

25 楼

没办法啊，早上我们只有一个小时的时间。

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

: 2岁的daycare一般会给早饭吧，7点多的确有点早。

m*i2010-09-13 07:09

26 楼

minimum
new
same as
这个解对所有数字unique有效，如果可以duplication.那要小改一下

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

: Use an extra stack to maintain the minimums.
: To retrieve the current minimum, just return the top element from minimum
: stack.
: Each time you perform a push operation, check if the pushed element is a new
: minimum. If it is, push it to the minimum stack too.
: When you perform a pop operation, check if the popped element is the same as
: the current minimum. If it is, pop it off the minimum stack too.

s*l2010-09-13 07:09

27 楼

我的意思是说，daycare给早饭，在家吃不吃不是什么问题。

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

: 没办法啊，早上我们只有一个小时的时间。

c*t2010-09-13 07:09

28 楼

赞！明白了！
不过push rear 的操作不能保证是O(1）吧。极端的情况可能是O(n), 比如 2，3，4，5
，1. push 1的时候,要在min queue比较删除前4个

1

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

: 是检查minqueue 的后面，不时前面。
: minqueue = [1, 3], push 2 的时候，因为 3 > 2，pop 3 from back，然后再比较 1
: 和 2. 因为 1 <= 2，那就把 2 push 进 minqueue。这时候 minqueue = [1, 2].
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: queue

r*e2010-09-13 07:09

29 楼

我们儿子去的daycare没有早饭，也没有中饭，晚饭也没有。

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

: 我的意思是说，daycare给早饭，在家吃不吃不是什么问题。

c*t2010-09-13 07:09

30 楼

只要小于等于minimum top的都push into stack就好了

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

:
: minimum
: new
: same as
: 这个解对所有数字unique有效，如果可以duplication.那要小改一下

r*f2010-09-13 07:09

31 楼

什么意思？你可以把cheerios换成面包馒头花卷吧

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

: 因为两个人都工作，所以早晨没有多少时间。想在允许的时间内让孩子吃的好些。
: 儿子一般是快7点起床，起来换尿布后，放到high chair上开始吃cheerios, 吃不了多
: 少，好像一般是不饿，这时候大人在蒸鸡蛋羹或煎鸡蛋，好了后连哄带看iPad 能吃一
: 大半，然后和6oz奶。大人洗脸刷牙的时候，他自己玩玩，臭臭，最后换尿布，出门。
: 整个过程大约1小时10分钟。
: 总觉得他吃淀粉的东西少，大家有什么建议？

i*e2010-09-13 07:09

32 楼

你说的没错，依你这种最坏情况在 push 1 的时候是 O(N)，但是其余的 operations
都是 O（1）的。而这最坏的情况是出现于在 push 了 N 个元素之后，在 push 一个最
小值，使得这个 operation 为 O(N).根据 amortized analysis，这平均复杂度为 O(N
)/N = O(1).当 push 了这个最小值之后，又不可能立刻出现 O(N) 的状况了。
请参考：
http://en.wikipedia.org/wiki/Amortized_analysis
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

，5

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

: 赞！明白了！
: 不过push rear 的操作不能保证是O(1）吧。极端的情况可能是O(n), 比如 2，3，4，5
: ，1. push 1的时候,要在min queue比较删除前4个
:
: 1

D*R2010-09-13 07:09

33 楼

我自己的经验是早晨刚起来没活动的时候，啥都吃不下去。
我家早晨时间充足，躺床上先喝6oz奶，然后下地吃他爱吃的水果，如果有muffin，他
会很爱吃，不过我懒得做。
好像我家也很少吃淀粉。。。
我看costco有卖现成的pancake mix的，要不要试试？
还有我认识的娃很爱吃米粥拌蛋黄的，大早上有点汤水更舒服，可惜我娃过敏。。
我自己早晨喜欢汤面，可惜没啥时间做。。。

c*t2010-09-13 07:09

34 楼

多谢，多谢！

(N

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

: 你说的没错，依你这种最坏情况在 push 1 的时候是 O(N)，但是其余的 operations
: 都是 O（1）的。而这最坏的情况是出现于在 push 了 N 个元素之后，在 push 一个最
: 小值，使得这个 operation 为 O(N).根据 amortized analysis，这平均复杂度为 O(N
: )/N = O(1).当 push 了这个最小值之后，又不可能立刻出现 O(N) 的状况了。
: 请参考：
: http://en.wikipedia.org/wiki/Amortized_analysis
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: ，5

b*d2010-09-13 07:09

35 楼

早上是要多吃淀粉的，淀粉提供一天脑子活动需要的酮。
我们早上cheerios＋牛奶，中国店买的各种包子，糯米鸡什么的，微波炉热完掰开，2
分钟就凉下来了。用toaster oven热waffle, pancake, 切片面包什么的，很快，加一
点黄油，再切一块奶酪。有时候会煎蛋，但是那个要等凉下来需要挺长时间的，LZ家恐
怕来不及。

e*a2010-09-13 07:09

36 楼

ihasleetcode, 我怎么觉得第二个用来存minimums的queue, 跟任何时候只保持当前
minimum相比，没有什么优势呢？原因是这样的:
如果旧的minimum被pop了，要找新的minimum, 如果新的min离对头很近，也不用O(n),
如果离得很远，是要O(n), 但是这种情况下，你的push_rear()操作也要O(n),因为你从
min queue里pop走了很多比新的min大的元素。
所以说，只keep record of current min有类似O(1)的复杂度.请问是这样么？谢谢

a*n2010-09-13 07:09

37 楼

煎蛋里加一两勺shredded cheese，或者用butter煎蛋。

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

: 鸡蛋羹或煎蛋有没有什么办法加点什么进去就什么营养都有了？这样就吃煎蛋和奶好了
: ，奶他非常喜欢，一看到奶就迫不及待。

e*a2010-09-13 07:09

38 楼

对 1，2，3，4，5，6 输入序列，ihasleetcode 你的复杂度是 O(1)的，我的是O(n)的
。

m*a2010-09-13 07:09

39 楼

孩子喜欢变化，要换换样子孩子就喜欢了。比如单一颜色的换多种颜色的cheerios，小
小孩要喂，一边喂一边鼓励。粥可以加肉末鸡蛋豆类煮，还可以上咸菜，少点就是了。
或者上番茄酱。蛋可以煎蛋或者切白煮蛋蘸酱，总之，各种花样吧。还有，吃饭就吃
饭，不能上玩具

h*k2010-09-13 07:09

40 楼

这里用来保存minimums的不能是queue，因为queue严格讲只提供了两个操作，从前面
pop()和从后面push()。你不能从一
个queue的后面pop。这里可以用doubly linked list来做这个。

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

: 这题用两个 queue 就行了。
: 一个 queue 来 maintain minimums，另一个 queue 来 push_rear 和 pop_front.
: 每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
: 话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
: 每次 pop_front 的时候，就检查现在 pop 的元素是否与 current min 相等。如果是
: 的话，就从 queue 和 min queue 同时 pop.
: 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
: 因为同样一个 data structure 就直接能应用于 finding sliding window minimum，
: 并且得到 O(N) 的复杂度。
: Reference:

M*n2010-09-13 07:09

41 楼

waffles made with pancake mix, egg, butter and (peanut butter/chocolate chip
, etc)... use cooke cutters to cut into different shapes...

i*e2010-09-13 07:09

42 楼

恩，对。
如果 double ended queue 应该可以吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 这里用来保存minimums的不能是queue，因为queue严格讲只提供了两个操作，从前面
: pop()和从后面push()。你不能从一
: 个queue的后面pop。这里可以用doubly linked list来做这个。

o*n2010-09-13 07:09

43 楼

吃面包吗？Costco的全美面包，做成french toast，我闺女能吃一片半
我闺女一起床先给喝奶，8oz，饿了一晚上，一口气就喝完了，然后玩，我们准备好早
饭后和我们一起吃，再吃一个鸡蛋，一片面包，前后也差不多一小时
小娃娃一下子不能吃很多东西，你早上有一小时时间，试试先喝奶，过半小时再吃面食
如果你们不介意给宝宝果酱，可以在面包上抹点果酱，有味道了人家估计就爱吃了

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

: 因为两个人都工作，所以早晨没有多少时间。想在允许的时间内让孩子吃的好些。
: 儿子一般是快7点起床，起来换尿布后，放到high chair上开始吃cheerios, 吃不了多
: 少，好像一般是不饿，这时候大人在蒸鸡蛋羹或煎鸡蛋，好了后连哄带看iPad 能吃一
: 大半，然后和6oz奶。大人洗脸刷牙的时候，他自己玩玩，臭臭，最后换尿布，出门。
: 整个过程大约1小时10分钟。
: 总觉得他吃淀粉的东西少，大家有什么建议？

s*v2010-09-13 07:09

44 楼

en, 和那个stack的题目思路类似..

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

: 这题用两个 queue 就行了。
: 一个 queue 来 maintain minimums，另一个 queue 来 push_rear 和 pop_front.
: 每次 push 一个新元素的时候，检查 min queue 的后面的值是否大于新值。如果是的
: 话，就一直 pop，直到后边值小于或者等于新值（或者 min queue 为空）。
: 每次 pop_front 的时候，就检查现在 pop 的元素是否与 current min 相等。如果是
: 的话，就从 queue 和 min queue 同时 pop.
: 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
: 因为同样一个 data structure 就直接能应用于 finding sliding window minimum，
: 并且得到 O(N) 的复杂度。
: Reference:

D*R2010-09-13 07:09

45 楼

哦，对了，我娃本来对面包兴趣不大，后来我们买了个cut模具，切出来都是小汽车图
案的，娃特别喜欢，是在local 日本店买的

b*y2010-09-13 07:09

46 楼

Great idea!

【在 D**********R 的大作中提到】

: 哦，对了，我娃本来对面包兴趣不大，后来我们买了个cut模具，切出来都是小汽车图
: 案的，娃特别喜欢，是在local 日本店买的