Data Structures and Algorithms in C (DSA)

📘 Chapter 42: Interview Problems from FAANG Companies

You've built a robust foundation in Data Structures and Algorithms. Now, it's time to apply that knowledge to the kinds of challenges you'll face in technical interviews at companies like FAANG (Facebook, Apple, Amazon, Netflix, Google) and other leading tech firms. These interviews aren't just about finding the correct answer; they're about demonstrating your problem-solving process, ability to optimize, communication skills, and handling edge cases.

In this chapter, we'll walk through several frequently asked interview problems. For each, we'll:

• Understand the problem statement and clarify any ambiguities.
• Explore different approaches, starting from a brute-force solution and incrementally optimizing towards the most efficient one.
• Discuss the time and space complexity of each approach.
• Provide clean, runnable code for the optimal solution.
• Highlight common pitfalls, edge cases, and interviewer expectations.

⭐ 1. Two Sum (Arrays & Hash Maps)

One of the most fundamental and frequently asked problems, often used as a warm-up or screening question.

Problem Statement:

Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`.
You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example: `nums = [2, 7, 11, 15]`, `target = 9`
Output: `[0, 1]` (because `nums[0] + nums[1] == 2 + 7 == 9`)

Approach 1: Brute Force

Iterate through each number and for each number, iterate through the rest of the array to find its complement.
Time Complexity: $O(N^2)$ (due to nested loops)
Space Complexity: $O(1)$

Approach 2: Using Hash Map (Optimized)

We can optimize this to $O(N)$ time by using a hash map (or dictionary in Python, `unordered_map` in C++).
The idea is to iterate through the array once. For each number `num` at `index`:

1. Calculate its `complement = target - num`.
2. Check if this `complement` already exists in our hash map.
   • If yes, we found the pair! Return `[map[complement], index]`.
   • If no, store the current `num` and its `index` in the hash map: `map[num] = index`. This prepares for future lookups.

// C++ Solution for Two Sum (Optimized)
#include <vector>
#include <unordered_map>
#include <iostream>

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> num_map; // Stores {number: index}

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        // Check if the complement exists in our map
        if (num_map.count(complement)) {
            // Found it! Return the indices
            return {num_map[complement], i};
        }
        // If not found, add the current number to the map for future lookups
        num_map[nums[i]] = i;
    }
    // According to problem statement, exactly one solution exists, so this line won't be reached
    return {};
}

// Example Usage:
// int main() {
//     std::vector<int> nums = {2, 7, 11, 15};
//     int target = 9;
//     std::vector<int> result = twoSum(nums, target);
//     std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl; // Output: [0, 1]
//     return 0;
// }
  

Time Complexity: $O(N)$ (single pass through array, hash map lookups/insertions average $O(1)$)
Space Complexity: $O(N)$ (for the hash map, storing up to $N$ elements in the worst case)

📝 2. Valid Parentheses (Stacks)

A common problem testing your understanding of stacks and string parsing.

Problem Statement:

Given a string `s` containing just the characters '(', ')', '{', '}', '[', ']', determine if the input string is valid.
A valid string must satisfy these rules:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Approach: Using a Stack

The Last-In-First-Out (LIFO) nature of a stack is perfect for this problem. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check the top of the stack.

1. Initialize an empty stack.
2. Iterate through each character `char` in the input string `s`:
   • If `char` is an opening bracket (`(`, `{`, `[`), push it onto the stack.
   • If `char` is a closing bracket (`)`, `}`, `]`):
     • Check if the stack is empty. If it is, it means we have a closing bracket without a matching opening one, so the string is invalid. Return `false`.
     • Pop the top element from the stack.
     • Check if the popped opening bracket matches the current closing bracket type. If not, the string is invalid. Return `false`.
3. After iterating through the entire string, if the stack is empty, it means all opening brackets were correctly closed. The string is valid. Return `true`. If the stack is not empty, there are unmatched opening brackets, so return `false`.

// C++ Solution for Valid Parentheses
#include <string>
#include <stack>
#include <unordered_map>
#include <iostream>

bool isValid(std::string s) {
    std::stack<char> st;
    std::unordered_map<char, char> mappings = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };

    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c); // Push opening brackets
        } else { // It's a closing bracket
            if (st.empty()) { // No matching opening bracket
                return false;
            }
            char top_element = st.top();
            st.pop();
            // Check if the popped opening bracket matches the current closing bracket
            if (top_element != mappings[c]) {
                return false;
            }
        }
    }
    // If the stack is empty, all brackets matched
    return st.empty();
}

// Example Usage:
// int main() {
//     std::cout << "()[]{}: " << (isValid("()[]{}") ? "true" : "false") << std::endl; // true
//     std::cout << "([{}]): " << (isValid("([{}])") ? "true" : "false") << std::endl; // true
//     std::cout << "({[)]}: " << (isValid("({[)]") ? "true" : "false") << std::endl; // false
//     std::cout << "(: " << (isValid("(") ? "true" : "false") << std::endl;         // false
//     std::cout << "]: " << (isValid("]") ? "true" : "false") << std::endl;         // false
//     return 0;
// }
  

Time Complexity: $O(N)$ (single pass through the string)
Space Complexity: $O(N)$ (in the worst case, e.g., "((((()))))", the stack could store all `N/2` opening brackets)

🔗 3. Merge Two Sorted Lists (Linked Lists)

A fundamental linked list problem that tests pointer manipulation.

Problem Statement:

Merge two sorted linked lists `list1` and `list2` into a single sorted list. The new list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Example: `list1 = [1,2,4]`, `list2 = [1,3,4]`
Output: `[1,1,2,3,4,4]`

Approach: Iterative Merge

This is typically preferred over recursion for linked list problems in interviews to avoid potential stack overflow with very long lists.

1. Create a dummy node (e.g., with value 0) to simplify edge cases, particularly handling the head of the new list. Let `current` pointer point to this dummy node.
2. While both `list1` and `list2` are not null:
   • Compare the values of the nodes `list1` and `list2`.
   • Append the node with the smaller value to `current->next`.
   • Move the pointer of the list from which the node was taken (`list1` or `list2`) to its next node.
   • Move `current` pointer to `current->next` (the newly added node).
3. After one list becomes null, append the remaining (non-null) list to `current->next`.
4. Return `dummy->next` (the actual head of the merged list).

// C++ Solution for Merge Two Sorted Lists (Iterative)
#include <cstddef> // For NULL
#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    // Create a dummy node to simplify handling the head of the merged list
    ListNode dummy_head(0);
    ListNode* current = &dummy_head; // Pointer to the last node of the merged list

    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next; // Move current pointer forward
    }

    // Attach the remaining part of the non-null list
    if (list1 != nullptr) {
        current->next = list1;
    } else if (list2 != nullptr) {
        current->next = list2;
    }

    return dummy_head.next; // The head of the actual merged list
}

// Helper to print list (for testing)
// void printList(ListNode* head) {
//     while (head) {
//         std::cout << head->val << " -> ";
//         head = head->next;
//     }
//     std::cout << "NULL" << std::endl;
// }

// Example Usage:
// int main() {
//     ListNode* l1 = new ListNode(1, new ListNode(2, new ListNode(4))); // 1->2->4
//     ListNode* l2 = new ListNode(1, new ListNode(3, new ListNode(4))); // 1->3->4
//     ListNode* merged_head = mergeTwoLists(l1, l2);
//     printList(merged_head); // Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> NULL
//     // Don't forget to free memory in real applications!
//     return 0;
// }
  

Time Complexity: $O(M + N)$, where $M$ and $N$ are the lengths of `list1` and `list2`. We iterate through each node once.
Space Complexity: $O(1)$ (constant extra space, excluding the output list, as we are only manipulating pointers).

🧮 4. Product of Array Except Self (Arrays & Prefix/Suffix Products)

A challenging array problem that requires clever use of prefix/suffix products without division.

Problem Statement:

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`.
The problem guarantees that the product of elements of any prefix or suffix of `nums` is within a 32-bit integer. You must write an algorithm that runs in $O(N)$ time and **without using the division operator**.

