Coding interview questions & answers

Model answer

The flow

1. Clarify inputs & output shape: Understand the DataFrame structure and the requirements for cleaning.
2. Brute force first: Implement straightforward solutions for removing duplicates and handling missing values.
3. Optimize: Utilize pandas built-in functions to efficiently perform the operations.
4. State complexity: Consider the time complexity of operations, especially with large datasets.
5. Test the edges: Ensure the solution handles edge cases like all values missing or no duplicates.

The answer

1. Clarify inputs & output shape

• We have a DataFrame df with columns Date, Sales, and Customer_Rating.
• The task is to remove duplicate rows and fill missing values in Customer_Rating with the average rating.

2. Brute force first

• Start by identifying duplicate rows and removing them.
• Calculate the average of Customer_Rating and use it to fill missing values.

3. Optimize

• Use pandas functions like drop_duplicates() and fillna() to efficiently clean the DataFrame.

import pandas as pd

# Sample DataFrame
# df = pd.DataFrame({
#     'Date': [...],
#     'Sales': [...],
#     'Customer_Rating': [...]
# })

# Remove duplicate rows
cleaned_df = df.drop_duplicates()

# Calculate the mean of Customer_Rating, ignoring NaN values
average_rating = cleaned_df['Customer_Rating'].mean()

# Fill missing values in Customer_Rating with the average rating
cleaned_df['Customer_Rating'].fillna(average_rating, inplace=True)

• Approach:
• drop_duplicates() removes all duplicate rows based on all columns.
• mean() calculates the average of Customer_Rating, ignoring NaN values.
• fillna() replaces NaN values with the calculated average.
• Complexity: The time complexity is approximately $O(n)$ for both removing duplicates and filling NaN values, where $n$ is the number of rows in the DataFrame.

4. Test the edges

• Ensure the solution works when all Customer_Rating values are missing, or when there are no duplicates.

Why this works

• Testing understanding: The interviewer is assessing your ability to use pandas for data cleaning tasks.
• Efficiency: Using pandas built-in functions ensures operations are performed efficiently on potentially large datasets.
• Edge cases: A strong answer considers edge cases, such as all values missing or no duplicates, ensuring robustness.
• Weak answers: Failing to handle missing values correctly or not removing duplicates would indicate a lack of attention to detail or understanding of pandas capabilities.

Model answer

// Question 1: Near-palindrome with one deletion
function validPalindrome(s) {
    function isPalindrome(l, r) {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    }

    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) {
            // Try removing one character from either end
            return isPalindrome(left + 1, right) || isPalindrome(left, right - 1);
        }
        left++;
        right--;
    }
    return true;
}

// Approach for Question 1:
// - Use two pointers to check if the string is a palindrome.
// - If a mismatch is found, check if removing one of the mismatched characters results in a palindrome.
// - This is done by checking two substrings: one excluding the left character and one excluding the right character.

// Complexity for Question 1:
// Time: O(n), where n is the length of the string, as we may need to check the entire string.
// Space: O(1), as we use a constant amount of extra space.


// Question 2: Binary tree vertical order traversal
function verticalOrder(root) {
    if (!root) return [];

    const columnTable = new Map();
    const queue = [{ node: root, col: 0 }];
    let minCol = 0, maxCol = 0;

    while (queue.length > 0) {
        const { node, col } = queue.shift();

        if (!columnTable.has(col)) {
            columnTable.set(col, []);
        }
        columnTable.get(col).push(node.val);

        if (node.left) {
            queue.push({ node: node.left, col: col - 1 });
            minCol = Math.min(minCol, col - 1);
        }
        if (node.right) {
            queue.push({ node: node.right, col: col + 1 });
            maxCol = Math.max(maxCol, col + 1);
        }
    }

    const result = [];
    for (let i = minCol; i <= maxCol; i++) {
        result.push(columnTable.get(i));
    }
    return result;
}

// Approach for Question 2:
// - Use a BFS approach to traverse the tree while keeping track of the column index for each node.
// - Store nodes in a map where keys are column indices and values are lists of node values.
// - Track the minimum and maximum column indices to determine the range of columns to output.
// - Collect results from the map in order from the smallest to the largest column index.

// Complexity for Question 2:
// Time: O(n), where n is the number of nodes in the tree, as each node is processed once.
// Space: O(n), for the map and queue used to store nodes and their column indices.

Model answer

// Problem 1: Deep copy a linked list with extra pointers

function copyRandomList(head) {
    if (!head) return null;

    // Step 1: Create new nodes and interleave them with the original nodes
    let current = head;
    while (current) {
        const newNode = new Node(current.val);
        newNode.next = current.next;
        current.next = newNode;
        current = newNode.next;
    }

    // Step 2: Assign random pointers for the new nodes
    current = head;
    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }

    // Step 3: Separate the new list from the original list
    current = head;
    const newHead = head.next;
    while (current) {
        const newNode = current.next;
        current.next = newNode.next;
        if (newNode.next) {
            newNode.next = newNode.next.next;
        }
        current = current.next;
    }

    return newHead;
}

// Problem 2: Find the k most frequent integers in an array

function topKFrequent(nums, k) {
    const frequencyMap = new Map();

    // Count the frequency of each number
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    // Create an array of buckets to store numbers by frequency
    const buckets = Array(nums.length + 1).fill().map(() => []);
    for (const [num, freq] of frequencyMap.entries()) {
        buckets[freq].push(num);
    }

    // Gather the top k frequent elements
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i].length > 0) {
            result.push(...buckets[i]);
        }
    }

    return result.slice(0, k);
}

