return 1

krishnaik06 / The-Grand-Complete-Data-Science-Materials Public return n * factorial(n-1)

Code Issues Pull requests 4 Actions Projects Security Insights

4. Fibonacci Series

The-Grand-Complete-Data-Science-Materials / Python / Python DSA Interviews.md Question: Generate the nth Fibonacci number.
Answer:
krishnaik06 Add files via upload 3 weeks ago

def fibonacci(n):
1500 lines (1105 loc) · 63.7 KB if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
Preview Code Blame Raw

Here's a comprehensive list of interview questions on data structures and algorithms, along 5. Linked List Cycle Detection
with their answers and Python code:
Question: Detect if there is a cycle in a linked list.
1. Reverse a String Answer:

Question: Reverse a given string.

class ListNode:
Answer: def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reverse_string(s):
return s[::-1]
def has_cycle(node):
slow, fast = node, node
while fast and fast.next:
2. Check Palindrome slow = slow.next
fast = fast.next.next
Question: Check if a string is a palindrome. if slow == fast:
return True
Answer: return False

def is_palindrome(s):
return s == s[::-1]
6. Merge Two Sorted Lists

Question: Merge two sorted linked lists.

3. Find Factorial Answer:

Question: Calculate the factorial of a number.

def merge_sorted_lists(l1, l2):
Answer: dummy = ListNode(0)
current = dummy
def factorial(n):
while l1 and l2:
if n <= 1:
 if l1.value < l2.value: self.right = right
current.next, l1 = l1, l1.next
else: def is_balanced(root):
current.next, l2 = l2, l2.next def check_balance(node):
current = current.next if not node:
return 0, True
current.next = l1 or l2 left_height, left_balanced = check_balance(node.left)
return dummy.next right_height, right_balanced = check_balance(node.right)
return max(left_height, right_height) + 1, left_balanced and
right_balanced and abs(left_height - right_height) <= 1

7. Find the Middle of Linked List return check_balance(root)[1]

Question: Find the middle element of a linked list.

Answer:
10. Breadth-first Search (BFS) in Graph

def find_middle(node): Question: Implement BFS for a graph.

slow, fast = node, node
Answer:
while fast and fast.next:
slow = slow.next
fast = fast.next.next from collections import deque
return slow
def bfs(graph, start):
visited = set()
queue = deque([start])
8. Maximum Subarray Sum while queue:
vertex = queue.popleft()
Question: Find the maximum subarray sum using Kadane's algorithm. if vertex not in visited:
Answer: visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def max_subarray(nums):
max_current = max_global = nums[0]
for i in range(1, len(nums)):
max_current = max(nums[i], max_current + nums[i]) 11. Depth-first Search (DFS) in Graph
max_global = max(max_global, max_current)
return max_global Question: Implement DFS for a graph.
Answer:

9. Check if a Tree is Balanced def dfs(graph, start, visited=None):

if visited is None:
Question: Check if a binary tree is balanced. visited = set()
Answer: visited.add(start)
for vertex in graph[start] - visited:
dfs(graph, vertex, visited)
class TreeNode: return visited
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
12. Implement a Stack self.stack2.append(self.stack1.pop())
return self.stack2.pop() if self.stack2 else None
Question: Implement a stack using linked list.
Answer:
14. Implement a Priority Queue
class StackNode:
Question: Implement a priority queue using a heap.
def __init__(self, value=0, next=None):
self.value = value Answer:
self.next = next

import heapq
class Stack:
def __init__(self):
class PriorityQueue:
self.top = None
def __init__(self):
self.queue = []
def push(self, value):
self.top = StackNode(value, self.top)
def enqueue(self, value, priority=0):
heapq.heappush(self.queue, (priority, value))
def pop(self):
if not self.top:
def dequeue(self):
return None
return heapq.heappop(self.queue)[1] if self.queue else None
value = self.top.value
self.top = self.top.next
return value

15. Implement Hashmap

def peek(self):
return None if not self.top else self.top.value
Question: Implement a simple hashmap.
def is_empty(self): Answer:
return self.top is None

class Hashmap:
def __init__(self):
13. Implement a Queue self.size = 1000
self.map = [None] * self.size
Question: Implement a queue using two stacks.
def _hash(self, key):
Answer: return hash(key) % self.size

def put(self, key, value):

