Data Structure and Algorithm - Detect Missing Numbers in a Large Set

1. Problem Description
This is an Amazon interview question for senior software development engineer from careercup. Here is the original thread,
"

Given an array of 1 billion numbers with just a few 100 missing, find all the missing numbers. you have only enough memory to store only 10k elements

- PS October 07, 2016 in United States | Report Duplicate | Flag ".


2. Data Structure and Algorithm
3 approaches are proposed in my C++ post, Data Structure and Algorithm - Detect Missing Numbers in a Large Set. The C++ implementation is there too.

3. Python Implementation
An abstract base class called "NumberStream" is implemented to act as the 1 billion numbers. A derived class called "NumberGenerator" is implemented to return the numbers with range of 1 billion with missing numbers.

A loop and recursive solution are implemented for Approach 2. A loop implementation is implemented for Approach 3. The test is based on a smaller scale, with 1 million number with 100 missing and 10000/100000/1000000 memory available

# *******************************************************************************
# Implementation
# *******************************************************************************
from abc import ABCMeta, abstractmethod

class NumberStream:
    """description of class"""
    __metadata__ = ABCMeta

    @abstractmethod
    def HasNext(self):
        pass

    @abstractmethod
    def GetNext(self):
        pass

    @abstractmethod
    def ResetToHead(self):
        pass

    @abstractmethod
    def GetMissingNumbers(self):
        pass  

    @abstractmethod
    def GetUpperBound(self):
        pass

    @abstractmethod
    def GetMissing(self):
        pass
.
from NumberStream import NumberStream
import random

class NumberGenerator(NumberStream):
    """description of class"""

    def __init__(self, upperBound, missing):
        #super(self, upperBound, missing)
        self.m_UpperBound = upperBound
        self.m_Missing = missing
        self.m_MissingNumbers = set()
        self.m_CurVal = 0;
        self.m_MissingDetected = 0;
        random.seed()
        count = 0
        # generate random numbers as the missing numbers
        while count < missing:
            temp = random.randint(1, upperBound)
            if temp not in self.m_MissingNumbers:
                self.m_MissingNumbers.add(temp)
                count = count + 1

    def GetNext(self):
        self.m_CurVal = self.m_CurVal + 1
        while self.m_CurVal in self.m_MissingNumbers:
            self.m_CurVal = self.m_CurVal + 1
            self.m_MissingDetected = self.m_MissingDetected + 1
        return self.m_CurVal

    def HasNext(self):
        return self.m_CurVal < self.m_UpperBound and \
            (self.m_UpperBound - self.m_CurVal) > (self.m_Missing - self.m_MissingDetected)
 
    def ResetToHead(self):
        self.m_CurVal = 0
        self.m_MissingDetected = 0  

    def GetMissingNumbers(self):
        return self.m_MissingNumbers

    def GetUpperBound(self):
        return self.m_UpperBound

    def GetMissing(self):
        return self.m_Missing

# Approach 2 and 3 implementation
from NumberStream import NumberStream

import sortedcontainers
import sys

