Q1) Given a n rows of m seats, and a list of specific taken seats, return how many ways 2 people can sit next to each other. Limits: n and m up to 1 billion and number of taken seats up to 50.
A1) Very very easy. Use long long to avoid overflow. For each row with taken seats get the sorted taken seats in that row, then for each gap greater than 1, add gap-1 to the total. Finally add number of empty rows times m-1.
Not my favourite kind of question, simply because I am not uber-speed code writer.
Q2) Given a counter which ticks down every minute, and a set of k items which each have a time length, but increase the counter by j at a specific time within that time length, determine the maximum number of items which can be processed completely before the counter drops below 0. If there are multiple ways to achieve this goal, return the order which prefers lower numbered items first. Limits: k up to 20.
A2) Each item has a minimum requirement, and a net effect. If there is a non-negative net effect which we can meet the minimum requirement for, we want to use it. If there are only negative net effects, which we can meet the minimum requirements for, we will never be able to use anything which is currently not at minimum requirement. However, the order of the things left is non-trivial.
With a limit on k of only 20, every possible subset is a valid consideration if we can process it quickly. This provided a hint, but I needed to look at a solution to get the rest. If we divide the input into start and end sections, we can determine which of the end section can be placed immediately after the start section. This lets us create a DP of maximum number which can be processed from a set which appear after the rest not in the set (regardless of whether the rest not in the set can actually all be processed before it). That final condition may sound crazy, but once you get to the full set, the not-in set becomes empty set and the condition is fine, so the rest doesn’t matter.
Once the DP is done, you just have to do the ‘reverse dp walk’ to construct the output.
Q3) Given a list of items and 2 queues to put them in, where each item has a processing time, which depends which queue it is in, and after processing is placed into the other queue, unless it has already been processed by that queue, determine how many different ways to place the items in the 2 queues subject to 2 conditions. 1) The items have to be added to the queues in the same order as the input. 2) Neither queue must ever be empty before the other queue has finished its initial list. Limits: up to 47 items and each processing time is between 1 and 20.
A3) No clue – the processing time limit seems suspiciously small though. Maybe a dp on the number of solutions with an initial queue time of n? Let me look at a solution.
Rather than solving the problem as given, solve a different problem, number of ways for queue 1 to run out before queue 2 is done its initial list. Then switch queues and use the same logic again. Subtract both from number of possible distributions.
So, how to count the number of ways for it to run out. Each time we put something on to queue 1, it makes it harder to run out, each time we put something on queue 2 it is easier to run out. Some analysis is required to work out the DP. The definition of fail is if total queue 1 time + total time of first i-1 from queue 2 processed at queue 1 speed – total time of first i from queue 2 processed at queue 2 speed < 0 for any i. We want to know what the minimum of the left for any i is, for each possible distribution in order to know whether it has failed, if that minimum is less than 0, then it is a fail. As each new item is added to the pile this function changes. If we add one to queue 1, all possible left hand sides increase by the processing time, thus also increasing the minimum. If we add one to queue 2, the inequality doesn’t change except for the new i=new length of queue 2 case. In that case the inequality equals the previous scenario where all were processed minus the new addition as a possible new minimum. So we can minimize between that and the old minimum. The only problem is we need to know that previous scenario as well. So ‘previous scenario’ and ‘minimum’ are 2 parameters to the DP, the 3rd being number of items en-queued.
Now that we have this new parameter we need to know how it changes. If we add to the first pile, it goes up exactly the same as the minimum does, adding the queue 1 processing time. If its added to the second queue, that causes a subtraction of the queue 2 processing time, and an addition of the queue 1 processing time.
Potential range on previous scenario and minimum are pretty large so memory is an issue if the entire dp was kept in memory. Helpfully each case only depends on the previous number of items en-queued, and the final summation is only on the full list of items en-queued, so we can throw away memory as we go. (Avoid garbage collection issues and alternate arrays, don’t keep allocating.) Additionally with the inequality range being +/- ~900, that is close to 200million dp locations filled without any optimisation. Running with c++ this is probably reasonable, but with Java further trimming helped. For instance minimums only ever get smaller and we are only interested in the negative ones, so treat all positive minimums as 0, and we save half the state space. Furthermore the area of the DP increases by +/- 20 in both dimensions with each step, taking this into account can save another factor of ~3 rather than blindly checking every spot.
Again out of my range, but useful to sit down and understand how it works.