个人评价:简单基础的系统设计题,可考虑优化其可扩展性
题目难度:🌟 (参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 )
另,通常算法题会考察分析时间复杂度和空间复杂度,可参考笔者之前的文章
设计停车系统
题目描述
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类:
- ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,三个参数分别对应每种停车位的数目。
- bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位,请返回 false ,否则将该车停入车位并返回 true 。
示例 1:
输入:
[“ParkingSystem”, “addCar”, “addCar”, “addCar”, “addCar”] [[1, 1, 0], [1], [2], [3], [1]]
输出:
[null, true, true, false, false]
解释:
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ,因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ,因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ,因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ,因为没有空的大车位,唯一一个大车位已经被占据了
提示:
0 <= big, medium, small <= 1000 carType 取值为 1, 2 或 3 最多会调用 addCar 函数 1000 次
解题思路
比较简单,基础定义类型,判断是否存在不同类型的空车位即可
Golang 实现代码如下:
type ParkingSystem struct {
big int
medium int
small int
}
func Constructor(big int, medium int, small int) ParkingSystem {
return ParkingSystem{big, medium, small}
}
func (this *ParkingSystem) AddCar(carType int) bool {
switch carType {
case 1:
if this.big > 0 {
this.big--
return true
}
case 2:
if this.medium > 0 {
this.medium--
return true
}
case 3:
if this.small > 0 {
this.small--
return true
}
default:
return false
}
return false
}
复杂度?🙌 操作的时间和空间复杂度均为常量 O(1)
优化点?复杂度上没必要了,想想可扩展性以及后续可能的使用场景,如下:
- 车子驶离车位
- 若允许小车停在更大的车位,如何判断及操作?
- 固定车位(私家车位)只允许标识为固定车位的车驶入,系统如何扩展设计
总结
题是简单的,但是后续系统可使用场景可开阔下产品思维,作为面试题也是不错的~