Example: `nums = [1, 2, 3, 4]`
Output: `[24, 12, 8, 6]` (e.g., `answer[0]` is $2*3*4=24$)

Approach: Two-Pass Scan

The key insight is that `answer[i]` is `(product of elements to the left of i) * (product of elements to the right of i)`. We can calculate these two products in separate passes.

1. Initialize an `answer` array of the same size as `nums`, filled with 1s.
2. First Pass (Calculate Prefix Products):
   • Iterate from left to right. Keep a running `left_product`.
   • `answer[i]` will store the product of elements *to the left* of `nums[i]`.
   • `answer[0]` is 1 (nothing to its left).
   • For `i > 0`, `answer[i] = answer[i-1] * nums[i-1]`.
3. Second Pass (Calculate Suffix Products and Final Result):
   • Iterate from right to left. Keep a running `right_product`.
   • Initially, `right_product = 1` (nothing to its right).
   • For each `i` (from right to left):
     • Multiply `answer[i]` (which currently holds the prefix product) by `right_product`. This completes the calculation for `answer[i]`.
     • Update `right_product` by multiplying it with `nums[i]` for the next iteration.

// C++ Solution for Product of Array Except Self
#include <vector>
#include <iostream>
#include <numeric> // For std::accumulate (not used in final, but helpful for initial thoughts)

