Coding Projects

Average time complexity:

O(n)

Additional space:

O(n)

This is usually faster than comparing every pair, which can take O(n²).

🔹 8. What is the Two Sum problem?

Answer:

You are given an array and a target value. Find two elements whose sum equals the target.

Example:

Array: [2, 7, 11, 15]

Target: 9

The answer is:

2 + 7 = 9

A HashMap can solve this efficiently.

arr = [2, 7, 11, 15]
target = 9

seen = {}

for i, num in enumerate(arr):
    complement = target - num

    if complement in seen:
        print(seen[complement], i)
        break

    seen[num] = i

Output:

0 1

Average time complexity:

O(n)

Space complexity:

O(n)

This is one of the most important patterns to recognize in array interviews.

🔹 9. How do you move all zeroes to the end?

Example:

Input:

[0, 1, 0, 3, 12]

Output:

[1, 3, 12, 0, 0]

A Two Pointer approach can solve this in-place.

arr = [0, 1, 0, 3, 12]

position = 0

for i in range(len(arr)):
    if arr[i] != 0:
        arr[position], arr[i] = arr[i], arr[position]
        position += 1

print(arr)

Output:

[1, 3, 12, 0, 0]

Time complexity:

O(n)

Space complexity:

O(1)

🔹 10. How do you find the missing number?

Suppose the array contains numbers from "0" to "n", but one number is missing.

Example:

[3, 0, 1]

The missing number is:

2

One efficient approach uses the expected sum:

arr = [3, 0, 1]

n = len(arr)

expected_sum = n * (n + 1) // 2
actual_sum = sum(arr)

missing = expected_sum - actual_sum

print(missing)

Output:

Time complexity:

O(n)

Space complexity:

O(1)

🔹 11. What is the difference between Linear Search and Binary Search?

Answer:

Linear Search checks elements one by one.

Time: O(n)

It can work on unsorted data.

Binary Search repeatedly divides the search space approximately in half.

Time: O(log n)

It requires suitable sorted data.

For example:

Linear Search:

10 → 20 → 30 → 40 → 50

Binary Search:

30

/ \

10 40...

The key interview point is not simply memorizing the complexities. You should understand when Binary Search can actually be applied.

🔹 12. What is an in-place algorithm?

Answer:

An in-place algorithm modifies the input data structure while using only a small amount of additional memory.

For example, reversing an array using two pointers:

arr = [1, 2, 3, 4]

left = 0
right = len(arr) - 1

while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1

No second array is created.

Therefore, the extra space used is:

O(1)

🔹 13. What is the Maximum Subarray problem?

Answer:

You are given an array of integers and need to find the contiguous subarray with the maximum sum.

Example:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum-sum contiguous subarray is:

[4, -1, 2, 1]

Its sum is:

6

A famous solution uses Kadane's Algorithm.

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

current = arr[0]
maximum = arr[0]

for i in range(1, len(arr)):
    current = max(arr[i], current + arr[i])
    maximum = max(maximum, current)

print(maximum)

Output:

❤1😁1

1.78K views05:57