RandomQuestions1

Question 1

If subset of another tree-2

Answer 1

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def isSubtree(s, t):
def isMatch(s, t):
# Base cases
if not s and not t:
return True
if not s or not t:
return False

    # Check if the current nodes match and recursively check left and right subtrees
    return s.val == t.val and isMatch(s.left, t.left) and isMatch(s.right, t.right)

def traverse(s, t):
    if not s:
        return False
    if s.val == t.val and isMatch(s, t):
        return True

    # Recursively check the left and right subtrees
    return traverse(s.left, t) or traverse(s.right, t)

return traverse(s, t)

Question 2

Same Tree-2

Answer 2

def isSameTree(p, q):
# If both trees are empty, they are the same
if not p and not q:
return True
# If one tree is empty but the other isn’t, they are not the same
if not p or not q:
return False
# Check if the current nodes have the same value
if p.val != q.val:
return False
# Recursively check the left and right subtrees
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right

Question 3

Serializer, Deserializer-2

Answer 3

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Codec:
def serialize(self, root):
“"”Encodes a tree to a single string.”””
if not root:
return “None,”

    left_serialized = self.serialize(root.left)
    right_serialized = self.serialize(root.right)

    return str(root.val) + "," + left_serialized + right_serialized

def deserialize(self, data):
    """Decodes your encoded data to tree."""
    def helper(queue):
        val = queue.pop(0)
        if val == "None":
            return None
        node = TreeNode(int(val))
        node.left = helper(queue)
        node.right = helper(queue)
        return node

    data_list = data.split(',')
    root = helper(data_list)
    return root

Question 4

Max sum of binary tree:

Answer 4

answer = float(‘-inf’)

def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left = root.left
        right = root.right

        x = max(self.maxPathSum(left),0)
        y = max(self.maxPathSum(right),0)
        self.answer = max(self.answer,int(x) + int(y) + root.val)
        return root.val

Question 5

countBits

Answer 5

def countBits(n):
# Initialize a list to store the counts of 1 bits for each number from 0 to n
counts = [0] * (n + 1)

# Iterate through numbers from 1 to n
for i in range(1, n + 1):
    # To count the bits for a number, add 1 to the count of bits in its rightmost position (i & 1)
    # and then shift the number to the right by one bit (i >> 1) to continue counting the remaining bits.
    counts[i] = counts[i >> 1] + (i & 1)

return counts

Question 6

Check if cycle

Answer 6

def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = fast = head
fast = fast.next
while fast and fast.next:
if slow == fast:
return True

        slow = slow.next
        fast = fast.next.next
    return False

Question 7

Clone graph-1

Answer 7

def cloneGraph(self, node: Optional[‘Node’]) -> Optional[‘Node’]:
seen = {}
if not node:
return None
def dfs(root):
new_neighbor = []
new_node = Node(root.val)
seen[new_node.val] = new_node

        for n in root.neighbors:
            if n.val not in seen:
                new_neighbor.append(dfs(n))
            else:
                new_neighbor.append(seen[n.val])
        new_node.neighbors = new_neighbor
        return new_node
    return dfs(node)

Question 8

Spiral Order-1

Answer 8

def spiralOrder(matrix):
if not matrix:
return []

result = []
top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1

while top <= bottom and left <= right:
    # Traverse from left to right along the top row
    for i in range(left, right + 1):
        result.append(matrix[top][i])
    top += 1

    # Traverse from top to bottom along the rightmost column
    for i in range(top, bottom + 1):
        result.append(matrix[i][right])
    right -= 1

    # Ensure we haven't crossed the boundaries
    if top <= bottom:
        # Traverse from right to left along the bottom row
        for i in range(right, left - 1, -1):
            result.append(matrix[bottom][i])
        bottom -= 1

    # Ensure we haven't crossed the boundaries
    if left <= right:
        # Traverse from bottom to top along the leftmost column
        for i in range(bottom, top - 1, -1):
            result.append(matrix[i][left])
        left += 1

return result

Question 9

Course Schedule-1

Answer 9

def canFinish(numCourses, prerequisites):
# Create an adjacency list to represent the graph
graph = defaultdict(list)
in_degree = [0] * numCourses

