o******s
发帖数: 28 | 1 音乐会演出设计题。First come first serve. 一天只有一个演出，任何演出5天之内
不在重复演出。
（1） 设计一个data structure, check by date, insert performance, delete
performance from calendar in O(log n), n is the number of performance.
(2) 找出任何两天之间的performance，d1
num of such performance.
(3)找出任何两天之间的number of perforances.
(4)Given a requested time d which is impossible (i.e. within 5 days of an
already scheduled performance), give an O(log n)-time algorithm to find the
next available day d2 (d2 > d). |
b*****u
发帖数: 648 | 2 用一个vector存储空闲日期段的开始
一个map 存储日期到演出的mapping
class calendar
{
vector available;
map dateToShow;
}
class performance
{
int date;
int program;
}
// assume that int binarySearch(vectorA, int x) returns the target
index i that A[i] <= x
// cost: log n
// return 0 if available, program id if not
int calendar::check(int date)
{
if (dateToShow.find(date)==dateToShow.end())
return 0;
else
return dateToShow[date];
}
// return true if successfully inserted
bool calendar::insert(int date, int program)
{
if (dateToShow.find(date)!=dateToShow.end())
return false;
// check within +- 5 days
for (int i = date-4; i
{
if (this->check(i)==program)
return false;
}
int lastAvailable = binarySearch(available, date);
map[date]=program;
if (available[lastAvailable]==date)
available.erase(available.begin()+lastAvailable);
if (dateToshow.find(date+1)==dateToShow.end())
available.insert(available.beign()+lastAvailable, date+1);
return true;
}
//delete is similar to insert...
// (2) find performances between d1
vector calendar:findPerformances(int d1, int d2)
{
vectorresult;
int tryDate;
// O(log n)
i1=binarySearch(available,d1);
i2=binarySearch(available,d2);
// O(k)
for (int i = i1+1, i
{
tryDate = available[i]-1;
while(check(tryDate)!=0)
result.push_back(check(tryDate--));
}
tryDate = d2-1;
while(check(tryDate)!=0)
result.push_back(check(tryDate--));
}
// (4) find next available date for a illegal input target
int calendar::findNextVaild(int illegalDate,int program)
{
// the existing show date with same program
int existing;
// check within +- 5 days
for (int i = date-4; i
{
if (this->check(i)==program)
{
existing = i;
break;
}
}
return available[binarySearch(available, existing+5)+1];
} |
r*********n
发帖数: 4553 | 3 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
member，储存子树大小(以实现(3)，rank之差)
“任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
则不插入。
第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
key is greater than d in O(logn)(worst case, one performance with n
different dates)。
我感觉应该还有更简洁的实现吧。 |
r*********n
发帖数: 4553 | 4 补充一点，上面的hash table needs to use linear probing to resolve collision
btw different performance names that result in the same hash value. |
o******s
发帖数: 28 | 5 是不是要用tree结构呢？比如说BST,日期作为value. 这样check，insert, delete就可
以O(log n)完成了。每次插入要检查前后5天的performance是否冲突。
第二，三问就是 遍历树的两个节点。
第四问就是检查下一个available的日子。
【在 b*****u 的大作中提到】
: 用一个vector存储空闲日期段的开始
: 一个map 存储日期到演出的mapping
: class calendar
: {
: vector available;
: map dateToShow;
: }
: class performance
: {
: int date;
|
b*****u
发帖数: 648 | 6 我跟楼上两位想的不一样的地方在于，你们觉得log n 是在暗示tree，我觉得是在暗示
binary search。比如给定一个日期，我们就在空闲日期的开始 序列里找，找到一个区
间之后再线性探查，查map，这么个logn + k |
o******s
发帖数: 28 | 7 关于rank的问题，这个子树的大小怎么算呢？ 给举个例子吧。多谢大牛！
【在 r*********n 的大作中提到】
: 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
: 出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
: member，储存子树大小(以实现(3)，rank之差)
: “任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
: 其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
: 则不插入。
: 第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
: bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
: 通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
: key is greater than d in O(logn)(worst case, one performance with n
|
o******s
发帖数: 28 | 8 不一定要算rank吧？把插入日期+5，-5， 然后找出这个range的所有演出，如果有这个
要插入的演出，就不能插入；如果没有，可以插入。
【在 r*********n 的大作中提到】
: 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
: 出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
: member，储存子树大小(以实现(3)，rank之差)
: “任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
: 其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
: 则不插入。
: 第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
: bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
: 通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
: key is greater than d in O(logn)(worst case, one performance with n
|
c********t
发帖数: 5706 | 9 3)要求复杂度是多少？感觉和2）问的一样啊。如果每个节点加一个total
performances 可以lg(n)做出。
4）没有那么简单，如果下m个日子都不available，就变成遍历了，复杂度不是lg(n)
【在 o******s 的大作中提到】
: 是不是要用tree结构呢？比如说BST,日期作为value. 这样check，insert, delete就可
: 以O(log n)完成了。每次插入要检查前后5天的performance是否冲突。
: 第二，三问就是 遍历树的两个节点。
: 第四问就是检查下一个available的日子。
|
b*****u
发帖数: 648 | |
|
|
o******s
发帖数: 28 | 11 对于同名performance, 不同日期的演出，你的class怎么维护？而且available date
是很难维护的，因为是unlimited.
【在 b*****u 的大作中提到】
: 把124写了一下在2楼
|
r*********n
发帖数: 4553 | 12 子树大小是在insert的时候maintain，所以不会增加复杂度
关于rank，你去看看Sedgewick的Algorithms那本书，里面有Java代码
http://algs4.cs.princeton.edu/home/
【在 o******s 的大作中提到】
: 关于rank的问题，这个子树的大小怎么算呢？ 给举个例子吧。多谢大牛！
|
m*********g
发帖数: 170 | 13 是不是应该问一下出题人：可以预定多长时间内地performance。如果是一年，一个数
组就都解决了。：） |
m*********g
发帖数: 170 | 14 可以先问一下空间复杂度，通过反馈决定数据结构。
不过如果空间复杂度是O(n).应该是用Tree。 |
o******s
发帖数: 28 | 15 音乐会演出设计题。First come first serve. 一天只有一个演出，任何演出5天之内
不在重复演出。
（1） 设计一个data structure, check by date, insert performance, delete
performance from calendar in O(log n), n is the number of performance.
(2) 找出任何两天之间的performance，d1
num of such performance.
(3)找出任何两天之间的number of perforances.
(4)Given a requested time d which is impossible (i.e. within 5 days of an
already scheduled performance), give an O(log n)-time algorithm to find the
next available day d2 (d2 > d). |
b*****u
发帖数: 648 | 16 用一个vector存储空闲日期段的开始
一个map 存储日期到演出的mapping
class calendar
{
vector available;
map dateToShow;
}
class performance
{
int date;
int program;
}
// assume that int binarySearch(vectorA, int x) returns the target
index i that A[i] <= x
// cost: log n
// return 0 if available, program id if not
int calendar::check(int date)
{
if (dateToShow.find(date)==dateToShow.end())
return 0;
else
return dateToShow[date];
}
// return true if successfully inserted
bool calendar::insert(int date, int program)
{
if (dateToShow.find(date)!=dateToShow.end())
return false;
// check within +- 5 days
for (int i = date-4; i
{
if (this->check(i)==program)
return false;
}
int lastAvailable = binarySearch(available, date);
map[date]=program;
if (available[lastAvailable]==date)
available.erase(available.begin()+lastAvailable);
if (dateToshow.find(date+1)==dateToShow.end())
available.insert(available.beign()+lastAvailable, date+1);
return true;
}
//delete is similar to insert...
// (2) find performances between d1
vector calendar:findPerformances(int d1, int d2)
{
vectorresult;
int tryDate;
// O(log n)
i1=binarySearch(available,d1);
i2=binarySearch(available,d2);
// O(k)
for (int i = i1+1, i
{
tryDate = available[i]-1;
while(check(tryDate)!=0)
result.push_back(check(tryDate--));
}
tryDate = d2-1;
while(check(tryDate)!=0)
result.push_back(check(tryDate--));
}
// (4) find next available date for a illegal input target
int calendar::findNextVaild(int illegalDate,int program)
{
// the existing show date with same program
int existing;
// check within +- 5 days
for (int i = date-4; i
{
if (this->check(i)==program)
{
existing = i;
break;
}
}
return available[binarySearch(available, existing+5)+1];
} |
r*********n
发帖数: 4553 | 17 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
member，储存子树大小(以实现(3)，rank之差)
“任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
则不插入。
第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
key is greater than d in O(logn)(worst case, one performance with n
different dates)。
我感觉应该还有更简洁的实现吧。 |
r*********n
发帖数: 4553 | 18 补充一点，上面的hash table needs to use linear probing to resolve collision
btw different performance names that result in the same hash value. |
o******s
发帖数: 28 | 19 是不是要用tree结构呢？比如说BST,日期作为value. 这样check，insert, delete就可
以O(log n)完成了。每次插入要检查前后5天的performance是否冲突。
第二，三问就是 遍历树的两个节点。
第四问就是检查下一个available的日子。
【在 b*****u 的大作中提到】
: 用一个vector存储空闲日期段的开始
: 一个map 存储日期到演出的mapping
: class calendar
: {
: vector available;
: map dateToShow;
: }
: class performance
: {
: int date;
|
b*****u
发帖数: 648 | 20 我跟楼上两位想的不一样的地方在于，你们觉得log n 是在暗示tree，我觉得是在暗示
binary search。比如给定一个日期，我们就在空闲日期的开始 序列里找，找到一个区
间之后再线性探查，查map，这么个logn + k |
|
|
o******s
发帖数: 28 | 21 关于rank的问题，这个子树的大小怎么算呢？ 给举个例子吧。多谢大牛！
【在 r*********n 的大作中提到】
: 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
: 出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
: member，储存子树大小(以实现(3)，rank之差)
: “任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
: 其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
: 则不插入。
: 第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
: bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
: 通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
: key is greater than d in O(logn)(worst case, one performance with n
|
o******s
发帖数: 28 | 22 不一定要算rank吧？把插入日期+5，-5， 然后找出这个range的所有演出，如果有这个
要插入的演出，就不能插入；如果没有，可以插入。
【在 r*********n 的大作中提到】
: 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
: 出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
: member，储存子树大小(以实现(3)，rank之差)
: “任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
: 其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
: 则不插入。
: 第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
: bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
: 通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
: key is greater than d in O(logn)(worst case, one performance with n
|
c********t
发帖数: 5706 | 23 3)要求复杂度是多少？感觉和2）问的一样啊。如果每个节点加一个total
performances 可以lg(n)做出。
4）没有那么简单，如果下m个日子都不available，就变成遍历了，复杂度不是lg(n)
【在 o******s 的大作中提到】
: 是不是要用tree结构呢？比如说BST,日期作为value. 这样check，insert, delete就可
: 以O(log n)完成了。每次插入要检查前后5天的performance是否冲突。
: 第二，三问就是 遍历树的两个节点。
: 第四问就是检查下一个available的日子。
|
b*****u
发帖数: 648 | |
o******s
发帖数: 28 | 25 对于同名performance, 不同日期的演出，你的class怎么维护？而且available date
是很难维护的，因为是unlimited.
【在 b*****u 的大作中提到】
: 把124写了一下在2楼
|
r*********n
发帖数: 4553 | 26 子树大小是在insert的时候maintain，所以不会增加复杂度
关于rank，你去看看Sedgewick的Algorithms那本书，里面有Java代码
http://algs4.cs.princeton.edu/home/
【在 o******s 的大作中提到】
: 关于rank的问题，这个子树的大小怎么算呢？ 给举个例子吧。多谢大牛！
|
m*********g
发帖数: 170 | 27 是不是应该问一下出题人：可以预定多长时间内地performance。如果是一年，一个数
组就都解决了。：） |
m*********g
发帖数: 170 | 28 可以先问一下空间复杂度，通过反馈决定数据结构。
不过如果空间复杂度是O(n).应该是用Tree。 |
o****d
发帖数: 2835 | 29 同意这个
【在 r*********n 的大作中提到】
: 感觉(1)(2)(3)用一个balanced binary search tree就可以实现，key是日期，val是演
: 出名字，然后每个node有一个parent pointer(以实现(2))，每个node有一个int sz
: member，储存子树大小(以实现(3)，rank之差)
: “任何演出5天之内不在重复演出”：在insert的时候先搜索要插入演出的时间，算出
: 其rank，然后检查该rank在[rank-5, rank+5]之间的node，看看有没有重复演出名。有
: 则不插入。
: 第(4)，需要再加入一个基于separate chaining的hash table。key是演出名字，每个
: bucket用balanced binary search tree实现，用来存储同一个演出的所有日期。这样
: 通过演出名字O(1)时间内找到对应bucket，然后search for the first node whose
: key is greater than d in O(logn)(worst case, one performance with n
|
x*****0
发帖数: 452 | |