class MissingNumberDetector(object):
    """description of class"""

    def __init__(self):
        pass

    def __FindMissingNumber(self, numberStream, lowerBound, upperBound, memSize, results):
        try:
            #linear detect the missing number
            hashMap = bytearray([00]*memSize*4)
            numberStream.ResetToHead()
            while numberStream.HasNext():
                temp = numberStream.GetNext()
                if temp >= lowerBound and temp <= upperBound:
                    idx = (temp - lowerBound)/8
                    bits = (temp - lowerBound) - idx*8
                    hashMap[idx] = hashMap[idx] | (1 << bits)
            index = -1
            number = lowerBound
            for value in hashMap:
                if number > upperBound:
                    break
                index = index + 1
                if value == 255:
                    number = number + 8;
                    continue;
                for bit in range(0, 8):
                    flag = value & (1 << bit)
                    # each bit to represent if a number is missing (0 - missing)
                    if flag == 0:
                        results.add(lowerBound + index * 8 + bit)
                    number = number + 1;
                    if number > upperBound:
                        break;
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])

    # Approach 2 recursive implementation
    def DetectMissingNumber(self, numberStream, memSize = 1000):
        try:
            results = set()
            if numberStream.GetMissing() == 0:
                return results
            searchQueue = []
            searchQueue.append((1, numberStream.GetUpperBound()))
            totalLinearDetectSize = 1000 * 32
            while len(searchQueue) != 0:
                (lowerBound, upperBound) = searchQueue.pop()
                if (upperBound - lowerBound) <= totalLinearDetectSize:
                    # find missing numbers in small range (within mem size)
                    self.__FindMissingNumber(numberStream, lowerBound,\
                                    upperBound, memSize, results)
                else:
                    numberStream.ResetToHead();
                    mid = (lowerBound + upperBound)/2
                    countOf1stHalf = 0
                    countOf2ndHalf = 0
                    while numberStream.HasNext():
                        temp = numberStream.GetNext()
                        if temp <= mid and temp >= lowerBound:
                            countOf1stHalf = countOf1stHalf + 1
                        elif temp > mid and temp <= upperBound:
                            countOf2ndHalf = countOf2ndHalf + 1
                    if countOf1stHalf < (mid + 1 - lowerBound):
                        # push [lowerBound, mid]
                        searchQueue.append((lowerBound, mid))
                    if countOf2ndHalf < (upperBound - mid):
                        # push [mid + 1, upperBound]
                        searchQueue.append((mid + 1, upperBound))                      
            return results                  
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])
 
    # Approach 2 recursive internal implementation 
    def __DetectMissingNumber_R(self, numberStream, lowerBound,\
                                                        upperBound, memSize, results):
        try:
            if (upperBound - lowerBound) <= memSize*32:
                self.__FindMissingNumber(numberStream, lowerBound,\
                                upperBound, memSize, results)
                return

            numberStream.ResetToHead();
            mid = (lowerBound + upperBound)/2
            countOf1stHalf = 0
            countOf2ndHalf = 0
            while numberStream.HasNext():
                temp = numberStream.GetNext()
                if temp <= mid and temp >= lowerBound:
                    countOf1stHalf = countOf1stHalf + 1
                elif temp > mid and temp <= upperBound:
                    countOf2ndHalf = countOf2ndHalf + 1
            if countOf1stHalf < (mid + 1 - lowerBound):
                # sub problem [lowerBound, mid]
                self.__DetectMissingNumber_R(numberStream, lowerBound,\
                                mid, memSize, results)
            if countOf2ndHalf < (upperBound - mid):
                # sub problem [mid + 1, upperBound]
                self.__DetectMissingNumber_R(numberStream, mid + 1,
                                upperBound, memSize, results)          
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])  

    # Approach 2 recursive implementation
    def DetectMissingNumber_R(self, numberStream, memSize = 1000):
        try:
            results = set()
            if numberStream.GetMissing() > 0:
                self.__DetectMissingNumber_R(numberStream, 1, \
                       numberStream.GetUpperBound(), memSize, results)
            return results
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:              
            print ("Unexpected Error: ", sys.exc_info()[0])

    # Approach 3 implementation - divide ranges
    def __DivideRange(self, numberStream, lowerBound, upperBound, memSize, ranges):
        try:
            division = (upperBound + 1 - lowerBound) / (memSize << 5)
            ladders = sortedcontainers.SortedDict()
            ladders[lowerBound] = 0
            for idx in range(1, division):
                ladders[lowerBound + idx * (memSize << 5)] = 0
            if division * (memSize << 5) < upperBound:
                ladders[division * (memSize << 5) + lowerBound] = 0
         
            numberStream.ResetToHead()
            keys = ladders.keys();
            while numberStream.HasNext():
                temp = numberStream.GetNext()
                if temp >= lowerBound and temp <= upperBound:
                    lBound = ladders.bisect_left(temp)
                    uBound = ladders.bisect_right(temp)
                    if lBound != uBound:
                        key = keys[lBound];
                    else:
                        key = keys[uBound - 1]
                    ladders[key] = ladders[key] + 1

            for idx in range(0, len(keys) - 1) :
                if (keys[idx + 1] - keys[idx]) > ladders[keys[idx]]:
                    ranges.append((keys[idx], keys[idx + 1] - 1))
            if (upperBound - keys[len(keys) -1]) > ladders[keys[len(keys) - 1]]:
                ranges.append((keys[len(keys) - 1], upperBound))
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except IndexError as e:
            print ("IndexError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])
 
    # Approach 3 implementation
    def DetectMissingNumber_Div(self, numberStream, memSize):
        try:
            results = set()
            if numberStream.GetMissing() == 0:
                return results
            searchQueue = []
            searchQueue.append((1, numberStream.GetUpperBound()))
            totalLinearDetectSize = memSize * 32
            while len(searchQueue) != 0:
                (lowerBound, upperBound) = searchQueue.pop()
                if (upperBound - lowerBound) <= totalLinearDetectSize:
                    # find missing numbers in small range (within mem size)
                    self.__FindMissingNumber(numberStream, lowerBound,\
                                    upperBound, memSize, results)
                else:
                    # divide ranges
                    self.__DivideRange(numberStream, lowerBound,\
                                    upperBound, memSize, searchQueue)
            return results                  
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])

