Top 50 Data Structures Interview Questions 2026

Data Structures and Algorithms (DSA) form the foundation of computer science and are crucial for technical interviews at top tech companies. This comprehensive guide covers the top 50 data structures interview questions that are frequently asked in 2026, from basic concepts to advanced implementations. Once you're solid on data structures, level up with System Design Interview Questions 2026 to tackle architecture problems at Google, Amazon, and other top companies.

---

Table of Contents

1. Arrays & Strings (1-10)
2. Linked Lists (11-20)
3. Stacks & Queues (21-25)
4. Trees & Binary Trees (26-35)
5. Graphs (36-40)
6. Hash Tables & Heaps (41-45)
7. Advanced Data Structures (46-50)
8. FAQs

---

Arrays & Strings (1-10)

Question 1: What is an array? What are its advantages and disadvantages?

Difficulty: Easy
Why interviewers ask this: To test fundamental understanding of the most basic data structure.

An array is a collection of elements stored at contiguous memory locations.

# Array declaration in different languages
# Python
arr = [1, 2, 3, 4, 5]

# Java
int[] arr = {1, 2, 3, 4, 5};

# C++
int arr[5] = {1, 2, 3, 4, 5};

Advantages:

1. Random Access: O(1) access time using index
2. Cache Friendly: Contiguous memory improves cache performance
3. Simple Implementation: Easy to understand and use

Disadvantages:

1. Fixed Size: Most languages require specifying size upfront
2. Insertion/Deletion Cost: O(n) for shifting elements
3. Memory Wastage: If allocated size > actual need

Time Complexity:

Operation	Time Complexity
Access	O(1)
Search	O(n)
Insertion	O(n)
Deletion	O(n)

---

Question 2: What is the difference between array and linked list?

Difficulty: Easy

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed (static)	Dynamic (grows/shrinks)
Access	Random (O(1))	Sequential (O(n))
Insertion/Deletion	O(n) (shifting)	O(1) (if position known)
Memory Usage	Less overhead	More overhead (pointers)
Cache Performance	Better	Worse

# Array vs Linked List example

# Array insertion (shifting required)
def insert_array(arr, index, value):
    # Shift elements to right
    for i in range(len(arr)-1, index-1, -1):
        arr[i] = arr[i-1]
    arr[index] = value

# Linked list insertion (no shifting)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert_linked_list(head, position, new_node):
    if position == 0:
        new_node.next = head
        return new_node
    
    current = head
    for _ in range(position-1):
        current = current.next
    
    new_node.next = current.next
    current.next = new_node
    return head

---

Question 3: Reverse an array/string

Difficulty: Easy

# Method 1: Two-pointer approach
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# Method 2: Using slicing (Python)
def reverse_array_slice(arr):
    return arr[::-1]

# Method 3: Using built-in function
def reverse_array_builtin(arr):
    arr.reverse()
    return arr

# Reverse string
def reverse_string(s):
    # Convert to list, reverse, join back
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return ''.join(chars)

# Test cases
print(reverse_array([1, 2, 3, 4, 5]))  # [5, 4, 3, 2, 1]
print(reverse_string("hello"))         # "olleh"

---

Question 4: Find the maximum subarray sum (Kadane's Algorithm)

Difficulty: Medium

def max_subarray_sum(arr):
    """
    Kadane's Algorithm: O(n) time, O(1) space
    """
    max_ending_here = arr[0]
    max_so_far = arr[0]
    
    for i in range(1, len(arr)):
        # Either extend previous subarray or start new
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# Extended version: Also return subarray indices
def max_subarray_sum_with_indices(arr):
    max_ending_here = arr[0]
    max_so_far = arr[0]
    start = end = 0
    temp_start = 0
    
    for i in range(1, len(arr)):
        if arr[i] > max_ending_here + arr[i]:
            max_ending_here = arr[i]
            temp_start = i
        else:
            max_ending_here = max_ending_here + arr[i]
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i
    
    return max_so_far, start, end

# Test cases
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # 6 (subarray [4, -1, 2, 1])

---

Question 5: Find duplicates in an array

Difficulty: Easy

# Method 1: Using hash set (O(n) time, O(n) space)
def find_duplicates_hash(arr):
    seen = set()
    duplicates = set()
    
    for num in arr:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)
    
    return list(duplicates)

