小孩子6岁，咬被被，都咬了两个洞了，需要吃药吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Parenting - 为人父母

小孩子6岁，咬被被，都咬了两个洞了，需要吃药吗？

小孩子6岁，咬被被，都咬了两个洞了，需要吃药吗？# Parenting - 为人父母

l*b2014-05-21 07:05

1 楼

一个有口音的同学，不是老印。因为名字很米国。
一开始问什么是好的hashing function，我就说第一要简单啊，第二要能evenly
distribute。然后对方问，用memory address可以不？我说不太好吧。我觉得如果用
memory的话是不是浪费很多空间，然后说了equal的object可能给不同的hash value，
然后对方抓着我说为什么java用了memory address，我说那个是default的啊，他们不
能知道具体怎么hash啊，所以用memory address啊。然后他还不满意，我就说还有就是
因为用memory address的话，你等于要reserve所有memory space给hashing了。但是说
完，发现错了，可以用module的。反正问到最后没办法，我正在这边给中指，他在那边
不耐烦。最后我承认我不会。结束话题。后来聊天的时候想起来居然SB的没有说
collision的东西。太弱了。
接着给了一个coding的题目。很简单，实现一个InfiniteArray。然后我就写了一个
index用int的。然后用java的array做background的data structure。什么overflow，
negative index，等等情况都考虑了。写完以后他说可以。然后问什么效率，我就说因
为每次碰到index比现在array的size大的话，我就double，所以应该是一个o(logn)的
效率，因为你就只能double这么多次。然后主要的时间是花在copy旧的array到新的
array了。然后他也不值可否。
然后出了个follow up。说如果要实现array.set(Long.MAX_VALUE, value)的话怎么办
？就是说如果index是个long的话怎么实现。我说那就放external disk罗。没办法的话
，就分文件放。我的想法是如果array里面的值很少的话，这样是可行的。后来他提示
说，long多大啊，现在也没有这么大的硬盘能放吧，我才猛然醒悟，觉得他要问的是
HashMap，我就说那可以用HashMap吧。然后接着问，HashMap和Array做data structure
，各自有什么好处。我说Array相对来说应该省空间一些。HashMap应该更占空间。对方
大哥居然问我具体多用多少空间！我当时就树中指了。我就想了一下，说一般HashMap
这些都是一单满了一半就double size，所以应该是比array多了一倍吧。现在回想起来
，我觉得对方应该一开始就希望我用HashMap来写。但是后面他自己也说各有各的好处。
终结，很多东西平时觉得还行，真的被人往死里考，就会有doubt了。然后就是写code
觉得还不错，可能因为题目不难吧。这次肯定分母了。就当赞RP了。

j*n2014-05-21 07:05

2 楼

小孩子6岁，咬被被，都咬了两个洞了，需要吃药吗？

A*u2014-05-21 07:05

3 楼

我日
这全是细节啊

x*j2014-05-21 07:05

4 楼

what？没看懂你在说什么。

b*u2014-05-21 07:05

5 楼

是俄国人吧

s*e2014-05-21 07:05

6 楼

弄点苦瓜汁在被角上试试？

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

: 小孩子6岁，咬被被，都咬了两个洞了，需要吃药吗？

l*b2014-05-21 07:05

7 楼

名字很米国，我也就不猜是那里人了。也没什么意思。

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

: 是俄国人吧

a*m2014-05-21 07:05

8 楼

老干妈是不是效果更好点，呵呵

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

: 弄点苦瓜汁在被角上试试？

f*t2014-05-21 07:05

9 楼

bless

g*e2014-05-21 07:05

10 楼

你基础不行

k*x2014-05-21 07:05

11 楼

everybody loves hash table, lol.

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

: 一个有口音的同学，不是老印。因为名字很米国。
: 一开始问什么是好的hashing function，我就说第一要简单啊，第二要能evenly
: distribute。然后对方问，用memory address可以不？我说不太好吧。我觉得如果用
: memory的话是不是浪费很多空间，然后说了equal的object可能给不同的hash value，
: 然后对方抓着我说为什么java用了memory address，我说那个是default的啊，他们不
: 能知道具体怎么hash啊，所以用memory address啊。然后他还不满意，我就说还有就是
: 因为用memory address的话，你等于要reserve所有memory space给hashing了。但是说
: 完，发现错了，可以用module的。反正问到最后没办法，我正在这边给中指，他在那边
: 不耐烦。最后我承认我不会。结束话题。后来聊天的时候想起来居然SB的没有说
: collision的东西。太弱了。

y*g2014-05-21 07:05

12 楼