# ********************************************************************************
# Unit Test
# ********************************************************************************
import unittest
from MissingNumberDetector import MissingNumberDetector
from NumberStream import NumberStream
from NumberGenerator import NumberGenerator

class Test_MissingNumberDetector(unittest.TestCase):
    def test_MND(self):
        ns = NumberGenerator(1000000, 100)
        mbd = MissingNumberDetector()  
     
        results = mbd.DetectMissingNumber(ns, 1000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber(ns, 10000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber(ns, 100000)
        self.assertEqual(results, ns.GetMissingNumbers())

    def test_MND_R(self):
        ns = NumberGenerator(1000000, 100)
        mbd = MissingNumberDetector()  

        results = mbd.DetectMissingNumber_R(ns, 1000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber_R(ns, 10000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber_R(ns, 100000)
        self.assertEqual(results, ns.GetMissingNumbers())

    def test_MND_Div(self):
        ns = NumberGenerator(1000000, 100)
        mbd = MissingNumberDetector()  

        results = mbd.DetectMissingNumber_Div(ns, 1000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber_Div(ns, 10000)
        self.assertEqual(results, ns.GetMissingNumbers())

        results = mbd.DetectMissingNumber_Div(ns, 100000)
        self.assertEqual(results, ns.GetMissingNumbers())

if __name__ == '__main__':
    unittest.main()

Data Structure and Algorithm - Detect Word Permutation

1. Problem Description
This is a Microsoft interview question for software develop engineer from careercup. Here is the original thread,
"

A list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings.
eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE
eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE
The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string
One more constraint - some words from dict[] may also be left over unused

- novicedhunnu September 15, 2016 in India | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
The solution is based on Trie data structure and algorithm. Details refer to my Python post - Data Structure and Algorithm - Trie.
Pseudo-code and C++ implementation please refer to my C++ post, Data Structure and Algorithm - Detect Word Permutation.

3. Python Implementation
    - Python 2.7
    - Microsoft Visual Studio Community 2015
# ********************************************************************************
# Implementation
# ********************************************************************************
# PermutationDetector.py
from DictionaryTrie import DictionaryTrie

import sys

class PermutationDetector(object):
    """Word Permutation detector"""

    def __init__(self):
        self.m_DictRoot = None

    def __init__(self, words = None):
        self.m_DictRoot = None
        self.ConstructDict(words)

    def ConstructDict(self, words = None, appendMode = False):
        try:
            if words is None:
                return
           
            if self.m_DictRoot is None or appendMode:
                self.m_DictRoot = DictionaryTrie()
       
            for word in words:
                self.m_DictRoot.AddWord(word)
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])

    # non-recursive implementation
    def IsPermutation(self, word = None):
        try:
            if word is None or self.m_DictRoot is None:
                return False
            if len(word) == 0:
                return False

            nextToSearch = [0]
            StrSize = len(word)
            while (len(nextToSearch) > 0):
                # pop first or last (queue/stack) as breadth/depth-first search
                startSearchIndex = nextToSearch.pop(0)
                tempDict = self.m_DictRoot
                idx = 0
                for idx in range(startSearchIndex, StrSize):
                    startSearchIndex +=1
                    tempDict = tempDict.GetChildren()[ord(word[idx])]
                    if tempDict is None:
                        break
                    else :
                        if tempDict.GetValue() is not None:
                            # find a valid word/permutation in trie, push index for next search
                            nextToSearch.append(startSearchIndex)

                if idx == (StrSize - 1) \
                   and tempDict is not None \
                   and tempDict.GetValue() is not None:
                    return True
        except AttributeError as e:
            print ("AtrrinuteError: {0}". format(e))
        except:
            print ("Unexpected Erro: ", sys.exc_info()[0])
        return False

    def __IsPermutation_R(self, word = None, nextToSearch = None):
        try:
            if word is None:
                return False
            if nextToSearch is None or len(nextToSearch) == 0:
                return False
           
            tempDict = self.m_DictRoot
            # pop first or last (queue/stack) as breadth/depth-first search
            startSearchIndex = nextToSearch.pop(0)
            idx = 0
            searchedLen = 0
            for idx in range(startSearchIndex, len(word)) :
                searchedLen += 1
                tempDict = tempDict.GetChildren()[ord(word[idx])]
                if tempDict is None:
                    break;
                else:
                    if tempDict.GetValue() is not None:
                        # find a valid word/permutation in trie, push index for next search
                        nextToSearch.append(startSearchIndex + searchedLen)
               
            if idx == len(word) -1 \
               and tempDict is not None \
               and tempDict.GetValue() is not None:
                return True
           
            return self.__IsPermutation_R(word, nextToSearch)
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])
        return False

    # recursive implementation
    def IsPermutation_R(self, word = None):
        if word is None:
            return False

        nextToSearch = [0]
        return self.__IsPermutation_R(word, nextToSearch)
                           
# ********************************************************************************
# Test
# ********************************************************************************
# Test_PermutationDetector.py    
import unittest

from PermutationDetector import PermutationDetector

class Test_PermutationDetector(unittest.TestCase):
    def test_Failure(self):
        detector = PermutationDetector(("actor", "bad", "act", "good"))
        self.assertFalse(detector.IsPermutation("badactorgoodacting"))
        self.assertFalse(detector.IsPermutation_R("badactorgoodacting"))

    def test_Success(self):
        detector = PermutationDetector(("actor", "bad", "acting", "good"))
        self.assertTrue(detector.IsPermutation("badactorgoodacting"));
        self.assertTrue(detector.IsPermutation_R("badactorgoodacting"));

if __name__ == '__main__':
    unittest.main()

Data Structure and Algorithm - Find Path between Sensors

1. Problem Description
This is a Google interview question for software develop engineer from careercup. Here is the original thread,
"
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).

Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.

