Amex membership reward怎么用最合适 - 未名空间MITBBS历史存档

Amex membership reward怎么用最合适# Money - 海外理财

o*s2014-09-04 07:09

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，d1num 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).

i*i2014-09-04 07:09

2 楼

最近兑换 jetBlue的deal如何？

b*u2014-09-04 07:09

3 楼

用一个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 d1vector 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];
}

w*r2014-09-04 07:09

4 楼

换自己最需要的就是最值的

r*n2014-09-04 07:09

5 楼

感觉(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*n2014-09-04 07:09

6 楼

补充一点，上面的hash table needs to use linear probing to resolve collision
btw different performance names that result in the same hash value.

o*s2014-09-04 07:09

7 楼

是不是要用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*u2014-09-04 07:09

8 楼

我跟楼上两位想的不一样的地方在于，你们觉得log n 是在暗示tree，我觉得是在暗示
binary search。比如给定一个日期，我们就在空闲日期的开始序列里找，找到一个区
间之后再线性探查，查map，这么个logn + k

o*s2014-09-04 07:09

9 楼

关于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*s2014-09-04 07:09

10 楼

不一定要算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*t2014-09-04 07:09

11 楼

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*u2014-09-04 07:09

12 楼

把124写了一下在2楼

o*s2014-09-04 07:09

13 楼

对于同名performance, 不同日期的演出，你的class怎么维护？而且available date
是很难维护的，因为是unlimited.

【在 b*****u 的大作中提到】

: 把124写了一下在2楼

r*n2014-09-04 07:09

14 楼

子树大小是在insert的时候maintain，所以不会增加复杂度
关于rank，你去看看Sedgewick的Algorithms那本书，里面有Java代码
http://algs4.cs.princeton.edu/home/

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

: 关于rank的问题，这个子树的大小怎么算呢？给举个例子吧。多谢大牛！

m*g2014-09-04 07:09

15 楼

是不是应该问一下出题人：可以预定多长时间内地performance。如果是一年，一个数
组就都解决了。：）

m*g2014-09-04 07:09

16 楼

可以先问一下空间复杂度，通过反馈决定数据结构。
不过如果空间复杂度是O(n).应该是用Tree。

o*s2014-09-04 07:09

17 楼

音乐会演出设计题。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，d1num 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*u2014-09-04 07:09

18 楼

用一个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 d1vector 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*n2014-09-04 07:09

19 楼

感觉(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*n2014-09-04 07:09

20 楼

补充一点，上面的hash table needs to use linear probing to resolve collision
btw different performance names that result in the same hash value.

o*s2014-09-04 07:09

21 楼

是不是要用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*u2014-09-04 07:09

22 楼

我跟楼上两位想的不一样的地方在于，你们觉得log n 是在暗示tree，我觉得是在暗示
binary search。比如给定一个日期，我们就在空闲日期的开始序列里找，找到一个区
间之后再线性探查，查map，这么个logn + k

o*s2014-09-04 07:09

23 楼

关于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*s2014-09-04 07:09

24 楼

不一定要算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*t2014-09-04 07:09

25 楼

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*u2014-09-04 07:09

26 楼

把124写了一下在2楼

o*s2014-09-04 07:09

27 楼

对于同名performance, 不同日期的演出，你的class怎么维护？而且available date
是很难维护的，因为是unlimited.

【在 b*****u 的大作中提到】

: 把124写了一下在2楼

r*n2014-09-04 07:09

28 楼

子树大小是在insert的时候maintain，所以不会增加复杂度
关于rank，你去看看Sedgewick的Algorithms那本书，里面有Java代码
http://algs4.cs.princeton.edu/home/

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

: 关于rank的问题，这个子树的大小怎么算呢？给举个例子吧。多谢大牛！

m*g2014-09-04 07:09

29 楼

是不是应该问一下出题人：可以预定多长时间内地performance。如果是一年，一个数
组就都解决了。：）

m*g2014-09-04 07:09

30 楼

可以先问一下空间复杂度，通过反馈决定数据结构。
不过如果空间复杂度是O(n).应该是用Tree。

o*d2014-09-04 07:09

31 楼

同意这个

【在 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*02014-09-04 07:09

32 楼

mark