Given starting and endings time of movies, return maximum number of movies we can watch. Could come up with recurcive solution where f(1...n) = max ( 1 + f(k...n), f(2..n)) which can be memoized and dp can be used to reduce the time taken. But it seems there is a greedy approach where we sort by ending time and watch it in that order. It seem to give the maximum number of movies. Need to prove it. Two action items pending here -
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.
This is a simulation-based problem, we have to multiply the number with 3 and
add one if it is odd or divide it by 2 if it is even. Do it till we reach 1.
Missing Numbers
We will be given a number n and n-1 number from 1 to n. We have to find the
missing number. Maintained an arr of length n and marked the entry 1 if it
appeared.
Space complexity: O(n)
Create Strings 1:
Given a string, print all different combinations of it in a lexicographically sorted way. Used recursion. GetPermutations takes freq_array and size of expected string and returns the list of permutations possible. For each possible first letter, it appends it with strings returned by GetPermutaions( freq_array
with current char removed, size - 1). Time Complexity: O(2^n)
Apple Division
Given a bunch of apples and their weights, divide them into two groups such that the difference in weights is minimum. The approach here is to find all possible combinations and get the combination with the minimum absolute difference with total total_sum/2. Using the above algorithm to find the total sum for all combinations. This approach led to Timeout. Apparently, a better approach to code with is by using "Looping with BitMask".
for (int i = 0; i < 1 << n; i++) {
// new combination
for (int j = 0; j <= n; j++) {
if (1 << j & i) {
// included in current combination
}
}
}
In this case, we have to find out the sum of each combination so we just have to maintain a sum var in outer for loop and in the inner loop include each element in sum if the IF condition is satisfied.