class Queue:
key_hash = self._hash(key)
def __init__(self):
self.map[key_hash] = value
self.stack1 = []
self.stack2 = []
def get(self, key):
key_hash = self._hash(key)
def enqueue(self, value):
return self.map[key_hash]
self.stack1.append(value)

def remove(self, key):

def dequeue(self):
key_hash = self._hash(key)
if not self.stack2:
while self.stack1:
 self.map[key_hash] = None return False
node = node.children[char]
return node.is_end_of_word

16. Binary Search def starts_with(self, prefix):

node = self.root
Question: Implement binary search for a sorted list. for char in prefix:
Answer: if char not in node.children:
return False
node = node.children[char]
def binary_search(arr, x): return True
l, r = 0, len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == x: 18. Find First and Last Position of Element in Sorted Array
return mid
elif arr[mid] < x: Question: Given a sorted array of integers and a target value, find the starting and
l = mid + 1 ending position of the target value using binary search.
else:
Answer:
r = mid - 1
return -1
def search_range(nums, target):
def find_left_boundary(nums, target):
left, right = 0, len(nums) - 1
17. Implement Trie (Prefix Tree) while left <= right:
mid = (left + right) // 2
Question: Implement a basic trie for word insert, search and prefix search. if nums[mid] < target:
Answer: left = mid + 1
else:
right = mid - 1
class TrieNode: return left
def __init__(self):
self.children = {} left, right = find_left_boundary(nums, target), find_left_boundary(nums,
self.is_end_of_word = False target + 1) - 1
if left <= right:
class Trie: return [left, right]
def __init__(self): return [-1, -1]
self.root = TrieNode()

def insert(self, word):

node = self.root 19. Topological Sort
for char in word:
if char not in node.children: Question: Implement a topological sort for a directed graph.
node.children[char] = TrieNode()
Answer:
node = node.children[char]
node.is_end_of_word = True
from collections import defaultdict, deque
def search(self, word):
node = self.root def topological_sort(vertices, edges):
for char in word: graph = defaultdict(list)
if char not in node.children: in_degree = {v: 0 for v in vertices}
 return arr
for u, v in edges: pivot = arr[len(arr) // 2]
graph[u].append(v) left = [x for x in arr if x < pivot]
in_degree[v] += 1 middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
queue = deque([v for v, d in in_degree.items() if d == 0]) return quicksort(left) + middle + quicksort(right)
order = []

while queue:
vertex = queue.popleft() 22. Implement MergeSort
order.append(vertex)
for neighbor in graph[vertex]: Question: Implement the mergesort algorithm.
in_degree[neighbor] -= 1 Answer:
if in_degree[neighbor] == 0:
queue.append(neighbor)
def mergesort(arr):
return order if len(order) == len(vertices) else [] if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
20. Check if a String Contains All Binary Codes of Size K right = arr[mid:]
return merge(mergesort(left), mergesort(right))
Question: Given a binary string s and an integer k , check if all binary codes of length
k is a substring of s . def merge(left, right):
result = []
Answer:
i = j = 0
while i < len(left) and j < len(right):
def has_all_codes(s, k): if left[i] < right[j]:
needed = 1 << k result.append(left[i])
seen = set() i += 1
else:
for i in range(len(s) - k + 1): result.append(right[j])
substring = s[i:i+k] j += 1
if substring not in seen: result.extend(left[i:])
seen.add(substring) result.extend(right[j:])
needed -= 1 return result
if needed == 0:
return True

return False
23. Maximum Depth of Binary Tree

Question: Find the maximum depth of a binary tree.

Answer:
21. Implement QuickSort

Question: Implement the quicksort algorithm. def max_depth(root):

if not root:
Answer:
return 0
left_depth = max_depth(root.left)
def quicksort(arr): right_depth = max_depth(root.right)
if len(arr) <= 1:
 return max(left_depth, right_depth) + 1 right_max = [0] * n

left_max[0] = height[0]
for i in range(1, n):
24. Count the Number of Islands left_max[i] = max(height[i], left_max[i-1])

Question: Given a 2D grid consisting of '1's (land) and '0's (water), count the number of right_max[n-1] = height[n-1]
islands. An island is surrounded by water and is formed by connecting adjacent lands for i in range(n-2, -1, -1):
horizontally or vertically. right_max[i] = max(height[i], right_max[i+1])

Answer: ans = 0
for i in range(n):
ans += min(left_max[i], right_max[i]) - height[i]
def num_islands(grid):
if not grid:
return ans
return 0

count = 0
for i in range(len(grid)):
26. Coin Change
for j in range(len(grid[0])):
if grid[i][j] == '1':
Question: You are given coins of different denominations and a total amount of money
dfs(grid, i, j)
count += 1 amount. Write a function to compute the fewest number of coins that you need to make
return count up that amount. If that amount of money cannot be made up by any combination of the
coins, return -1.
def dfs(grid, i, j):
Answer:
if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] !=
'1'):
return def coin_change(coins, amount):
grid[i][j] = '#' dp = [float('inf')] * (amount + 1)
dfs(grid, i-1, j) dp[0] = 0
dfs(grid, i+1, j)
dfs(grid, i, j-1) for coin in coins:
dfs(grid, i, j+1) for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

