[go: up one dir, main page]
Scribd
Upload
38 views4 pages

DSA Coding Questions Solutions

The document contains a series of coding questions and their solutions related to data structures and algorithms. It includes problems such as finding a missing number in an array, checking for palindromes, performing binary search, merging sorted arrays, reversing a linked list, checking for balanced parentheses, finding the height of a binary tree, and calculating the longest common subsequence. Each solution is provided in Python code format with example outputs.

Uploaded by

rashid.chegg12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
38 views4 pages

DSA Coding Questions Solutions

The document contains a series of coding questions and their solutions related to data structures and algorithms. It includes problems such as finding a missing number in an array, checking for palindromes, performing binary search, merging sorted arrays, reversing a linked list, checking for balanced parentheses, finding the height of a binary tree, and calculating the longest common subsequence. Each solution is provided in Python code format with example outputs.

Uploaded by

rashid.chegg12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

DSA Coding Questions with Solutions

Q1: Find the Missing Number in an Array of 1 to N

def find_missing_number(arr):

n = len(arr) + 1

total_sum = n * (n + 1) // 2

return total_sum - sum(arr)

arr = [1, 2, 4, 5, 6]

print(find_missing_number(arr)) # Output: 3

Q2: Check if a String is a Palindrome

def is_palindrome(s):

return s == s[::-1]

s = 'madam'

print(is_palindrome(s)) # Output: True

Q3: Binary Search

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

Page 1
DSA Coding Questions with Solutions

arr = [1, 2, 3, 4, 5, 6]

print(binary_search(arr, 4)) # Output: 3

Q4: Merge Two Sorted Arrays

def merge_sorted_arrays(arr1, arr2):

i, j = 0, 0

result = []

while i < len(arr1) and j < len(arr2):

if arr1[i] < arr2[j]:

result.append(arr1[i])

i += 1

else:

result.append(arr2[j])

j += 1

result.extend(arr1[i:])

result.extend(arr2[j:])

return result

arr1 = [1, 3, 5]

arr2 = [2, 4, 6]

print(merge_sorted_arrays(arr1, arr2)) # Output: [1, 2, 3, 4, 5, 6]

Q5: Reverse a Linked List

class Node:

def __init__(self, data):

self.data = data

self.next = None

Page 2
DSA Coding Questions with Solutions

def reverse_linked_list(head):

prev = None

curr = head

while curr:

next_node = curr.next

curr.next = prev

prev = curr

curr = next_node

return prev

Q6: Check for Balanced Parentheses

def is_balanced(expression):

stack = []

pairs = {')': '(', '}': '{', ']': '['}

for char in expression:

if char in pairs.values():

stack.append(char)

elif char in pairs.keys():

if not stack or stack.pop() != pairs[char]:

return False

return len(stack) == 0

expr = '{[()]}'

print(is_balanced(expr)) # Output: True

Q7: Find the Height of a Binary Tree

class TreeNode:

Page 3
DSA Coding Questions with Solutions

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def tree_height(root):

if not root:

return 0

return 1 + max(tree_height(root.left), tree_height(root.right))

Q9: Longest Common Subsequence

def lcs(X, Y):

m, n = len(X), len(Y)

dp = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):

for j in range(1, n+1):

if X[i-1] == Y[j-1]:

dp[i][j] = dp[i-1][j-1] + 1

else:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

return dp[m][n]

X = 'AGGTAB'

Y = 'GXTXAYB'

print(lcs(X, Y)) # Output: 4

Page 4

You might also like