A piece of advice I used to give followed the lines of “If I managed to do it… so can you!”. In retrospect, that was terrible advice because I perpetuated survivorship bias. A younger student at my college recently confessed to me their admiration for my successes and their hopes to manifest as something akin to myself. While I’m flattered someone would regard me as a desirable outcome, I regret not being forthcoming on my failures.
I’m open about my bitter childhood because it makes my current all the sweeter. I never talk about my current bitters because they haven’t yet yielded fruit. Talking about my current trails would detract from the overall persona I want to present.
That reason is precisely why I want to start documenting those struggles. It is not so simple as foot of the mountain to high horse. In the process, I hope I will become a better mentor.
A few days ago I did a code sprint competition on HackerRank with my friend Steven, a second year CS major. With fresh Starbucks coffees and muffins in hand, we had one hour to answer 3 increasingly difficult questions. I’ll provide the link for the full description if you want to read them, but I’ll also sum up the question and my problem solving approach to them.
Question 1: Chess Board. Rated: Easy. First place time: 1 min 03 sec. Our time: 14 min 23 sec.
The input is a 8 by 8 binary array. Determine if the board is a valid chess board.
A chess board needs to alternate values and the following row needs to be the opposite of the values above it. In pseudo code, I know I needed to do these steps:
1.) Check if the first row is alternating
2.) Flip the values for the second row
3.) Check that all even rows are the same as row 0
4.) Check that all odd rows are the same as row 1
5.) If the above are satisfied, return True, otherwise False
We wrote a loop to check each element with the next element in the first row. We wrote a helper function flip(x) that would allow us to loop through a good row and return the opposite for each element, thereby producing the next good row. We then iterate through the whole array row by row instead of element by element to check row equivalence. It was clean code that ran without problems on the first try and scored us full marks.
There will be some who regard our method as overly complicated and others who feel we skipped a few steps in explaining the method. A good teacher can simplify or explain as needed to suit the individual—something I hope to eventually do.
Question 2: Coprime sets. Rated: Medium. First place time: 8 min 20 sec. Our time: 46 mins, did not finish.
The input is an array of varying integers up to a million or so. Find the number of coprime set pairings that can be made from the given array, meaning the gcd of the geometric sum of both sets is 1. In addition, return the answer as in modulo form.
Unlike the chess board problem, I did not have an immediate plan. I did not even have an immediate understanding of the question. The first thing that came to mind was the math library in python has a gcd function, but that would mean running possibly thousands of iterations through the gcd function and sorting by values == 1. For the extremely large inputs, we would probably time out. It would also be a question if we could even generate all the possible sets that need to be inputted to the gcd function. Then I thought about Euclidian’s algorithm and prime numbers. Finding the gcd is basically simplifying factors until only prime numbers remain. So in any given array, we could get rid of all composite numbers first. And if we get rid of all composite numbers, the gcd of all prime numbers is 1 because primes are all coprime. That was our plan. Steps:
1.) Remove composite numbers from an array so only primes remain
2.) Take the factorial (using python math library) to calculate the total number of “pairs” we can make. **
3.) Convert answer to modulo form
**Sets are unique collections of unordered elements. So even though we are finding “pairs” of sets, it’s basically just different ways of rearranging the same prime array. The number of ways of rearranging a list is the factorial.
We ran out of time typing up this solution and didn’t convert our answer to modulo form, earning 0 marks. Even then, I’m not sure it would have worked on the first try.
Question 3: Did not attempt. Did not read.
In summary, I got wrecked. I ranked 1173 out of 1906.