r****l
发帖数: 32 | 1 this is a coding question for senior java developer. If you can do it,
send answer to my mitbbs mailbox. i will fit in you an interview.
Online Auction Coding Sample Instructions
Implement a solution to the following problem using the latest released
version of Java. Your project should include unit tests using the open
source JUnit framework. The program should be an object-oriented API and
should not include a user interface of any kind. There is no need to
provide any form of data persistence.
We are looking for clean, well-factored, object-oriented code that has
accompanying JUnit tests.
Here are the requirements:
Consider a new and different computerized auction site where a seller
can offer an item up for sale and people can bid against each other to
buy the item. The company building this site has asked you to come up
with the algorithm to automatically determine the winning bid after all
bidders have entered their information on the site. Your API will be
integrated into the site by other developers working on the project.
The site will allow each bidder to enter three parameters:
Starting bid - The first and lowest bid the buyer is willing to offer
for the item.
Max bid - This maximum amount the bidder is willing to pay for the item.
Auto-increment amount - A dollar amount that the computer algorithm will
add to the bidder's current bid each time the bidder is in a losing
position relative to the other bidders. The algorithm should never let
the current bid exceed the Max bid. The algorithm should only allow
increments of the exact auto-increment amount.
Here is the data to use for your testing. In each case the algorithm
should determine the winning bidder and the amount of the winning bid.
The bidders are listed in the order they entered their information on
the site. If there is a tie between two or more bidders, the first
person that entered their information wins. The amount of the winner's
bid should be the lowest amount possible (given all the previous rules)
that will win the auction.
Auction One -
Bicycle
Auction Two -
Scooter
Auction Three -
Boat
Bidder: Alice
Starting bid
$50
$700
$2,500
Max bid
$80
$725
$3,000
Auto-increment amount
$3
$2
$500
Bidder: Aaron
Starting bid
$60
$599
$2,800
Max bid
$82
$725
$3,100
Auto-increment amount
$2
$15
$201
Bidder: Amanda
Starting bid
$55
$625
$2,501
Max bid
$85
$725
$3,200
Auto-increment amount
$5
$8
$247 |
r****l
发帖数: 32 | 2 ding
【在 r****l 的大作中提到】
: this is a coding question for senior java developer. If you can do it,
: send answer to my mitbbs mailbox. i will fit in you an interview.
: Online Auction Coding Sample Instructions
: Implement a solution to the following problem using the latest released
: version of Java. Your project should include unit tests using the open
: source JUnit framework. The program should be an object-oriented API and
: should not include a user interface of any kind. There is no need to
: provide any form of data persistence.
: We are looking for clean, well-factored, object-oriented code that has
: accompanying JUnit tests.
|
m****i
发帖数: 650 | |
y***m
发帖数: 7027 | 4 只是interview,offer还远着...
公司，薪水透明后大火看是否合适再弄呗
【在 r****l 的大作中提到】
: this is a coding question for senior java developer. If you can do it,
: send answer to my mitbbs mailbox. i will fit in you an interview.
: Online Auction Coding Sample Instructions
: Implement a solution to the following problem using the latest released
: version of Java. Your project should include unit tests using the open
: source JUnit framework. The program should be an object-oriented API and
: should not include a user interface of any kind. There is no need to
: provide any form of data persistence.
: We are looking for clean, well-factored, object-oriented code that has
: accompanying JUnit tests.
|
e*****e
发帖数: 1275 | 5 这题目大家有啥思路？俺觉得挺有意思的。。。。
我所想到的就是第一找true max.
true max 就是用auto increase, 你能bid 到最高的
num_max_inc = (max - start)/incr
true_max = start + num_nmax_inc * inc;
如果你的inc太高，一步就超过max了，true_max 就是 start
第二就是找second max from all the true max list.
如果没有second max, 大家都愿意出到最高，那就哥们1，最先bid的那个是winner.
如果有seonc max,如下。。。
max 可以有好多duplicate,如果没有duplicate,
这个max - N*inc 大于secon max, 这就是解。N>=0,要最大。
然后从哪个duplicate 的 max 的true_max list 里面找solution.
比如如下。。。second max is 14, max is 18
A 15, 18
B 16, 17, 18
C 16, 18
怎么找solution呢？ 去掉max,然后找second max'好了。。。就是recursive 一直到找
到solution.
随便写的，也不知道对不对，请指正。~~~~~~
>_< |
i**********e
发帖数: 1145 | 6 你的解法可以再 generalized 些，不需要特别处理 duplicate 情况：
解法如下：
Assume a[i] = starting bid, b[i] = largest bid, k[i] = bid increment amount,
where i is the person's index
1) First, calculate the maximum possible bid for each person = a+k*floor((b-
a)/k).
2）Second, find the max and the second_max (can be done in O(N) with about
2N comparisons) among all the maximums calculated in 1). You don't have to
store the results in 1) with extra storage, you can just calculate and
record the max/second_max at the same time (You would need to record the
index too). Doesn't matter if there are duplicates for max. max will always
be the first seen element among the duplicates. There are efficient ways to
find the max and the second_max with minimum number of comparisons (N+log N-
2) such as the tournament algorithm, but that is more advanced and doesn't
improve the run time asymptotic bound.
3) Then the winning bid amount for the player with the max bid is:
Assign a = a[index_of_max], k = k[index_of_max]
a+k*ceiling((second_max - a)/k)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 e*****e 的大作中提到】
: 这题目大家有啥思路？俺觉得挺有意思的。。。。
: 我所想到的就是第一找true max.
: true max 就是用auto increase, 你能bid 到最高的
: num_max_inc = (max - start)/incr
: true_max = start + num_nmax_inc * inc;
: 如果你的inc太高，一步就超过max了，true_max 就是 start
: 第二就是找second max from all the true max list.
: 如果没有second max, 大家都愿意出到最高，那就哥们1，最先bid的那个是winner.
: 如果有seonc max,如下。。。
: max 可以有好多duplicate,如果没有duplicate,
|
e*****e
发帖数: 1275 | 7 哦，对对对。。俺脑子进水了。。。。。。想到duplicate的时候想歪了~~~~
多谢指正~~~ |
z********i
发帖数: 543 | 8 我觉得 每个action里面维护一个bider_list
然后模拟每轮拍卖
超过bidder max bid的就从list里面删去
就成了 |
e*****e
发帖数: 1275 | |
z********i
发帖数: 543 | 10 这个atuo increase怎么理解呢
这个increase是加在bidder自己之前的bid上呢
还是现在的price上呢
比方说，
auto increase
A 3
B 4
假设一开始是0
A bid了3
那B应该是4呢 还是7呢？
【在 e*****e 的大作中提到】
: 那个效率不好~~~~不过也算是solution
|
|
|
i**********e
发帖数: 1145 | 11 应该是 4. B 没必要把 bid 给加到 7，因为他本身是 high bidder.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 z********i 的大作中提到】
: 这个atuo increase怎么理解呢
: 这个increase是加在bidder自己之前的bid上呢
: 还是现在的price上呢
: 比方说，
: auto increase
: A 3
: B 4
: 假设一开始是0
: A bid了3
: 那B应该是4呢 还是7呢？
|
z********i
发帖数: 543 | 12 这样的话，不就只要算出每人能出的最高价
再比较，就完了？
【在 i**********e 的大作中提到】
: 应该是 4. B 没必要把 bid 给加到 7，因为他本身是 high bidder.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
r****l
发帖数: 32 | 13 company:financial service provider for hedge funds.
location : mid town Manhattan.
salary: 120k+ based on experience.
role: senior tech lead role.
hope above info helps. can't give more details unless you send in a
qualified answer to my mit inbox. |
r****l
发帖数: 32 | 14 nobody think of multi threading solution? it will be much clean and simple.
each bider is a runnable , sharing a current bid price on each item. |
e*****e
发帖数: 1275 | 15 为啥要multi-thread 呢？ 俺假设这service 是在server 上run的。。。一个user 一
个thread....那多浪费啊, 关thread switch context 就忙不过来~~~何况现在很多
server 都是event driven.
就mantain一个current winner table for each item,一个线程专门来搞这个~~
当然如果item太多。。。。像ebay那么NB,就只好多线程啦~~那也是一个线程管一堆
item
BTW: senior tech lead role 120+少了点~~~那是在manhattan 哦~~~金金堆起来滴地
方哦~~~
俺可是听说有个非死不可的东东，fresh graduate都给150K得~~~俺现在天天都在做梦
投奔非死不可~~~抢钱抢粮抢股票~~ |
B*M
发帖数: 1340 | 16 这题都够个大paper了，
估计是来骗idea的，
【在 r****l 的大作中提到】
: this is a coding question for senior java developer. If you can do it,
: send answer to my mitbbs mailbox. i will fit in you an interview.
: Online Auction Coding Sample Instructions
: Implement a solution to the following problem using the latest released
: version of Java. Your project should include unit tests using the open
: source JUnit framework. The program should be an object-oriented API and
: should not include a user interface of any kind. There is no need to
: provide any form of data persistence.
: We are looking for clean, well-factored, object-oriented code that has
: accompanying JUnit tests.
|
e*****e
发帖数: 1275 | 17 这题目不难啊~~~
我倒是觉得很多amazon滴题目好刁~~ |
