LinkedIn_Phone_interview question

# For Ryan Voldstad only
# A quick implementation about the 2 phone interview question in code and with test.

# you can run this file in the terminal 
# ex: python file_path/LinkedIn_Phone_interview_questoin.py

# Second question
from collections import defaultdict
import sys

class WordDistanceFinder(object):
    """
    This class will be given a list of words (such as might be tokenized
    from a paragraph of text), and will provide a method that takes two
    words and returns the shortest distance (in words) between those two
    words in the provided text.
 
    ::
      finder = WordDistanceFinder(["the", "quick", "brown", "fox", "quick"])
      assert finder.distance("fox", "the") == 3
      assert finder.distance("quick", "fox") == 1
 
    "quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
        (3 - 1) = 2 and (4 - 3) = 1.
 
    Since we have to return the shortest distance between the two words we return 1.
 
    """
    def __init__(self):
        self.dictionary = defaultdict(list)
    
    def preprocess(self, words):
        """
        Builds up word dictionary once.

Complexity: 
            O(N) where N is the number of words.
        """
        for idx, word in enumerate(words):
            self.dictionary[word].append(idx)
        
    def distance(self, wordOne, wordTwo):
        """
        Getting distance between wordOne and wordTwo
        Args:
            wordOne (str): A word string.
            wordTwo (str): A word string.
        """
        word_one_idx = self.dictionary[wordOne] 
        word_two_idx = self.dictionary[wordTwo]
        return self.getSmallest(word_one_idx, word_two_idx)
    
    def getSmallest(self, l1, l2):
        """
        Get the smallest difference between two list. 
        Args:
            l1 (list): A list of integers
            l2 (list): A list of integers

Complexity: 
            O(M + N) where M is the length of l1 and N is the length of l2.
        """
        distance = sys.maxint
        l, r = 0, 0
        # base case where words cant be found.
        if not l1 or not l2:
            return -1
        while(l < len(l1) and r < len(l2)):
            diff = abs(l1[l] - l2[r])
            if ( diff< distance) and diff != 0:
                # update the distance
                distance = diff
            # move pointer
            if (l1[l] > l2[r]):
                r += 1
            else:
                l += 1
        return distance

list_of_strings = ["the", "quick", "brown", "fox", "quick"]
finder = WordDistanceFinder()
finder.preprocess(list_of_strings)

# TEST CASES
assert finder.distance("fox", "the") == 3
assert finder.distance("quick", "fox") == 1
assert finder.distance("quick", "quick") == 3  # Special case where search the same word
print('='*10 + ' Pass WordDistanceFinder tests ' + '='*10)

# first question
class NestList(object):
    def __init__(self, values):
        self.content = values
    
    def sumDepth(self):
        """
        Get the depth sum from Nested list
        """
        return self.helper(1)
    
    def helper(self, depth):
        """
        Calculate the sum base on the depth of the nested list
        Args:
            depth (int): A number represents the depth of nested list
        """
        result = 0
        for ele in self.content:
            try:
                result += ele.helper(depth+1)
            except:
                result += ele * depth
        return result

# TEST CASES
assert NestList([1, 1, NestList([2, 2]) ,1]).sumDepth() == 11  # {1, 1, {2, 2}, 1} -> 1 + 1 + 1 + 2 * (2 + 2) = 11
assert NestList([1, NestList([2, NestList([3, 3]), 2])]).sumDepth() == 27  # {1, {2, {3,3}, 2}} -> 1 + 2 * (2 + 2) + 3 * (3 + 3) = 27
print('='*10 + ' Pass NestList sum tests ' + '='*10)

Python Fiddle

Python Cloud IDE