某公司一道面试题：赛车名次， 桶排序

本文主要是介绍某公司一道面试题：赛车名次， 桶排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Suppose you are a fan of auto-racing and want to figure out which drivers are likely to perform well in an
upcoming race. Luckily you have access to a log of the times that each racer started and finished their test race
the day before.

The particular rating algorithm you have chosen is to assign each racer R a score that equals the number of
other racers who both started after R started and also finished before R finished.

Note that a lower score generally suggests that the racer is faster, and this rating algorithm keeps from penalizing
fast racers who have slow times simply because they are stuck behind a crash or slow racer. Additionally, this
rating algorithm does not reward fast racers who pass tons of slow racers in comparison to fast racers who race
when there are not many slow racers on the track to pass (compare this with rating a racer based on the net
number of passes).

More formally, you want to write a program that will read the test race log from standard input. The first line of
the log contains a single integer n from 0 to 70,000 that represents the number of racers in the log. The next n
lines of the test race log have the following format:
racerId startTime endTime
where racerId is an integer in the range [0,10^9] and startTime and endTime are both integers such that 0
<= startTime < endTime <= 10^18. Each racerId will be distinct. Also, the collection of all start and end
times will not contain any duplicate elements.

Given such an input, you should print output in the following format:
racerId score
where score is the score as defined above for racer racerId. The output lines should be sorted in ascending
order of score with ties broken by sorting by racerId, also in ascending order. This can be accomplished with
a simple sort at the end.

Directions:
Please code this problem in Java, C, or C++. Your solution should run in o(N^2) time on all inputs (i.e., strictly less
than O(N^2) -- an O(N^2) algorithm will not be fast enough).

Hint: The naive brute force solution is too slow to run within the time limit. You will need to think of a faster
solution. Specifically, we are looking for a solution that is guaranteed to be less than O(N^2) on all inputs. One
possible way to accomplish this (there are several other acceptable methods) is to use a data structure with K
buckets (e.g., K = 300), each of which is initially empty and is defined by two times. Each bucket will eventually
contain racers whose start time falls between the two times. The bucket boundaries should be chosen such that
they ultimately will contain the same number of racers. Then iterate through the racers in end time order and, as
you iterate over each racer, build up this bucketed data structure in such a way that you can use it to quickly
count the number of racers that finished before him but started after him.

What We Are Looking For:
For this problem, we simply want to see that you can implement the algorithm correctly, without particular regard
to principles of object orientation or modularity. Do give us at least minimal documentation to help us
understand what you are trying to accomplish in certain key places of the algorithm.

Example:
input:
5
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198

output:
3 0
4 0
1 1
5 2
2 3

Note in the above example that racer 3 has a score of 0 because no one starts after racer 3 (a drawback to this
scoring system is the last racer always has a score of 0). Racer 4 also has a score of 0 because the only racer who
starts after racer 4's start time (racer 3) has a later finish time. Racer 3 is listed ahead of racer 4 despite having a
slower time because racer 3's id is lower. At the other end, racer 2 has a score of 3 because racers 3, 4, and 5
start after racer 2 and finish before racer 2 finishes.

解答：

要注意的几点：

1）输入是stdin；

2）赛车手编号范围0-10^9，int；开始和完成时间0-10^18，long long；

3）桶排序，桶的尺寸和个数。

#include <iostream>
#include <vector>
#include <cassert>
#include <set>using namespace std;typedef int racerID_t;
typedef long long startTime_t;
typedef long long endTime_t;struct racer {racerID_t racerID;startTime_t startTime;endTime_t endTime;racer(racerID_t arg_racer, startTime_t arg_st, endTime_t arg_et):racerID(arg_racer), startTime(arg_st), endTime(arg_et) {} 
};struct endTimeSort{bool operator()(racer r1, racer r2){return r1.endTime > r2.endTime;}
};struct scoreSort{bool operator()(pair<racerID_t, int> r1, pair<racerID_t, int> r2){if(r1.second == r2.second)return r1.first < r2.first;else {return r1.second < r2.second;}}
};int main() {int numberOfRacer = 0;int bucketSize = 100;cin >> numberOfRacer;int numberOfBuckets = numberOfRacer / bucketSize;vector<racer> racerArray;/// Initialize the buckets.vector<set<racer, endTimeSort>> racerBucket(numberOfBuckets + 1);assert( numberOfRacer != 0 );startTime_t maxStartTime = 0;while( numberOfRacer > 0 ){racerID_t id;startTime_t start;endTime_t end;cin >> id >> start >> end;if( start > maxStartTime)maxStartTime = start;racerArray.push_back(racer(id, start, end));numberOfRacer--;}/// while( !racerArray.empty() ){racer current = racerArray.back();int bucketIndex = (int)((double)(current.startTime / maxStartTime) * numberOfBuckets);racerBucket[bucketIndex].insert(current);racerArray.pop_back();}set<pair<racerID_t, int>, scoreSort> scoreArray;for(vector<set<racer, endTimeSort>>::iterator iter = racerBucket.begin(); iter < racerBucket.end(); iter++){for(set<racer, endTimeSort>::iterator iter2 = iter->begin(); iter2 != iter->end(); iter2++){int score = 0;racerID_t id = iter2->racerID;for(set<racer, endTimeSort>::iterator iter3 = iter2; iter3 != iter->end(); iter3++){if(iter3->startTime >= iter2->startTime && iter3->endTime < iter2->endTime)score++;}scoreArray.insert(pair<racerID_t, int>(id, score));}}for(set<pair<racerID_t, int>, scoreSort>::iterator iter = scoreArray.begin(); iter != scoreArray.end(); iter++){cout << iter->first << " " << iter->second << endl;}return 0;
}