std::vector<int> productExceptSelf(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> answer(n);

    // First pass: Calculate prefix products
    // answer[i] will contain product of all elements to the left of i
    // answer[0] will be 1 (as there are no elements to the left of the first element)
    answer[0] = 1;
    for (int i = 1; i < n; ++i) {
        answer[i] = answer[i-1] * nums[i-1];
    }

    // Second pass: Calculate suffix products and combine with prefix products
    // right_product will store product of all elements to the right of current element
    int right_product = 1;
    for (int i = n - 1; i >= 0; --i) {
        answer[i] = answer[i] * right_product; // Combine prefix and suffix products
        right_product = right_product * nums[i]; // Update right_product for next iteration
    }

    return answer;
}

// Example Usage:
// int main() {
//     std::vector<int> nums = {1, 2, 3, 4};
//     std::vector<int> result = productExceptSelf(nums);
//     std::cout << "[";
//     for (int i = 0; i < result.size(); ++i) {
//         std::cout << result[i] << (i == result.size() - 1 ? "" : ", ");
//     }
//     std::cout << "]" << std::endl; // Output: [24, 12, 8, 6]
//     return 0;
// }
  

Time Complexity: $O(N)$ (two passes through the array)
Space Complexity: $O(1)$ (excluding the output array, which is required by the problem)

🔑 Key Takeaways for Interview Success

• 1. Understand & Clarify: Don't jump into coding. Ask clarifying questions about constraints, data types, edge cases (empty input, nulls, negative numbers, duplicates), and expected output format.
• 2. Brute Force First: Always start by explaining a naive (brute-force) solution. This shows you can solve the problem, even if inefficiently. It also provides a baseline for optimization.
• 3. Optimize Iteratively: Discuss how to improve the brute-force solution. Think about data structures (hash maps, stacks, queues, heaps) that can speed up lookups or manage state. Analyze time and space complexity at each step.
• 4. Communicate Your Thoughts: Explain your thought process out loud. Why are you choosing a particular approach? What are its trade-offs? Interviewers want to understand how you think.
• 5. Handle Edge Cases: Explicitly mention and test your code with edge cases. What if the input is empty? What if `target` in Two Sum is 0? What if lists are null in Merge Sorted Lists?
• 6. Write Clean Code: Use meaningful variable names. Structure your code logically. Keep functions concise.
• 7. Test Your Solution: Walk through your code with an example, simulating its execution step by step. This helps catch bugs and demonstrates confidence.

📌 Real-life Applications (UdaanPath Context)

These seemingly abstract problems have direct analogues in real-world systems:

• Two Sum:
  • E-commerce: Finding two products whose prices add up to a gift card value.
  • UdaanPath: Identifying two courses whose combined credits meet a certain degree requirement or finding two user activities that sum up to a specific engagement score for a gamification badge.
• Valid Parentheses:
  • Compilers/IDEs: Syntax validation for programming languages (ensuring brackets, braces, and parentheses are correctly nested).
  • UdaanPath: Validating complex user input for quizzes or code editors where specific delimiters or tags must be properly balanced.
• Merge Two Sorted Lists:
  • Database Merges: Combining sorted results from multiple database queries efficiently.
  • UdaanPath: Merging sorted lists of student progress records from different learning modules, or combining sorted log files based on timestamps.
• Product of Array Except Self:
  • Data Analytics: Calculating normalized scores or statistical measures where each data point needs to be contextualized by the aggregate of others.
  • UdaanPath: Imagine a recommendation engine where a student's affinity for a course is calculated based on its popularity relative to all other courses, but without counting the course itself (a form of weighted average where product might be involved).

✅ Summary: Your Interview Toolkit

• Interview problems assess not just your knowledge but your problem-solving process and communication.
• Always clarify requirements and constraints first.
• Start with a working (even if inefficient) solution, then optimize it.
• Leverage appropriate data structures (Hash Maps for $O(N)$ lookups, Stacks for LIFO operations).
• Pay close attention to edge cases and off-by-one errors.
• Practice thinking out loud and explaining your reasoning.

📤 Coming Next: Competitive Coding Patterns

We've tackled interview-style problems. Our next chapter will broaden our horizons to Competitive Coding Patterns. This will involve recognizing more specialized problem types and advanced techniques that are common in coding contests, helping you solve problems faster and more efficiently under pressure.