leetcode.py

#in a matrix of integers find the length of the longest path of increaseing numbers
#https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
class Solution(object):
    def __init__(self):
        self.memo = None
    
    def is_bounded(self,i,j,matrix):
        return not(i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]))

    #find the length of the longest increasing path from a starting point.        
    def longestIncreasingPathStart(self, matrix, start_i, start_j, travelled):
        if self.memo[start_i][start_j] > 0:
            return self.memo[start_i][start_j]
        elif travelled[start_i][start_j]:
            return 0
        
        travelled[start_i][start_j] = True
        surrounding_indexes = [(start_i-1,start_j),(start_i+1,start_j),(start_i,start_j-1),(start_i,start_j+1)]
        longest_paths = [self.longestIncreasingPathStart(matrix,i,j,travelled) for i,j in surrounding_indexes if self.is_bounded(i,j,matrix) and matrix[i][j] > matrix[start_i][start_j]]
        result = max(longest_paths) + 1 if len(longest_paths) > 0 else 1
        self.memo[start_i][start_j] = result
        travelled[start_i][start_j] = False
        return result
    #find the longest increasing path 
    def longestIncreasingPath(self, matrix):
        if len(matrix) == 0:
            return 0
        self.memo = [[0 for _ in matrix[0]] for _ in matrix]
        travelled = [[False for _ in matrix[0]] for _ in matrix]
        max_length = float("-inf")
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                max_length = max(max_length, self.longestIncreasingPathStart(matrix, i, j, travelled))
        return max_length

leetcode1.py

#Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
#https://leetcode.com/problems/number-of-islands/description/
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        
        result = 0
        for x in xrange(len(grid)):
            for y in xrange(len(grid[0])):
                print x,y,grid[x][y]
                if grid[x][y] == "1":
                    result += 1
                    self.flood(grid, x, y)
                else:
                    continue
        return result
    
    def flood(self, grid, startx, starty):
        if startx < 0 or startx >= len(grid) or starty < 0 or starty >= len(grid[0]):
            return
        elif grid[startx][starty] == "1":
            grid[startx][starty] = "0"
            self.flood(grid, startx+1, starty)
            self.flood(grid, startx-1, starty)
            self.flood(grid, startx, starty+1)
            self.flood(grid, startx, starty-1)

leetcode2.py

#https://leetcode.com/problems/lru-cache/description/

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.head = None
        self.tail = None
        self.hash = {}
        self.count = 0
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        #nokey
        if key not in self.hash:
            return -1
        #key in hash and is head
        elif self.hash[key]["key"] == self.head["key"]:
            pass
        #key is in hash and is at the tail.
        elif self.hash[key]["key"] == self.tail["key"]:
            self.head["next"] = self.tail
            self.tail["prev"] = self.head
            self.tail["next"]["prev"] = None
            self.head = self.tail
            self.tail = self.tail["next"]
            self.head["next"] = None
        #key is in hash and is inbetween nodes
        else:
            self.head["next"] = self.hash[key]
            self.hash[key]["prev"]["next"] = self.hash[key]["next"]
            self.hash[key]["next"]["prev"] = self.hash[key]["prev"]
            self.hash[key]["next"] = None
            self.hash[key]["prev"] = self.head
            self.head = self.hash[key]
        return self.hash[key]["value"]
            
            
            
        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        # queue empty
        
        
        if key in self.hash:
            self.get(key) #bring node to the top of the queue
            self.head["value"] = value
        else:
            dataNode = {
                "value":value,
                "key":key,
                "next":None,
                "prev":None
            }
            self.hash[key] = dataNode
            if self.count == 0:
                self.tail = dataNode
                self.head = dataNode
                self.count += 1

            #queue partially full
            elif self.count < self.capacity:
                self.head["next"] = dataNode
                dataNode["prev"] = self.head
                self.head = dataNode
                self.count += 1

            #full
            else:
                #create new head
                self.head["next"] = dataNode
                dataNode["prev"] = self.head
                self.head = dataNode
                #move tail up
                del self.hash[self.tail["key"]]
                self.tail = self.tail["next"]
                self.tail["prev"] = None
            
            
        


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

leetcode3.py

#this is very similar to the 2nd interview question 2sum. 
#this is actually nsum and find all combinations.
#https://leetcode.com/problems/combination-sum/description/

class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates = [i for i in candidates if i <= target]
        result = []
        if target == 0:
            return [[]]
        elif target < 0:
            return []
        for idx, num in enumerate(candidates):
            if num == target:
                result.append([num])
            else:
                rest = self.combinationSum(candidates[idx:], target - num)
                if len(rest) >= 0:
                    result = result + [[num] + nums for nums in rest]
        return result