求助， flood, mold - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

求助， flood, mold

求助， flood, mold# Living

l*e2014-01-21 08:01

1 楼

假设有一个stream of numbers （譬如stock prices)。在每个时刻，需要你能给出
the minimum number among the last k numbers. 有什么比较好的办法吗？
我给出的答案是用一个heap (priority queue)。但是面试官说这答案虽然可以接受，
但是有更好的。

c*72014-01-21 08:01

2 楼

开盘就跌了50%以上，牛X呵。。。

s*r2014-01-21 08:01

3 楼

前些日子contractor截错水管，厨房里的水大概2公分深。好在是水泥地面，损失相对
较小。当时我们就很担心mold,几个人再三向我们保证，气候干燥，不打开也没有问题
。到底放心不过，请mold公司的人来看，已经是一个月后了。检查后说橱柜下面风险不
小。打开一看，mold很严重，有些橱柜脚已经泡烂。厨房厅之间的墙下面很湿，虽然目
测还好，但mold公司的人说多半有mold.
这些日子很难过，厨房几乎无法使用，烘干，除湿，空气过滤就这样一起来。好在lab
结果出来，mold并不致命。contractor很想推到我们头上，mold公司的人说，如果两天
内打开看还有可能推到我们头上，一个月已经太晚了。现在的方案是要把发霉的板子去
除，但橱柜后的墙面情况还不清楚。
不知道这样flood会不会影响resale的价格。一年新的10K+的橱柜就这样坏了，修了也
是个refurbished很不爽。大家有没有碰到类似的倒霉事。都是怎么处理的。实在是有
点折腾不起了，如果用最保守的方法修，可以索赔吗？
谢谢，

j*82014-01-21 08:01

4 楼

Sliding window
[在 lurie (lurie) 的大作中提到：]
：假设有一个stream of numbers （譬如stock prices)。在每个时刻，需要你能给出
：the minimum number among the last k numbers. 有什么比较好的办法吗？
：...........

M*82014-01-21 08:01

5 楼

SYMBOL, DATE, PRICE, FORECAST, PERCENT
TSTR, 20101019, 0.0750, 0.1412, 188.3

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

: 开盘就跌了50%以上，牛X呵。。。

i*e2014-01-21 08:01

6 楼

不是很懂，帮楼主顶一下。
我在想如果是contractor 工作所失所照成，没有理由不能索赔的，或者去到小额法庭
。貌似修好得花不少钱，也可以试着和你的房屋保险公司联系。

lab

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

: 前些日子contractor截错水管，厨房里的水大概2公分深。好在是水泥地面，损失相对
: 较小。当时我们就很担心mold,几个人再三向我们保证，气候干燥，不打开也没有问题
: 。到底放心不过，请mold公司的人来看，已经是一个月后了。检查后说橱柜下面风险不
: 小。打开一看，mold很严重，有些橱柜脚已经泡烂。厨房厅之间的墙下面很湿，虽然目
: 测还好，但mold公司的人说多半有mold.
: 这些日子很难过，厨房几乎无法使用，烘干，除湿，空气过滤就这样一起来。好在lab
: 结果出来，mold并不致命。contractor很想推到我们头上，mold公司的人说，如果两天
: 内打开看还有可能推到我们头上，一个月已经太晚了。现在的方案是要把发霉的板子去
: 除，但橱柜后的墙面情况还不清楚。
: 不知道这样flood会不会影响resale的价格。一年新的10K+的橱柜就这样坏了，修了也

y*i2014-01-21 08:01

7 楼

is it sorted list?

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

: 假设有一个stream of numbers （譬如stock prices)。在每个时刻，需要你能给出
: the minimum number among the last k numbers. 有什么比较好的办法吗？
: 我给出的答案是用一个heap (priority queue)。但是面试官说这答案虽然可以接受，
: 但是有更好的。

M*82014-01-21 08:01

8 楼

http://yhoo.it/diBqbm

s*r2014-01-21 08:01

