This isn't a solution write-up.
I'm just noting the parts I missed, tips to remember, and so on.
- New ID Recommendation - LEVEL 1
Coding Test Practice - New ID Recommendation
When you need to remove certain elements from an array many times,
you can handle it in O(N) by copying into another array.
- Menu Renewal - LEVEL 2
Coding Test Practice - Menu Renewal
- Ranking Search - LEVEL 2
Coding Test Practice - Ranking Search
Language, job group, experience, and soul food split into 4, 3, 3, 3 options each, so
you could store this in a 4D array, but
if you call each attribute's index idx1, idx2, idx3, idx4,
you can store it more simply in a 1D array like idx127 + idx29 + idx3*3 + idx4.
Speed-wise too, it gets slow when references keep happening, so this seems like a much better way.
- Shared Taxi Fare - LEVEL 3
Coding Test Practice - Shared Taxi Fare
Honestly, it's just that the algorithm is used less than in other problems,
but in terms of measuring how well you can apply things it was really easy.
- Ad Insertion - LEVEL 3
Coding Test Practice - Ad Insertion
If play_time's max second weren't 360000, this would have been a LEVEL 4 problem.
You just record how many viewers are watching at each second in O(N), then
go through every second with prefix sums or sweeping, record the max cumulative watch time, and return it.
If the seconds got really large, you'd have to infer the following fact
If we call the time each viewer starts or stops watching an event,
the start time of the public service ad is an element of event.
Because, suppose our answer is in a part that doesn't change even if the event moves a bit to the right or left;
moving it a bit to the left doesn't change the viewers' cumulative time,
and we have to return the leftmost answer, so it's proven that it's not the answer we're looking for.
So for each event, you have to consider both whether the public service ad starts there or ends there.
What to remember when implementing is that every time you move,
you have to check whether the event that would be the next ad end time is closer to the current ad end time,
or whether the event that would be the next ad start time is closer to the current ad start time,
and iterate over whichever event is closer.
- Matching Card Pairs - LEVEL 3
Coding Test Practice - Matching Card Pairs
I tried to handle every state with bitmasking, but
bitmasking is made of only 0s and 1s, so it can only record two kinds of states.
So recording whether a card is face up, face down, or already found makes the data structure pretty huge.
If this were the intended solution, the difficulty should have been higher,
I should have caught on from the fact that there are at most 6 kinds of cards.
Decide the order of cards to find first with permutation (6!), and
running a bfs to find those cards is enough to solve it within the time limit.