Note: all coordinates are real numbers

(a,b)
|----------------------------------------------|
|.............................................................|end
|.............................................................|
|start......................................................|
|.............................................................|
|----------------------------------------------|(c,d)

Edit: You have to avoid sensors.
Also u can move in any direction any time.
- ankit3600 June 14, 2016 in India | Report Duplicate | Flag
".

2. Data Structure and Algorithm

Please refer to my C++ post.

3. Python Implementation

# ********************************************************************************
# Implementation
# ********************************************************************************
# Locaiton.py
import math

class Location(object):
    """Location"""
    def __init__(self):
        self.x = -1.0
        self.y = -1.0

    def __init__(self, x, y):
        self.x = x
        self.y = y

    @staticmethod
    def GetDistance(l1, l2):
        deltaX = l1.x - l2.x
        deltaY = l1.y - l2.y
        return math.sqrt(deltaX*deltaX + deltaY*deltaY)

    def __str__(self):
        return str(self.__dict__)
   
    # implement the following 2 function to enable Location as key of sorted container
    def __eq__(self, rhs):
        return self.__dict__ == rhs.__dict__

    def __cmp__(self, rhs):
        return self.__dict__ == rhs.__dict__

#EdgeCross.py

import sys

class EdgeCross(object):

    """EdgeCross class"""

    @staticmethod

    def LEFT():

        return 0

    @staticmethod

    def TOP() :

        return 1

    @staticmethod

    def RIGHT():

        return 2

    @staticmethod

    def BOTTOM():

        return 3

    @staticmethod

    def MAX():

        return 4

    

    def __init__(self, lb = sys.float_info.max, ub = sys.float_info.min):

        self.lowerBound = lb

        self.upperBound = ub

    # implement the 3 following function to enable it as key of dictionary or sorted container

    def __hash__(self):

        return hash((self.lowerBound, self.upperBound))

    def __eq__(self, rhs):

        return self.lowerBound == rhs.lowBound and self.upperBound == rhs.upperBound

    def __lt__(self, rhs):

        return self.upperBound < rhs.lowerBound

    def SetBounds(self, lb, ub):

        self.lowerBound = lb

        self.upperBound = ub

    def SetLowerBound(self, lb):

        self.lowerBound = lb

    def SetUpperBound(self, ub):

        self.upperBound = ub

    def IsValid(self):

        return self.lowerBound != sys.float_info.max and self.upperBound != sys.float_info.min

    def MergeBounds(self, rhs):

        self.SetBounds(min(self.lowerBound, rhs.lowerBound), \
                                 max(self.upperBound, rhs.upperBound))