9 楼

谢谢，要联系保险公司一下。但一个是contractor失误，二是contractor明显耽误了修
理。不知道保险公司是否会受理。

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

: 不是很懂，帮楼主顶一下。
: 我在想如果是contractor 工作所失所照成，没有理由不能索赔的，或者去到小额法庭
: 。貌似修好得花不少钱，也可以试着和你的房屋保险公司联系。
:
: lab

l*e2014-01-21 08:01

10 楼

surely not...
具体情形就比如现实的stock prices，你知道所有的历史价格，要求过去几小时（或者
几天）的最低价格。

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

: is it sorted list?

f*i2014-01-21 08:01

11 楼

licensed and insured contractor？

lab

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

l*e2014-01-21 08:01

12 楼

多谢。Now I get it

【在 j*****8 的大作中提到】

: Sliding window
: [在 lurie (lurie) 的大作中提到：]
: ：假设有一个stream of numbers （譬如stock prices)。在每个时刻，需要你能给出
: ：the minimum number among the last k numbers. 有什么比较好的办法吗？
: ：...........

s*r2014-01-21 08:01

13 楼

yeah. It is licensed and insured contractor.
但是好像他们很不愿意走保险。听说很贵。我也不知道保险会怎么处理。修了就完了？
如果被flood,mold 的地方都移除，很麻烦，台面也保不住。但是如果简单修修，刚用
了大半年的柜子就成refurbished了，很不爽。他们没责任吗。还没算其他的麻烦。而
且整修没完，还要合作。
中国人的contractor,本来也不想怎么样，协商解决吧。但三番两次说可能是我们以前
自己漏水搞坏的，实在是出离愤怒。真不排除死磕。

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

: licensed and insured contractor？
:
: lab

g*d2014-01-21 08:01

14 楼

bloomberg?

f*i2014-01-21 08:01

15 楼

都这个地步了，还在为对方的几百块钱考虑？
你的损失好几千呢

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

: yeah. It is licensed and insured contractor.
: 但是好像他们很不愿意走保险。听说很贵。我也不知道保险会怎么处理。修了就完了？
: 如果被flood,mold 的地方都移除，很麻烦，台面也保不住。但是如果简单修修，刚用
: 了大半年的柜子就成refurbished了，很不爽。他们没责任吗。还没算其他的麻烦。而
: 且整修没完，还要合作。
: 中国人的contractor,本来也不想怎么样，协商解决吧。但三番两次说可能是我们以前
: 自己漏水搞坏的，实在是出离愤怒。真不排除死磕。

l*e2014-01-21 08:01

16 楼

不是，是投行quant。根本没想到会问算法，我从来没准备过。。。我就只能想出heap
的算法。幸好他也没指望我能想出最优解法

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

: bloomberg?

a*l2014-01-21 08:01

17 楼

走对方的保险

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

S*t2014-01-21 08:01

18 楼

deque 存non decreasing sequence

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

s*r2014-01-21 08:01

19 楼

多谢。只是真的有点折腾不动了。

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

: 都这个地步了，还在为对方的几百块钱考虑？
: 你的损失好几千呢

f*r2014-01-21 08:01

20 楼

您说的是non－increasing deque吧

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

: deque 存non decreasing sequence

s*r2014-01-21 08:01

21 楼

谢谢。

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

: 走对方的保险

S*t2014-01-21 08:01

22 楼

no, I meant what I said

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

: 您说的是non－increasing deque吧

i*e2014-01-21 08:01

23 楼

从楼主这个回复上感觉到问题似乎出在contractor 上。
如果下一次再有超过1000刀的装修，签合同前，有必要要求contractor 提供给你一份
执照和保险的copy,而且这是很合理的。如果现在有contractor 的 liability
insurance 或者是Contractor's Bond(看不同的州).
http://www.cslb.ca.gov/Contractors/MaintainLicense/BondRequirem
那么主动权就在你这边了。
从你表述的这些情况，感觉要测彻底修到满意，将会花许多钱，比装新的还麻烦。有必
要走Contractor 的保险如果他们有。

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