• Approach for Problem 1:
• Interleave Nodes: Create new nodes and interleave them with the original nodes.
• Assign Random Pointers: Set the random pointers for the new nodes using the interleaved structure.
• Separate Lists: Detach the new list from the original list to form the deep copy.
• Approach for Problem 2:
• Frequency Map: Use a hash map to count the frequency of each element.
• Bucket Sort: Use an array of buckets where the index represents frequency.
• Collect Top k: Collect elements from the highest frequency bucket downwards until k elements are gathered.

Complexity:

• Time Complexity: Both solutions run in O(n) time, where n is the number of nodes or elements.
• Space Complexity: O(n) additional space is used for both solutions, primarily for the new nodes and frequency map.

Model answer

import numpy as np

def precision_recall_curve(y_true, y_score):
    # Sort scores and corresponding true labels in descending order
    desc_score_indices = np.argsort(y_score)[::-1]
    y_true = np.array(y_true)[desc_score_indices]
    y_score = np.array(y_score)[desc_score_indices]

    # Initialize variables
    thresholds = []
    precision = []
    recall = []
    tp = 0  # True positives
    fp = 0  # False positives
    fn = np.sum(y_true)  # False negatives initially all positives

    # Iterate through scores to calculate precision and recall
    for i in range(len(y_score)):
        if i == 0 or y_score[i] != y_score[i - 1]:
            thresholds.append(y_score[i])
            precision.append(tp / (tp + fp) if (tp + fp) > 0 else 1.0)
            recall.append(tp / (tp + fn) if (tp + fn) > 0 else 0.0)

        if y_true[i] == 1:
            tp += 1
            fn -= 1
        else:
            fp += 1

    # Add the last point at threshold 0
    thresholds.append(0)
    precision.append(tp / (tp + fp) if (tp + fp) > 0 else 1.0)
    recall.append(tp / (tp + fn) if (tp + fn) > 0 else 0.0)

    return thresholds, precision, recall

# Example usage
y_true = [0, 1, 1, 0, 1]
y_score = [0.1, 0.4, 0.35, 0.8, 0.7]
thresholds, precision, recall = precision_recall_curve(y_true, y_score)
print("Thresholds:", thresholds)
print("Precision:", precision)
print("Recall:", recall)

• Precision is the ratio of true positives to the sum of true positives and false positives. It measures the accuracy of positive predictions.
• Recall is the ratio of true positives to the sum of true positives and false negatives. It measures the ability to find all positive samples.
• To compute the precision-recall curve, sort y_score in descending order and iterate over it. For each unique score, calculate precision and recall, updating true positives, false positives, and false negatives accordingly.

Complexity:

• Time: O(n log n) due to sorting, where n is the number of samples.
• Space: O(n) for storing sorted indices and result arrays.

Edge Cases/Pitfalls:

1. Ties in scores: Ensure that precision and recall are calculated correctly when multiple instances have the same score.
2. No predicted positives: Handle cases where no samples are predicted as positive at a certain threshold, which can lead to division by zero in precision calculation.

Average Precision / AUPRC:

• Average Precision (AP) is the area under the precision-recall curve. It summarizes the precision-recall trade-off across thresholds. The baseline for AP is the proportion of positive samples in the dataset.

Model answer

// Function to compute the probability that a match goes to 5 games
function probabilityOfFiveGames(p) {
  // Probability that the match goes to 5 games
  // This happens if both players win 2 games each in the first 4 games
  const prob = 6 * Math.pow(p, 2) * Math.pow(1 - p, 2);
  return prob;
}

// Monte Carlo simulation to estimate the probability of a match going to 5 games
function simulateMatches(numMatches, p) {
  let fiveGameMatches = 0;

  for (let i = 0; i < numMatches; i++) {
    let winsA = 0;
    let winsB = 0;
    let gamesPlayed = 0;

    while (winsA < 3 && winsB < 3) {
      gamesPlayed++;
      if (Math.random() < p) {
        winsA++;
      } else {
        winsB++;
      }
    }

    if (gamesPlayed === 5) {
      fiveGameMatches++;
    }
  }

  return fiveGameMatches / numMatches;
}

// Function to build a confidence interval for the estimated probability
function confidenceInterval(numMatches, p, confidenceLevel = 0.95) {
  const thetaEstimate = simulateMatches(numMatches, p);
  const z = 1.96; // z-score for 95% confidence
  const marginOfError = z * Math.sqrt((thetaEstimate * (1 - thetaEstimate)) / numMatches);

  return [thetaEstimate - marginOfError, thetaEstimate + marginOfError];
}

// Example usage
const p = 0.5; // Probability that player A wins a game
const numMatches = 10000; // Number of simulated matches
console.log("Probability of 5 games (analytical):", probabilityOfFiveGames(p));
console.log("Probability of 5 games (simulation):", simulateMatches(numMatches, p));
console.log("95% Confidence Interval:", confidenceInterval(numMatches, p));