25. Trapping Rain Water

Question: Given n non-negative integers representing an elevation map where the width 27. Decode Ways
of each bar is 1, compute how much water it can trap after raining.
Question: A message containing letters from A-Z is being encoded to numbers using the
Answer:
following mapping: 'A' -> '1', 'B' -> '2', ..., 'Z' -> '26'. Given a non-empty string containing
only digits, determine the total number of ways to decode it.
def trap(height):
if not height: Answer:
return 0
def num_decodings(s):
n = len(height)
if not s:
left_max = [0] * n
return 0
 n = len(s) def fibonacci(n):
dp = [0] * (n + 1) if n <= 1:
dp[0] = 1 return n
dp[1] = 0 if s[0] == '0' else 1 a, b = 0, 1
for _ in range(2, n + 1):
for i in range(2, n + 1): a, b = b, a + b
first = int(s[i-1:i]) return b
second = int(s[i-2:i])
if 1 <= first <= 9:
dp[i] += dp[i-1]
if 10 <= second <= 26:
30. Longest Increasing Subsequence
dp[i] += dp[i-2]
Question: Given an unsorted array of integers, find the length of longest increasing
return dp[n] subsequence.
Answer:

28. Container With Most Water def length_of_lis(nums):

if not nums:
Question: Given n non-negative integers a1, a2, ..., an , where each represents a return 0
point at coordinate (i, ai) . n vertical lines are drawn such that the two endpoints of
dp = [1] * len(nums)
the line i is at (i, ai) and (i, 0) . Find two lines, which, together with the x-axis
for i in range(len(nums)):
forms a container, such that the container contains the most water.
for j in range(i):
Answer: if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)

def max_area(height):
return max(dp)
left, right = 0, len(height) - 1
max_area = 0

while left < right: 31. Check for Palindrome

h = min(height[left], height[right])
max_area = max(max_area, h * (right - left)) Question: Write a function that checks whether a given word or phrase is palindrome.
if height[left] < height[right]:
left += 1
Answer:
else:
right -= 1 def is_palindrome(s):
s = ''.join([c for c in s if c.isalnum()]).lower()
return max_area return s == s[::-1]

29. Fibonacci Series 32. Maximum Subarray

Question: Implement a function to compute the nth Fibonacci number. Question: Given an integer array nums, find the contiguous subarray (containing at least
Answer: one number) which has the largest sum and return its sum.
Answer:
 def max_sub_array(nums): return not stack
if not nums:
return 0
cur_sum = max_sum = nums[0]
for num in nums[1:]: 35. Reverse a String
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum) Question: Implement a function that reverses a string.
return max_sum
Answer:

def reverse_string(s):
33. Longest Common Prefix return s[::-1]

Question: Write a function to find the longest common prefix string amongst an array of
strings. If there is no common prefix, return an empty string "".
36. Intersection of Two Arrays II
Answer:
Question: Given two arrays, write a function to compute their intersection. Each element
def longest_common_prefix(strs): in the result should appear as many times as it shows in both arrays. The result can be in
if not strs: any order.
return ""
Answer:
prefix = strs[0]
for s in strs[1:]: from collections import Counter
i = 0
while i < len(prefix) and i < len(s) and prefix[i] == s[i]:
def intersect(nums1, nums2):
i += 1 c1, c2 = Counter(nums1), Counter(nums2)
prefix = prefix[:i] return list((c1 &amp; c2).elements())
return prefix

37. Single Number

34. Check for Balanced Parentheses
Question: Given a non-empty array of integers nums, every element appears twice except
Question: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if
for one. Find that single one.
the input string is valid. An input string is valid if brackets are closed in the correct order.
Answer:
Answer:

