Coding Problems - Deloitte Interview Prep

1. Class Monitor

Array Easy

Problem Statement:

Given a sequence of ranks of students, count how many times the current rank is less than any previous rank (i.e., how many times you need to "cut the name" because someone with better rank came before).

Example:

Input: ranks = [5, 2, 7, 3, 1]
Output: 6
Explanation:
- At index 1 (rank 2): cuts 1 name (rank 5)
- At index 3 (rank 3): cuts 2 names (ranks 5, 7)
- At index 4 (rank 1): cuts 3 names (ranks 5, 7, 3)
Total = 1 + 2 + 3 = 6

Constraints:

1 ≤ n ≤ 10^5
1 ≤ ranks[i] ≤ 10^9

💡 Solution Approach:

For each position, count how many elements before it are greater than the current element. This can be done efficiently using various approaches:

Approach 1: Brute Force O(n²)

// C++ Solution
int countCuts(vector<int>& ranks) {
    int n = ranks.size();
    int totalCuts = 0;
    
    for (int i = 0; i < n; i++) {
        int cuts = 0;
        // Count elements before index i that are greater than ranks[i]
        for (int j = 0; j < i; j++) {
            if (ranks[j] > ranks[i]) {
                cuts++;
            }
        }
        totalCuts += cuts;
    }
    
    return totalCuts;
}

// Example usage
int main() {
    vector<int> ranks = {5, 2, 7, 3, 1};
    cout << "Total cuts: " << countCuts(ranks) << endl; // Output: 6
    return 0;
}

Approach 2: Using Multiset O(n log n)

// C++ Optimized Solution
int countCutsOptimized(vector<int>& ranks) {
    int n = ranks.size();
    int totalCuts = 0;
    multiset<int> seen;
    
    for (int i = 0; i < n; i++) {
        // Count elements in seen that are greater than ranks[i]
        auto it = seen.upper_bound(ranks[i]);
        totalCuts += distance(it, seen.end());
        seen.insert(ranks[i]);
    }
    
    return totalCuts;
}

Python Solution:

def count_cuts(ranks):
    n = len(ranks)
    total_cuts = 0
    
    for i in range(n):
        cuts = 0
        # Count elements before index i that are greater than ranks[i]
        for j in range(i):
            if ranks[j] > ranks[i]:
                cuts += 1
        total_cuts += cuts
    
    return total_cuts

# Example
ranks = [5, 2, 7, 3, 1]
print(f"Total cuts: {count_cuts(ranks)}")  # Output: 6

Time & Space Complexity:

Brute Force: Time: O(n²), Space: O(1)
Optimized (Multiset): Time: O(n log n), Space: O(n)

Key Points:

This problem is about counting inversions
For large inputs, use optimized approach with BST or Merge Sort
Practice dry-running with small examples

2. Corona for Computer

Bit Manipulation Medium

Problem Statement:

Given an array of decimal numbers, remove 'n' least significant binary bits from each number and output the new decimal values.

Example:

Input: numbers = [25, 18, 33], n = 2
Output: [6, 4, 8]

Explanation:
25 = 11001 (binary) → Remove 2 LSBs → 110 (binary) = 6 (decimal)
18 = 10010 (binary) → Remove 2 LSBs → 100 (binary) = 4 (decimal)
33 = 100001 (binary) → Remove 2 LSBs → 1000 (binary) = 8 (decimal)

Constraints:

1 ≤ array length ≤ 10^4
0 ≤ n ≤ 30
0 ≤ numbers[i] ≤ 10^9

💡 Solution Approach:

To remove n least significant bits, we can simply right-shift the number by n positions. This is equivalent to dividing by 2^n and taking the floor.

C++ Solution:

// C++ Solution
vector<int> removeNBits(vector<int>& numbers, int n) {
    vector<int> result;
    
    for (int num : numbers) {
        // Right shift by n removes n least significant bits
        int newNum = num >> n;
        result.push_back(newNum);
    }
    
    return result;
}