# Build the graph and calculate in-degrees
for course, prereq in prerequisites:
    graph[prereq].append(course)
    in_degree[course] += 1

# Create a queue for topological sorting
queue = deque()

# Initialize the queue with courses having no prerequisites
for i in range(numCourses):
    if in_degree[i] == 0:
        queue.append(i)

# Perform topological sorting
while queue:
    course = queue.popleft()
    numCourses -= 1

    for neighbor in graph[course]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

# If we successfully finished all courses, return True
return numCourses == 0

Question 10

Merge K List

Answer 10

def mergeKLists(lists):
# Create a min-heap to store the current smallest nodes from each list
min_heap = []

# Initialize the min-heap with the first node from each list (if it exists)
for i, head in enumerate(lists):
    if head:
        heapq.heappush(min_heap, (head.val, i, head))

# Dummy node to simplify the result list construction
dummy = ListNode()
current = dummy

while min_heap:
    val, list_idx, node = heapq.heappop(min_heap)
    
    # Append the smallest node to the result list
    current.next = node
    current = current.next
    
    # Move to the next node in the corresponding list
    if node.next:
        heapq.heappush(min_heap, (node.next.val, list_idx, node.next))

return dummy.next

Question 11

Merge Intervals

Answer 11

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if(len(intervals) <= 1):
return intervals

    intervals.sort(key=lambda x: x[0])
    
    result = [intervals[0]]

    for x in range(1, len(intervals)):
        currentInterval = intervals[x]
        tmpResult = result[-1] #Get the last updated result for comparsion

        if currentInterval[0] > tmpResult[1]:
            result.append(intervals[x])
        else:
            result[-1][1] = max(currentInterval[1],tmpResult[1])
    return result

Question 12

groupAnagrams

Answer 12

def groupAnagrams(strs):
# Create a dictionary to store anagrams
anagrams = {}

# Iterate through the list of strings
for word in strs:
    # Sort the characters in the word and use it as a key
    sorted_word = ''.join(sorted(word))

    # Add the word to the list of anagrams for the sorted key
    if sorted_word in anagrams:
        anagrams[sorted_word].append(word)
    else:
        anagrams[sorted_word] = [word]

# Convert the values (lists of anagrams) from the dictionary to a list of lists
grouped_anagrams = list(anagrams.values())

return grouped_anagrams

Question 13

maxProfit stock

Answer 13

def maxProfit(prices):
min_val = float(‘inf’)
max_profit = 0

for i in range(len(prices)):
    if prices[i] < min_val:
        min_val = prices[i]
    elif prices[i] - min_val > max_profit:
        max_profit = prices[i] - min_val

return max_profit

Question 14

Rotate Matrix

Answer 14

def rotate(matrix):
n = len(matrix)