请问楼主面的哪里的google

l*b2014-05-21 07:05

13 楼

我也不知道，不好意思。Recuriter说会帮我都投。我也没关心具体那个office的。但
是面试的时间约的是PST的，应该是MV的吧.

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

: 请问楼主面的哪里的google

s*c2014-05-21 07:05

14 楼

"每次碰到index比现在array的size大的话，我就double，所以应该是一个o(logn)的
效率"
-- amortized complexity of vector doubling should be o(1)

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

l*b2014-05-21 07:05

15 楼

好吧，我不是google的料，已经move on。谢谢。

d*g2014-05-21 07:05

16 楼

感觉memory address那儿答得没啥问题啊~

y*o2014-05-21 07:05

17 楼

然后出了个follow up。说如果要实现array.set(Long.MAX_VALUE, value)的话怎么办
？就是说如果index是个long的话怎么实现。我说那就放external disk罗。没办法的话
，就分文件放。我的想法是如果array里面的值很少的话，这样是可行的。后来他提示
说，long多大啊，现在也没有这么大的硬盘能放吧，我才猛然醒悟，觉得他要问的是
HashMap，我就说那可以用HashMap吧。然后接着问，HashMap和Array做data structure
，各自有什么好处。我说Array相对来说应该省空间一些。HashMap应该更占空间。对方
大哥居然问我具体多用多少空间！我当时就树中指了。我就想了一下，说一般HashMap
这些都是一单满了一半就double size，所以应该是比array多了一倍吧。现在回想起来
，我觉得对方应该一开始就希望我用HashMap来写。但是后面他自己也说各有各的好处
彻底不懂，为啥long就要用hashmap呀？如果硬盘不够，array比hash升空间，用
hashmap有什么好处呢

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

o*d2014-05-21 07:05

18 楼

you are right, using memory address is default
but the reason for most JDK classes override hashCode() is that, we always
want hashCode() to be "compatible" with equals(); that is, if a.equals(b),
then we want a.hashCode() == b.hashCode()
otherwise, if we have two string instance str1="abc", str2="abc"
then their hash values will be different, which is weird

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

t*02014-05-21 07:05

19 楼

LZ，你不冤枉

l*b2014-05-21 07:05

20 楼

这个我后来说了的，equals的object可能hash不同，他表示我之前没有告诉他。然后说
我说得用memory address不是hashing function，我说没有啊，我说的不是good
hashing。反正吵来吵去。真的没什么意思。

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

: you are right, using memory address is default
: but the reason for most JDK classes override hashCode() is that, we always
: want hashCode() to be "compatible" with equals(); that is, if a.equals(b),
: then we want a.hashCode() == b.hashCode()
: otherwise, if we have two string instance str1="abc", str2="abc"
: then their hash values will be different, which is weird

l*b2014-05-21 07:05

21 楼

有啥子冤枉的？不行就是不行。很多大牛都还被刷呢，我心满意足了。
再次表示，justtry面试的题目我到现在为止都没看懂。

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

: LZ，你不冤枉

d*g2014-05-21 07:05

22 楼

仔细说说具体问题在哪儿？

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

: LZ，你不冤枉

a*e2014-05-21 07:05

23 楼

但凡有 GC 的语言，是不可以用 memory address 做 hash key 的，因为会变。
http://stackoverflow.com/questions/13257553/memory-address-as-h

M*k2014-05-21 07:05

24 楼

成了学术贴

l*b2014-05-21 07:05

25 楼

并不是说用memory address真的做hash，java的object的hashCode好像是一个用内存地
址生成的[email protected]这样来的。具体前面那个我不敢肯定，但是我印象中是和memory
address有关系的。
和人谈话，你说2句就可以知道这个人具体怎么样了。我个人的感觉是对方比较冲。抓
着我问为什么用memory address不好的话java还要default用这个。为什么不能throw
exception。他说这个以后我真心不理解什么意思了。
当然和大牛说的一样，我基础比较差。毕竟毕业几年，很多基本的概念真的不能说全部
记得。我自己的理解就是一个好的hashing function就是要简单，然后能evenly
distribute。其他的平时真的没具体注意了。
后面写完code以后分析efficiency的时候我已经有点不耐烦了。所以错很多，其实我说
o(logn)的时候自己都知道是o(1)的，但是一下子阴差阳错就说了个o(logn)。

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

: 但凡有 GC 的语言，是不可以用 memory address 做 hash key 的，因为会变。
: http://stackoverflow.com/questions/13257553/memory-address-as-h

c*e2014-05-21 07:05

26 楼