def single_number(nums):
def is_valid(s): res = 0
stack = []
for num in nums:
mapping = {")": "(", "}": "{", "]": "["}
res ^= num
return res
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element: 38. Rotate Array
return False
else: Question: Given an array, rotate the array to the right by k steps, where k is non-negative.
stack.append(char)
 Answer:
from collections import Counter

def rotate(nums, k): def first_uniq_char(s):

k %= len(nums) count = Counter(s)
nums[:] = nums[-k:] + nums[:-k] for idx, ch in enumerate(s):
if count[ch] == 1:
return idx
return -1
39. Product of Array Except Self

Question: Given an array nums of n integers where n > 1, return an array output such
that output[i] is equal to the product of all the elements of nums except nums[i]. 42. Two Sum

Answer: Question: Given an array of integers nums and an integer target , return indices of the
two numbers such that they add up to target .
def product_except_self(nums): Answer:
length = len(nums)
output = [1] * length
left, right = 1, 1 def two_sum(nums, target):
num_to_index = {}
for i in range(length): for i, num in enumerate(nums):
output[i] *= left diff = target - num
left *= nums[i] if diff in num_to_index:
output[-1 - i] *= right return [num_to_index[diff], i]
right *= nums[-1 - i] num_to_index[num] = i

return output

43. Count Primes

40. Implement strStr() Question: Count the number of prime numbers less than a non-negative number, n.
Answer:
Question: Implement strStr() . Return the index of the first occurrence of needle in
haystack, or -1 if needle is not part of haystack.
def count_primes(n):
Answer:
if n <= 2:
return 0
def str_str(haystack, needle): primes = [True] * n
if not needle: primes[0], primes[1] = False, False
return 0 for i in range(2, int(n**0.5) + 1):
return haystack.find(needle) if primes[i]:
for j in range(i*i, n, i):
primes[j] = False
return sum(primes)
41. First Unique Character in a String

Question: Given a string, find the first non-repeating character in it and return its index. If
44. Majority Element
it doesn't exist, return -1 .
Answer:
 Question: Given an array of size n, find the majority element. The majority element is the return True

element that appears more than n/2 times.

Answer:
46. Move Zeroes

from collections import Counter

Question: Given an array nums , write a function to move all 0 's to the end of it while
def majority_element(nums):
maintaining the relative order of the non-zero elements.
counts = Counter(nums) Answer:
return max(counts.keys(), key=counts.get)

def move_zeroes(nums):
pos = 0
45. Valid Sudoku for i in range(len(nums)):
if nums[i] != 0:
Question: Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be nums[pos], nums[i] = nums[i], nums[pos]
pos += 1
validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
47. Best Time to Buy and Sell Stock
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Answer: Question: Say you have an array for which the i th element is the price of a given stock
on day i . If you were only permitted to complete at most one transaction (i.e., buy one
and sell one share of the stock), design an algorithm to find the maximum profit.
def is_valid_sudoku(board):
rows = [set() for _ in range(9)] Answer:
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
def max_profit(prices):
if not prices:
for i in range(9):
return 0
for j in range(9):
val = board[i][j]
min_price = prices[0]
if val == '.':
max_profit = 0
continue

for price in prices:

if val in rows[i]:
if price < min_price:
return False
min_price = price
rows[i].add(val)
else:
max_profit = max(max_profit, price - min_price)
if val in cols[j]:
return False
return max_profit
cols[j].add(val)

