Task 1: Third Highest
Task
You are given an array of integers.
Write a script to find out the Third Highest if found otherwise return the maximum.
My solution
This is relatively straight forward. It is clear from the third example, that we only care about unique numbers. The first thing I do is sort the list removing non-unique numbers. For Python, I use sorted(set(n)). Sets are by-definition unique, and sorted will turn the set back to a list. In Perl, I used sort {$a <=> $b} (uniq(@n)). uniq comes from List::Util, while {$a <=> $b} sorts values numerically.
If there are three or more unique values in the list, I get the value third from the end and display it. If there are less than 3 unique values, I display the last one.
Examples
$ ./ch-1.py 5 3 4
3
$ ./ch-1.py 5 6
6
$ ./ch-1.py 5 4 4 3
3
Task 2: Maximum XOR
Task
You are given an array of integers.
Write a script to find the highest value obtained by XORing any two distinct members of the array.
My solution
In both Python and Perl, the ^ operator returns the XOR-ed value of the two integers. Like with the first task, I remove non-unique values. A number XOR-ed with itself will always be zero.
I'm sure some cleverer Team PWC members have some formula to get the most efficient XOR-ed values, I just try every combination.
Given that we only need to compare two values, I use a simple iteration rather than methods like combinations from itertools to produce all possible combinations.
This is done with two loops. The outer loop (with the variable first) loops from 0 to 2 less than the length of the array. The inner loop (called second) loops from one more than first to one less than the length of the array. For each iterations, I calculate the XOR-ed number of the two numbers at the appropriate position. If it is greater than the current max, I set a new max value.
Examples
$ ./ch-2.py 1 2 3 4 5 6 7
7
$ ./ch-2.py 2 4 1 3
7
$ ./ch-2.py 10 5 7 12 8
15
Top comments (1)
For problem 1 you don't need to sort the whole list. That's on average o(n*log(n)). Just keep a list of the highest values, up to 3. Kind of an expanded version of the typical max search algorithm. Can be done in o(n) guaranteed.