c**********e
发帖数: 48 | 1 Design question.
how to sort a list of books by seller rating first and then by price. |
t*****j
发帖数: 1105 | 2 sell rating的可能值很少，有的是几星几星，数字的话最多是一位小数。
比如 1，2，3，4，5等相当于不同的bucket，先把书放进不同bucket，
然后根据价格排序。最后连起来就行。
design的话，可以考虑bucket总的是个大容器，里面有5个小容器桶，存书的ID和price
.每次新增加书或者书的rating变化的话，就插入到相应的桶里。桶里各个书的结构可
以用BST.
这样排序是O(nlogn),插入，删除，rating调整都是O(logn)
我瞎说的，请高人看看行不行。
【在 c**********e 的大作中提到】
: Design question.
: how to sort a list of books by seller rating first and then by price.
|
s*******t
发帖数: 248 | 3 Sounds good.
price
【在 t*****j 的大作中提到】
: sell rating的可能值很少，有的是几星几星，数字的话最多是一位小数。
: 比如 1，2，3，4，5等相当于不同的bucket，先把书放进不同bucket，
: 然后根据价格排序。最后连起来就行。
: design的话，可以考虑bucket总的是个大容器，里面有5个小容器桶，存书的ID和price
: .每次新增加书或者书的rating变化的话，就插入到相应的桶里。桶里各个书的结构可
: 以用BST.
: 这样排序是O(nlogn),插入，删除，rating调整都是O(logn)
: 我瞎说的，请高人看看行不行。
|
c**********e
发帖数: 48 | 4 我一开始也是focus on algorithm
但interviewer 很快提醒我 这是 design question 不是algorithm question.
可以选择任意语言 主要是问如何实现
for example, 可以用C++ STL的 quicksort 排序
要考虚的是如何设计类，如何传递排序的对象，参数等等 |
t*****j
发帖数: 1105 | 5 int ID=0;
Book {
Private:
static int ID,
char[40] name,
char[40] Publisher,
int Book_ID;
float Price;
float rate;
int num_of_rating;
Public:
Book(char* Name, int Name_length, float Price)
{set name, price; Book_ID = ID++;};
int GetBookID();
float GetPrice();
void SetPrice();
void getRate();
void UpdateRate(int rate1){};
...
}; |
s*****n
发帖数: 5488 | 6 文不对题。可能是要考decorator pattern，保证程序不变，排序方式任意组合。
【在 t*****j 的大作中提到】
: int ID=0;
: Book {
: Private:
: static int ID,
: char[40] name,
: char[40] Publisher,
: int Book_ID;
: float Price;
: float rate;
: int num_of_rating;
|
t*****j
发帖数: 1105 | 7 ~~~~跪请各位高人给讲讲，这题到底是怎么做？
【在 s*****n 的大作中提到】
: 文不对题。可能是要考decorator pattern，保证程序不变，排序方式任意组合。
|
s*****n
发帖数: 5488 | 8 个人看法：
先定义出book对象，sort algorithm对象（应该是个decorator,就是可以pipeline到另
外一个alg对象上），然后需要定义less than, 定义adapter到STL quicksort。
public void sort()
{
call adaptoer method or obj from i to n.
for (i = k; i< booklist.count; i++)
{
if key[i] = key [j] continue;
else
if (mydecotor is not null)
mydecortor.setvalue(j, k);
mydecortor.sort();
}
大概框架应该是这样。
【在 t*****j 的大作中提到】
: ~~~~跪请各位高人给讲讲，这题到底是怎么做？
|
c*******w
发帖数: 63 | 9 可以把Books放到一个Array吗? 然后
Arrays.Sort(bookArray, new BookCompare())
事先定义一个Class BookCompare implements Comparator
{
//Override the compareTo method
public int compareTo(Book book1, Book book2)
{
//rating first
//if a tie, based on price
}
} |
