Redian新闻
>
[包子急问]这个home inspector可用么?
avatar
[包子急问]这个home inspector可用么?# Living
n*s
1
之前面试碰到的一个题,一直没找到好的解法, 和大家分享一下
有N 个set, e.g. {a,b,c,}, {b, c}, {a,c,d} .... 要求去掉能被其他set包含的set。
比如 上面三个set 要去掉{b,c}
不知道是不是有什么数据结构可以O(N)弄出来.
avatar
b*g
2
agent推荐的,不过网上查的是Complete ASHI Certified Home Inspections,yelp和
www.ashi.org都有他。是不是就说明他还算可靠?
avatar
h*l
3
弄个hashtable记录是否出现过
如果有一个set里面没有新的,就删除
不就是 o(n)吗

set。

【在 n********s 的大作中提到】
: 之前面试碰到的一个题,一直没找到好的解法, 和大家分享一下
: 有N 个set, e.g. {a,b,c,}, {b, c}, {a,c,d} .... 要求去掉能被其他set包含的set。
: 比如 上面三个set 要去掉{b,c}
: 不知道是不是有什么数据结构可以O(N)弄出来.

avatar
c*h
4
问他有无实际建筑经验,自己盖过房子没有。最好是做过builder或者carpenter. 是
licensed contractor的更好。有的inspector半路出家的,也就handyman的水平。
另外要看inspector对附近的房子常见问题是否熟悉,在附近有没做过inspection。
如果找不到local的inspector, 也可以向他要sample report,看report里面是否表现
inspector的水平。最基本的是要上房顶,走阁楼,钻crawl space。如果当地雨水多,
可以考虑找个雨天做inspection.

【在 b******g 的大作中提到】
: agent推荐的,不过网上查的是Complete ASHI Certified Home Inspections,yelp和
: www.ashi.org都有他。是不是就说明他还算可靠?

avatar
j*e
5
除了N,还有set的最大size (K)要考虑吧。
假如K是很小的常数,可以建一个大的Hashtable,把每个set的所有subset
(O(N*2^K)但是K是constant)都放进去,然后扫描一遍就知道了。

set。

【在 n********s 的大作中提到】
: 之前面试碰到的一个题,一直没找到好的解法, 和大家分享一下
: 有N 个set, e.g. {a,b,c,}, {b, c}, {a,c,d} .... 要求去掉能被其他set包含的set。
: 比如 上面三个set 要去掉{b,c}
: 不知道是不是有什么数据结构可以O(N)弄出来.

avatar
S*h
6
O(n)不知道,我的想法是降低比较每两个set的复杂度。可以用一个int来代表一个set,
a对应0位,z对应25位。这样 if( x & y == x) x就是y的子集,可以直接去掉x。因为
是x的子集肯定是y的子集。
复杂度应该是n^2

【在 h**********l 的大作中提到】
: 弄个hashtable记录是否出现过
: 如果有一个set里面没有新的,就删除
: 不就是 o(n)吗
:
: set。

avatar
S*h
7
O(n)不知道,我的想法是降低比较每两个set的复杂度。可以用一个int来代表一个set,
a对应0位,z对应25位。这样 if( x & y == x) x就是y的子集,可以直接去掉x。因为
是x的子集肯定是y的子集。
复杂度应该是n^2

【在 h**********l 的大作中提到】
: 弄个hashtable记录是否出现过
: 如果有一个set里面没有新的,就删除
: 不就是 o(n)吗
:
: set。

avatar
p*2
8
不考虑每个set的size的话,可以O(n)
avatar
l*8
9
你还不去睡觉?

【在 p*****2 的大作中提到】
: 不考虑每个set的size的话,可以O(n)
avatar
S*h
10
求idea

【在 p*****2 的大作中提到】
: 不考虑每个set的size的话,可以O(n)
avatar
p*2
11

这么早睡什么呀?

【在 l*********8 的大作中提到】
: 你还不去睡觉?
avatar
p*2
12

刚才想的不对。不好意思。

【在 S****h 的大作中提到】
: 求idea
avatar
t*h
13
只能想到O(n^2)的,哪位大牛给个O(n)的解法?

set。

【在 n********s 的大作中提到】
: 之前面试碰到的一个题,一直没找到好的解法, 和大家分享一下
: 有N 个set, e.g. {a,b,c,}, {b, c}, {a,c,d} .... 要求去掉能被其他set包含的set。
: 比如 上面三个set 要去掉{b,c}
: 不知道是不是有什么数据结构可以O(N)弄出来.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。