c**********e
发帖数: 2007 | 1 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
一般的停车场根本不是这样子。
最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？ |
h*******s
发帖数: 8454 | 2 你咋能找到这么多面试呢？
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
c**********e
发帖数: 2007 | 3 找不到工作，只好接着面。
【在 h*******s 的大作中提到】
: 你咋能找到这么多面试呢？
:
: 置？
|
h*******s
发帖数: 8454 | 4 羡慕~
都没人稀得面试我。。。
【在 c**********e 的大作中提到】
: 找不到工作，只好接着面。
|
t****t
发帖数: 6806 | 5 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
--赠careerchange
【在 c**********e 的大作中提到】
: 找不到工作，只好接着面。
|
c**********e
发帖数: 2007 | 6 谢谢老大。命真是比黄连苦啊。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
n******t
发帖数: 4406 | 7 你居然开始恶搞了。。。。。不错。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
r****y
发帖数: 26819 | 8 我生不面试，肚子又很饿。苦为面试累，犹恐不为多。朝看南家经，暮盼北家果。
面试能几何？但求得offer。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
|
h*******s
发帖数: 8454 | 9 天天找面试，面试不找我，时光尽蹉跎，肚子开始饿。。。
【在 r****y 的大作中提到】
: 我生不面试，肚子又很饿。苦为面试累，犹恐不为多。朝看南家经，暮盼北家果。
: 面试能几何？但求得offer。
|
s*w
发帖数: 729 | 10 没google,扯两句;这东西有点瞎扯的意思,要看多大程度模拟真实的停车场
通常停车场规模不大,几百个车位了不得了,都是进去沿着固定路线转,直到找到第一个空
位,相当于linear search;
先进的停车场(我想的,没见过)进去的时候可以告诉你哪个位子是空的,适用于很大的停
车场(airport? stadium?),没有固定路线的搜索,这样子的话,最好是在一个array里面存
下来所有的空位,按照离进口的距离来排序一下, priority queue, 里面每个元素存储车
位,包括有key+卫星数据(比如direction from entrance to the spot)
每次爬车的时候,取第一个元素,得到空位; O(1) 查选, O(n) 删除
每次走人的时候,把该车位加回去 queue, 插入合适的位置, 有点慢,需要挪 O(n) 元素
这样的好处是最快速方便顾客查询, 删除和插入都是顾客不care 的,
这个 priority queue 也可以用 bst 来实现, 那就可以让 查询, 删除,插入都是 O(lo
gn) , 更均衡些
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
|
|
d****n
发帖数: 1637 | 11 My implementation using min heap
//file name parkinglots.c
#include
#include
int *lots; //parking lots
#define LOTSMAX 16 //lots size
void Heapify( int i, int mx);
void car_enter();
void car_leave(int i);
void print_lots();
int main(){
int i;
lots=(int *)calloc( (LOTSMAX), sizeof(int));
printf("car enter\n");
for(i=0;i
if(lots[0]!=1){
car_enter();
print_lots();
}
}
printf("car leave\n");
for(i=LOTSMAX-1;i>=0; --i){
if(lots[i]!=0){
car_leave(i);
print_lots();
}
}
free(lots);
return 1;
}
void print_lots(){
int i ;
for(i=0;i
printf("%d ",lots[i]);
}
printf("\n");
}
void Heapify(int i, int mx){
int l, r, min,parent;
//heapify downward
l=2*i+1;
r=2*i+2 ;
min=i;
if(lots[min]>lots[l]&&l<=mx )
min=l;
if(lots[min] >lots[r] && r<=mx)
min=r;
if(min!=i){
int tmp=lots[i];
lots[i]=lots[min];
lots[min]=tmp;
i=min;
Heapify(i, mx);
}
//heapify upward
parent=(i-1)/2;
if (parent<0)return ;
if (lots[parent]>lots[i]){
int tmp=lots[i];
lots[i]=lots[parent];
lots[parent]=tmp;
i=parent;
Heapify(i, mx);
}
}
void car_enter(){
lots[0]=1;// 1 is occupied
Heapify(0,(LOTSMAX-1) );
}
void car_leave(int i){
lots[i]=0;// 0 is empty
Heapify(i, (LOTSMAX-1) );
} |
d****n
发帖数: 1637 | 12 output
car enter
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1
0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
car leave
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1
0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1
0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 |
d****n
发帖数: 1637 | 13 explain
using a min heap
whenever a car enter, set the root=1 heapify it int O(log(N))time
So it makes sure available lot is at the root.
whenever a car leaving, clear i=0 and then upward heapify it.
For entirely solving the problem, e.g, which lot is available or not,
you need map the geometry parking lots onto this heap/array.
I think interview will not be interested with that, but the data structure
and algo.
good luck. |
a****l
发帖数: 8211 | 14 当然是矩阵了.这个世界上哪里有过停车位数量可以变化的停车场?创建的时候给个大小
就固定好了,以后不能动了.
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
r****y
发帖数: 26819 | 15 现在新修的停车场可以做全场监控，总入口处显示每层剩余车位，而且每一层的入口处
都显示该层剩余车位。这样可以避免跨层找车位。
个空
面存
储车
【在 s*w 的大作中提到】
: 没google,扯两句;这东西有点瞎扯的意思,要看多大程度模拟真实的停车场
: 通常停车场规模不大,几百个车位了不得了,都是进去沿着固定路线转,直到找到第一个空
: 位,相当于linear search;
: 先进的停车场(我想的,没见过)进去的时候可以告诉你哪个位子是空的,适用于很大的停
: 车场(airport? stadium?),没有固定路线的搜索,这样子的话,最好是在一个array里面存
: 下来所有的空位,按照离进口的距离来排序一下, priority queue, 里面每个元素存储车
: 位,包括有key+卫星数据(比如direction from entrance to the spot)
: 每次爬车的时候,取第一个元素,得到空位; O(1) 查选, O(n) 删除
: 每次走人的时候,把该车位加回去 queue, 插入合适的位置, 有点慢,需要挪 O(n) 元素
: 这样的好处是最快速方便顾客查询, 删除和插入都是顾客不care 的,
|
d****n
发帖数: 1637 | 16 only array is not gonna work without algorithm.
To iterate 1 million elements in an array is not acceptable.
Also, this is only a question model, not for real design. I think.
【在 a****l 的大作中提到】
: 当然是矩阵了.这个世界上哪里有过停车位数量可以变化的停车场?创建的时候给个大小
: 就固定好了,以后不能动了.
:
: 置？
|
a****l
发帖数: 8211 | 17 This is exactly my point: the model has to match real things. Discussing
fancy design suited for imaginary/nonexistent things is good for only
academia practices.
【在 d****n 的大作中提到】
: only array is not gonna work without algorithm.
: To iterate 1 million elements in an array is not acceptable.
: Also, this is only a question model, not for real design. I think.
|
g*****g
发帖数: 34805 | 18 In real world practice, this will be a single database table,
with whatever attribute you need, e.g. level. And build index
on those attribute you frequently search. It's faster, it's simpler.
Call it B+ tree if you want.
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
d****n
发帖数: 1637 | 19 Interviewer asked "what data structure" not database.
Neither they mentioned to need to solve a "real world" problem.
【在 g*****g 的大作中提到】
: In real world practice, this will be a single database table,
: with whatever attribute you need, e.g. level. And build index
: on those attribute you frequently search. It's faster, it's simpler.
: Call it B+ tree if you want.
:
: 置？
|
p*********t
发帖数: 2690 | 20 英文原话怎么说的？设计停车场？不就是停车楼或者parking lot几种吗，还用设计？
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
|
|
m*p
发帖数: 1331 | |
g***f
发帖数: 18 | 22 非也非也，天行健，change rules the univ。停车场重新划线，调整位宽，增加楼层
的那些事儿俺都见过。。So it needs to be at least one dynamic structure + one
auxiliary structure
了,以后不能动了.
【在 a****l 的大作中提到】
: This is exactly my point: the model has to match real things. Discussing
: fancy design suited for imaginary/nonexistent things is good for only
: academia practices.
|
c**********e
发帖数: 2007 | 23 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
一般的停车场根本不是这样子。
最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？ |
h*******s
发帖数: 8454 | 24 你咋能找到这么多面试呢？
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
c**********e
发帖数: 2007 | 25 找不到工作，只好接着面。
【在 h*******s 的大作中提到】
: 你咋能找到这么多面试呢？
:
: 置？
|
h*******s
发帖数: 8454 | 26 羡慕~
都没人稀得面试我。。。
【在 c**********e 的大作中提到】
: 找不到工作，只好接着面。
|
t****t
发帖数: 6806 | 27 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
--赠careerchange
【在 c**********e 的大作中提到】
: 找不到工作，只好接着面。
|
c**********e
发帖数: 2007 | 28 谢谢老大。命真是比黄连苦啊。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
n******t
发帖数: 4406 | 29 你居然开始恶搞了。。。。。不错。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
r****y
发帖数: 26819 | 30 我生不面试，肚子又很饿。苦为面试累，犹恐不为多。朝看南家经，暮盼北家果。
面试能几何？但求得offer。
【在 t****t 的大作中提到】
: 面试复面试, 面试何其多. 我生待面试, 万事成蹉跎.
: --赠careerchange
|
|
|
h*******s
发帖数: 8454 | 31 天天找面试，面试不找我，时光尽蹉跎，肚子开始饿。。。
【在 r****y 的大作中提到】
: 我生不面试，肚子又很饿。苦为面试累，犹恐不为多。朝看南家经，暮盼北家果。
: 面试能几何？但求得offer。
|
s*w
发帖数: 729 | 32 没google,扯两句;这东西有点瞎扯的意思,要看多大程度模拟真实的停车场
通常停车场规模不大,几百个车位了不得了,都是进去沿着固定路线转,直到找到第一个空
位,相当于linear search;
先进的停车场(我想的,没见过)进去的时候可以告诉你哪个位子是空的,适用于很大的停
车场(airport? stadium?),没有固定路线的搜索,这样子的话,最好是在一个array里面存
下来所有的空位,按照离进口的距离来排序一下, priority queue, 里面每个元素存储车
位,包括有key+卫星数据(比如direction from entrance to the spot)
每次爬车的时候,取第一个元素,得到空位; O(1) 查选, O(n) 删除
每次走人的时候,把该车位加回去 queue, 插入合适的位置, 有点慢,需要挪 O(n) 元素
这样的好处是最快速方便顾客查询, 删除和插入都是顾客不care 的,
这个 priority queue 也可以用 bst 来实现, 那就可以让 查询, 删除,插入都是 O(lo
gn) , 更均衡些
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
d****n
发帖数: 1637 | 33 My implementation using min heap
//file name parkinglots.c
#include
#include
int *lots; //parking lots
#define LOTSMAX 16 //lots size
void Heapify( int i, int mx);
void car_enter();
void car_leave(int i);
void print_lots();
int main(){
int i;
lots=(int *)calloc( (LOTSMAX), sizeof(int));
printf("car enter\n");
for(i=0;i
if(lots[0]!=1){
car_enter();
print_lots();
}
}
printf("car leave\n");
for(i=LOTSMAX-1;i>=0; --i){
if(lots[i]!=0){
car_leave(i);
print_lots();
}
}
free(lots);
return 1;
}
void print_lots(){
int i ;
for(i=0;i
printf("%d ",lots[i]);
}
printf("\n");
}
void Heapify(int i, int mx){
int l, r, min,parent;
//heapify downward
l=2*i+1;
r=2*i+2 ;
min=i;
if(lots[min]>lots[l]&&l<=mx )
min=l;
if(lots[min] >lots[r] && r<=mx)
min=r;
if(min!=i){
int tmp=lots[i];
lots[i]=lots[min];
lots[min]=tmp;
i=min;
Heapify(i, mx);
}
//heapify upward
parent=(i-1)/2;
if (parent<0)return ;
if (lots[parent]>lots[i]){
int tmp=lots[i];
lots[i]=lots[parent];
lots[parent]=tmp;
i=parent;
Heapify(i, mx);
}
}
void car_enter(){
lots[0]=1;// 1 is occupied
Heapify(0,(LOTSMAX-1) );
}
void car_leave(int i){
lots[i]=0;// 0 is empty
Heapify(i, (LOTSMAX-1) );
} |
d****n
发帖数: 1637 | 34 output
car enter
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1
0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1
0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
car leave
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1
0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1
0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 |
d****n
发帖数: 1637 | 35 explain
using a min heap
whenever a car enter, set the root=1 heapify it int O(log(N))time
So it makes sure available lot is at the root.
whenever a car leaving, clear i=0 and then upward heapify it.
For entirely solving the problem, e.g, which lot is available or not,
you need map the geometry parking lots onto this heap/array.
I think interview will not be interested with that, but the data structure
and algo.
good luck. |
a****l
发帖数: 8211 | 36 当然是矩阵了.这个世界上哪里有过停车位数量可以变化的停车场?创建的时候给个大小
就固定好了,以后不能动了.
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
r****y
发帖数: 26819 | 37 现在新修的停车场可以做全场监控，总入口处显示每层剩余车位，而且每一层的入口处
都显示该层剩余车位。这样可以避免跨层找车位。
个空
面存
储车
【在 s*w 的大作中提到】
: 没google,扯两句;这东西有点瞎扯的意思,要看多大程度模拟真实的停车场
: 通常停车场规模不大,几百个车位了不得了,都是进去沿着固定路线转,直到找到第一个空
: 位,相当于linear search;
: 先进的停车场(我想的,没见过)进去的时候可以告诉你哪个位子是空的,适用于很大的停
: 车场(airport? stadium?),没有固定路线的搜索,这样子的话,最好是在一个array里面存
: 下来所有的空位,按照离进口的距离来排序一下, priority queue, 里面每个元素存储车
: 位,包括有key+卫星数据(比如direction from entrance to the spot)
: 每次爬车的时候,取第一个元素,得到空位; O(1) 查选, O(n) 删除
: 每次走人的时候,把该车位加回去 queue, 插入合适的位置, 有点慢,需要挪 O(n) 元素
: 这样的好处是最快速方便顾客查询, 删除和插入都是顾客不care 的,
|
d****n
发帖数: 1637 | 38 only array is not gonna work without algorithm.
To iterate 1 million elements in an array is not acceptable.
Also, this is only a question model, not for real design. I think.
【在 a****l 的大作中提到】
: 当然是矩阵了.这个世界上哪里有过停车位数量可以变化的停车场?创建的时候给个大小
: 就固定好了,以后不能动了.
:
: 置？
|
a****l
发帖数: 8211 | 39 This is exactly my point: the model has to match real things. Discussing
fancy design suited for imaginary/nonexistent things is good for only
academia practices.
【在 d****n 的大作中提到】
: only array is not gonna work without algorithm.
: To iterate 1 million elements in an array is not acceptable.
: Also, this is only a question model, not for real design. I think.
|
g*****g
发帖数: 34805 | 40 In real world practice, this will be a single database table,
with whatever attribute you need, e.g. level. And build index
on those attribute you frequently search. It's faster, it's simpler.
Call it B+ tree if you want.
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
|
|
d****n
发帖数: 1637 | 41 Interviewer asked "what data structure" not database.
Neither they mentioned to need to solve a "real world" problem.
【在 g*****g 的大作中提到】
: In real world practice, this will be a single database table,
: with whatever attribute you need, e.g. level. And build index
: on those attribute you frequently search. It's faster, it's simpler.
: Call it B+ tree if you want.
:
: 置？
|
p*********t
发帖数: 2690 | 42 英文原话怎么说的？设计停车场？不就是停车楼或者parking lot几种吗，还用设计？
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
m*p
发帖数: 1331 | |
l**********a
发帖数: 181 | |
q*c
发帖数: 9453 | 45 这是亚麻的经典题目。
要 oop.object 后面用 sql back up.
置？
【在 c**********e 的大作中提到】
: 如何设计一个停车场。问该用什么数据结构。我想了一下，我觉得要是用vector话，找
: 一个空位就成了线性的。要是用stack或者 queue，那就只能从一个具体的位置停车，
: 一般的停车场根本不是这样子。
: 最后我说用 linked list，因为linked list可以把空位加在头上。找空位就简单了。
: 但是如果来了一辆车停在头的位置，不就有难找空位了？还是说停车只能停在特定位置？
|
i**i
发帖数: 1500 | 46 P.
if (num of car entered > N) show "full", otherwise, show "not full".
exit. |
a*w
发帖数: 4495 | 47 扁他，他把别人的面试机会都抢光了。
【在 h*******s 的大作中提到】
: 你咋能找到这么多面试呢？
:
: 置？
|
q*c
发帖数: 9453 | 48 fire 了， fire 了。
这是要你设计 sql table 得。 每个 table 对应一个实体， 或者交易。
你这是手工作坊得把式。
【在 d****n 的大作中提到】
: My implementation using min heap
: //file name parkinglots.c
: #include
: #include
: int *lots; //parking lots
: #define LOTSMAX 16 //lots size
: void Heapify( int i, int mx);
: void car_enter();
: void car_leave(int i);
: void print_lots();
|
q*c
发帖数: 9453 | 49 ... database 就不是 data structure 啦？
实际上就是 data structure, 每个 class 对应后面一张表， ORM. 这几个名词出来，
这几个表之间的 foreign key u安息， 等等， 面试就搞定一半了。
【在 d****n 的大作中提到】
: Interviewer asked "what data structure" not database.
: Neither they mentioned to need to solve a "real world" problem.
|
z****e
发帖数: 54598 | 50 a data structure is a particular way of STORING and organizing data
【在 d****n 的大作中提到】
: Interviewer asked "what data structure" not database.
: Neither they mentioned to need to solve a "real world" problem.
|