box_idx = (i // 3) * 3 + j // 3
if val in boxes[box_idx]:
48. Valid Anagram
return False
boxes[box_idx].add(val)
Question: Given two strings s and t , write a function to determine if t is an anagram
of s .
Answer:
 These are just some examples, and the above solutions can be optimized and extended in
from collections import Counter
various ways, depending on the exact constraints and requirements.
def is_anagram(s, t):
return Counter(s) == Counter(t)
51. Merge Two Sorted Lists

Question: Merge two sorted linked lists and return it as a new sorted list.
Answer:
49. Maximum Depth of Binary Tree

Question: Given a binary tree, find its maximum depth. The maximum depth is the class ListNode:
def __init__(self, val=0, next=None):
number of nodes along the longest path from the root node down to the farthest leaf
self.val = val
node.
self.next = next
Answer:
def merge_two_lists(l1, l2):
dummy = ListNode(-1)
class TreeNode:
prev = dummy
def __init__(self, val=0, left=None, right=None):
self.val = val
while l1 and l2:
self.left = left
if l1.val <= l2.val:
self.right = right
prev.next = l1
l1 = l1.next
def max_depth(root):
else:
if not root:
prev.next = l2
return 0
l2 = l2.next
return 1 + max(max_depth(root.left), max_depth(root.right))
prev = prev.next

prev.next = l1 if l1 else l2
return dummy.next
50. Palindrome Linked List

Question: Given a singly linked list, determine if it is a palindrome.

Answer: 52. Implement Stack using Queues

Question: Implement a stack using only instances of a queue.

class ListNode:
def __init__(self, val=0, next=None): Answer:
self.val = val
self.next = next
from collections import deque

def is_palindrome(head):
class MyStack:
vals = []
def __init__(self):
current = head
self.q = deque()
while current:
vals.append(current.val)
def push(self, x):
current = current.next
self.q.append(x)
return vals == vals[::-1]
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())

def pop(self):
 return self.q.popleft() def level_order(root):
if not root:
def top(self): return []
return self.q[0] result, queue = [], [root]
while queue:
def empty(self): level, level_len = [], len(queue)
return not self.q for i in range(level_len):
node = queue.pop(0)
level.append(node.val)
if node.left:
53. Min Stack queue.append(node.left)
if node.right:
Question: Design a stack that supports push, pop, top, and retrieving the minimum queue.append(node.right)
element in constant time. result.append(level)
return result
Answer:

class MinStack:
def __init__(self): 55. Linked List Cycle
self.stack = []
self.min_stack = [] Question: Given a linked list, determine if it has a cycle in it.
Answer:
def push(self, x):
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]: class ListNode:
self.min_stack.append(x) def __init__(self, x):
self.val = x
def pop(self): self.next = None
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop() def has_cycle(head):
slow, fast = head, head
def top(self): while fast and fast.next:
return self.stack[-1] slow = slow.next
fast = fast.next.next
def getMin(self): if slow == fast:
return self.min_stack[-1] return True
return False

54. Binary Tree Level Order Traversal

56. Invert Binary Tree
Question: Given a binary tree, return the level order traversal of its nodes' values.
Question: Invert a binary tree.
Answer:
Answer:

class TreeNode:
def __init__(self, val=0, left=None, right=None): class TreeNode:
self.val = val def __init__(self, val=0, left=None, right=None):
self.left = left self.val = val
self.right = right self.left = left
self.right = right
 def invert_tree(root): def top_k_frequent(nums, k):
if not root: count = Counter(nums)
return None return heapq.nlargest(k, count.keys(), key=count.get)
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root

59. Decode String

57. Serialize and Deserialize Binary Tree Question: Given an encoded string, return its decoded string. The encoding rule is:
k[encoded_string], where the encoded_string inside the square brackets is being
Question: Design an algorithm to serialize and deserialize a binary tree.
repeated exactly k times.
Answer:
Answer:

class TreeNode:
def decode_string(s):
def __init__(self, x):
stack, curr_num, curr_str = [], 0, ''
self.val = x
for char in s:
self.left = None
if char == '[':
self.right = None
stack.append(curr_str)
stack.append(curr_num)
class Codec:
curr_str, curr_num = '', 0
def serialize(self, root):
elif char == ']':
def dfs(node):
num = stack.pop()
if not node:
prev_str = stack.pop()
return ["None"]
curr_str = prev_str + num * curr_str
return [str(node.val)] + dfs(node.left) + dfs(node.right)
elif char.isdigit():
return ",".join(dfs(root))
curr_num = curr_num * 10 + int(char)
else:
def deserialize(self, data):
curr_str += char
data_list = data.split(',')
return curr_str
def dfs():
val = data_list.pop(0)
if val == "None":
return None 60. Number of Islands
node = TreeNode(int(val))
node.left = dfs() Question: Given a 2D grid map of '1's (land) and '0's (water), count the number of islands.
node.right = dfs()
return node Answer:
return dfs()
def num_islands(grid):
if not grid:
return 0
58. Top K Frequent Elements
rows, cols = len(grid), len(grid[0])
Question: Given a non-empty array of integers, return the k most frequent elements.
visited = [[0 for _ in range(cols)] for _ in range(rows)]
Answer: directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
islands = 0

from collections import Counter