class EdgeCrosses(object):

    

    def __init__(self):

        self.ecs = []

        for idx in range(0, EdgeCross.MAX()):

            self.ecs.append(EdgeCross())

#Rectangle.py

from EdgeCross import EdgeCross

import array

class Rectangle(object):

    """Rectangle class"""

    def __init__(self, l, r, t, b):

        self.edges = array.array('d', [0, 0, 0, 0])

        self.edges[EdgeCross.LEFT()] = l

        self.edges[EdgeCross.RIGHT()] = r

        self.edges[EdgeCross.TOP()] = t

        self.edges[EdgeCross.BOTTOM()] = b

#Sensor.py

from EdgeCross import EdgeCross

from EdgeCross import EdgeCrosses

from Location import Location

import math

class Sensor(object):

    """Sensor class"""

    

    def __init__(self):

        self.center = Location()

        self.radius = 0.0

    

    def __init__(self, center, radius):

        self.center = center

        self.radius = radius

        assert(radius > 0)

    def Crossed(self, rhs):

        distance = Location.GetDistance(self.center, rhs.center)

        return distance <= math.fabs(self.radius + rhs.radius)

    def CrossedWithHLine(self, Y, ec):

        if Y >= (self.center.y - self.radius) and Y <= (self.center.y + self.radius):

            deltaY = self.center.y - Y;

            deltaX = math.sqrt(self.radius*self.radius - deltaY*deltaY)

            ec.SetBounds(self.center.x - deltaX, self.center.x + deltaX)

            return True

        return False

    def CrossedWithVLine(self, X, ec):

        if X >= (self.center.x - self.radius) and X <= (self.center.x + self.radius):

            deltaX = self.center.x - X;

            deltaY = math.sqrt(self.radius*self.radius - deltaX*deltaX)

            ec.SetBounds(self.center.y - deltaY, self.center.y + deltaY)

            return True

        return False

#SensorRange.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Sensor import Sensor

class SensorRange(object):
    """SensorRange class"""

    def __init__(self, *args, **kwargs):
        self.edgeCrosses = EdgeCrosses()
        self.sensors = list()

    def MergeEdgeCross(self, ecs):
        for idx in range(0, EdgeCross.MAX()):
            self.edgeCrosses.ecs[idx].MergeBounds(ecs.ecs[idx])

    def Merge(self, sr):
        self.MergeEdgeCross(sr.edgeCrosses)
        self.sensors.extend(sr.sensors)

#FindPathBetweenSensors_Google.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
from SensorRange import SensorRange

import sortedcontainers
from exceptions import AttributeError
import sys

