/********
Information:
	Assumptions: 
		Box weight is never 0 or negative, percentile is in 0 < p <= 1.
	Approach:
		Store all the boxes in a map for quick, associative storage and retrieval by boxId string.
		A separate sortedweights vector is kept to sort boxes by weight and retrieve a weight given the percentile.
	Runtime:
                // actually, it's O(n) to write and O(1) to retrieve either percentile weight or box weight. You could improve the write to O(log n) easily.
		O(nlogn) to write, O(logn) to retrieve weight by ID, O(1) to retrieve percentile weight
	Storage:
                // remember, multiples don't matter for big O. This is just O(n) storage
		O(2n)
	Additional Data Structures:
                // depending on what they wanted from the percentile function, I would advocate dropping the vector and trying to just use the map, as you 
                // introduce the possibility of inconsistent duplicate data. 
		A map to store and retrieve boxes by ID and a vector to store weights in sorted order.
	Possible Improvements:
		Turn sortedweights insert into a binary insert instead of linear insert to improve write runtime to O(2logn).

********/

#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <vector>

// Generally, it's considered good practice to avoid polluting the namespace. Instead of "using namespace std;", you would make calls out to std::map, std::vector,and the like.
using namespace std;

class BoxManager {
        /* variables in C++ are private by default, but I'd rather see a confirmation that these structures are private and not viewable outside the class, just for readability's sake/
         */
	map<string,double> boxes;
	vector<double> sortedweights;

public:
	void write(string boxId, double weight);
        /* since both of these functions do not change the state of BoxManager, they should both be labelled as const.
         */
	double getWeightByBoxId(string boxId);
	double getWeightAtPercentile(double percentile);
};

// Write new box into boxes map and into a sorted weights vector (for percentile retrieval)
void BoxManager::write(string boxId, double weight) {
        /*
         * What happens in the case where boxId already exists? Should an exception be thrown? Should the weight of the box be updated?
         */
	boxes[boxId] = weight;
	
        /*
         * this is an O(n) insertion operation on this list. you can find the position this needs to be inserted at with a O(log n) binary search. 
         * But you already mentioned that. A binary search isn't hard to code.
         * Much faster for large cases.
         */
	int i;
	for(i = 0; i < (int)sortedweights.size(); i++) {
		if(weight <= sortedweights[i]) {
			sortedweights.insert(sortedweights.begin()+i, weight);
			break;
		}
	}

	if (i == (int)sortedweights.size()) {
		sortedweights.push_back(weight);
	}

	return;
}

// Find box by ID and return weight. Result will be 0 if not found.
double BoxManager::getWeightByBoxId(string boxId) {
        /*
         * What happens in the case where boxId does not exist?
         */
	return(boxes[boxId]);
}

// Find a box's weight at the given percentile
double BoxManager::getWeightAtPercentile(double percentile) {
        /*
         * What happens when I pass in a value of percentile that is not between 0 and 1?
         */
	int index = (int)ceil(percentile * (double)sortedweights.size());
	return(sortedweights[index-1]);
}

int main(void) {
	BoxManager boxmgr;
	boxmgr.write("test1", 1);
	boxmgr.write("test2", 2);
	boxmgr.write("test3", 3);
	boxmgr.write("test4", 4);
	boxmgr.write("test5", 5);
	boxmgr.write("test6", 6);
	boxmgr.write("test7", 7);
	boxmgr.write("test8", 8);
	boxmgr.write("test9", 9);
	boxmgr.write("test10", 10);
	
	cout << boxmgr.getWeightByBoxId("test3") << endl;
	cout << boxmgr.getWeightByBoxId("test7") << endl;
	cout << boxmgr.getWeightByBoxId("test10") << endl << endl;
	
	cout << boxmgr.getWeightAtPercentile(0.1) << endl;
	cout << boxmgr.getWeightAtPercentile(0.25) << endl;
	cout << boxmgr.getWeightAtPercentile(0.6) << endl;
	cout << boxmgr.getWeightAtPercentile(0.99) << endl;

	return(0);
}