Looks like it was pretty competitive to qualify in this round. With two questions that were not that difficult and one which was quite unusual and challenging the top 1000 were defined by getting both of the first 2 questions completely in under 2:15. The third question was unusual because it was based on randomness to the point that there was a chance you would get it wrong even if your code was as good as it could be.
Q1) Given a set (no duplicates) of binary representations of equal length, determine if there exists a bit flip pattern which can be applied to all of them such that they become set equal to a second set (no duplicates) of binary representations of same size and length.
A1) The actual wording of this question was quite involved and I suspect would hide how easy this question is to many. The small input was limited to up to 10 bits in length, so a brute force of the 2^10 bit flip patterns could be tried. Large input however went to 40 bits to ensure such an approach wouldn’t work.
Looking at the other constraint however, the number of elements in each set, that is limited to 150, so a O(N^2) is clearly feasible. Since every element in the original set has to map to an element of the target set, obviously at least one element in the original has to map to an element of the target set. So take one element of the original set and determine the bit flip pattern which will work for each member of the target set. Then for each of these up to 150 patterns (rather than potentially 2^40) the set equality can be tested.
For a nice compact solution code, the bit patterns on input can be parsed into 64 bit integers. Then the bit flip pattern can be represented as another 64 bit integer, which will be applied using xor. In this version generating the (up to) 150 patterns is as simple as calculating the xor of one element of the first set with each element of the second. Each element of the target set can be placed into a set object, and the set equality (since we already know that they have the same number of elements and that xor with a pattern is a bijection, so there won’t be any duplicates generated) is as simple as checking that every value in the original set xor’d with the pattern value is a member of that target set.
Q2) Given a connected acyclic undirected graph, determine the minimum number of nodes to remove to be able to make it into full binary tree (where every node other than a leaf has 2 children for some choice of root).
A2) Again the small input invites brute force with only up to 15 nodes. The large input of up to 1000 nodes is more interesting.
With a limit of 1000 nodes O(N^2) is acceptable, and this is not too difficult to obtain. Choosing each of the nodes in turn as a possible root node, a recursive solution taking two parameters, current node index and previous, can traverse the tree in O(N) time. Specifically the recursion is the maximum nodes which can be kept – the final answer then being the best of each possible root subtracted away from the total number of nodes in the original graph.
The recursion is to consider every edge of the current node which doesn’t connect to the previous node. Recursion down those edges will return a set of values. If the set is 2 or greater, choose the largest two and return the sum, plus one for the current node. Otherwise just return 1, since only this node can be kept. For each recursion run from a root this obviously linear in the number of edges. Each edge is only considered twice, once on the way out and again to be excluded at the next level down in the recursion. Since there are no cycles in the graph, the recursion trivially terminates when it gets to a node with no connections other than to the previous node. Since the graph is acyclic and connected the number of edges equals N – 1 and so the total running time over all recursions is O(N^2).
Of interest to me here was whether the problem can be solved in O(N). The recursion itself invites a memoization over previous and current, which has O(N) states, but a simple star type graph, shows the total time in this case is still O(N^2) because the centre node of the star can be arrived from each of the leaves and has O(N) exiting edges which must be considered. Even with the trivial optimization of not calling the recursion if there is only 1 candidate which fixes the basic star case, slightly more complicated star type graphs are still O(N^2).
I think I have a solution, which unfortunately complicates the algorithm a bit. The idea is for each node to gather the (up to) 3 highest values of the recursion which have it as the previous node. So we start by performing the standard set of recursions, but rather than simply taking the best 2, and memoizing the sum we take a slightly different set of rules. First check if a memoization value for current node exists. If not, recurse as normal, but store the 3 highest values and the previous index in the memoization for the current node, rather than memoizing against the sum against the current/previous pair. If a value does exist in the memoization table but the table entry also contains a valid previous index which is not the same as the current one, call the recursion specifically for that edge, and replace the smallest value in the memoization table if appropriate, and mark the previous index in the memoization table as invalid. Now there are up to 3 largest values in the table, and we can select the 2 largest of those are not for the previous index.
So, the memoization table contains O(N) entries, each of which get updated at most twice. Since it is clear that the recursive calls made are only a subset of those made by the original algorithm, it will terminate. The claim that it is has a total run time of O(N) is slightly trickier. The first time a specific value in the memoization table is calculated, it could involve O(N) calls to recursion, but because the memoization is stored keyed by nodes instead of by previous/current pairs it won’t potentially be rerun for multiple different previous nodes, which is what caused the O(N^2) logic in the previous version. Basically each node may be visited once for every edge it has, but the total work performed over those visits is proportional to the number of edges it has. Since each edge connects 2 nodes, each edge in the graph might be considered twice, but not repeatedly as in the original algorithm. This makes the total run time proportional to the number of edges and hence total run time is O(N).
Q3) Given 120 examples of permutations of the numbers 0 through 999 where each one was generated either by a correct, or incorrect random shuffle with a 50% chance, correctly identify at least 109 of them. Initial state before shuffle is ascending order and the incorrect random shuffle performs one random swap for each index in order from first index to last, with a randomly selected index which is selected amongst all indexes. (As opposed to correct which only selects from current or higher indexes.)
A3) Since the incorrect shuffle has as a subset of its possible swaps all of the possible swaps performed by the correct shuffle, there is no pattern which is ‘obviously’ only the output of the correct shuffle. Also since every permutation is a possible output of the correct shuffle there are none which are obviously only the output of the incorrect shuffle. Therefore the best you can do is come up with a heuristic which tells you something about the probability of a permutation being from the incorrect shuffle and hope that it can managed to identify 109 out of 120 a decent percentage of the time.
I think the key component of this problem is actually writing a program to perform the incorrect shuffles so you can look at the probability distributions. One aspect of a correct random shuffle is the probability of index i being k should be equal for all valid k and i. If you were to run 1 million shuffles for instance, there should be approximately 1000 cases of any given index i being equal to a specific value k. Running 1 million incorrect shuffles, takes a while, but not so long as to rule out doing it once for every time you submit the problem set. Indeed this naturally leads to an approach of generating this table, and then for each input looking up the index and value for the 1000 elements, and calculating a product of the ratio of the value in the table to 1000 (to avoid over/underflowing double) for each lookup. The higher the result the more likely it is from the incorrect shuffle. It might seem at first glance that a threshold of one is appropriate but the calculations are more complicated than that and they are effectively overlapping distributions where you want to choose a threshold to minimize false positives and false negatives. Potentially better luck can be had by taking into account the fact that things are generated with equal probability of correct or wrong and instead sorting the scores and giving out the highest half scores as being incorrect and the lower half as being from the correct sort method.
I found this approach to be somewhat cumbersome, and 1 million incorrect shuffles is 1 billion random number and swap operations, which is a lot of CPU time to be chewing up every submission. So I had a look at the generated tables and tried to come up with a formula which approximated their outcome with minimal computation cost. I came up with if value <= index return 1.0, otherwise linearly interpolate 1.3 to 0.7 for values between index + 1 and 999. Using this and some sample testing I ran on my machine with a bunch of randomly generated problem sets I was managing to get a >93% success rate at identifying individual permutations correctly with an appropriately selected threshold. This may only be 112 out of 120, but it does provide a pretty decent chance of getting past on any given submission.