class FindPathBetweenSensors_Google(object):
    """FindPathBetweenSensors of class"""

    def __init__(self, *args, **kwargs):
        return super(FindPathBetweenSensors_Google, self).__init__(*args, **kwargs)

    @staticmethod
    def __FindCrossBetweenSensorAndRect(sensor, rect, edgeCrosses):
        for edge in range(0, EdgeCross.MAX()) :
            if edge & 1:
                sensor.CrossedWithHLine(rect.edges[edge], edgeCrosses.ecs[edge])
            else:
                sensor.CrossedWithVLine(rect.edges[edge], edgeCrosses.ecs[edge])

    @staticmethod
    # merege sensors into sensor ranges
    def __GenerateSensorRangeMap(sensors, rect, breakIfNoPath, vPath, sensorRanges):
        for sensor in sensors:
            toMerge = []
            CUR_SIZE = len(sensorRanges)
            # populate all crossed sensor ranges with this sensor
            for idx in range(0, CUR_SIZE):
                for s in sensorRanges[idx].sensors:
                    if s.Crossed(sensor) :
                        toMerge.append(idx)
                        break
       
            workingSR = None
            if len(toMerge) == 0:
                # create a new sensor range
                sr = SensorRange()
                sr.sensors.append(sensor)
                FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect( \
                                                                        sensor, rect, sr.edgeCrosses)
                sensorRanges.append(sr)
                workingSR = sr
            else:
                # merge all existing sensor range
                # 1. merge the rest into the first senror range
                # 2. erase the sensor ranges except the very first
                for idx in range(len(toMerge) - 1, 0, -1):
                    sRangeToKeep = sensorRanges[toMerge[0]]
                    sRangeToMerge = sensorRanges[toMerge[idx]]
                    sRangeToKeep.Merge(sRangeToMerge)
                    del sensorRanges[toMerge[idx]]
           
                # merge with the sensor
                edgeCrosses = EdgeCrosses()
                FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect(\
                                                                       sensor, rect, edgeCrosses)
                sRangeToKeep= sensorRanges[toMerge[0]]
                sRangeToKeep.MergeEdgeCross(edgeCrosses)
                sRangeToKeep.sensors.append(sensor)
                workingSR = sRangeToKeep
       
            if workingSR is not None and breakIfNoPath:
                if (vPath and workingSR.edgeCrosses.ecs[EdgeCross.LEFT()].IsValid() \
                               and workingSR.edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid())
                    or (not vPath and workingSR.edgeCrosses.ecs[EdgeCross.TOP()].IsValid()
                          and workingSR.edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid()):
                    return False
        return True
   
    @staticmethod
    def __ProcessCornerCase(vPath, edgeCrosses, rect, edge):
        if edge.IsValid():
            if vPath:
                # left corner
                if edgeCrosses.ecs[EdgeCross.LEFT()].IsValid():
                    edge.SetLowerBound(rect.edges[EdgeCross.LEFT()])
                # right corner
                if edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid():
                    edge.SetUpperBound(rect.edges[EdgeCross.RIGHT()])
            else:
                # top corner
                if edgeCrosses.ecs[EdgeCross.TOP()].IsValid():
                    edge.SetUpperBound(rect.edges[EdgeCross.TOP()])
                # bottom corner
                if edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid():
                    edge.SetLowerBound(rect.edges[EdgeCross.BOTTOM()])
            return True
        return False

    @staticmethod
    def __GetMidPointOfFirstGap(ecs, rect, vPath, val):
        lowerBound = rect.edges[EdgeCross.BOTTOM()]
        upperBound = rect.edges[EdgeCross.TOP()]
        if vPath:
            lowerBound = rect.edges[EdgeCross.LEFT()]
            upperBound = rect.edges[EdgeCross.RIGHT()]
   
        if len(ecs) == 0:
            val[0] = (lowerBound + upperBound)/2
            return True
   
        if ecs[0].lowerBound > lowerBound:
            val[0] = (ecs[0].lowerBound + lowerBound)/2
            return True

        if len(ecs) == 1:
            if ecs[0].upperBound < upperBOund:
                val[0] = (ecs[0].upperBound + upperBound)/2
                return True
            return False

        if ecs[0].upperBound < ecs[1].lowerBound:
            val[0] = (ecs[0].upperBound + ecs[1].lowerBound)/2
            return True
   
        return False

    @staticmethod
    def FindPath(sensors, rect, vPath, path):
        try:
            sensorRanges = list()
            if len(sensors) != 0:
                if not FindPathBetweenSensors_Google.__GenerateSensorRangeMap(\
                                                                  sensors, rect, True, vPath, sensorRanges):
                    return False
            if len(sensorRanges) == 0:
                if vPath:
                    path.append(Location(rect.edges[EdgeCross.LEFT()], \
                                         rect.edges[EdgeCross.TOP()]))
                    path.append(Location(rect.edges[EdgeCross.LEFT()], \                                                                                                rect.edges[EdgeCross.BOTTOM()]))
                else:
                    path.append(Location(rect.edges[EdgeCross.LEFT()], \
                                         rect.edges[EdgeCross.TOP()]))
                    path.append(Location(rect.edges[EdgeCross.RIGHT()], \
                                         rect.edges[EdgeCross.TOP()]))
                return True

            ecsFrom = sortedcontainers.SortedSet([])
            ecsTo = sortedcontainers.SortedSet([])
            for sr in sensorRanges:
                if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
                   vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.TOP()]):
                    ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.TOP()])
                if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
                   vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.BOTTOM()]):
                    ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.BOTTOM()])
                if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
                   vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.LEFT()]):
                    ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.LEFT()])
                if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
                    vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.RIGHT()]):
                    ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.RIGHT()])
 
            valFrom = [0.0]
            valTo = [0.0]
            if FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
                                                                       ecsFrom, rect, vPath, valFrom) \
               and FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
                                                                             ecsTo, rect, vPath, valTo) :
                if vPath:
                    path.append(Location(valFrom[0], rect.edges[EdgeCross.TOP()]))
                    path.append(Location(valTo[0], rect.edges[EdgeCross.BOTTOM()]))
                else:
                    path.append(Location(rect.edges[EdgeCross.LEFT()], valFrom[0]))
                    path.append(Location(rect.edges[EdgeCross.RIGHT()], valTo[0]))
                return True
        except AttributeError() as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected error: ", sys.exc_info()[0])
        return False