def dfs(row, col):
import heapq
 if row < 0 or col < 0 or row >= rows or col >= cols or visited[row]
[col] or grid[row][col] == '0': def two_sum(nums, target):
return num_map = {}
visited[row][col] = 1 for index, num in enumerate(nums):
for dr, dc in directions: complement = target - num
dfs(row + dr, col + dc) if complement in num_map:
return [num_map[complement], index]
for r in range(rows): num_map[num] = index
for c in range(cols):
if grid[r][c] == '1' and not visited[r][c]:
dfs(r, c)
islands += 1
63. Rotate Image

return islands Question: Given an image represented by an NxN matrix, rotate the image by 90
degrees.
Answer:
The explanations have been excluded for brevity, but it's essential to understand the logic
behind each code snippet and be prepared to explain the solution's approach and its time def rotate(matrix):
n = len(matrix)
and space complexity.
for i in range(n):
for j in range(i, n):
61. Maximum Depth of Binary Tree
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
Question: Given a binary tree, find its maximum depth.
row.reverse()
Answer:

class TreeNode:
64. Palindrome Linked List
def __init__(self, val=0, left=None, right=None):
self.val = val
Question: Check if a singly linked list is a palindrome.
self.left = left
self.right = right Answer:

def max_depth(root):
class ListNode:
if not root:
def __init__(self, val=0, next=None):
return 0
self.val = val
left = max_depth(root.left)
self.next = next
right = max_depth(root.right)
return max(left, right) + 1
def is_palindrome(head):
values = []
current = head
while current:
62. Two Sum
values.append(current.val)
current = current.next
Question: Given an array of integers, return indices of the two numbers such that they
return values == values[::-1]
add up to a specific target.
Answer:

65. Product of Array Except Self

 Question: Given an array nums of n integers where n > 1, return an array output such
def coin_change(coins, amount):
that output[i] is equal to the product of all the elements of nums except nums[i].
dp = [float('inf')] * (amount + 1)
Answer: dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
def product_except_self(nums):
dp[i] = min(dp[i], dp[i - coin] + 1)
n = len(nums) return dp[amount] if dp[amount] != float('inf') else -1
left, right, output = [1] * n, [1] * n, [1] * n

for i in range(1, n):

left[i] = nums[i - 1] * left[i - 1] 68. House Robber

for i in range(n - 2, -1, -1): Question: Given a list of non-negative integers representing the amount of money of
right[i] = nums[i + 1] * right[i + 1]
each house, determine the maximum amount of money you can rob without alerting the
for i in range(n):
police (you cannot rob two adjacent houses).
output[i] = left[i] * right[i] Answer:

return output
def rob(nums):
if not nums:
return 0
66. Find All Duplicates in an Array if len(nums) == 1:
return nums[0]
Question: Given an array of integers, where 1 ≤ a[i] ≤ n (n = size of array), some elements prev = nums[0]
curr = max(nums[0], nums[1])
appear twice and others appear once. Find all the elements that appear twice.
for i in range(2, len(nums)):
Answer: temp = curr
curr = max(prev + nums[i], curr)
prev = temp
def find_duplicates(nums):
return curr
result = []
for num in nums:
index = abs(num) - 1
if nums[index] < 0:
69. Longest Palindromic Substring
result.append(index + 1)
nums[index] = -nums[index]
Question: Given a string, find the longest substring which is a palindrome.
return result
Answer:

def longest_palindrome(s):
67. Coin Change
if not s:
return ""
Question: You are given coins of different denominations and a total amount of money
amount. Write a function to compute the fewest number of coins that you need to make
def expand_center(left, right):
up that amount. If that amount of money cannot be made up by any combination of the while left >= 0 and right < len(s) and s[left] == s[right]:
coins, return -1 . left -= 1
right += 1
Answer:
return s[left + 1:right]

result = ""
 for i in range(len(s)): return True
# Odd length palindrome
palindrome1 = expand_center(i, i)
# Even length palindrome
palindrome2 = expand_center(i, i + 1) These solutions are just the code implementations. It's important to understand the logic,
approach, and potentially the time and space complexities behind each one.
if len(palindrome1) > len(result):
result = palindrome1
if len(palindrome2) > len(result):
result = palindrome2
return result

70. Implement Trie (Prefix Tree)

Question: Implement a trie with insert, search, and startsWith methods.

Answer:

class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):

node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True

def search(self, word):

node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_word

def starts_with(self, prefix):

node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]