# Method 2: Sorting approach (O(n log n) time, O(1) space)
def find_duplicates_sort(arr):
    arr.sort()
    duplicates = []
    
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1] and (i == 1 or arr[i] != arr[i-2]):
            duplicates.append(arr[i])
    
    return duplicates

# Method 3: Using array indices (when 1 ≤ arr[i] ≤ n)
def find_duplicates_index(arr):
    """
    For array of size n with elements in range [1, n]
    """
    duplicates = []
    
    for i in range(len(arr)):
        index = abs(arr[i]) - 1
        
        if arr[index] < 0:
            duplicates.append(abs(arr[i]))
        else:
            arr[index] = -arr[index]
    
    # Restore array
    for i in range(len(arr)):
        arr[i] = abs(arr[i])
    
    return duplicates

# Test cases
print(find_duplicates_hash([1, 2, 3, 1, 3, 6, 6]))  # [1, 3, 6]
print(find_duplicates_index([4, 3, 2, 7, 8, 2, 3, 1]))  # [2, 3]

---

Question 6: Rotate an array by k positions

Difficulty: Medium

# Method 1: Using extra array (O(n) time, O(n) space)
def rotate_array_extra(arr, k):
    n = len(arr)
    k = k % n  # Handle k > n
    
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = arr[i]
    
    return result