# ********************************************************************************
# Test
# ********************************************************************************
from FindPathBetweenSensors_Google import FindPathBetweenSensors_Google
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
import unittest


class Test_Test_FindPathBetweenSensors(unittest.TestCase):
    def test_A(self):
        path = []
        rect = Rectangle(1.0, 9.0, 8.0, 1.0)
        sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
                    Sensor(Location(4.0, 3.0), 1.0), \
                    Sensor(Location(6.0, 3.0), 1.0), \
                    Sensor(Location(8.0, 3.0), 1.0) ]
        self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
        self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
        self.assertEqual(path[0], Location(1.0, 2.0))
        self.assertEqual(path[1], Location(9.0, 2.0))

    def test_B(self):
        path = []
        rect = Rectangle(1.0, 9.0, 8.0, 1.0)
        sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
                    Sensor(Location(4.0, 3.0), 1.0), \
                    Sensor(Location(6.0, 3.0), 1.0), \
                    Sensor(Location(8.0, 3.0), 1.0), \
                    Sensor(Location(8.0, 8.0), 1.0), \
                    Sensor(Location(7.0, 7.0), 1.0) ]
        self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
        self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
        self.assertEqual(path[0], Location(1.0, 2.0))
        self.assertEqual(path[1], Location(9.0, 2.0))

    def test_C(self):
        path = []
        rect = Rectangle(1.0, 9.0, 8.0, 1.0)
        sensors = [ Sensor(Location(2.0, 7.2), 1.0), \
                    Sensor(Location(3.0, 6.0), 1.0), \
                    Sensor(Location(4.0, 4.5), 1.0), \
                    Sensor(Location(8.0, 7.2), 1.0), \
                    Sensor(Location(7.0, 6.2), 1.0), \
                    Sensor(Location(2.0, 3.0), 1.0), \
                    Sensor(Location(3.0, 4.0), 1.0), \
                    Sensor(Location(9.0, 1.0), 1.0) ]
        self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
        self.assertEqual(path[0], Location(5.0, 8.0))
        self.assertEqual(path[1], Location(4.5, 1.0))
        path = []
        self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
        self.assertEqual(path[0], Location(1.0, 2.0))
        self.assertEqual(path[1], Location(9.0, 4.6))

if __name__ == '__main__':
    unittest.main()

Data Structure and Algorithm - Find the Maximal Traffic between Cities

1. Problem Description:
This is a Google interview question for software engineer/developer from careercup. Here is the original thread,
"

You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:

Input:
1   2
 \ /
  5
 / \
4   3
Output:
1 14
2 13
3 12
4 11
5 4

Input:
         38
         /
        8
        /
      7
     /
1   2
 \ / \
  5   15
 / \
4   3
Output:
1 82
2 53
3 80
4 79
5 70
7 46
15 68
8 38
38 45

- djway August 10, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm

The data structure and algorithm is based on graph.

Details please refer to my C++ post.

3. Python Implementation

    - Python 2.7

    - Microsoft Visual Studio Community 2015

# ********************************************************************************

# Implementation

# ********************************************************************************

# gNodeHelper.py
from exceptions import AttributeError
import sys

# dict() to take neighbour id as key and MaxTraffic as value
class gNode (object):
    def __init__(self, id, traffic):
        self.id = id
        self.traffic = traffic
        self.neighbours = dict()
        self.maxTraffic = 0
        self.sumOfNeighboursTraffic = 0

    def AppendNeighbour(self, neighbour):
        if neighbour is None:
            return
        self.neighbours[neighbour] = 0

    def AppendNeighbours(self, neighbours = None):
        if neighbours is None:
            return
        for neighbour in neighbours:
            self.AppendNeighbour(neighbour)

    # override the following 2 functions to enable gNode as hash key
    def __hash__(self):
        return hash(self.id)
    def __eq__(self, other):
        return self.id == other.id


