q******8
发帖数: 848 | 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***2
发帖数: 838 | |
q******8
发帖数: 848 | 3 如果全开，内存太大。
【在 c***2 的大作中提到】
: 2. bit vector?
|
f****g
发帖数: 313 | 4 如果是32-bit的machine话， bitmap的话，需要(2^32 - 1)/2^5 = 2^27
如果available不多的话（相对不available的数），可以用hash table只存available
的数.
lz怎么答得阿:D
【在 q******8 的大作中提到】
: 如果全开，内存太大。
|
J*******i
发帖数: 2162 | 5 他没有别的什么提示么？就是还有什么别的一些条件或者关于这些available数的描述 |
H****S
发帖数: 1359 | 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******n
发帖数: 1009 | 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******n
发帖数: 1009 | 8 int check_out返回第一个available的number,这第一个是指第一个
check_in的还是指最小的？
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题答的不好，大家有什么方法？
|
c****o
发帖数: 41 | 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 的大作中提到】
: 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题答的不好，大家有什么方法？
|
j******y
发帖数: 238 | 10 我那次是直接念。
【在 S******n 的大作中提到】
: 你好，问一下Amazon电面的时候是在shared doc 上写code,还是自己
: 在纸上写然后念给对方听？谢谢
:
: number的value范围从0-
: {}: 返回number_pool里
: 为available。（number_
: 的，记不得了。
|
|
|
q******8
发帖数: 848 | 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**********3
发帖数: 161 | 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******8
发帖数: 848 | 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******n
发帖数: 1009 | 14 是的，如果用bitmap，看似省了不少空间，但要维持一个0到MAX_INT的
bitmap还是需要不少空间的，如果同时available 的数不是特别多的话，
我觉得可以用hash_map存储available的数
的琢磨的。我
【在 q******8 的大作中提到】
:
: memory)
: 果然被拒了，这道题bitmap的实现很简单，但是往深里挖觉得还真是挺有的琢磨的。我
: 是用的bitmap，然后就被问内存有
: 限的问题，说了file之类的，但是好像对方不满意。
|
S******n
发帖数: 1009 | 15 如果check_in的数已经available了再加进去就重复了
interger ++;
【在 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_
|
H****S
发帖数: 1359 | 16 这个number_pool是一个类似generator的东西吗？且不说function怎么实现，对于这个
number_pool的数据结构如何表达很好奇。
【在 q******8 的大作中提到】
:
: memory)
: 果然被拒了，这道题bitmap的实现很简单，但是往深里挖觉得还真是挺有的琢磨的。我
: 是用的bitmap，然后就被问内存有
: 限的问题，说了file之类的，但是好像对方不满意。
|