• Analytical Calculation: The probability that a match goes to 5 games is calculated by considering the scenarios where both players win exactly 2 games each in the first 4 games. This is given by \(6 \times p^2 \times (1-p)^2\), where 6 is the number of ways to arrange 2 wins for each player in 4 games.
• Monte Carlo Simulation: Simulate a large number of matches, counting how many go to 5 games. For each match, simulate games until one player wins 3 games. Count matches where exactly 5 games are played.
• Confidence Interval: Use the normal approximation for the binomial distribution to calculate the confidence interval for the estimated probability. The margin of error is calculated using the standard error and the z-score for the desired confidence level.

Complexity:

• Time: \(O(M)\) for the simulation, where \(M\) is the number of matches.
• Space: \(O(1)\), constant space usage.

Model answer

The flow

1. Clarify inputs & output shape: Define the format of the raw text data and the expected output.
2. Brute force first: Write a simple script to read and process the text data.
3. Optimize: Improve the script for efficiency and scalability.
4. State complexity: Analyze the time and space complexity of the script.
5. Test the edges: Ensure the script handles edge cases and unexpected inputs.

The answer

Clarify inputs & output shape

• The raw text data is a collection of text files, each containing multiple lines of text.
• The goal is to analyze the frequency of words and output a summary report in CSV format.

Brute force first

• Start by writing a Python script that opens each text file and reads its contents.
• Use a dictionary to count the occurrences of each word across all files.

import os
import csv
from collections import defaultdict

# Directory containing text files
directory = 'text_data/'

# Dictionary to store word frequencies
word_count = defaultdict(int)

# Read and process each file
for filename in os.listdir(directory):
    if filename.endswith('.txt'):
        with open(os.path.join(directory, filename), 'r') as file:
            for line in file:
                # Tokenize the line into words
                words = line.strip().split()
                for word in words:
                    # Convert to lowercase and count
                    word_count[word.lower()] += 1

# Write the word frequencies to a CSV file
with open('word_frequencies.csv', 'w', newline='') as csvfile:
    writer = csv.writer(csvfile)
    writer.writerow(['Word', 'Frequency'])
    for word, count in word_count.items():
        writer.writerow([word, count])

Optimize

• Use more efficient data structures or libraries such as collections.Counter for counting.
• Implement parallel processing if dealing with a large number of files.

State complexity

• Time complexity: $O(n)$, where $n$ is the total number of words across all files.
• Space complexity: $O(m)$, where $m$ is the number of unique words.

Test the edges

• Test with files containing special characters, numbers, or empty lines.
• Ensure the script handles cases where the directory is empty or files are missing.

Why this works

• Interviewer is testing: Ability to process text data, write efficient code, and handle edge cases.
• Sanity check: Ensures that the candidate can handle common issues in text processing, such as case sensitivity and special characters.
• Weak answers fail: If a candidate doesn't optimize for large datasets or fails to handle edge cases, the solution won't scale or be robust.

Model answer

function blockPlacementSimulator(n, m, pieces, pieceShapes) {
    // Initialize an empty grid
    const grid = Array.from({ length: n }, () => Array(m).fill(false));

    // Helper function to check if a piece can be placed at a given position
    function canPlacePiece(pieceShape, startRow, startCol) {
        for (const [dr, dc] of pieceShape) {
            const newRow = startRow + dr;
            const newCol = startCol + dc;
            if (
                newRow < 0 || newRow >= n || 
                newCol < 0 || newCol >= m || 
                grid[newRow][newCol]
            ) {
                return false;
            }
        }
        return true;
    }

    // Helper function to place a piece on the grid
    function placePiece(pieceShape, startRow, startCol) {
        for (const [dr, dc] of pieceShape) {
            grid[startRow + dr][startCol + dc] = true;
        }
    }

    // Process each piece
    for (const pieceType of pieces) {
        const pieceShape = pieceShapes[pieceType];
        let placed = false;

        // Scan the grid to find the first valid position
        for (let row = 0; row < n && !placed; row++) {
            for (let col = 0; col < m && !placed; col++) {
                if (canPlacePiece(pieceShape, row, col)) {
                    placePiece(pieceShape, row, col);
                    placed = true;
                }
            }
        }

        // If a piece cannot be placed, stop processing
        if (!placed) {
            break;
        }
    }

    return grid;
}

// Example usage
const n = 5, m = 5;
const pieces = ['A', 'B', 'C'];
const pieceShapes = {
    'A': [[0, 0], [0, 1]], // Example shape for piece A
    'B': [[0, 0], [1, 0]], // Example shape for piece B
    'C': [[0, 0], [0, 1], [1, 0]], // Example shape for piece C
    // Define other shapes as needed
};

console.log(blockPlacementSimulator(n, m, pieces, pieceShapes));

• Approach:
• Initialize an n x m grid with all cells set to false (unoccupied).
• For each piece in the sequence, attempt to place it by scanning the grid from top-left to bottom-right.
• Use helper functions to check if a piece can be placed and to place the piece if possible.
• Stop processing if a piece cannot be placed due to lack of space.
• Complexity:
• Time: O(p n m * s), where p is the number of pieces, n and m are grid dimensions, and s is the maximum size of a piece.
• Space: O(n * m) for the grid.

Model answer

import threading
import queue
import time

