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
 

Invert Binary Tree - Leetcode Python Solution

 Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Iterative approcah . 

# 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 invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        q = []

        q.append(root)

        while q:

            curr = q.pop()

            curr.left , curr.right = curr.right,curr.left

            if curr.left:

                q.append(curr.left)

            if curr.right:

                q.append(curr.right)

        return root

            

        TC: O(n)

        SC: O(n) in worst case where queue is completely occupied. 

Recursive approch:

# 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 invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        curr.left,curr.right = curr.right,curr.left

        return root

            

    Recursive approach:

# 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 invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        curr.left,curr.right = curr.right,curr.left

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        return root

            

       TC: O(n)

       SC: O(n) 

Maximum Product Subarray - Python Leetcode

 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_so_far = nums[0]
        min_so_far = nums[0]
        result = max_so_far
        
        for i in range(1,len(nums)):
            curr = nums[i]
            temp_value = max(curr,max_so_far*curr,min_so_far*curr)
            min_so_far = min(curr,min_so_far*curr,max_so_far*curr)
            max_so_far = temp_value
            result = max(result,max_so_far)
            
        return result

TC:O(n)

SC:O(1)

Binary Tree Zigzag Level Order Traversal - Python Leetcode

 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        
        s1 = [root]
        s2 = []
        
        level =[]
        result = []
        
        while s1 or s2:
            while s1:
                root = s1.pop()
                level.append(root.val)
                if root.left:
                    s2.append(root.left)
                if root.right:
                    s2.append(root.right)
            if level:
                result.append(level)
            level = []
            while s2:
                root = s2.pop()
                level.append(root.val)
                if root.right:
                    s1.append(root.right)
                if root.left:
                    s1.append(root.left)
            if level:
                result.append(level)
            level = []
        return result
                
            
    TC : O(n)

SC:O(n)