A very interesting Question to be done in C or C++ as platform:
Given two input files.
Input file1.csv
Each line in the file describes a websites.
The first field is unique identifier for the site, the second field is the minimum amount in cents, the third field is a string that is the site’s URL:
2181, 320, abc.com
3288, 450, pqr.com
9662, 567, xyz.com
2675, 721, lmn.com
6434, 500, rst.com
8123, 5000, jjj.com
Input file2.csv
Each line in the file describes an ad. The first field is a 32bit unsigned integer which is the unique identifier for the ad , the second field which is the maximum amount in cents the ad is willing to pay to show on a site, the third field specifies the number of sites the ad wants to display on, followed by the site_ids of the sites.
9822, 450, 3, 2181, 9662, 66434
3421, 897, 3, 2675, 9662, 3288
8961, 342, 1, 9662
7623, 2000, 3, 2181, 2675, 9662
all integr fields are 32bit unsigned integer
In the above example, ad 9822 is willing to play on 3 sites(abc.com, xyz.com and rst.com) and pay a maximum amount of 450 cents. WAP that decides the appropriate ad by applying the following rules
1. An ad can be shown on this site only if the site is in the list of sites that the ad is interested in.
if no ad id found for a ite, then no ad is returned
2. The ad that is returned is chosen an auction thats is called second price auction. For ads to qualify for the second price auction,
auction for a site their bid_price should be greater than or equal to the reserve_price of the
site. The winner of the auction is the ad that has the maximum bid_price among these ads, and this
winning ad pays the second highest ad’s bid_price. For instance, if two ads with bid_price 500
and 600 are competing for a site that has a reserve_price of 400, then the ad that bid 600 wins,
but pays 500 (the second highest ad’s bid price).
3. In case of a tie between two or more ads, the ad with the lower ad_id wins and pays it’s
bid_price. In case, the auction has only one ad that qualifies, then that ad wins and pays
reserve_price of that site.
4. In case there are no ads that qualify for the auction for a site either because no ad expresses interest
in playing on that site or because none of the ads have bid_price greater than or equal to
reserve_price of that site then no ad is returned.
Your server should accept input file path,first.csv and the second.csv as
arguments and wait for input. The input is the site_id and the adserver should return the ad_id of the ad that wins the second price auction and price the ad pays for the display. An input of 1 ends the program. example:
$ ./adserver sites.csv ads.csv
2675
7623 897
3288
3421 450
6434
0 0
9999
0 0
8123
0 0
1
$
DIRECTIONS:
1. The code should compile at least on
http://www.compileonline.com/compile_cpp_online.php
2. Please note that will test your program on larger input files with 20K+ sites and
20K+ ads.
3. You have 1.5 hour to solve the problem, test and submit your solution. Your goal is to provide a working solution at least. You may submit additional code later if you think you can make it work better or faster.
For starters If I were to do this in Java:
Algo:
Step1: I/O
Store both the File Paths from STD IN
Take the SITE_ID as Input Then
Step 2: Pre Processing
Site_Map:
Create a Dictionary/HashMap of All the Site_ID and their Price
Ad_Map:
Create a Dictionary/HashMap of All the Ad_ID and the Ammount they Have
Site_to_Ad Map:
Create a Dictionary/HashMap of All the Site_ID and the Ad_IDs Interested to be on them.
Step 3: Auction Method
Iterate through the Site_to_Ad Map.
Fetch the Amount for Each ad_id from the Ad_Map
Compare it against the min price and if greater store it in a variable along with the ID. Fetch the Next ID and IF it is Higher, Replace and put this value in the variable. If there is a draw, compare the two ap_ids and store the one that has min ad_id value.
If min bid is not reached or if there are no ad_id values for that site, return no ad.
Add Constraints to the Auction block.
I believe in c++ we would use Dictionaries to achive this as we have HashMap in Java, can someone help m with the syntax.
Here is working code in C++.
- hankm2004 April 12, 2014