class PriorityThreadPoolExecutor:
    def __init__(self, max_workers):
        self.task_queue = queue.PriorityQueue()
        self.threads = []
        self.shutdown_flag = threading.Event()
        
        for _ in range(max_workers):
            thread = threading.Thread(target=self._worker)
            thread.start()
            self.threads.append(thread)

    def submit(self, fn, priority=0):
        # Use a tuple (priority, count, fn) to ensure tasks with the same priority maintain order
        count = time.time()  # Use timestamp to maintain order for tasks with the same priority
        self.task_queue.put((priority, count, fn))

    def _worker(self):
        while not self.shutdown_flag.is_set():
            try:
                priority, count, fn = self.task_queue.get(timeout=1)
                try:
                    fn()
                except Exception as e:
                    print(f"Exception in task: {e}")
                finally:
                    self.task_queue.task_done()
            except queue.Empty:
                continue

    def shutdown(self, wait=True):
        self.shutdown_flag.set()
        if wait:
            for thread in self.threads:
                thread.join()

# Example usage
def example_task():
    print("Task executed")

executor = PriorityThreadPoolExecutor(max_workers=3)
executor.submit(example_task, priority=1)
executor.submit(example_task, priority=0)
executor.shutdown()

• Approach:
• Use a PriorityQueue to manage tasks, ensuring lower numeric priorities are processed first.
• Each task is stored as a tuple (priority, count, fn) where count is a timestamp to maintain order for tasks with the same priority.
• Worker threads continuously fetch tasks from the queue and execute them.
• Implement a shutdown mechanism using a threading event to safely stop worker threads.
• Debugging and Safety:
• Shutdown: Use a threading event to signal shutdown, ensuring threads can exit gracefully.
• Exceptions: Wrap task execution in a try-except block to handle exceptions without crashing the worker.
• Concurrent Submissions: The PriorityQueue is thread-safe, handling concurrent submissions without additional locking.

Complexity:

• Time: O(1) for submitting tasks; O(log n) for retrieving tasks from the queue.
• Space: O(n) for storing tasks in the queue, where n is the number of tasks.

Model answer

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity; // Maximum capacity of the cache
    this.cache = new Map(); // Map to store key-value pairs
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1; // Return -1 if the key is not found
    }
    const value = this.cache.get(key);
    // Move the accessed key to the end to mark it as recently used
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      // If key exists, delete it to update its position
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // If cache is full, remove the least recently used (first) key
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    // Insert the key-value pair as the most recently used
    this.cache.set(key, value);
  }
}

// Approach:
// - Use a Map to store key-value pairs, as it maintains insertion order.
// - On `get`, check if the key exists. If yes, move it to the end of the Map.
// - On `put`, if the key exists, update its position. If the cache is full, remove the least recently used key.
// - This ensures both operations run in O(1) amortized time due to the properties of Map.

// Complexity:
// - Time: O(1) for both `get` and `put` operations.
// - Space: O(capacity) for storing the key-value pairs.

Problem 2: Assign Secret Gift Givers (Secret Santa)

function assignSecretSanta(participants) {
  const n = participants.length;
  const shuffled = [...participants];

  // Shuffle the array to randomize assignments
  for (let i = n - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }

  // Ensure no one is assigned to themselves
  for (let i = 0; i < n; i++) {
    if (shuffled[i] === participants[i]) {
      // Swap with the next person, or the first if it's the last person
      const swapIndex = i === n - 1 ? 0 : i + 1;
      [shuffled[i], shuffled[swapIndex]] = [shuffled[swapIndex], shuffled[i]];
    }
  }

  // Create the assignments
  const assignments = participants.map((person, index) => ({
    giver: person,
    receiver: shuffled[index],
  }));

  return assignments;
}

// Approach:
// - Shuffle the list of participants to randomize the order.
// - Ensure no participant is assigned to themselves by checking and swapping if necessary.
// - Return a list of assignments where each participant is paired with a different one.

// Complexity:
// - Time: O(n), where n is the number of participants, due to the shuffle and swap operations.
// - Space: O(n) for storing the shuffled list and assignments.

Model answer

// 1) Merge two sorted lists
function mergeSortedArrays(A, B) {
    let i = 0, j = 0;
    const merged = [];

    // Compare elements from both arrays and add the smaller one to the merged array
    while (i < A.length && j < B.length) {
        if (A[i] < B[j]) {
            merged.push(A[i]);
            i++;
        } else {
            merged.push(B[j]);
            j++;
        }
    }

    // Add remaining elements from A, if any
    while (i < A.length) {
        merged.push(A[i]);
        i++;
    }

    // Add remaining elements from B, if any
    while (j < B.length) {
        merged.push(B[j]);
        j++;
    }

    return merged;
}

// 2) Max profit from one stock transaction
function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let price of prices) {
        // Update minPrice to the lowest price seen so far
        if (price < minPrice) {
            minPrice = price;
        }
        // Calculate profit if selling at the current price
        const profit = price - minPrice;
        // Update maxProfit if the current profit is greater
        if (profit > maxProfit) {
            maxProfit = profit;
        }
    }

    return maxProfit;
}

// 3) Validate parentheses pairing
function isValidParentheses(s) {
    const stack = [];
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (let char of s) {
        if (char in map) {
            // Check if the stack's top matches the current closing bracket
            if (stack.length > 0 && stack[stack.length - 1] === map[char]) {
                stack.pop();
            } else {
                return false;
            }
        } else {
            // Push opening brackets onto the stack
            stack.push(char);
        }
    }

    // If stack is empty, all brackets were matched
    return stack.length === 0;
}

