Problem:

Amazon has decided to migrate the inventory data to Amazon.com cloud from other platform. It has the following feature : The cheapest item will be displayed first ,

1. 1st View returns the first cheapest item, similarly kth view returns the kth item in the list so far.
2. It is ensured that items already exist before the view query;

We have 2 kinds of operations "INSERT", "VIEW". "INSERT" inserts the item into the list, "VIEW" returns the cheapest element ( kth view returns k th cheapest element).

Input : we have each string with 3 entires [ "operation" , "item-name","cost"]
Return: result should be a vector of items when "View" Query comes up;

Eg : [["INSERT", "burger","4"],
["INSERT", "gum","1"],
["VIEW", "-" ,"-" ],
["INSERT", "chocolate","3"],
["INSERT", "PORK", "2"],
["VIEW","-","-"]]
Expected Result : ["GUM","PORK"]

Explanation ->
Gum(1) , burger(4) <-View => return "GUM" ( 1st View //returns first cheapest element from the list so far)
Gum(1), pork(2), chocolate(3), burger(4) => return "PORK" ( 2nd View //returns second cheapest element from the list so far).

I have solved the question using set the following approach, could pass 10/15 TestCases with TLE
TimeComplexity of the algorithm is O(N^2) - since finding the kth element we have to traverse the set from the beginning

vector<string> ShoppingList(vector<vector<string>> entries){
	set<pair<int,string>> s;
	int views = 0;
	vector<string> ans;
	for(auto entry : entries){
		if(entry[0] == "INSERT")
			s.insert(make_pair(stoi(entry[2]),entry[1]));
		else{
			auto it = s.begin();
			advance(it,views);
			ans.push_back(it->second);
			views++;
		}
	}
	return ans;
}

Can anyone suggest any better approach? (Seems like a design problem).

There can be multiple inputs with same prices, in that case we have to return an item with lexographically smaller name.