Insert Delete GetRandom O(1) - Python Leetcode

 Implement the RandomizedSet class:

• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

Follow up: Could you implement the functions of the class with each function works in average O(1) time?

 

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

 

Constraints:

• -231 <= val <= 231 - 1
• At most 105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

class RandomizedSet:

    def __init__(self):

        """

        Initialize your data structure here.

        """

        self.dict = {}

        self.list = []

        

    def insert(self, val: int) -> bool:

        """

        Inserts a value to the set. Returns true if the set did not already contain the specified element.

        """

        if val in self.dict:

            return False

        self.dict[val] = len(self.list)

        self.list.append(val)

        return True

        

    def remove(self, val: int) -> bool:

        """

        Removes a value from the set. Returns true if the set contained the specified element.

        """

        if val not in self.dict:

            return False

        idx = self.dict[val]

        lx = len(self.list)-1

        self.dict[self.list[lx]] = idx

        self.list[idx],self.list[lx]=self.list[lx],self.list[idx]

        self.list.pop()

        del self.dict[val]

        return True

    def getRandom(self) -> int:

        """

        Get a random element from the set.

        """

        return choice(self.list)

        

# Your RandomizedSet object will be instantiated and called as such:

# obj = RandomizedSet()

# param_1 = obj.insert(val)

# param_2 = obj.remove(val)

# param_3 = obj.getRandom()

Serialize and Deserialize Binary Tree - Python Leetcode

 Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

 

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

class Codec:
    '''       O(n) time and O(n) space, BFS traversal
    e.g., 1
         / \
        2   5
       / \
      3   4  , level order traversal, serialize will be '1,2,5,3,4,None,None,None,None,None,None,'; deserialize 
      with queue as well, convert back. Time and Space O(n).
    '''
    def serialize(self, root):
        if not root:
            return ''
        queue = collections.deque()
        queue.append(root)
        res = ''
        while queue:
            node = queue.popleft()
            if not node:
                res += 'None,'
                continue
            res += str(node.val) + ','
            queue.append(node.left)
            queue.append(node.right)
        return res
            
    def deserialize(self, data):
        if not data:
            return None
        ls = data.split(',')
        root = TreeNode(int(ls[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue and i < len(ls):
            node = queue.popleft()
            if ls[i] != 'None':
                left = TreeNode(int(ls[i]))
                node.left = left
                queue.append(left)
            i += 1
            if ls[i] != 'None':
                right = TreeNode(int(ls[i]))
                node.right = right
                queue.append(right)
            i += 1
        return root

        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Find Duplicate Subtrees - Python Leetcode

  Find Duplicate Subtrees

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

 

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        count = collections.Counter()
        trees = collections.defaultdict()
        trees.default_factory = trees.__len__
        ans = []
        def lookup(root):
            if root:
                uid = trees[root.val,lookup(root.left),lookup(root.right)]
                count[uid]+=1
                if count[uid] == 2:
                    ans.append(root)
                return uid
        
        lookup(root)
        return ans
        

TC: O(n) SC: O(n)

Next Closest Time

 Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

class Solution(object):
    def nextClosestTime(self, time):
        cur = 60 * int(time[:2]) + int(time[3:])
        allowed = {int(x) for x in time if x != ':'}
        while True:
            cur = (cur + 1) % (24 * 60)
            if all(digit in allowed
                    for block in divmod(cur, 60)
                    for digit in divmod(block, 10)):
                return "{:02d}:{:02d}".format(*divmod(cur, 60))

TC : O(1) max 24*60 iterations

SC : O(1) 

Top Interview Questions for Software Engineer (Google , Microsoft , Amazon , Uber , Airbnb)

 Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            if target-nums[i] in hashmap:
                return [i,hashmap[target-nums[i]]]
            else:
                hashmap[nums[i]] = i
        return []
            

TC : O(n) // Iterating over each element . SC: O(n) Extra space for Hashmap.

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            tailA = l1
            tailB = l2
            carry = 0
            dummyHead = ListNode(-1)
            resNode = dummyHead
            while tailA or tailB:
                x = tailA.val if tailA else 0
                y = tailB.val if tailB else 0
                val = x + y + carry
                resNode.next = ListNode(val % 10)
                carry = val // 10
                if tailA: tailA = tailA.next 
                if tailB: tailB = tailB.next
                resNode = resNode.next
                
            if carry == 1:
                resNode.next = ListNode(carry)
                resNode = resNode.next
     
            return dummyHead.next

TC : O(max(m,n)) SC: O(max(m,n)+1)

Strobogrammatic Number - Python Leetcode

 A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

 

Example 1:

Input: num = "69"
Output: true

Example 2:

Input: num = "88"
Output: true

Example 3:

Input: num = "962"
Output: false

Example 4:

Input: num = "1"
Output: true

TC: O(N) SC:O(1)

Solution 1:

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        if not num:
            return True
        map = {'0':'0','1':'1','6':'9','8':'8','9':'6','2':'','3':'','4':'','5':'','7':''}
        i = 0
        j = len(num)-1
        while i<=j:
            if num[i] != map[num[j]]:
                return False
            i+=1
            j-=1
        return True

Solution 2:

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        if not num:
            return True
        map = {'0':'0','1':'1','6':'9','8':'8','9':'6'}
        i = 0
        j = len(num)-1
        while i<=j:
            if num[j] not in map or num[i] != map[num[j]]:
                return False
            i+=1
            j-=1
        return True
    

Isomorphic Strings - Python Leetcode Solution

 Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if s==t or (s is None and t is None):
            return True
        if len(s) != len(t):
            return False
        map = {}
        for i in range(len(s)):
            if s[i] not in map and t[i] not in map.values(): 
                map[s[i]] = t[i] 
            if s[i] not in map or map[s[i]] != t[i]:  
                return False
            
        return True