-
Notifications
You must be signed in to change notification settings - Fork 2
Top 30 Python Coding QNA
Praveen Kumar Anwla edited this page Nov 10, 2023
·
12 revisions
Certainly! Here's a list of 30 Python coding interview questions along with brief answers. Note that the answers provided are concise; during an interview, you may be expected to explain your thought process and approach more thoroughly.
s = "hello"
reversed_s = s[::-1]def is_palindrome(s):
return s == s[::-1]from collections import Counter
def first_non_repeated_char(s):
count = Counter(s)
for char in s:
if count[char] == 1:
return chardef is_anagram(s1, s2):
return sorted(s1) == sorted(s2)def find_missing_number(nums):
n = len(nums) + 1
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sumdef binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = idef is_substring(s, sub):
return sub in sdef max_subarray_sum(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum```python
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
```
```python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
```
```python
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def is_empty(self):
return len(self.items) == 0
```
```python
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
```
```python
def count_set_bits(n):
return bin(n).count('1')
```
```python
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
```
```python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
```
```python
def reverse_linked_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
```
```python
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.data
```
def detect_loop(head):
seen = set()
current = head
while current:
if current in seen:
return True
seen.add(current)
current = current.next
return False
```
### 21. **Convert Sorted Array to Binary Search Tree:**
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst(nums[:mid])
root.right = sorted_array_to_bst(nums[mid+1:])
return root
```
### 22. **Serialize and Deserialize a Binary Tree:**
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def serialize(root):
if not root:
return "null"
left = serialize(root.left)
right = serialize(root.right)
return f"{{'val': {root.val}, 'left': {left}, 'right': {right}}}"
def deserialize(data):
if data == "null":
return None
data_dict = eval(data)
root = TreeNode(data_dict
['val'])
root.left = deserialize(data_dict['left'])
root.right = deserialize(data_dict['right'])
return root
```
### 23. **LCA (Lowest Common Ancestor) in a Binary Tree:**
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
return root if left and right else left or right
```
### 24. **Topological Sort:**
```python
from collections import defaultdict
def topological_sort(graph):
visited = set()
stack = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1]
```
### 25. **Dijkstra's Algorithm:**
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
```
### 26. **Depth-First Search (DFS) on a Graph:**
```python
def dfs(graph, node, visited):
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
```
### 27. **Breadth-First Search (BFS) on a Graph:**
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
queue.extend(graph[node] - visited)
return visited
```
### 28. **Heap Implementation:**
```python
import heapq
class MinHeap:
def __init__(self):
self.heap = []
def push(self, item):
heapq.heappush(self.heap, item)
def pop(self):
return heapq.heappop(self.heap)
def top(self):
return self.heap[0]
def size(self):
return len(self.heap)
```
### 29. **LRU Cache Implementation:**
```python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
else:
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
```
### 30. **Regular Expression Matching:**
```python
def is_match(s, p):
if not p:
return not s
first_match = bool(s) and (s[0] == p[0] or p[0] == '.')
if len(p) >= 2 and p[1] == '*':
return (is_match(s, p[2:]) or
(first_match and is_match(s[1:], p)))
else:
return first_match and is_match(s[1:], p[1:])
```
### 31. **Factorial:**
**Question:**
Write a function to calculate the factorial of a number.
**Answer:**
```python
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-1)Question: Write a function to generate the Fibonacci sequence up to n numbers.
Answer:
def fibonacci(n):
fib_sequence = [0, 1]
while len(fib_sequence) < n:
fib_sequence.append(fib_sequence[-1] + fib_sequence[-2])
return fib_sequenceRemember, the key to successfully tackling coding interviews is not just knowing the correct answers but also being able to explain your thought process, optimize your solutions, and handle edge cases effectively.