• Merge two sorted lists: Use two pointers to traverse both arrays, adding the smaller element to the result array. Continue until all elements from both arrays are added.
• Max profit from one stock transaction: Track the minimum price seen so far and calculate potential profit at each price. Update the maximum profit accordingly.
• Validate parentheses pairing: Use a stack to track opening brackets. For each closing bracket, check if it matches the top of the stack. If not, the string is invalid. Ensure the stack is empty at the end.

Complexity:

• Merge two sorted lists: Time O(n + m), Space O(n + m), where n and m are the lengths of A and B.
• Max profit from one stock transaction: Time O(n), Space O(1), where n is the number of prices.
• Validate parentheses pairing: Time O(n), Space O(n), where n is the length of the string.

Model answer

class Book {
  constructor(title, author, isbn) {
    this.title = title;
    this.author = author;
    this.isbn = isbn;
    this.isAvailable = true; // Indicates if the book is available for checkout
  }
}

class Member {
  constructor(name, memberId) {
    this.name = name;
    this.memberId = memberId;
    this.checkedOutBooks = []; // List of books checked out by the member
  }

  // Method to check out a book
  checkoutBook(book) {
    if (book.isAvailable) {
      book.isAvailable = false;
      this.checkedOutBooks.push(book);
      console.log(`${this.name} checked out "${book.title}"`);
    } else {
      console.log(`Sorry, "${book.title}" is currently unavailable.`);
    }
  }
}

class Library {
  constructor() {
    this.books = []; // Collection of books in the library
    this.members = []; // Collection of library members
  }

  // Method to add a new book to the library
  addBook(title, author, isbn) {
    const newBook = new Book(title, author, isbn);
    this.books.push(newBook);
    console.log(`Book "${title}" added to the library.`);
  }

  // Method to add a new member to the library
  addMember(name, memberId) {
    const newMember = new Member(name, memberId);
    this.members.push(newMember);
    console.log(`Member "${name}" added to the library.`);
  }

  // Method to find a book by ISBN
  findBook(isbn) {
    return this.books.find(book => book.isbn === isbn);
  }

  // Method to find a member by ID
  findMember(memberId) {
    return this.members.find(member => member.memberId === memberId);
  }

  // Method to check out a book to a member
  checkoutBookToMember(isbn, memberId) {
    const book = this.findBook(isbn);
    const member = this.findMember(memberId);
    if (book && member) {
      member.checkoutBook(book);
    } else {
      console.log('Book or Member not found.');
    }
  }
}

// Example usage:
const library = new Library();
library.addBook('The Great Gatsby', 'F. Scott Fitzgerald', '123456789');
library.addMember('Alice', 'M001');
library.checkoutBookToMember('123456789', 'M001');

• Approach:
• Classes: Define Book, Member, and Library classes to encapsulate related data and behavior.
• Book Management: Use a Book class with properties like title, author, isbn, and isAvailable.
• Member Management: Use a Member class to manage member details and their checked-out books.
• Library Operations: Implement addBook, addMember, and checkoutBookToMember methods in the Library class.
• Complexity:
• Time: Adding books and members is O(1). Checking out a book involves finding a book and a member, each O(n) in the worst case.
• Space: O(n) for storing books and members, where n is the number of books/members.

Model answer

# Given data:
# Bag A: 4 red, 6 green
# Bag B: 6 red, 4 green
# Bag C: 3 red, 7 green

# Step 1: Calculate the probability of drawing a red ball from each bag.
p_red_given_A = 4 / (4 + 6)  # Probability of red from Bag A
p_red_given_B = 6 / (6 + 4)  # Probability of red from Bag B
p_red_given_C = 3 / (3 + 7)  # Probability of red from Bag C

# Step 2: Calculate the total probability of drawing a red ball (P(red)).
p_red = (1/3) * p_red_given_A + (1/3) * p_red_given_B + (1/3) * p_red_given_C

# Step 3: Calculate P(B | red) using Bayes' Theorem.
# P(B | red) = (P(red | B) * P(B)) / P(red)
p_B_given_red = p_red_given_B * (1/3) / p_red

# Follow-up: If the bags are chosen with different probabilities:
p_A = 0.2
p_B = 0.5
p_C = 0.3

# Recalculate P(red) with new probabilities.
p_red_new = p_A * p_red_given_A + p_B * p_red_given_B + p_C * p_red_given_C

# Recalculate P(B | red) with new prior probabilities.
p_B_given_red_new = p_red_given_B * p_B / p_red_new

# Output results
p_B_given_red, p_B_given_red_new

• Approach:
• Use Bayes' Theorem to compute the posterior probability \( P(B | \text{red}) \).
• Calculate the probability of drawing a red ball from each bag.
• Compute the total probability of drawing a red ball.
• Adjust the calculation for different prior probabilities of selecting each bag.
• Complexity:
• Time: \( O(1) \), as the calculations involve a constant number of operations.
• Space: \( O(1) \), as no additional data structures are used.

Explanation:

• Initial Calculation:
• Each bag is equally likely to be chosen, so the prior probability for each is \( \frac{1}{3} \).
• Compute the probability of drawing a red ball from each bag.
• Use these probabilities to find the total probability of drawing a red ball.
• Apply Bayes' Theorem to find \( P(B | \text{red}) \).
• Follow-up:
• Change the prior probabilities to \( P(A) = 0.2 \), \( P(B) = 0.5 \), \( P(C) = 0.3 \).
• Recalculate the total probability of drawing a red ball with these new priors.
• Use Bayes' Theorem again to find the updated \( P(B | \text{red}) \).
• Intuition:
• The prior probabilities affect the posterior probability significantly. A higher prior probability for Bag B increases \( P(B | \text{red}) \), reflecting greater initial confidence in choosing Bag B.

