\n
def fibonacci(n):
\na, b = 0, 1
\nfor _ in range(n):
\nprint(a, end=’ ‘)
\na, b = b, a + b<\/p>\n<\/div><\/div>
7. How do you find the factorial of a given number n?<\/h3>
Answer:<\/strong><\/p>The factorial of a number is the product of all positive integers less than or equal to n<\/strong>. This can be computed using recursion.<\/p>\n
def factorial(n):
\nreturn 1 if n == 0 else n * factorial(n – 1)<\/p>\n<\/div><\/div>
8. How do you find the missing number in a sequence from 1 to n?<\/h3>
Answer:<\/strong><\/p>The sum of numbers from 1 to n<\/strong> is n*(n+1)\/\/2<\/strong>. Find the difference between this sum and the sum of elements in the array.<\/p>\n
def find_missing(arr, n):
\ntotal = n * (n + 1) \/\/ 2
\nreturn total – sum(arr)<\/p>\n<\/div><\/div>
9. How do you check if two strings are anagrams?<\/h3>
Answer:<\/strong><\/p>Two strings are anagrams if they contain the same characters in different orders. Sort both strings and compare them.<\/p>
\n
def are_anagrams(str1, str2):
\nreturn sorted(str1) == sorted(str2)<\/p>\n<\/div><\/div>
10. How do you find a duplicate element in an array?<\/h3>
Answer:<\/strong><\/p>Use a set to keep track of elements. If an element already exists in the set, it’s a duplicate.<\/p>
\n
def find_duplicate(arr):
\nseen = set()
\nfor num in arr:
\nif num in seen:
\nreturn num
\nseen.add(num)<\/p>\n<\/div><\/div>
11. How do you find the length of the longest substring without repeating characters?<\/h3>
Answer:<\/strong><\/p>Use a sliding window approach to track the longest substring with unique characters.<\/p>
\n
def longest_unique_substring(s):
\nchar_set = set()
\nl, res = 0, 0
\nfor r in range(len(s)):
\nwhile s[r] in char_set:
\nchar_set.remove(s[l])
\nl += 1
\nchar_set.add(s[r])
\nres = max(res, r – l + 1)
\nreturn res<\/p>\n<\/div><\/div>
12. How do you find the intersection of two arrays?<\/h3>
Answer:<\/strong><\/p>Convert both arrays to sets and use the & operator to find the intersection.<\/p>
\n
def intersection(arr1, arr2):
\nreturn list(set(arr1) & set(arr2))<\/p>\n<\/div><\/div>
13. How do you check if a binary tree is height-balanced?<\/h3>
Answer:<\/strong><\/p>A binary tree is balanced if the height difference between the left and right subtree is not more than 1.<\/p>
\n
def is_balanced(root):
\ndef height(node):
\nif not node:
\nreturn 0
\nleft = height(node.left)
\nright = height(node.right)
\nif left == -1 or right == -1 or abs(left – right) > 1:
\nreturn -1
\nreturn 1 + max(left, right)
\nreturn height(root) != -1<\/p>\n<\/div><\/div>
14. How do you implement binary search in a sorted array?<\/h3>
Answer:<\/strong><\/p>Binary search works by dividing the search space in half, checking the middle element, and deciding which half to search next.<\/p>
\n
def binary_search(arr, target):
\nlow, high = 0, len(arr) – 1
\nwhile low <= high:
\nmid = (low + high) \/\/ 2
\nif arr[mid] == target:
\nreturn mid
\nelif arr[mid] < target:
\nlow = mid + 1
\nelse:
\nhigh = mid – 1
\nreturn -1<\/p>\n<\/div><\/div>
15. How do you merge two sorted arrays into one sorted array?<\/h3>
Answer:<\/strong><\/p>Use two pointers to iterate through both arrays and append the smaller element to the result.<\/p>
\n
def merge_sorted_arrays(arr1, arr2):
\ni, j = 0, 0
\nresult = []\nwhile i < len(arr1) and j < len(arr2):
\nif arr1[i] < arr2[j]:
\nresult.append(arr1[i])
\ni += 1
\nelse:
\nresult.append(arr2[j])
\nj += 1
\nresult.extend(arr1[i:])
\nresult.extend(arr2[j:])
\nreturn result<\/p>\n<\/div><\/div>
16. How do you find the middle element of a linked list?<\/h3>
Answer:<\/strong><\/p>Use two pointers, one moving twice as fast as the other. When the fast pointer reaches the end, the slow pointer will be at the middle.<\/p>
\n
def find_middle(head):
\nslow, fast = head, head
\nwhile fast and fast.next:
\nslow = slow.next
\nfast = fast.next.next
\nreturn slow<\/p>\n<\/div><\/div>
17. How do you check if a number is prime?<\/h3>
Answer:<\/strong><\/p>A prime number has no divisors other than 1 and itself. Check divisibility up to the square root of the number.<\/p>
\n
def is_prime(n):
\nif n <= 1:
\nreturn False
\nfor i in range(2, int(n**0.5) + 1):
\nif n % i == 0:
\nreturn False
\nreturn True<\/p>\n<\/div><\/div>
18. How do you find the greatest common divisor (GCD) of two numbers?<\/h3>
Answer:<\/strong><\/p>Use Euclid’s algorithm: repeatedly divide the larger number by the smaller until the remainder is zero.<\/p>
\n
def gcd(a, b):
\nwhile b:
\na, b = b, a % b
\nreturn a<\/p>\n<\/div><\/div>
19. How do you merge overlapping intervals?<\/h3>
Answer:<\/strong><\/p>Sort the intervals by the start time, then iterate through them and merge overlapping intervals.<\/p>
\n
def merge_intervals(intervals):
\nintervals.sort(key=lambda x: x[0])
\nmerged = [intervals[0]]\nfor curr in intervals[1:]:
\nif curr[0] <= merged[-1][1]:
\nmerged[-1][1] = max(merged[-1][1], curr[1])
\nelse:
\nmerged.append(curr)
\nreturn merged<\/p>\n<\/div><\/div>
20. How do you find the Kth largest element in an array?<\/h3>
Answer:<\/strong><\/p>Sort the array and return the Kth largest element. Alternatively, use a min-heap.<\/p>
\n
import heapq<\/p>\n
def kth_largest(arr, k):
\nreturn heapq.nlargest(k, arr)[-1]\n<\/p><\/div><\/div>
21. How do you find the longest palindromic substring in a given string?<\/h3>
Answer:<\/strong><\/p>Expand around the center of the string and check for the longest palindrome in both even and odd-length substrings.<\/p>
\n
def longest_palindrome(s):
\ndef expand_around_center(left, right):
\nwhile left >= 0 and right < len(s) and s[left] == s[right]:
\nleft -= 1
\nright += 1
\nreturn right – left – 1<\/p>\n
start, end = 0, 0
\nfor i in range(len(s)):
\nlen1 = expand_around_center(i, i)
\nlen2 = expand_around_center(i, i + 1)
\nmax_len = max(len1, len2)
\nif max_len > end – start:
\nstart = i – (max_len – 1) \/\/ 2
\nend = i + max_len \/\/ 2
\nreturn s[start:end + 1]\n<\/p><\/div><\/div>
22. How do you check if a string containing parentheses is balanced?<\/h3>
Answer:<\/strong><\/p>Use a stack to keep track of open parentheses. For each closing parenthesis, pop the stack and check for a matching opening parenthesis.<\/p>
\n
def is_balanced(s):
\nstack = []\nmatching_parentheses = {‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘}
\nfor char in s:
\nif char in matching_parentheses.values():
\nstack.append(char)
\nelif char in matching_parentheses:
\nif not stack or stack.pop() != matching_parentheses[char]:
\nreturn False
\nreturn not stack<\/p>\n<\/div><\/div>
23. How do you find a subarray with a given sum in a non-negative array?<\/h3>
Answer:<\/strong><\/p>Use the sliding window technique to adjust the window size dynamically until the target sum is found.<\/p>
\n
def find_subarray_with_sum(arr, target):
\nstart, current_sum = 0, 0
\nfor end in range(len(arr)):
\ncurrent_sum += arr[end]\nwhile current_sum > target:
\ncurrent_sum -= arr[start]\nstart += 1
\nif current_sum == target:
\nreturn arr[start:end + 1]\nreturn []\n<\/p><\/div><\/div>
24. How do you find the minimum element in a rotated sorted array?<\/h3>
Answer:<\/strong><\/p>Use binary search to find the inflection point where the array is rotated.<\/p>
\n
def find_min_in_rotated_array(arr):
\nlow, high = 0, len(arr) – 1
\nwhile low < high:
\nmid = (low + high) \/\/ 2
\nif arr[mid] > arr[high]:
\nlow = mid + 1
\nelse:
\nhigh = mid
\nreturn arr[low]\n<\/p><\/div><\/div>
Answer:<\/strong><\/p>Use binary search on the smaller array to partition both arrays into two halves, ensuring that the left half contains smaller elements than the right half.<\/p>
\n
def find_median_sorted_arrays(nums1, nums2):
\nif len(nums1) > len(nums2):
\nnums1, nums2 = nums2, nums1
\nx, y = len(nums1), len(nums2)
\nlow, high = 0, x
\nwhile low <= high:
\npartitionX = (low + high) \/\/ 2
\npartitionY = (x + y + 1) \/\/ 2 – partitionX<\/p>\n
maxX = float(‘-inf’) if partitionX == 0 else nums1[partitionX – 1]\nminX = float(‘inf’) if partitionX == x else nums1[partitionX]\n<\/p>
maxY = float(‘-inf’) if partitionY == 0 else nums2[partitionY – 1]\nminY = float(‘inf’) if partitionY == y else nums2[partitionY]\n<\/p>
if maxX <= minY and maxY <= minX:
\nif (x + y) % 2 == 0:
\nreturn (max(maxX, maxY) + min(minX, minY)) \/ 2
\nelse:
\nreturn max(maxX, maxY)
\nelif maxX > minY:
\nhigh = partitionX – 1
\nelse:
\nlow = partitionX + 1<\/p>\n<\/div><\/div>
26. How do you implement a queue using two stacks?<\/h3>
Answer:<\/strong><\/p>Use two stacks: one for enqueuing elements and another for dequeuing.<\/p>
\n
class QueueUsingStacks:
\ndef __init__(self):
\nself.stack1 = []\nself.stack2 = []\n<\/p>
def enqueue(self, x):
\nself.stack1.append(x)<\/p>\n
def dequeue(self):
\nif not self.stack2:
\nwhile self.stack1:
\nself.stack2.append(self.stack1.pop())
\nreturn self.stack2.pop()<\/p>\n<\/div><\/div>
27. How do you check if a binary tree is symmetric?<\/h3>
Answer:<\/strong><\/p>A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.<\/p>
\n
def is_symmetric(root):
\ndef is_mirror(t1, t2):
\nif not t1 and not t2:
\nreturn True
\nif not t1 or not t2:
\nreturn False
\nreturn t1.val == t2.val and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left)
\nreturn is_mirror(root, root)<\/p>\n<\/div><\/div>
28. How do you find the lowest common ancestor of two nodes in a binary tree?<\/h3>
Answer:<\/strong><\/p>The LCA is the node that is the deepest common ancestor of both nodes. Traverse the tree recursively, and return the node where the paths to both nodes diverge.<\/p>
\n
def lowest_common_ancestor(root, p, q):
\nif not root or root == p or root == q:
\nreturn root
\nleft = lowest_common_ancestor(root.left, p, q)
\nright = lowest_common_ancestor(root.right, p, q)
\nif left and right:
\nreturn root
\nreturn left if left else right<\/p>\n<\/div><\/div>
29. How do you count the number of islands in a 2D grid?<\/h3>
Answer:<\/strong><\/p>Perform a depth-first search (DFS) to mark all connected components of land (1) as visited.<\/p>
\n
def num_islands(grid):
\nif not grid:
\nreturn 0<\/p>\n
def dfs(grid, i, j):
\nif i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == ‘0’:
\nreturn
\ngrid[i][j] = ‘0’
\ndfs(grid, i + 1, j)
\ndfs(grid, i – 1, j)
\ndfs(grid, i, j + 1)
\ndfs(grid, i, j – 1)<\/p>\n
count = 0
\nfor i in range(len(grid)):
\nfor j in range(len(grid[0])):
\nif grid[i][j] == ‘1’:
\ndfs(grid, i, j)
\ncount += 1
\nreturn count<\/p>\n<\/div><\/div>
30. How do you find the maximum sum of a subarray using Kadane’s Algorithm?<\/h3>
Answer:<\/strong><\/p>Kadane’s algorithm scans the array and computes the maximum subarray sum in linear time by updating the current maximum at each step.<\/p>
\n
def max_subarray_sum(arr):
\nmax_so_far = max_ending_here = arr[0]\nfor i in range(1, len(arr)):
\nmax_ending_here = max(arr[i], max_ending_here + arr[i])
\nmax_so_far = max(max_so_far, max_ending_here)
\nreturn max_so_far<\/p>\n<\/div><\/div>
31. How do you implement a stack using two queues?<\/h3>
Answer:<\/strong><\/p>You can implement a stack by using two queues, one for pushing and the other for popping elements. When popping, the elements are dequeued until only one remains.<\/p>
\n
from collections import deque<\/p>\n
class StackUsingQueues:
\ndef __init__(self):
\nself.queue1 = deque()
\nself.queue2 = deque()<\/p>\n
def push(self, x):
\nself.queue1.append(x)<\/p>\n
def pop(self):
\nwhile len(self.queue1) > 1:
\nself.queue2.append(self.queue1.popleft())
\npopped = self.queue1.popleft()
\nself.queue1, self.queue2 = self.queue2, self.queue1
\nreturn popped<\/p>\n
def top(self):
\nreturn self.queue1[-1]\n<\/p>
def empty(self):
\nreturn not self.queue1<\/p>\n<\/div><\/div>
32. How do you find all permutations of a string?<\/h3>
Answer:<\/strong><\/p>Use backtracking to generate all possible permutations of a string by swapping characters.<\/p>
\n
def permute(s):
\ndef backtrack(start):
\nif start == len(s) – 1:
\nresult.append(”.join(s))
\nfor i in range(start, len(s)):
\ns[start], s[i] = s[i], s[start]\nbacktrack(start + 1)
\ns[start], s[i] = s[i], s[start]\n<\/p>
result = []\ns = list(s)
\nbacktrack(0)
\nreturn result<\/p>\n<\/div><\/div>
33. How do you find the Kth smallest element in a Binary Search Tree (BST)?<\/h3>
Answer:<\/strong><\/p>Inorder traversal of a BST gives the elements in sorted order. Perform an inorder traversal and stop at the Kth element.<\/p>
\n
def kth_smallest(root, k):
\ndef inorder(node):
\nif node:
\nyield from inorder(node.left)
\nyield node.val
\nyield from inorder(node.right)<\/p>\n
gen = inorder(root)
\nfor _ in range(k):
\nresult = next(gen)
\nreturn result<\/p>\n<\/div><\/div>
34. How do you find a peak element in an array where an element is greater than its neighbors?<\/h3>
Answer:<\/strong><\/p>Use binary search to efficiently find a peak element.<\/p>
\n
def find_peak(arr):
\nlow, high = 0, len(arr) – 1
\nwhile low < high:
\nmid = (low + high) \/\/ 2
\nif arr[mid] < arr[mid + 1]:
\nlow = mid + 1
\nelse:
\nhigh = mid
\nreturn arr[low]\n<\/p><\/div><\/div>
35. How do you count the number of 1’s in the binary representation of an integer?<\/h3>
Answer:<\/strong><\/p>Use bit manipulation by repeatedly clearing the least significant bit set to 1.<\/p>
\n
def count_ones(n):
\ncount = 0
\nwhile n:
\nn &= n – 1
\ncount += 1
\nreturn count<\/p>\n<\/div><\/div>
36. How do you convert a binary tree to a doubly linked list in-place?<\/h3>
Answer:<\/strong><\/p>Perform an inorder traversal and adjust pointers as you visit each node to create a doubly linked list.<\/p>
\n
def convert_to_dll(root):
\ndef inorder(node):
\nnonlocal prev
\nif not node:
\nreturn
\ninorder(node.left)
\nif prev:
\nprev.right = node
\nnode.left = prev
\nprev = node
\ninorder(node.right)<\/p>\n
if not root:
\nreturn None
\nprev = None
\ninorder(root)
\nwhile root.left:
\nroot = root.left
\nreturn root<\/p>\n<\/div><\/div>
37. How do you find the longest increasing subsequence in an array?<\/h3>
Answer:<\/strong><\/p>Use dynamic programming to store the length of the longest subsequence that ends at each element.<\/p>
\n
def longest_increasing_subsequence(arr):
\ndp = [1] * len(arr)
\nfor i in range(1, len(arr)):
\nfor j in range(i):
\nif arr[i] > arr[j]:
\ndp[i] = max(dp[i], dp[j] + 1)
\nreturn max(dp)<\/p>\n<\/div><\/div>
38. How do you flatten a multilevel doubly linked list where each node can have a child pointing to another doubly linked list?<\/h3>
Answer:<\/strong><\/p>Perform a depth-first traversal and adjust pointers to flatten the multilevel list.<\/p>
\n
def flatten(head):
\nif not head:
\nreturn head
\ndummy = Node(0)
\nprev = dummy
\nstack = [head]\n<\/p>
while stack:
\ncurr = stack.pop()
\nprev.next = curr
\ncurr.prev = prev
\nif curr.next:
\nstack.append(curr.next)
\nif curr.child:
\nstack.append(curr.child)
\ncurr.child = None
\nprev = curr<\/p>\n
dummy.next.prev = None
\nreturn dummy.next<\/p>\n<\/div><\/div>
39. How do you find the maximum product of a contiguous subarray?<\/h3>
Answer:<\/strong><\/p>Keep track of the current maximum and minimum products as you iterate through the array.<\/p>
\n
def max_product_subarray(nums):
\nmax_prod, min_prod, result = nums[0], nums[0], nums[0]\nfor i in range(1, len(nums)):
\ncandidates = (nums[i], nums[i] * max_prod, nums[i] * min_prod)
\nmax_prod = max(candidates)
\nmin_prod = min(candidates)
\nresult = max(result, max_prod)
\nreturn result<\/p>\n<\/div><\/div>
Answer:<\/strong><\/p>Use two heaps: a max-heap for the lower half and a min-heap for the upper half of the data.<\/p>
\n
import heapq<\/p>\n
class MedianFinder:
\ndef __init__(self):
\nself.low = [] # Max-heap
\nself.high = [] # Min-heap<\/p>\n
def add_num(self, num):
\nheapq.heappush(self.low, -num)
\nheapq.heappush(self.high, -heapq.heappop(self.low))
\nif len(self.low) < len(self.high):
\nheapq.heappush(self.low, -heapq.heappop(self.high))<\/p>\n
def find_median(self):
\nif len(self.low) > len(self.high):
\nreturn -self.low[0]\nreturn (-self.low[0] + self.high[0]) \/ 2<\/p>\n<\/div><\/div>
41. How do you find all unique triplets in an array that sum to zero?<\/h3>
Answer:<\/strong><\/p>Sort the array and use two pointers to find pairs that sum to the negative of the current element.<\/p>
\n
def three_sum(nums):
\nnums.sort()
\nresult = []\nfor i in range(len(nums) – 2):
\nif i > 0 and nums[i] == nums[i – 1]:
\ncontinue
\nleft, right = i + 1, len(nums) – 1
\nwhile left < right:
\ntotal = nums[i] + nums[left] + nums[right]\nif total < 0:
\nleft += 1
\nelif total > 0:
\nright -= 1
\nelse:
\nresult.append([nums[i], nums[left], nums[right]])
\nwhile left < right and nums[left] == nums[left + 1]:
\nleft += 1
\nwhile left < right and nums[right] == nums[right – 1]:
\nright -= 1
\nleft += 1
\nright -= 1
\nreturn result<\/p>\n<\/div><\/div>
42. How do you find the minimum window substring in a string that contains all the characters of another string?<\/h3>
Answer:<\/strong><\/p>Use a sliding window and a hash map to track the frequency of required characters.<\/p>
\n
from collections import Counter<\/p>\n
def min_window(s, t):
\nif not s or not t:
\nreturn “”
\ndict_t = Counter(t)
\nrequired = len(dict_t)
\nleft, right = 0, 0
\nformed = 0
\nwindow_counts = {}
\nans = float(“inf”), None, None
\nwhile right < len(s):
\nchar = s[right]\nwindow_counts[char] = window_counts.get(char, 0) + 1
\nif char in dict_t and window_counts[char] == dict_t[char]:
\nformed += 1
\nwhile left <= right and formed == required:
\nchar = s[left]\nif right – left + 1 < ans[0]:
\nans = (right – left + 1, left, right)
\nwindow_counts[char] -= 1
\nif char in dict_t and window_counts[char] < dict_t[char]:
\nformed -= 1
\nleft += 1
\nright += 1
\nreturn “” if ans[0] == float(“inf”) else s[ans[1]:ans[2] + 1]\n<\/p><\/div><\/div>
43. How do you serialize and deserialize a binary tree?<\/h3>
Answer:<\/strong><\/p>Serialize the tree into a string using pre-order traversal and deserialize it back into a tree using a queue.<\/p>
\n
def serialize(root):
\ndef helper(node):
\nif not node:
\nresult.append(‘None’)
\nelse:
\nresult.append(str(node.val))
\nhelper(node.left)
\nhelper(node.right)<\/p>\n
result = []\nhelper(root)
\nreturn ‘,’.join(result)<\/p>\n
def deserialize(data):
\ndef helper():
\nval = next(values)
\nif val == ‘None’:
\nreturn None
\nnode = TreeNode(int(val))
\nnode.left = helper()
\nnode.right = helper()
\nreturn node<\/p>\n
values = iter(data.split(‘,’))
\nreturn helper()<\/p>\n<\/div><\/div>
44. How do you implement an LRU (Least Recently Used) Cache?<\/h3>
Answer:<\/strong><\/p>Use a combination of a dictionary and a doubly linked list to keep track of the least recently used elements.<\/p>
\n
class LRUCache:
\ndef __init__(self, capacity):
\nself.cache = {}
\nself.capacity = capacity
\nself.head = ListNode(0)
\nself.tail = ListNode(0)
\nself.head.next = self.tail
\nself.tail.prev = self.head<\/p>\n
def _add(self, node):
\np = self.head.next
\nself.head.next = node
\nnode.prev = self.head
\nnode.next = p
\np.prev = node<\/p>\n
def _remove(self, node):
\np = node.prev
\nn = node.next
\np.next = n
\nn.prev = p<\/p>\n
def get(self, key):
\nif key in self.cache:
\nnode = self.cache[key]\nself._remove(node)
\nself._add(node)
\nreturn node.val
\nreturn -1<\/p>\n
def put(self, key, value):
\nif key in self.cache:
\nself._remove(self.cache[key])
\nnode = ListNode(key, value)
\nself.cache[key] = node
\nself._add(node)
\nif len(self.cache) > self.capacity:
\nn = self.tail.prev
\nself._remove(n)
\ndel self.cache[n.key]\n<\/p><\/div><\/div>
45. How do you find the maximum path sum in a binary tree?<\/h3>
Answer:<\/strong><\/p>Recursively calculate the maximum gain from each node and update the global maximum path sum.<\/p>
\n
def max_path_sum(root):
\ndef helper(node):
\nnonlocal max_sum
\nif not node:
\nreturn 0
\nleft_gain = max(helper(node.left), 0)
\nright_gain = max(helper(node.right), 0)
\nmax_sum = max(max_sum, node.val + left_gain + right_gain)
\nreturn node.val + max(left_gain, right_gain)<\/p>\n
max_sum = float(‘-inf’)
\nhelper(root)
\nreturn max_sum<\/p>\n<\/div><\/div>
46. How do you find the longest common subsequence (LCS) between two strings?<\/h3>
Answer:<\/strong><\/p>Use dynamic programming to store the LCS length at each substring.<\/p>
\n
def longest_common_subsequence(text1, text2):
\ndp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]\nfor i in range(1, len(text1) + 1):
\nfor j in range(1, len(text2) + 1):
\nif text1[i – 1] == text2[j – 1]:
\ndp[i][j] = dp[i – 1][j – 1] + 1
\nelse:
\ndp[i][j] = max(dp[i – 1][j], dp[i][j – 1])
\nreturn dp[-1][-1]\n<\/p><\/div><\/div>
47. How do you find the shortest path in a graph using Dijkstra’s Algorithm?<\/h3>
Answer:<\/strong><\/p>Use a priority queue to greedily select the node with the smallest distance, and update the distances of its neighbors.<\/p>
\n
import heapq<\/p>\n
def dijkstra(graph, start):
\ndistances = {node: float(‘infinity’) for node in graph}
\ndistances[start] = 0
\npq = [(0, start)]\n<\/p>
while pq:
\ncurrent_distance, current_node = heapq.heappop(pq)
\nif current_distance > distances[current_node]:
\ncontinue
\nfor neighbor, weight in graph[current_node]:
\ndistance = current_distance + weight
\nif distance < distances[neighbor]:
\ndistances[neighbor] = distance
\nheapq.heappush(pq, (distance, neighbor))<\/p>\n
return distances<\/p>\n<\/div><\/div>
48. How do you count the number of inversions in an array (where i < j and arr[i] > arr[j])?<\/h3>
Answer:<\/strong><\/p>Use a modified merge sort algorithm to count the inversions while sorting the array.<\/p>
\n
def merge_sort_and_count(arr):
\nif len(arr) < 2:
\nreturn arr, 0
\nmid = len(arr) \/\/ 2
\nleft, left_inv = merge_sort_and_count(arr[:mid])
\nright, right_inv = merge_sort_and_count(arr[mid:])
\nmerged, split_inv = merge_and_count(left, right)
\nreturn merged, left_inv + right_inv + split_inv<\/p>\n
def merge_and_count(left, right):
\nresult = []\ni = j = inv_count = 0
\nwhile i < len(left) and j < len(right):
\nif left[i] <= right[j]:
\nresult.append(left[i])
\ni += 1
\nelse:
\nresult.append(right[j])
\nj += 1
\ninv_count += len(left) – i
\nresult += left[i:]\nresult += right[j:]\nreturn result, inv_count<\/p>\n<\/div><\/div>
49. How do you check if a given number is a power of two?<\/h3>
Answer:<\/strong><\/p>A number is a power of two if it has only one bit set in its binary representation.<\/p>
\n
def is_power_of_two(n):
\nreturn n > 0 and (n & (n – 1)) == 0<\/p>\n<\/div><\/div>
50. How do you implement a Trie for storing words and their prefixes?<\/h3>
Answer:<\/strong><\/p>A Trie is a tree-like data structure where each node represents a single character, and paths represent words.<\/p>
![\"dsa](\"https:\/\/www.placementpreparation.io\/blog\/wp-content\/uploads\/2024\/05\/dsa-using-python-course-desktop-banner-horizontal.webp\")
<\/a><\/p>