Distinct Number
Given n integers find number of disctinct integers among them. Constraint : 'n <= 2 * 10^5'. Tried by maintaining a unorder_set first but that times out when there are 2 * 10^5 unique integers. But storing it in a vector and sorting all at time seem to work fine. Good to find what is the complexity when we use unordered_set and why is it slow?
Ferris Wheel
Given n integers divide them into groups of 2 or 1 so that sum of integers in the group doesn't exceed x. We just have to sort the array and maintain two pointers going from front and back. Intersting thing is while initializing a vector when the reserve function is used sort function doesn't work? but when resize is use it works.
Concert Ticket
Given n tickets and m customer. Each ticket has a price and customers have a certain maximum value they can spend on the ticket. If customers come one by one, what will be the price for each customer? To solve the first tried to sort it and do binary search for each customer. But since multiple tickets can have same price and we can't reuse a ticket binary search can be linear. So we use this new concept called Coordinate Compression which means we can reduce the size of sorted vector if duplicate values can be eliminated.
No comments:
Post a Comment