My notes from a Google coding event held at uOttawa on Sep, 25, 2018
The event started with some resume tips and then moved into coding problems. We were given a problem and 5 minutes or so to solve it. Some students wrote their solutions on blackboards and explained them to the room. The Googlers running the event asked questions ("what happens if an array with duplicate elements is passed in?") and provided advice.
It was fun and gave me an idea what a technical interview at Google is like.
Write a method that when given an array of integers returns the second largest value.
def secondLargest(arr):
arr.sort()
return arr[-2]
test1 = [3, 1, 100, 99]
secondLargest(test1)
99
However, this is $O(n\log{n})$.
def secondLargest2(arr):
largest = 0
secondLargest = 0
for el in arr:
if el > largest:
# Then we have a new largest number
largest = el
if (el > secondLargest) and (el < largest):
# Then we have a new second largest number
secondLargest = el
return secondLargest
secondLargest(test1)
99
secondLargest2()
only requires one loop and each loop only does constant time operations. Therefore, it is $O(n)$.
A student came up with an interesting solution using a modified variant of Selection Sort. His strategy was to use Selection sort except move larger values to the front and stop early (as soon as the second largest was found). This approach is $O(K*N)$ , where $K$ is the $K^{th}$ largest element in the array.
An interesting property is that this solution can be generalized to more than just the second largest value.
An assumption was made that the second largest element can be the same as the largest element (e.g. the second largest value of [3, 5, 4, 5]
is 5).
We should ask clarifying questions (what happens if there is a duplicated element)?
Don't start programming right away. Plan it out, use diagrams
Declare input and output types
Write a method that when given an array of integers returns true if any of the values make a double decker. A value is considered a double decker if it appears 3 times with an alternating second value (a, b, a, b, a).
[1, 2, 1, 2, 1] -> True
First attempt developed with help from Dan (the guy who sat beside me):
def doubleDecker(arr):
if len(arr) < 5:
return False
for i, el in enumerate(arr):
if (i + 4) > len(arr)-1:
return False
if (el == arr[i+2]) and (el == arr[i+4]) and (arr[i+3] != el) and (arr[i+1] != el):
return True
doubleDecker([1, 2, 1, 2, 1])
True
Can $a$ and $b$ be the same value? I kind of doubt it, but the question doesn't say definitively that $a \ne b$.
doubleDecker([1, 2, 2, 2, 1, 2])
False
First I'm going to create a function that takes an array of at least 5 elements and returns True
if it contains a double decker.
def ddHelper(arr):
# ddHelper only works with arrays of 5 element or less.
if len(arr) > 5:
raise ValueError('ddHelper only works with arrays of 5 elements or less!')
# If the array contains less than 5 elements, it cannot hold a double decker
if len(arr) < 5:
return False
# A double decker is possible.
# Start by unpacking the array:
first = arr[0]
second = arr[1]
third = arr[2]
fourth = arr[3]
fifth = arr[4]
# Then apply the conditions a set of 5 values must satisfy in order to be a double decker.
# Condition 1: the first element must match the third and fifth elements.
if not ( first == third == fifth ):
return False
# Condition 2: the second element must match the fourth element.
if not ( second == fourth ):
return False
# Assumption: 'a' can not equal 'b' in [a, b, a, b, a]. This assumptions leads to...
# Condition 3: the first element cannot equal the second element.
# Note that at this point, it has been established that first == third == fourth and
# second == fourth.
if first == second:
return False
# If the function hasn't returned yet, a double decker exists in arr.
return True
# No double decker
ddTest1 = [1, 2, 1, 2]
ddHelper(ddTest1)
False
# Double decker!
ddTest2 = [1, 2, 1, 2, 1]
ddHelper(ddTest2)
True
I should probably make test cases for all the conditions, but I feel pretty good about this function.
To handle larger arrays, I'll write a second function:
def doubleDecker2(arr):
# Move down the array, testing every 5-element subset to see if it is a double decker.
# We can stop as soon as it becomes impossible to slice out a 5-element subset.
# e.g. [..., n-4, n-3, n-2, n-1, n] at index n-4, it is no longer possible to form a 5-element
# subset.
finalIndex = len(arr) - 4
for i in range(finalIndex):
# Slice out the next 5 elements (from i to i+5).
s = arr[i:i+5]
# Check if the slice is a double decker.
result = ddHelper(s)
# If it is, the array contains a double decker!
if result:
return True
# The function never returned, so the array must not contain a double decker.
return False
ddTest3 = ddTest1 + ddTest2
ddTest3
[1, 2, 1, 2, 1, 2, 1, 2, 1]
doubleDecker2(ddTest3)
True
doubleDecker2([])
False
Something that may feel a bit weird about this solution is: does it actually test all possible 5-element groupings? I think it does, but I don't feel 100% confident about it.
This solution also turned out quite long and possibly more complicated than it needed to be. The draft solution was much shorter.
I should:
grind more HackerRank problems
practice writing code on a white board and explaining my thought process aloud
review algorithms and data structures
write Python more often to forgetting syntax