Amazon电面面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon电面面经

Amazon电面面经# JobHunting - 待字闺中

q*82010-12-08 08:12

1 楼

1. c++， java对比。（因为说语言时候说都可以）
2. coding: 一个interface叫foo，有一个number_pool, 里面number的value范围从0-
MAXINT, 这些number有
available和unavailable两种状态，方法1 int check_out(){}: 返回number_pool里
的第一个available的number。方法2
void check_in(int i){}：把number_pool里的相应number设为available。（number_
pool的数据结构自定）。实现这个
interface。
3. follow up 一些java的问题： java MAXINT是多少。。。之类的，记不得了。
coding题答的不好，大家有什么方法？

c*22010-12-08 08:12

2 楼

2. bit vector?

q*82010-12-08 08:12

3 楼

如果全开，内存太大。

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

: 2. bit vector?

f*g2010-12-08 08:12

4 楼

如果是32-bit的machine话， bitmap的话，需要(2^32 - 1)/2^5 = 2^27
如果available不多的话（相对不available的数），可以用hash table只存available
的数.
lz怎么答得阿:D

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

: 如果全开，内存太大。

J*i2010-12-08 08:12

5 楼

他没有别的什么提示么？就是还有什么别的一些条件或者关于这些available数的描述

H*S2010-12-08 08:12

6 楼

byte[] number_pool = new byte[Integer.MAX_VALUE / 8] (takes up to 1GB memory)
set availability: number_pool[n / 8] |= 1 << (n % 8);
judge availability: number_pool[n / 8] & 1 << (n % 8) == 1;

S*n2010-12-08 08:12

7 楼

你好，问一下Amazon电面的时候是在shared doc 上写code,还是自己
在纸上写然后念给对方听？谢谢

number的value范围从0-
{}: 返回number_pool里
为available。（number_
的，记不得了。

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

: 1. c++， java对比。（因为说语言时候说都可以）
: 2. coding: 一个interface叫foo，有一个number_pool, 里面number的value范围从0-
: MAXINT, 这些number有
: available和unavailable两种状态，方法1 int check_out(){}: 返回number_pool里
: 的第一个available的number。方法2
: void check_in(int i){}：把number_pool里的相应number设为available。（number_
: pool的数据结构自定）。实现这个
: interface。
: 3. follow up 一些java的问题： java MAXINT是多少。。。之类的，记不得了。
: coding题答的不好，大家有什么方法？

S*n2010-12-08 08:12

8 楼

int check_out返回第一个available的number,这第一个是指第一个
check_in的还是指最小的？

number的value范围从0-
{}: 返回number_pool里
为available。（number_
的，记不得了。

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

c*o2010-12-08 08:12

9 楼

My 2 cents for question 2:
number_pool keeps a integer and a min-heap;
initial: integer = 0; min_heap is empty;
check_out: if min-heap is empty, return the integer; interger ++;
else return the min value in the min heap;
check_in: add the value into the min_heap

number_

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

j*y2010-12-08 08:12

10 楼

我那次是直接念。

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

: 你好，问一下Amazon电面的时候是在shared doc 上写code,还是自己
: 在纸上写然后念给对方听？谢谢
:
: number的value范围从0-
: {}: 返回number_pool里
: 为available。（number_
: 的，记不得了。

q*82010-12-08 08:12

11 楼

如果内存没那么大呢？

memory)

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

: byte[] number_pool = new byte[Integer.MAX_VALUE / 8] (takes up to 1GB memory)
: set availability: number_pool[n / 8] |= 1 << (n % 8);
: judge availability: number_pool[n / 8] & 1 << (n % 8) == 1;

l*32010-12-08 08:12

12 楼

那如果User先checkout所有的数，然后再checkin所有的数，你的minheap就会用光所有
的memory。
你的想法可以，不过我觉得要限制一下min heap的size。

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

: My 2 cents for question 2:
: number_pool keeps a integer and a min-heap;
: initial: integer = 0; min_heap is empty;
: check_out: if min-heap is empty, return the integer; interger ++;
: else return the min value in the min heap;
: check_in: add the value into the min_heap
:
: number_

q*82010-12-08 08:12

13 楼

memory)
果然被拒了，这道题bitmap的实现很简单，但是往深里挖觉得还真是挺有的琢磨的。我
是用的bitmap，然后就被问内存有
限的问题，说了file之类的，但是好像对方不满意。

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

: byte[] number_pool = new byte[Integer.MAX_VALUE / 8] (takes up to 1GB memory)
: set availability: number_pool[n / 8] |= 1 << (n % 8);
: judge availability: number_pool[n / 8] & 1 << (n % 8) == 1;

S*n2010-12-08 08:12

14 楼

是的，如果用bitmap，看似省了不少空间，但要维持一个0到MAX_INT的
bitmap还是需要不少空间的，如果同时available 的数不是特别多的话，
我觉得可以用hash_map存储available的数

的琢磨的。我

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

:
: memory)
: 果然被拒了，这道题bitmap的实现很简单，但是往深里挖觉得还真是挺有的琢磨的。我
: 是用的bitmap，然后就被问内存有
: 限的问题，说了file之类的，但是好像对方不满意。

S*n2010-12-08 08:12

15 楼

如果check_in的数已经available了再加进去就重复了

interger ++;

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

H*S2010-12-08 08:12

16 楼

这个number_pool是一个类似generator的东西吗？且不说function怎么实现，对于这个
number_pool的数据结构如何表达很好奇。

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