Stage I: Easy Questions

Arrays

Pattern: Basic Traversal & Inspection

These problems test your ability to iterate through an array and inspect or count elements based on a specific condition.

Find Numbers with Even Number of Digits

Companies: Amazon, Microsoft

Concept Tested: Iterating through each element and applying a helper logic (counting digits) to it.

Replace Elements with Greatest Element on Right Side

Companies: Amazon, Facebook (Meta)

Concept Tested: The value of traversing an array from right to left, which is a powerful technique.

Pattern: In-Place Manipulation

These problems challenge you to modify the array directly without using extra memory, forcing you to be clever with indices.

Move Zeroes

Companies: Facebook (Meta), Amazon, Google, Microsoft, Bloomberg

Concept Tested: Using a "slow" pointer (or index) to keep track of where the next non-zero element should go.

Remove Duplicates from Sorted Array

Companies: Amazon, Microsoft, Facebook (Meta), Apple, Google

Concept Tested: A classic two-pointer technique where one pointer finds unique elements and another places them correctly.

Pattern: Subarray Analysis

These problems involve analyzing a contiguous block of elements.

Maximum Subarray (Kadane's Algorithm)

Companies: Amazon, Microsoft, Google, Apple, Facebook (Meta), LinkedIn

Concept Tested: A single-pass traversal where you keep track of the "best sum ending at this position" and the "overall best sum found so far".

Time Complexity

Constant Time & Space Complexity: O(1)

Problem: Analyze the time and space complexity of a function that retrieves an item from an array using its index.

Concept Tested: Your understanding of O(1) Constant Time access.


def get_middle_element(items):
    # Assumes the array has at least one element
    middle_index = len(items) // 2
    return items[middle_index]

Analysis:

Time Complexity: O(1). The number of operations is constant. It doesn't matter if the array has 10 elements or 10 million; the time taken is the same.
Space Complexity: O(1). Only one new variable (middle_index) is created. The memory usage does not scale with the input size.

Linear Time & Constant Space: O(n) Time, O(1) Space

Problem: Analyze the complexity of finding the maximum value in an unsorted list.

Concept Tested: Your understanding of O(n) Linear Time, where you must inspect every element once.


def find_max(numbers):
    if not numbers:
        return None
    max_val = numbers[0]
    for num in numbers: # This loop runs 'n' times
        if num > max_val:
            max_val = num
    return max_val

Analysis:

Time Complexity: O(n). In the worst-case scenario, you must iterate through all n elements. If the list doubles in size, the work done also doubles.
Space Complexity: O(1). The memory used for variables is constant and does not depend on the input size n.

Linear Time & Linear Space: O(n) Time, O(n) Space

Problem: Analyze a function that creates a new array containing the squares of all numbers from an input array.

Concept Tested: Understanding how creating new data structures affects Space Complexity.

LeetCode Link: Squares of a Sorted Array

Companies: Facebook (Meta), Amazon, Apple, Google, Microsoft


def create_squared_array(numbers):
    squared_numbers = [] # A new list is created
    for num in numbers:
        squared_numbers.append(num * num)
    return squared_numbers

Analysis:

Time Complexity: O(n). The code iterates through the input array once.
Space Complexity: O(n). A new list is created whose size is directly proportional to the size of the input list.

Logarithmic Time Complexity: O(log n)

Problem: Analyze the time complexity of the following code snippet.

Concept Tested: Your understanding of O(log n) Logarithmic Time, where the problem size is halved at each step.


def logarithmic_operation(n):
    count = 0
    i = 1
    while i < n:
        i = i * 2 # The search space is effectively halved
        count += 1
    return count

Analysis:

Time Complexity: O(log n). The loop doesn't run n times. The variable i doubles each time. To reach n, it takes approximately log_2(n) steps.
Space Complexity: O(1). It uses a fixed number of variables.