一年后修改做法：

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
#include<climits>using namespace std;typedef int racerID_t;
typedef long long startTime_t;
typedef long long endTime_t;struct Racer {racerID_t racerID;startTime_t startTime;endTime_t endTime;int score;
};struct Bucket {vector<startTime_t> startTimes;startTime_t earliestStartTime;startTime_t latestStartTime;
};bool startTimeSort(const Racer r1, const Racer r2) {return r1.startTime < r2.startTime;
}bool endTimeSort(const Racer r1, const Racer r2) {return r1.endTime < r2.endTime;
}bool scoreSort(const Racer r1, const Racer r2) {if(r1.score == r2.score)return r1.racerID < r2.racerID;elsereturn r1.score < r2.score;
}int getBucketIndex(vector<Bucket> & buckets, long long startTime) {int low = 0, high = (int)buckets.size()-1;int middle = 0;while(low <= high) {middle = (low + high) / 2;if(buckets[middle].earliestStartTime <= startTime && buckets[middle].latestStartTime >=  startTime)return middle;else if(buckets[middle].earliestStartTime > startTime)high = middle - 1;elselow = middle + 1;}return middle;
}int insertAndComputeScore(vector<Bucket> & buckets, int startBucket, int endBucket, long long startTime) {vector<long long>::iterator iter = buckets[startBucket].startTimes.begin();int temp = 0;for(; iter!= buckets[startBucket].startTimes.end(); iter++) {if(*iter > startTime) {buckets[startBucket].startTimes.insert(iter, startTime);break;}temp++;}if(iter == buckets[startBucket].startTimes.end())buckets[startBucket].startTimes.push_back(startTime);int score = (int)buckets[startBucket].startTimes.size() - temp - 1;for(int j = startBucket + 1; j <= endBucket; j++)score += buckets[j].startTimes.size();return score;
}void initBuckets(vector<Bucket> & buckets, vector<Racer> & racers) {int numberOfBuckets = (int)sqrt(racers.size());//cout << numberOfBuckets << endl;int racersPerBucket = (int)racers.size() / numberOfBuckets;sort(racers.begin(), racers.end(), startTimeSort);for(int i = 0; i < numberOfBuckets; i++) {buckets.push_back(Bucket());buckets[i].earliestStartTime = racers[i * racersPerBucket].startTime;buckets[i].latestStartTime = racers[i * racersPerBucket + racersPerBucket - 1].startTime;}buckets[numberOfBuckets-1].latestStartTime = LLONG_MAX;
}void fillBucket(vector<Bucket> & buckets, vector<Racer> & racers) {unsigned numberOfRacers = (unsigned)racers.size();sort(racers.begin(), racers.end(), endTimeSort);int whichBucketStart = 0, whichBucketEnd = 0;for(unsigned i = 0; i < numberOfRacers; i++) {whichBucketStart = getBucketIndex(buckets, racers[i].startTime);whichBucketEnd = getBucketIndex(buckets, racers[i].endTime);racers[i].score = insertAndComputeScore(buckets, whichBucketStart, whichBucketEnd, racers[i].startTime);}
}int main(int argc, const char * argv[])
{ifstream infile("data.txt", ios::in);if(infile) {vector<Racer> racers;string line;getline(infile, line);int number = atoi(line.c_str());for(int i = 0; i < number; i++) {Racer r;getline(infile, line);string word;istringstream stream(line);stream >> word;r.racerID = atoi(word.c_str());stream >> word;r.startTime = atoll(word.c_str());stream >> word;r.endTime = atoll(word.c_str());racers.push_back(r);}infile.close();vector<Bucket> buckets;initBuckets(buckets, racers);fillBucket(buckets, racers);sort(racers.begin(), racers.end(), scoreSort);//Test start.for(int i = 0; i < racers.size(); i++)cout << racers[i].racerID << " " << racers[i].score << endl;ofstream outfile("result.txt");if(outfile) {for(int i = 0; i < racers.size(); i++)outfile << racers[i].racerID << " " << racers[i].score << endl;outfile.close();} else {cout << "The file doesn't exist!" << endl;}//Test end.} else {cout << "The file does not exist." << endl;}return 0;
}

这篇关于某公司一道面试题：赛车名次， 桶排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---