// Example usage
int main() {
    vector<int> numbers = {25, 18, 33};
    int n = 2;
    vector<int> result = removeNBits(numbers, n);
    
    cout << "Result: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl; // Output: 6 4 8
    
    return 0;
}

Python Solution:

def remove_n_bits(numbers, n):
    result = []
    
    for num in numbers:
        # Right shift by n removes n least significant bits
        new_num = num >> n
        result.append(new_num)
    
    return result

# Example
numbers = [25, 18, 33]
n = 2
result = remove_n_bits(numbers, n)
print(f"Result: {result}")  # Output: [6, 4, 8]

# Detailed explanation
print("\nDetailed breakdown:")
for num in numbers:
    binary = bin(num)[2:]
    shifted = num >> n
    shifted_binary = bin(shifted)[2:]
    print(f"{num} = {binary} → {shifted} = {shifted_binary}")

Java Solution:

public class CoronaComputer {
    public static int[] removeNBits(int[] numbers, int n) {
        int[] result = new int[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            result[i] = numbers[i] >> n;
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] numbers = {25, 18, 33};
        int n = 2;
        int[] result = removeNBits(numbers, n);
        
        System.out.print("Result: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
        // Output: 6 4 8
    }
}

Time & Space Complexity:

Time: O(m) where m is the array length
Space: O(m) for the result array

Key Points:

Right shift (>>) operator removes least significant bits
num >> n is equivalent to floor(num / 2^n)
This is a direct application of bit manipulation
Be careful with negative numbers if required

3. Help of Prepsters (Set Bits)

Bit Manipulation Medium

Problem Statement:

Count how many numbers less than n have exactly k set bits in their binary representation.

Example:

Input: n = 10, k = 2
Output: 4

Explanation:
Numbers < 10 with exactly 2 set bits:
3 = 11 (binary) - has 2 set bits ✓
5 = 101 (binary) - has 2 set bits ✓
6 = 110 (binary) - has 2 set bits ✓
9 = 1001 (binary) - has 2 set bits ✓
Total = 4

Constraints:

1 ≤ n ≤ 10^6
0 ≤ k ≤ 20

💡 Solution Approach:

Iterate through all numbers from 1 to n-1 and count set bits for each. If count equals k, increment result.

C++ Solution:

// C++ Solution
int countSetBits(int num) {
    int count = 0;
    while (num > 0) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

int countNumbersWithKSetBits(int n, int k) {
    int result = 0;
    
    for (int i = 1; i < n; i++) {
        if (countSetBits(i) == k) {
            result++;
        }
    }
    
    return result;
}

// Using built-in function (more efficient)
int countNumbersWithKSetBitsOptimized(int n, int k) {
    int result = 0;
    
    for (int i = 1; i < n; i++) {
        if (__builtin_popcount(i) == k) {
            result++;
        }
    }
    
    return result;
}

// Example usage
int main() {
    int n = 10, k = 2;
    cout << "Count: " << countNumbersWithKSetBits(n, k) << endl; // Output: 4
    
    // Show which numbers have exactly k set bits
    cout << "Numbers with " << k << " set bits: ";
    for (int i = 1; i < n; i++) {
        if (countSetBits(i) == k) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    return 0;
}

Python Solution:

def count_set_bits(num):
    count = 0
    while num > 0:
        count += num & 1
        num >>= 1
    return count

def count_numbers_with_k_set_bits(n, k):
    result = 0
    
    for i in range(1, n):
        if count_set_bits(i) == k:
            result += 1
    
    return result

# Using Python's built-in bin() function
def count_numbers_with_k_set_bits_v2(n, k):
    result = 0
    
    for i in range(1, n):
        if bin(i).count('1') == k:
            result += 1
    
    return result

# Example
n, k = 10, 2
print(f"Count: {count_numbers_with_k_set_bits(n, k)}")  # Output: 4

# Show which numbers
print(f"Numbers with {k} set bits:")
for i in range(1, n):
    if count_set_bits(i) == k:
        print(f"{i} = {bin(i)} (has {count_set_bits(i)} set bits)")

Time & Space Complexity:

Time: O(n * log(max_value)) where log(max_value) is for counting bits
Space: O(1)

Key Points:

Use __builtin_popcount() in C++ for efficiency
In Python, bin(n).count('1') counts set bits
Brian Kernighan's algorithm: n & (n-1) removes rightmost set bit
For very large n, consider combinatorial approach

4. Momentum (LinkedList)

Linked List Easy

Problem Statement:

Given a linked list where each node has mass (m) and velocity (v), compute total momentum = sum(m*v) for all nodes.

Example:

Input: LinkedList with nodes:
Node 1: mass=2, velocity=3
Node 2: mass=5, velocity=2
Node 3: mass=1, velocity=10

Output: 26

Explanation:
Total momentum = (2*3) + (5*2) + (1*10) = 6 + 10 + 10 = 26

Constraints:

1 ≤ number of nodes ≤ 10^5
1 ≤ mass, velocity ≤ 10^3

💡 Solution Approach:

Traverse the linked list and sum up the product of mass and velocity for each node.

C++ Solution:

// Node structure
struct Node {
    int mass;
    int velocity;
    Node* next;
    
    Node(int m, int v) : mass(m), velocity(v), next(nullptr) {}
};

// Calculate total momentum
long long calculateMomentum(Node* head) {
    long long totalMomentum = 0;
    Node* current = head;
    
    while (current != nullptr) {
        totalMomentum += (long long)current->mass * current->velocity;
        current = current->next;
    }
    
    return totalMomentum;
}

// Example usage
int main() {
    // Create linked list: (2,3) -> (5,2) -> (1,10)
    Node* head = new Node(2, 3);
    head->next = new Node(5, 2);
    head->next->next = new Node(1, 10);
    
    long long momentum = calculateMomentum(head);
    cout << "Total Momentum: " << momentum << endl; // Output: 26
    
    return 0;
}

Python Solution:

class Node:
    def __init__(self, mass, velocity):
        self.mass = mass
        self.velocity = velocity
        self.next = None

def calculate_momentum(head):
    total_momentum = 0
    current = head
    
    while current:
        total_momentum += current.mass * current.velocity
        current = current.next
    
    return total_momentum

# Example usage
head = Node(2, 3)
head.next = Node(5, 2)
head.next.next = Node(1, 10)

momentum = calculate_momentum(head)
print(f"Total Momentum: {momentum}")  # Output: 26

# Detailed traversal
print("\nNode-wise calculation:")
current = head
node_num = 1
while current:
    mom = current.mass * current.velocity
    print(f"Node {node_num}: mass={current.mass}, velocity={current.velocity}, momentum={mom}")
    current = current.next
    node_num += 1

Java Solution:

class Node {
    int mass;
    int velocity;
    Node next;
    
    Node(int mass, int velocity) {
        this.mass = mass;
        this.velocity = velocity;
        this.next = null;
    }
}

public class Momentum {
    public static long calculateMomentum(Node head) {
        long totalMomentum = 0;
        Node current = head;
        
        while (current != null) {
            totalMomentum += (long) current.mass * current.velocity;
            current = current.next;
        }
        
        return totalMomentum;
    }
    
    public static void main(String[] args) {
        Node head = new Node(2, 3);
        head.next = new Node(5, 2);
        head.next.next = new Node(1, 10);
        
        long momentum = calculateMomentum(head);
        System.out.println("Total Momentum: " + momentum); // Output: 26
    }
}

Time & Space Complexity:

Time: O(n) where n is number of nodes
Space: O(1) - only using a few variables

Key Points:

Simple linked list traversal problem
Use long long to avoid integer overflow
Momentum = mass × velocity (basic physics formula)
Be careful with null pointer checks