这到底是考什么呀，和工作一点都不沾边，没问你做j2ee,c#之类的问题？
hashtable搞这么多，有意思吗？程序员只要知道怎么用就行了。

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

v*n2014-05-21 07:05

27 楼

悲剧完全记不起来什么是哈希的人默默飘过

t*02014-05-21 07:05

28 楼

都是基础题啊。
hash那个你自己不也知道自己想岔了几次么？
coding这个刚开始想岔了就算了，后面你已经明白要hashmap了，就应该想到那是个
sparse array，居然还说hash更占空间。

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

:
: 仔细说说具体问题在哪儿？

J*a2014-05-21 07:05

29 楼

有两个错误很明显啊数组自动double怎么会是O(log n)呢肯定还是O(1)啊
最后一题当然是hashmap省空间 array都比hash省空间的话还要hash做什么。。。完
全答反考官可能就印象不太好了

J*a2014-05-21 07:05

30 楼

除非简历上写了J2EE或者c# 否则问到的机率还不如hashtable吧

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

: 这到底是考什么呀，和工作一点都不沾边，没问你做j2ee,c#之类的问题？
: hashtable搞这么多，有意思吗？程序员只要知道怎么用就行了。

l*b2014-05-21 07:05

31 楼

这个不是我问的。
对方没说是sparse array，讨论的时候问的是什么时候array好，什么时候HashMap好。
一开始coding我问有什么要求，对方说没有，看你自己。我就说那我用Array，对方没
表示，coding完加问的如果index用long怎么弄。
hash那个想错很多，我刚刚才放映过来吧toString想成hashCode了。

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

: 都是基础题啊。
: hash那个你自己不也知道自己想岔了几次么？
: coding这个刚开始想岔了就算了，后面你已经明白要hashmap了，就应该想到那是个
: sparse array，居然还说hash更占空间。

l*b2014-05-21 07:05

32 楼

这个我可以完全反给你啊，Hash都比Array还省空间的话，要Array干嘛？这个要看情况
的吧。你怎么知道一定是sparse的array。
我不知道你们有没有实际的工作经验，你们自己去看看自己写的code，那个array可能
是sparse的。我还真没见过那个initializ一个100个element的array然后只用一个。
我不是反驳我多厉害，我基础是很差，我不否认，写这个是分享经验。不是吐槽面试官。

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

: 有两个错误很明显啊数组自动double怎么会是O(log n)呢肯定还是O(1)啊
: 最后一题当然是hashmap省空间 array都比hash省空间的话还要hash做什么。。。完
: 全答反考官可能就印象不太好了

J*a2014-05-21 07:05

33 楼

这个明显是答反了还要强词夺理。。。
人家都说了index是long，还可能不sparse？

官。

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

: 这个我可以完全反给你啊，Hash都比Array还省空间的话，要Array干嘛？这个要看情况
: 的吧。你怎么知道一定是sparse的array。
: 我不知道你们有没有实际的工作经验，你们自己去看看自己写的code，那个array可能
: 是sparse的。我还真没见过那个initializ一个100个element的array然后只用一个。
: 我不是反驳我多厉害，我基础是很差，我不否认，写这个是分享经验。不是吐槽面试官。

l*b2014-05-21 07:05

34 楼

大哥/大姐，人家问用Array和HashMap做data structure分别有什么好处。和用long做
index是2个问题。我是不是应该说如果data set不是sparse的话，HashMap会比Array用
更多的空间？
我有啥子强词夺理的，现在完全是事后诸葛亮，你硬要说Array比HashMap多用空间，那
我也没办法。

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

: 这个明显是答反了还要强词夺理。。。
: 人家都说了index是long，还可能不sparse？
:
: 官。

J*a2014-05-21 07:05

35 楼

好吧如果是分开的两道题当我没说
不过单独问数组和hash哪个好最大的区别应该是查找复杂度一个O(n)一个O(1)

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

: 大哥/大姐，人家问用Array和HashMap做data structure分别有什么好处。和用long做
: index是2个问题。我是不是应该说如果data set不是sparse的话，HashMap会比Array用
: 更多的空间？
: 我有啥子强词夺理的，现在完全是事后诸葛亮，你硬要说Array比HashMap多用空间，那
: 我也没办法。

l*b2014-05-21 07:05

36 楼

纯学术啊，Array为什么要查找啊？Array如果查找的话就是查找index指向那个东西吧
？那样，为什么Array Based的是O(n)？为什么hash的是o(1)？
整个class就要求set(int index, T t)和get(int index)这2个方法。我觉得coding那
块真没什么好说的，题目比较简单。就注意一下overflow什么的就可以了。如果说真的
他一开始就想让我用HashMap写的话，那更没意思了。那是完全无聊了。
基础差+老年痴呆+上礼拜东岸飞西岸真的很累，所以很多东西没答出来。

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