class gNodeHelper (object):
    def __init__(self):
        pass

    @staticmethod
    def __CalculateNeighboursTraffic(root, parent):
        if root is None:
            return 0
        if len(root.neighbours) == 1 and parent is not None:
            return root.traffic

        traffic = 0
        for key in root.neighbours.keys():
            if parent is None or key.id != parent.id:
                root.neighbours[key] = gNodeHelper.__CalculateNeighboursTraffic(key, root)
                traffic += root.neighbours[key]
        return traffic + root.traffic

    @staticmethod
    def __CalculateParentTraffic(root, parent):
        if root is None:
            return
        if parent is not None:
            root.neighbours[parent] = parent.sumOfNeighboursTraffic + \
                                                      parent.traffic - parent.neighbours[root]
   
        for val in root.neighbours.values():
            root.sumOfNeighboursTraffic += val
   
        for key in root.neighbours.keys():
            if parent is None or key.id != parent.id:
                gNodeHelper.__CalculateParentTraffic(key, root)

    @staticmethod
    def __PopulateMaxTraffic(root, parent):
        if root is None:
            return
        for val in root.neighbours.values():
            if root.maxTraffic < val:
                root.maxTraffic = val
   
        for key in root.neighbours.keys():
            if parent is None or key != parent:
                gNodeHelper.__PopulateMaxTraffic(key, root)

    @staticmethod
    def GenerateMaxTraffic(root):
        try:
            gNodeHelper.__CalculateNeighboursTraffic(root, None)
            gNodeHelper.__CalculateParentTraffic(root, None)
            gNodeHelper.__PopulateMaxTraffic(root, None)
        except AttributeError() as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected error: ", sys.exc_info()[0])

# ********************************************************************************
# Test
# ********************************************************************************
# Test_GenerateMaxTraffic.py
import unittest
from gNodeHelper import gNode
from gNodeHelper import gNodeHelper

class Test_GenerateMaxTraffic(unittest.TestCase):
    def test_A(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbour(node5)
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)

        gNodeHelper.GenerateMaxTraffic(node1)

        self.assertEqual(node1.maxTraffic, 14)
        self.assertEqual(node2.maxTraffic, 13)
        self.assertEqual(node3.maxTraffic, 12)
        self.assertEqual(node4.maxTraffic, 11)
        self.assertEqual(node5.maxTraffic, 4)

    def test_B(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbour(node5)
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)

        gNodeHelper.GenerateMaxTraffic(node5)

        self.assertEqual(node1.maxTraffic, 14)
        self.assertEqual(node2.maxTraffic, 13)
        self.assertEqual(node3.maxTraffic, 12)
        self.assertEqual(node4.maxTraffic, 11)
        self.assertEqual(node5.maxTraffic, 4)

    def test_C(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)
        node7 = gNode(7, 7)
        node8 = gNode(8, 8)
        node15 = gNode(15, 15)
        node38 = gNode(38, 38)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbours((node5, node7, node15))
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)
        node7.AppendNeighbours((node2, node8))
        node8.AppendNeighbours((node7, node38))
        node15.AppendNeighbour(node2)
        node38.AppendNeighbour(node8)

        gNodeHelper.GenerateMaxTraffic(node1)

        self.assertEqual(node1.maxTraffic, 82)
        self.assertEqual(node2.maxTraffic, 53)
        self.assertEqual(node3.maxTraffic, 80)
        self.assertEqual(node4.maxTraffic, 79)
        self.assertEqual(node5.maxTraffic, 70)
        self.assertEqual(node7.maxTraffic, 46)
        self.assertEqual(node8.maxTraffic, 38)
        self.assertEqual(node15.maxTraffic, 68)
        self.assertEqual(node38.maxTraffic, 45)

    def test_D(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)
        node7 = gNode(7, 7)
        node8 = gNode(8, 8)
        node15 = gNode(15, 15)
        node38 = gNode(38, 38)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbours((node5, node7, node15))
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)
        node7.AppendNeighbours((node2, node8))
        node8.AppendNeighbours((node7, node38))
        node15.AppendNeighbour(node2)
        node38.AppendNeighbour(node8)

        gNodeHelper.GenerateMaxTraffic(node5)

        self.assertEqual(node1.maxTraffic, 82)
        self.assertEqual(node2.maxTraffic, 53)
        self.assertEqual(node3.maxTraffic, 80)
        self.assertEqual(node4.maxTraffic, 79)
        self.assertEqual(node5.maxTraffic, 70)
        self.assertEqual(node7.maxTraffic, 46)
        self.assertEqual(node8.maxTraffic, 38)
        self.assertEqual(node15.maxTraffic, 68)
        self.assertEqual(node38.maxTraffic, 45)

if __name__ == '__main__':
    unittest.main()