#!/usr/bin/env python
# coding: utf-8

# *My notes from a Google coding event held at uOttawa on Sep, 25, 2018*
# 
# <hr>

# 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.

# # Problem 1
# 
# > Write a method that when given an array of integers returns the second largest value.

# ## The Easy Way

# In[1]:


def secondLargest(arr):
    arr.sort()
    return arr[-2]


# In[2]:


test1 = [3, 1, 100, 99]


# In[3]:


secondLargest(test1)


# However, this is $O(n\log{n})$.

# ## The Faster Way?

# In[4]:


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


# In[5]:


secondLargest(test1)


# `secondLargest2()` only requires one loop and each loop only does constant time operations. Therefore, it is $O(n)$.

# ## With Selection Sort??
# 
# 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).

# # Comments
# 
# - 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

# # Question 2
# 
# > 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

# ## Rush Solution
# 
# First attempt developed with help from Dan (the guy who sat beside me):

# In[6]:


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


# In[7]:


doubleDecker([1, 2, 1, 2, 1])


# Can $a$ and $b$ be the same value? I kind of doubt it, but the question doesn't say definitively that $a \ne b$.

# In[8]:


doubleDecker([1, 2, 2, 2, 1, 2])


# ## Second Attempt

# 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.

# In[9]:


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


# In[10]:


# No double decker
ddTest1 = [1, 2, 1, 2]


# In[11]:


ddHelper(ddTest1)


# In[12]:


# Double decker!
ddTest2 = [1, 2, 1, 2, 1]


# In[13]:


ddHelper(ddTest2)


# 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:

# In[14]:


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


# In[15]:


ddTest3 = ddTest1 + ddTest2
ddTest3


# In[16]:


doubleDecker2(ddTest3)


# In[17]:


doubleDecker2([])


# 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.

# # Conclusions
# 
# 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