# Method 2: Reverse method (O(n) time, O(1) space)
def rotate_array_reverse(arr, k):
    n = len(arr)
    k = k % n
    
    # Helper function to reverse array between indices
    def reverse(start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    # Reverse entire array
    reverse(0, n-1)
    # Reverse first k elements
    reverse(0, k-1)
    # Reverse remaining elements
    reverse(k, n-1)
    
    return arr

# Method 3: Juggling algorithm (O(n) time, O(1) space)
def rotate_array_juggling(arr, k):
    n = len(arr)
    k = k % n
    
    # Find GCD of n and k
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    g = gcd(n, k)
    
    for i in range(g):
        temp = arr[i]
        j = i
        
        while True:
            d = (j + k) % n
            if d == i:
                break
            arr[j] = arr[d]
            j = d
        
        arr[j] = temp
    
    return arr

# Test cases
arr = [1, 2, 3, 4, 5, 6, 7]
print(rotate_array_reverse(arr.copy(), 3))  # [5, 6, 7, 1, 2, 3, 4]

---

Question 7: Implement two-sum problem

Difficulty: Easy

# Problem: Given an array and target, find two numbers that sum to target
# Return their indices

# Method 1: Brute force (O(n²) time, O(1) space)
def two_sum_brute(arr, target):
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target:
                return [i, j]
    return []

# Method 2: Using hash map (O(n) time, O(n) space)
def two_sum_hash(arr, target):
    num_map = {}
    
    for i, num in enumerate(arr):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    
    return []

# Method 3: Two-pointer with sorted array (O(n log n) time, O(1) space)
def two_sum_sorted(arr, target):
    # Create list of (value, index) pairs
    indexed_arr = [(val, idx) for idx, val in enumerate(arr)]
    indexed_arr.sort(key=lambda x: x[0])
    
    left, right = 0, len(indexed_arr) - 1
    
    while left < right:
        current_sum = indexed_arr[left][0] + indexed_arr[right][0]
        
        if current_sum == target:
            return [indexed_arr[left][1], indexed_arr[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

# Test cases
arr = [2, 7, 11, 15]
target = 9
print(two_sum_hash(arr, target))  # [0, 1] (2 + 7 = 9)

---

Question 8: Find the majority element (Boyer-Moore Voting Algorithm)

Difficulty: Medium

def majority_element(arr):
    """
    Boyer-Moore Voting Algorithm
    Returns element that appears more than n/2 times
    O(n) time, O(1) space
    """
    candidate = None
    count = 0
    
    # Phase 1: Find candidate
    for num in arr:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    # Phase 2: Verify candidate
    count = 0
    for num in arr:
        if num == candidate:
            count += 1
    
    if count > len(arr) // 2:
        return candidate
    return None

# Extended version: Find all elements appearing more than n/3 times
def majority_element_ii(arr):
    """
    Returns elements that appear more than n/3 times
    """
    if not arr:
        return []
    
    # Candidates and counts
    cand1, cand2 = None, None
    count1, count2 = 0, 0
    
    # First pass: Find candidates
    for num in arr:
        if cand1 == num:
            count1 += 1
        elif cand2 == num:
            count2 += 1
        elif count1 == 0:
            cand1 = num
            count1 = 1
        elif count2 == 0:
            cand2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
    
    # Second pass: Verify candidates
    count1 = count2 = 0
    for num in arr:
        if num == cand1:
            count1 += 1
        elif num == cand2:
            count2 += 1
    
    result = []
    if count1 > len(arr) // 3:
        result.append(cand1)
    if count2 > len(arr) // 3:
        result.append(cand2)
    
    return result

# Test cases
print(majority_element([3, 2, 3]))  # 3
print(majority_element_ii([1, 1, 1, 3, 3, 2, 2, 2]))  # [1, 2]

---

Question 9: Merge two sorted arrays

Difficulty: Easy

# Method 1: Using extra space (O(m+n) time, O(m+n) space)
def merge_sorted_arrays(arr1, arr2):
    result = []
    i = j = 0
    
    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
    
    # Add remaining elements
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    
    return result

# Method 2: Merge in-place when arr1 has enough space
def merge_in_place(arr1, m, arr2, n):
    """
    arr1 has size m+n with first m elements valid
    arr2 has n elements
    """
    i = m - 1  # Last valid element in arr1
    j = n - 1  # Last element in arr2
    k = m + n - 1  # Last position in arr1
    
    while i >= 0 and j >= 0:
        if arr1[i] > arr2[j]:
            arr1[k] = arr1[i]
            i -= 1
        else:
            arr1[k] = arr2[j]
            j -= 1
        k -= 1
    
    # Copy remaining elements from arr2
    while j >= 0:
        arr1[k] = arr2[j]
        j -= 1
        k -= 1
    
    return arr1

# Test cases
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
print(merge_sorted_arrays(arr1, arr2))  # [1, 2, 3, 4, 5, 6, 7, 8]

# In-place merge test
arr1_large = [1, 3, 5, 7, 0, 0, 0, 0]
arr2_small = [2, 4, 6, 8]
print(merge_in_place(arr1_large, 4, arr2_small, 4))  # [1, 2, 3, 4, 5, 6, 7, 8]

---

Question 10: Find missing number in array

Difficulty: Easy

# Problem: Array of size n contains numbers from 0 to n (one missing)
# Find the missing number

# Method 1: Sum formula (O(n) time, O(1) space)
def missing_number_sum(arr):
    n = len(arr)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

# Method 2: XOR approach (O(n) time, O(1) space)
def missing_number_xor(arr):
    n = len(arr)
    xor_all = 0
    
    # XOR all numbers from 0 to n
    for i in range(n + 1):
        xor_all ^= i
    
    # XOR all numbers in array
    for num in arr:
        xor_all ^= num
    
    return xor_all

# Method 3: Cyclic sort (O(n) time, O(1
---

## Related Articles
- [System Design Interview Questions 2026](/article/system-design-interview-questions-2026) � Apply your DSA knowledge to build scalable systems
- [Top 50 Java Interview Questions 2026](/article/java-interview-questions-2026) � Implement DSA solutions in Java for MNC interviews
- [Top 50 Python Interview Questions 2026](/article/python-interview-questions-2026) � Python-based DSA implementations and algorithm questions
- [Networking Interview Questions 2026](/article/networking-interview-questions-2026) � Computer networks fundamentals to pair with DSA prep

*Last Updated: March 2026 | � 2026 PapersAdda.com*