: 好吧如果是分开的两道题当我没说
: 不过单独问数组和hash哪个好最大的区别应该是查找复杂度一个O(n)一个O(1)

J*a2014-05-21 07:05

37 楼

为什么要查找？这问题问得。。。
任何数据结构都有查找复杂度比如hash表O(1) BST O(logn)数组当然是O(n)
比如我存了MITBBS所有注册用户的信息在hash表里那我想要查询lanb是什么时候注册
的 O(1)就能查到如果存在数组里需要遍历整个数组才能找到lanb 这么说明白了？

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

: 纯学术啊，Array为什么要查找啊？Array如果查找的话就是查找index指向那个东西吧
: ？那样，为什么Array Based的是O(n)？为什么hash的是o(1)？
: 整个class就要求set(int index, T t)和get(int index)这2个方法。我觉得coding那
: 块真没什么好说的，题目比较简单。就注意一下overflow什么的就可以了。如果说真的
: 他一开始就想让我用HashMap写的话，那更没意思了。那是完全无聊了。
: 基础差+老年痴呆+上礼拜东岸飞西岸真的很累，所以很多东西没答出来。

l*b2014-05-21 07:05

38 楼

好吧，我题意没有说清楚。人家问的是写InfiniteArray的时候，用Array和HashMap做
backend data structure分别有什么好处。我应该说Array查找要O(n)，HashMap查找要
O(1)？
Array本来就不是用来查找的。

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

: 为什么要查找？这问题问得。。。
: 任何数据结构都有查找复杂度比如hash表O(1) BST O(logn)数组当然是O(n)
: 比如我存了MITBBS所有注册用户的信息在hash表里那我想要查询lanb是什么时候注册
: 的 O(1)就能查到如果存在数组里需要遍历整个数组才能找到lanb 这么说明白了？

j*x2014-05-21 07:05

39 楼

楼主没认真准备而已
这些题目也不是很好的题，题目讲的清楚就完全没有难度，考的竟然是交际能力。。。
难道是面试官要搞基，想找个善解人意的。。。

n*m2014-05-21 07:05

40 楼

首先感谢分享
我没看懂lz用Array怎么做的
非要我用Array来做的我还是得再加个hash map来记录两种index的对应关系

l*b2014-05-21 07:05

41 楼

和ArrayList一个道理。

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

: 首先感谢分享
: 我没看懂lz用Array怎么做的
: 非要我用Array来做的我还是得再加个hash map来记录两种index的对应关系

l*b2014-05-21 07:05

42 楼

还准备蛮久的。只是基础不好罢了。这个没什么好说的。

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

: 楼主没认真准备而已
: 这些题目也不是很好的题，题目讲的清楚就完全没有难度，考的竟然是交际能力。。。
: 难道是面试官要搞基，想找个善解人意的。。。

q*r2014-05-21 07:05

43 楼

mark

x*02014-05-21 07:05

44 楼

mark

q*82014-05-21 07:05

45 楼

不知道lz面的时候问没问initinityarray的定义。我觉得如果那人说请现实一个
inifinityArray，这个明显没法写吧，如果定义好了，需求明确，那估计他就会把
sparse array说出来了。我觉得前面有人说人家都说long index了，一定是sparse
array，我觉得这也太。。。。你怎么知道啊。
我觉得如果光看lz提供的面经，问题应该是lz没问仔细需求，一下就开始coding了
总之感谢lz宝贵面经

l*b2014-05-21 07:05

46 楼

真实没有怎么问问题，因为到那个的时候我已经状态很差了。本来上礼拜去A onsite，
累到想吐。所以状态一直都不好。加上个人感觉对方不是很想沟通，所以等他问那个
coding题目的时候已经没什么力气了。long的话可能是sparse，但是也不一定吧。现在
内存这么大，装不完long，装多过int还是可能的。
反正写出来是让大家看我教训的。不是吐槽什么的。

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

: 不知道lz面的时候问没问initinityarray的定义。我觉得如果那人说请现实一个
: inifinityArray，这个明显没法写吧，如果定义好了，需求明确，那估计他就会把
: sparse array说出来了。我觉得前面有人说人家都说long index了，一定是sparse
: array，我觉得这也太。。。。你怎么知道啊。
: 我觉得如果光看lz提供的面经，问题应该是lz没问仔细需求，一下就开始coding了
: 总之感谢lz宝贵面经