Leetcode Master Flashcards
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor appetite[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size cookie_size[j]. If cookie_size[j] >= appetite[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
GREEDY
Brute:
Assign each cookie optimally/greedily to the children.
1. Sort the children greed array
2. Iterate cookie array, Start with smallest cookie, assign it to the first child with greed[i] <= cookie size, if he has not received it.
TC: O(NlogN + O(N*M)
Optimized:
Sort both cookie and greed arrays.
Take two pointers for cookie and child (greed) array.
if a child can be satisfied with current cookie, increment child.
Always increment cookie, whether it was given to a child or not.
NOTE: intuition, The child with most appetite wil suffer, and children with average to below average appetite will has higher probablitiy of getting the cookie.
TC: O(NlogN + MLogM) + O(N+M)
At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
GREEDY?
Approach:
Initialize inventory of 5$, 10$ bills to 0.
Traverse the bills,
if bill is $20: check for
1 10$ bill and 1 5$ bill in inventory
3 5$ bills in inventory
if not return False
<Order is important above, 5$ denominations can be flexible, so you would want to keep it>
if bill is $10: check for
1 5$ bill
if not return False
Add 10$ bill to inventory
if bill is $5:
Add $5 to inventory
TC: O(N)
Shortest Job First Scheduling Algorithm
A software engineer is tasked with using the shortest job first (SJF) policy to calculate the average waiting time for each process. The shortest job first also known as shortest job next (SJN) scheduling policy selects the waiting process with the least execution time to run next.
Given an array of n integers representing the burst times of processes, determine the average waiting time for all processes and return the closest whole number that is less than or equal to the result.
Approach:
Sort the array of burst times.
Initialize time to be zero
Initialize total_waiting_time to be zero
Traverse the burst times array.
Increment total_waiting_time by current time (as waiting time for current process).
Pick up the process (Increment time by burst times).
In the end return average = total_wait_time / number of processes.
TC: O(N)
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Approach:
Initialize global_reachable_index to 0
- Traverse the array
IMP: If current index > global_reachable_index then return False as this index can never be arrived at. - Calculate the current_reachable_index as index + jump value at that index
- Update the global_reachable_index if it is greater.
- If global_reachable_index exceeds length of array, return True.
End of Loop
TC: O(N)
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Approach:
Initialize
curr_end = 0
index = 0
Traverse nums array
1. Get the farthest you can travel.
2. if you have reached current end, update the jump count. And update current end to farthest.
return the number of jumps
INTUITION:
1. Till you make a jump from current end, you explore the farthest you can jump from any of index till current end.
2. Because you can reach the currend index in a single jump, you can jump anywhere before that index in a single jump too and use it to reach the farthest end.