Model answer

const fs = require('fs');
const crypto = require('crypto');

class URLShortener {
  constructor(filePath = 'url_mappings.json') {
    this.filePath = filePath;
    this.urlMap = new Map();
    this.loadMappings();
  }

  // Validate URL
  isValidURL(url) {
    try {
      new URL(url);
      return true;
    } catch (_) {
      return false;
    }
  }

  // Shorten a long URL
  shorten(longUrl) {
    if (!this.isValidURL(longUrl)) {
      throw new Error('Invalid URL');
    }

    // Check if URL is already shortened
    for (let [shortCode, originalUrl] of this.urlMap.entries()) {
      if (originalUrl === longUrl) {
        return shortCode;
      }
    }

    // Generate a unique short code
    let shortCode;
    do {
      shortCode = crypto.randomBytes(4).toString('hex');
    } while (this.urlMap.has(shortCode));

    // Store the mapping
    this.urlMap.set(shortCode, longUrl);
    this.saveMappings();

    return shortCode;
  }

  // Resolve a short code to the original URL
  resolve(shortCode) {
    return this.urlMap.get(shortCode) || null;
  }

  // Save mappings to a JSON file
  saveMappings() {
    const data = JSON.stringify(Object.fromEntries(this.urlMap));
    fs.writeFileSync(this.filePath, data);
  }

  // Load mappings from a JSON file
  loadMappings() {
    if (fs.existsSync(this.filePath)) {
      const data = fs.readFileSync(this.filePath);
      const entries = JSON.parse(data);
      this.urlMap = new Map(Object.entries(entries));
    }
  }
}

// Example usage
const shortener = new URLShortener();
const shortCode = shortener.shorten('https://www.example.com');
console.log(shortCode);
console.log(shortener.resolve(shortCode));

• Approach:
• Validate URLs using the URL constructor to ensure they are well-formed.
• Use a Map to store mappings between short codes and original URLs, ensuring O(1) access time.
• Generate short codes using crypto.randomBytes to ensure uniqueness and handle collisions.
• Persist mappings to a JSON file for durability across program restarts.
• Reload mappings from the JSON file on startup to maintain state.
• Complexity:
• Time: O(1) for both shorten and resolve operations due to hash map usage.
• Space: O(n) where n is the number of unique URLs stored, as each URL and its mapping are stored in memory.

Model answer

import numpy as np

def kmeans(X, k, max_iters=100, tol=1e-4):
    # Step 1: Initialize k centroids randomly from the dataset
    n_samples, n_features = X.shape
    centroids = X[np.random.choice(n_samples, k, replace=False)]

    for _ in range(max_iters):
        # Step 2: Assign each point to the nearest centroid
        distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
        labels = np.argmin(distances, axis=1)

        # Step 3: Recompute centroids as the mean of assigned points
        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])

        # Check for convergence (if centroids do not change significantly)
        if np.all(np.linalg.norm(new_centroids - centroids, axis=1) < tol):
            break

        centroids = new_centroids

    return centroids, labels

def kmeans_plus_plus(X, k):
    n_samples, n_features = X.shape
    centroids = np.empty((k, n_features))
    
    # Initialize the first centroid randomly
    centroids[0] = X[np.random.choice(n_samples)]
    
    # Initialize the remaining centroids
    for i in range(1, k):
        distances = np.min(np.linalg.norm(X[:, np.newaxis] - centroids[:i], axis=2), axis=1)
        probabilities = distances / np.sum(distances)
        centroids[i] = X[np.random.choice(n_samples, p=probabilities)]

    return centroids

# Example usage
X = np.random.rand(100, 2)  # Example dataset
k = 3
initial_centroids = kmeans_plus_plus(X, k)
final_centroids, assignments = kmeans(X, k)

• K-means Objective: K-means aims to minimize the variance within each cluster, effectively minimizing the sum of squared distances between data points and their respective cluster centroids.
• Lloyd’s Algorithm: 1. Initialize k centroids randomly. 2. Assign each data point to the nearest centroid. 3. Update centroids by calculating the mean of all points assigned to each centroid. 4. Repeat steps 2 and 3 until convergence or a maximum number of iterations is reached.
• Improved Initialization (K-means++):
• Select the first centroid randomly.
• For each subsequent centroid, choose a data point with a probability proportional to its distance squared from the nearest existing centroid.
• This helps in spreading out the initial centroids, leading to faster convergence and better clustering results.
• Handling Empty Clusters: If a cluster becomes empty, reinitialize its centroid to a random data point.
• Stopping Criteria: Convergence is typically determined by checking if the centroids do not change significantly between iterations.

Complexity:

• Time: O(n k t * d), where n is the number of points, k is the number of clusters, t is the number of iterations, and d is the dimensionality.
• Space: O(n d) for storing the dataset and O(k d) for the centroids.

Model answer

// Problem 1: Zigzag level-order traversal of a binary tree
function zigzagLevelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
        leftToRight = !leftToRight;
    }
    
    return result;
}

