Leetcode Solutions Week 1.2

93. Restore IP Address

Complexity : O(2^n) [Probably should try memoization]

Ouput has list of repeating sequences. I’ve created a set to find out unique valid ips

Amazon Interview question 2019 summer USC

class Solution:
    
    def isValidIP(self, ip):
        count = 0
        for section in ip:
            count += 1
            if len(section) > 3 or int(section) > 255:
                return False
        return True
    def helper(self, rstring, ip):
        if len(ip) == 4:
            if rstring:
                return
            elif self.isValidIP(ip):
                self.valid_ips.append(".".join(ip))        
        else:                
            if not rstring:
                return
            elif len(ip) == 3:
                if rstring[0] == '0':
                    self.helper(rstring[1:], ip+[rstring[0]])
                else:
                    self.helper("", ip+[rstring])
                    self.helper("", ip+[rstring])
                    self.helper("", ip+[rstring])
            else:
                if rstring[0] == '0':
                    self.helper(rstring[1:], ip+[rstring[0]])
                else:
                    self.helper(rstring[1:], ip+[rstring[:1]])
                    self.helper(rstring[2:], ip+[rstring[:2]])
                    self.helper(rstring[3:], ip+[rstring[:3]])
    
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.valid_ips = []
        if len(s) > 12 or len(s) < 4:
            return []
        else:
            self.helper(s, [])
            
        return list(set(self.valid_ips))

17. Letter Combinations of a Phone Number

# Backtracking # Python # Amazon top 50

class Solution:
    
    def helper(self, digits, c_string): 
        if not digits:
            if c_string:
                self.solutions.append(c_string)
        else:
            for c in self.number_letter_dict[digits[0]]:
                self.helper(digits[1:], c_string+c)
    
    def letterCombinations(self, digits: str) -> List[str]:
        self.number_letter_dict = {
            '1':[]
        }
        char_pointer = 0
        for i in range(0, 8):
            if i != 7 and i != 5:
                self.number_letter_dict[str(i+2)] = [chr(97 + j) for j in range(char_pointer, char_pointer + 3)]
                char_pointer += 3
            else:
                self.number_letter_dict[str(i+2)] = [chr(97 + j) for j in range(char_pointer, char_pointer + 4)]
                char_pointer += 4
                
        self.solutions = []
        self.helper(digits, "") 
        return self.solutions

500. Keyboard Row

# Hashtable # O(n³)

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        position_dict = {
            1: "qwertyuiop", 
            2: "asdfghjkl",
            3: "zxcvbnm"
        }
        
        encoding = []
        
        for word in words:
            o = set()
            for c in word:
                for k in position_dict:
                    if c in position_dict[k]:
                        o.add(k)
            if len(o) == 1:
                encoding.append(word)
                    
        return encoding

535. Priority Caching => Hackerrank Feature Labs (coding test)

# Hashtable # Array # Cumbersome problems

def cacheContents(callLogs):
count_dict = {}
cache_values = []
call_log_dict = {}
min_time = math.inf
max_time = -math.inf
for time, value in callLogs:
if time > max_time:
max_time = time
if time < min_time:
min_time = time
if call_log_dict.get(time):
call_log_dict[time].append(value)
else:
call_log_dict[time] = [value]
for time in range(min_time, max_time+1):
values = call_log_dict[time]
for c_key, c_value in count_dict.items():
if c_value > 0 and c_key not in values:
count_dict[c_key] -= 1
for value in values:
if count_dict.get(value):
count_dict[value] += 2
else:
count_dict[value] = 2
for count_key, value in count_dict.items():
if value > 5 and count_key not in cache_values:
cache_values.append(count_key)
if value <= 3 and count_key in cache_values:
cache_values.remove(count_key)
return cache_values

763 Partition Labels

# Amazon Top 50 # 2 pointers # queue # fadoo !!

Complexity : O(n²)

def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        if not len(S):
            return []
        out = [] 
        l_pointer = 0
        while l_pointer < len(S):
            gr_pointer = -1
            # print("gr_pointer {}".format(gr_pointer))
            queue = [S[l_pointer]]
            queue_index = 0
            while len(queue) > queue_index:
                value = queue[queue_index]
                # print(value)
                queue_index += 1
                r_pointer = len(S) - 1
                while(S[r_pointer] != value):
                    r_pointer -= 1
                # print(r_pointer)
                gr_pointer = r_pointer if r_pointer > gr_pointer else gr_pointer
                for i in range(l_pointer, r_pointer):
                    if S[i] not in queue:
                        queue.append(S[i])
                        
            # print(queue, l_pointer, gr_pointer)              
            out.append(S[l_pointer: gr_pointer+1]) 
            l_pointer = gr_pointer + 1
                    
        # print(out, len(out))           
        out = [len(i) for i in out]
        return out

238 Product of Array Except Self

# Amazon Top 50 #Arrays

**Ratta** -> for these kind of problems always its 2 passes forward, backward and multiply or add

def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l_prod = []
        r_prod = []
        r_nums = list(reversed(nums))
        for index in range(len(nums)):
            if index == 0:
                l_prod.append(1)
                r_prod.append(1)
            else:
                l_prod.append(l_prod[index-1] * nums[index-1])
                r_prod.append(r_prod[index-1] * r_nums[index-1])
        r_prod.reverse()               
        out = []
        for i in range(len(nums)):
            out.append(r_prod[i] * l_prod[i])
            
        return out