# Transpose the matrix
for i in range(n):
    for j in range(i, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Reverse each row
for i in range(n):
    matrix[i].reverse()

Example usage:
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

rotate(matrix)

The matrix is now rotated by 90 degrees clockwise:
# [
# [7, 4, 1],
# [8, 5, 2],
# [9, 6, 3]
# ]

Question 15

productExceptSelf

Answer 15

def productExceptSelf(nums):
n = len(nums)

# Initialize two arrays to store the products to the left and right of each element.
left_products = [1] * n
right_products = [1] * n

# Calculate the product of elements to the left of each element.
left_product = 1
for i in range(n):
    left_products[i] = left_product
    left_product *= nums[i]

# Calculate the product of elements to the right of each element.
right_product = 1
for i in range(n - 1, -1, -1):
    right_products[i] = right_product
    right_product *= nums[i]

# Multiply the corresponding elements from the left and right product arrays.
result = [left_products[i] * right_products[i] for i in range(n)]

return result

Question 16

Merge of two sort arrays

Answer 16

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 and not list2:
return list1
if list2 and not list1:
return list2

    dummy = ListNode(0)
    current = dummy
    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next 
        current = current.next
    if list1:
        current.next = list1
    if list2:
        current.next = list2
    return dummy.next

    
    return result

Question 17

Invert Tree

Answer 17

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return root

        left = root.left
        right  = root.right

        root.left = right
        root.right = left
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Question 18

eraseOverlapIntervals

Answer 18

def eraseOverlapIntervals(intervals):
if not intervals:
return 0

# Sort the intervals by their ending points in ascending order.
intervals.sort(key=lambda x: x[1])

count = 1  # Initialize the count to 1 to account for the first interval.
end = intervals[0][1]  # Initialize the end point to the ending point of the first interval.

# Iterate through the sorted intervals.
for interval in intervals[1:]:
    start, current_end = interval

    # If the current interval does not overlap with the previous one, update the count and end point.
    if start >= end:
        count += 1
        end = current_end

# Calculate the minimum number of intervals to remove to keep them non-overlapping.
min_removals = len(intervals) - count

return min_removals

Question 19

maxSubArray

Answer 19

def maxSubArray(nums):
max_sum = nums[0] # Initialize max_sum to the first element
current_sum = nums[0] # Initialize current_sum to the first element

# Iterate through the array starting from the second element
for num in nums[1:]:
    # Choose the larger of the current element and the current element plus current_sum
    current_sum = max(num, current_sum + num)
    # Update max_sum with the maximum of max_sum and current_sum
    max_sum = max(max_sum, current_sum)

return max_sum

Question 20

Maximum Depth of Binary Tree

Answer 20

def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0

    leftNode = self.maxDepth(root.left)
    rightNode = self.maxDepth(root.right)

    return max(leftNode,rightNode) + 1

Question 21

remove From Nth End

Answer 21

def removeNthFromEnd(head, n):
# Create a dummy node to simplify edge cases
dummy = ListNode(0)
dummy.next = head
first = dummy
second = dummy

# Move the first pointer n+1 steps ahead
for _ in range(n + 1):
    first = first.next

# Move first to the end, maintaining the gap
while first is not None:
    first = first.next
    second = second.next

# Remove the nth node from the end
second.next = second.next.next

return dummy.next

Question 22

Climbing stairs

Answer 22

def climbStairs(self, n: int) -> int:
ans = [i for i in range(n+1)]
ans[0] = 1
ans[1] = 1
for i in range(2,n+1):
ans[i] = ans[i - 1] + ans[i-2]

    return ans[n]

Question 23

isAnagram

Answer 23

def isAnagram(s, t):
# If the lengths of the strings are different, they can’t be anagrams
if len(s) != len(t):
return False

# Create dictionaries to store character frequencies for both strings
s_count = {}
t_count = {}

# Count the frequency of each character in string s
for char in s:
    s_count[char] = s_count.get(char, 0) + 1

# Count the frequency of each character in string t
for char in t:
    t_count[char] = t_count.get(char, 0) + 1

# Compare the character frequencies in the two dictionaries
return s_count == t_count

Question 24

two sums without + -

Answer 24

def getSum(self, a: int, b: int) -> int:
if not a or not b:
return None
while b != 0:
a = a ^ b
carry = a & b
b = carry &laquo_space;1
return a

Question 25

Zeros of matrix

Answer 25

def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ if not matrix: return None row,column = len(matrix),len(matrix[0]) zeroRow,zeroColumn = set(),set() for r in range(row): for c in range(column): if matrix[r][c] == 0: zeroRow.add(r) zeroColumn.add(c) for r in zeroRow: for c in range(column): matrix[r][c] = 0 for r in range(row): for c in zeroColumn: matrix[r][c] = 0 return matrix

Question 26

Reverse LL

Answer 26

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head == None: return head result = None while head: nextNode = head.next head.next = result result = head head = nextNode

Question 27

Breath Level Order

Answer 27

def levelOrder(root): if not root: return [] result = [] queue = [root] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.pop(0) current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result

Question 28

Number of 1 bits

Answer 28

def hammingWeight(self, n: int) -> int: ans = 0 while n: n=n&(n-1) ans+=1 return ans

Question 29

coinChange

Answer 29

def coinChange(coins, amount): # Initialize a list dp to store the minimum number of coins for each amount from 0 to the given amount. dp = [float('inf')] * (amount + 1) # The minimum number of coins needed to make 0 amount is 0. dp[0] = 0 # Iterate through each coin denomination. for coin in coins: # Update dp[i] for each i amount from coin to amount. for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) # If dp[amount] is still set to float('inf'), it means no valid combination exists. # Otherwise, it contains the minimum number of coins needed to make the amount. return dp[amount] if dp[amount] != float('inf') else -1