// Problem 2: Longest palindromic subsequence length
function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}

// Problem 3: Integer square root (floor)
function mySqrt(x) {
    if (x < 2) return x;
    
    let left = 1, right = Math.floor(x / 2);
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midSquared = mid * mid;
        
        if (midSquared === x) return mid;
        if (midSquared < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
}

// Problem 4: Spreadsheet column label to number
function titleToNumber(col) {
    let result = 0;
    
    for (let i = 0; i < col.length; i++) {
        result = result * 26 + (col.charCodeAt(i) - 'A'.charCodeAt(0) + 1);
    }
    
    return result;
}

• Problem 1: Use a queue for level-order traversal, alternating between pushing and unshifting node values based on the current direction.
• Problem 2: Use dynamic programming to build a table dp[i][j] representing the longest palindromic subsequence between indices i and j.
• Problem 3: Use binary search to find the integer square root by narrowing down the range based on the midpoint square.
• Problem 4: Convert the column label to a number by iterating through the string and using a base-26 calculation.

Complexity:

• Problem 1: Time/Space: O(n), where n is the number of nodes.
• Problem 2: Time/Space: O(n^2), where n is the length of the string.
• Problem 3: Time: O(log x), Space: O(1).
• Problem 4: Time: O(m), Space: O(1), where m is the length of the column string.

Model answer

class NestedIterator {
    constructor(nestedList) {
        this.nestedList = nestedList;
        this.outerIndex = 0;
        this.innerIndex = 0;
        this.lastReturned = null;
        this.advanceToNext();
    }

    // Advance to the next available integer
    advanceToNext() {
        while (this.outerIndex < this.nestedList.length) {
            if (this.innerIndex < this.nestedList[this.outerIndex].length) {
                return;
            }
            this.outerIndex++;
            this.innerIndex = 0;
        }
    }

    hasNext() {
        return this.outerIndex < this.nestedList.length;
    }

    next() {
        if (!this.hasNext()) {
            throw new Error("No more elements");
        }
        this.lastReturned = [this.outerIndex, this.innerIndex];
        const result = this.nestedList[this.outerIndex][this.innerIndex];
        this.innerIndex++;
        this.advanceToNext();
        return result;
    }

    remove() {
        if (this.lastReturned === null) {
            throw new Error("Illegal state");
        }
        const [outer, inner] = this.lastReturned;
        this.nestedList[outer].splice(inner, 1);
        if (inner < this.innerIndex) {
            this.innerIndex--;
        }
        this.lastReturned = null;
    }
}

// Example usage:
const data = [[], [1, 2, 3], [4, 5], [], [6]];
const it = new NestedIterator(data);
console.log(it.hasNext()); // true
console.log(it.next());    // 1
console.log(it.next());    // 2
it.remove();
console.log(data);         // [[], [1, 3], [4, 5], [], [6]]
console.log(it.next());    // 3

• Approach:
• Maintain indices outerIndex and innerIndex to track the current position in the nested list.
• Use advanceToNext() to skip empty inner arrays and position the iterator at the next available integer.
• hasNext() checks if there are more integers to iterate over.
• next() returns the current integer and advances the iterator.
• remove() deletes the last returned integer and adjusts indices accordingly.

Complexity:

• Time: O(1) for hasNext(), next(), and remove() in typical cases, though advanceToNext() may take O(n) in the worst case when skipping empty arrays.
• Space: O(1), as we use a fixed amount of extra space.

Model answer

// Problem 1: Count unique Morse code translations

function uniqueMorseRepresentations(words) {
    const morseCodeMap = [
        ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
        "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."
    ];
    
    const seen = new Set();
    
    for (let word of words) {
        let morseTranslation = '';
        for (let char of word) {
            morseTranslation += morseCodeMap[char.charCodeAt(0) - 'a'.charCodeAt(0)];
        }
        seen.add(morseTranslation);
    }
    
    return seen.size;
}

// Problem 2: Return all valid word-break sentences

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();
    
    function backtrack(start) {
        if (memo.has(start)) return memo.get(start);
        if (start === s.length) return [''];
        
        const sentences = [];
        
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.substring(start, end);
            if (wordSet.has(word)) {
                const restOfSentences = backtrack(end);
                for (let sentence of restOfSentences) {
                    sentences.push(word + (sentence ? ' ' + sentence : ''));
                }
            }
        }
        
        memo.set(start, sentences);
        return sentences;
    }
    
    return backtrack(0);
}

// Approach for Problem 1:
// - Create a map of Morse code for each letter.
// - Use a set to store unique Morse translations of words.
// - For each word, translate it to Morse code and add to the set.
// - Return the size of the set as the count of unique translations.

// Approach for Problem 2:
// - Use a backtracking approach with memoization to explore all possible sentences.
// - For each starting index, check all substrings if they are in the word dictionary.
// - Recursively find valid sentences for the remaining string.
// - Memoize results to avoid redundant calculations.

// Complexity:
// - Problem 1: Time O(n * m), Space O(n), where n is the number of words and m is the average length of a word.
// - Problem 2: Time O(n^3), Space O(n^3), where n is the length of the string `s`.

Model answer

// Function to reverse-print a binary tree level by level from bottom to top
function reverseLevelOrder(root) {
    if (!root) return [];

    const queue = [root];
    const result = [];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        // Insert the current level at the beginning of the result array
        result.unshift(currentLevel);
    }

    return result;
}