f*r2014-01-21 08:01

24 楼

具体算法在：http://stackoverflow.com/questions/29969345/find-the-lowest-number-from-last-k-elements-in-an-infinite-set-of-numbers

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

: no, I meant what I said

m*32014-01-21 08:01

25 楼

既然这Contractor有执照，有保险，而且照楼主所说，这问题很明显出在他们身上，那
还妄想不承担责任？强烈建议楼主和丫的死磕。

w*x2014-01-21 08:01

26 楼

应该是decreasing，我敢觉思路和min stack有点像

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

: 您说的是non－increasing deque吧

s*r2014-01-21 08:01

27 楼

受教了。确实没有要执照和保险。
用保险应该是比较省心的，但是argue走保险一定是不省心的。
谢谢。

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

: 从楼主这个回复上感觉到问题似乎出在contractor 上。
: 如果下一次再有超过1000刀的装修，签合同前，有必要要求contractor 提供给你一份
: 执照和保险的copy,而且这是很合理的。如果现在有contractor 的 liability
: insurance 或者是Contractor's Bond(看不同的州).
: http://www.cslb.ca.gov/Contractors/MaintainLicense/BondRequirem
: 那么主动权就在你这边了。
: 从你表述的这些情况，感觉要测彻底修到满意，将会花许多钱，比装新的还麻烦。有必
: 要走Contractor 的保险如果他们有。

S*t2014-01-21 08:01

28 楼

从进queue的顺序上看，queue里的元素是非递减的。
按照stackoverflow上的答案，里面假想元素是从左边入queue从右边出，所以从左
到右的顺序是非递增。
不过我鼓励尽量独立想问题，少看答案，实在想看，最好是看提示。

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

: 具体算法在：http://stackoverflow.com/questions/29969345/find-the-lowest-number-from-last-k-elements-in-an-infinite-set-of-numbers

k*r2014-01-21 08:01

29 楼

https://leetcode.com/problems/sliding-window-maximum/

f*r2014-01-21 08:01

30 楼

这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
均时间少，最坏时间比较差。
heap保证最坏时间都只是lg k。

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

: 从进queue的顺序上看，queue里的元素是非递减的。
: 按照stackoverflow上的答案，里面假想元素是从左边入queue从右边出，所以从左
: 到右的顺序是非递增。
: 不过我鼓励尽量独立想问题，少看答案，实在想看，最好是看提示。

x*z2014-01-21 08:01

31 楼

这个是平均O(1)的，因为每个元素最多add一次remove一次。用heap的话不止O(logn),
因为按顺序remove的时候需要O(n)。

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

: 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
: 均时间少，最坏时间比较差。
: heap保证最坏时间都只是lg k。

s*x2014-01-21 08:01

32 楼

Quick sort worst case O(n^2) heap sort worst nlogn.
但实际上sort 都是用Quicksort 做的。

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

: 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
: 均时间少，最坏时间比较差。
: heap保证最坏时间都只是lg k。

m*y2014-01-21 08:01

33 楼

这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
别了。
就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
function,要不有专门的优化过的库。
就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
件deque快的多。

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

:
: Quick sort worst case O(n^2) heap sort worst nlogn.
: 但实际上sort 都是用Quicksort 做的。

s*x2014-01-21 08:01

34 楼

stack
关键是 heap is not the right data structure for this. yeah, you can insert
in logN and find min in O(1), but it is tricky to remove one element out of
the window. you have to have some sort of index to the position in the
heap from the position in the sliding window. far worse than a queue, or
circular buffer, or even stack etc.

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

: 这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
: 别了。
: 就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
: 构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
: function,要不有专门的优化过的库。
: 就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
: 来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
: 件deque快的多。

w*12014-01-21 08:01

35 楼

确实啊，这题可以叫min queue，基本是一个思想

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

: 应该是decreasing，我敢觉思路和min stack有点像