// Function to find the length of the longest palindromic subsequence
function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    // Each character is a palindrome of length 1
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Build the dp table
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

• Reverse Level Order Traversal:
• Use a queue to perform a level-order traversal (BFS).
• For each level, store node values in a temporary list.
• Insert each level's list at the start of the result list to reverse the order.
• Longest Palindromic Subsequence:
• Use dynamic programming to build a table dp where dp[i][j] represents the length of the longest palindromic subsequence in s[i...j].
• Initialize dp[i][i] to 1 for all i since each character is a palindrome.
• Fill the table by checking if characters at i and j are equal, and use previously computed values to find the longest subsequence.

Complexity:

• Reverse Level Order Traversal: Time: O(n), Space: O(n), where n is the number of nodes.
• Longest Palindromic Subsequence: Time: O(n^2), Space: O(n^2), where n is the length of the string.

Model answer

The flow

1. Clarify inputs & output shape: Identify the data types and structures needed for the project.
2. Brute force first: Implement a basic solution using Python lists and dictionaries.
3. Optimize: Improve the efficiency of data manipulation and retrieval.
4. State complexity: Analyze the time and space complexity of the solution.
5. Test the edges: Ensure the solution handles edge cases and large datasets effectively.

The answer

1. Clarify inputs & output shape

• For a data science project, you often deal with datasets that can be represented as lists of dictionaries, where each dictionary represents a data record with key-value pairs.
• Example: A dataset of employees where each employee has attributes like name, age, and department.

2. Brute force first

• Start by using lists to store multiple records and dictionaries to store attributes of each record.

# Example dataset of employees
employees = [
    {"name": "Alice", "age": 30, "department": "HR"},
    {"name": "Bob", "age": 25, "department": "Engineering"},
    {"name": "Charlie", "age": 35, "department": "Marketing"}
]

# Function to find employees in a specific department
def find_employees_by_department(employees, department):
    return [emp for emp in employees if emp["department"] == department]

# Example usage
hr_employees = find_employees_by_department(employees, "HR")
print(hr_employees)

• Approach: Use a list comprehension to filter employees by department.

3. Optimize

• If frequent lookups by department are needed, consider restructuring the data for faster access.

# Optimized data structure using a dictionary
employees_by_department = {
    "HR": [{"name": "Alice", "age": 30}],
    "Engineering": [{"name": "Bob", "age": 25}],
    "Marketing": [{"name": "Charlie", "age": 35}]
}

# Function to get employees by department
def get_employees_by_department(department):
    return employees_by_department.get(department, [])

# Example usage
hr_employees = get_employees_by_department("HR")
print(hr_employees)

• Approach: Use a dictionary to map departments to lists of employees, improving lookup time.

4. State complexity

• Time Complexity: Initial brute force approach has $O(n)$ time complexity for lookups, where $n$ is the number of employees. Optimized approach reduces lookup time to $O(1)$.
• Space Complexity: Both approaches use $O(n)$ space, but the optimized approach may require additional space for the dictionary.

5. Test the edges

• Test with an empty list, a single record, and a large dataset to ensure robustness.

Why this works

• Interviewer is testing: Ability to use basic data structures effectively and optimize for efficiency.
• Sanity check: Ensures the candidate understands how to structure data for common operations.
• Weak answers: May overlook the need for optimization or fail to handle edge cases, leading to inefficient or incorrect solutions.

Model answer

class Rover {
  constructor(x, y, direction) {
    this.x = x; // X-coordinate on the grid
    this.y = y; // Y-coordinate on the grid
    this.direction = direction; // Current direction the rover is facing
    this.directions = ['N', 'E', 'S', 'W']; // Possible directions
  }

  // Method to turn the rover left
  turnLeft() {
    const currentIndex = this.directions.indexOf(this.direction);
    this.direction = this.directions[(currentIndex + 3) % 4];
  }

  // Method to turn the rover right
  turnRight() {
    const currentIndex = this.directions.indexOf(this.direction);
    this.direction = this.directions[(currentIndex + 1) % 4];
  }

  // Method to move the rover forward
  moveForward() {
    switch (this.direction) {
      case 'N':
        this.y += 1;
        break;
      case 'E':
        this.x += 1;
        break;
      case 'S':
        this.y -= 1;
        break;
      case 'W':
        this.x -= 1;
        break;
    }
  }

  // Method to execute a series of commands
  executeCommands(commands) {
    for (let command of commands) {
      switch (command) {
        case 'L':
          this.turnLeft();
          break;
        case 'R':
          this.turnRight();
          break;
        case 'M':
          this.moveForward();
          break;
      }
    }
  }

  // Method to get the current position and direction of the rover
  getPosition() {
    return `${this.x} ${this.y} ${this.direction}`;
  }
}

// Example usage:
const rover = new Rover(0, 0, 'N');
rover.executeCommands('LMLMLMLMM');
console.log(rover.getPosition()); // Output: "0 1 N"

• Approach:
• Define a Rover class with properties for position (x, y) and direction.
• Implement methods to turn the rover left or right and move it forward.
• Use an array to manage direction changes, allowing easy calculation of new directions.
• Provide a method to execute a sequence of commands and update the rover's state.
• Complexity:
• Time: O(n) for executing commands, where n is the number of commands.
• Space: O(1), as the space used does not scale with input size.