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

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

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

// 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; // Toggle direction
    }

    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 = 0; i < n; i++) {
        dp[i][i] = 1; // Single character is a palindrome
    }

    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];
}

// Problem 3: Integer square root (floor)

function mySqrt(x) {
    if (x < 2) return x; // 0 and 1 are their own square roots

    let left = 2, right = Math.floor(x / 2);
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const square = mid * mid;

        if (square === x) return mid;
        if (square < x) left = mid + 1;
        else right = mid - 1;
    }

    return right; // right is the floor of sqrt(x)
}

// Problem 4: Spreadsheet column label to number

function titleToNumber(col) {
    let result = 0;
    const length = col.length;

    for (let i = 0; i < length; i++) {
        result = result * 26 + (col.charCodeAt(i) - 'A'.charCodeAt(0) + 1);
    }

    return result;
}

// Approach Summary:
// 1. For zigzag traversal, use a queue to traverse levels and toggle direction.
// 2. For longest palindromic subsequence, use dynamic programming to build a table.
// 3. For integer square root, apply binary search to find the floor value.
// 4. For column label conversion, calculate the value using base 26 arithmetic.

// Complexity: 
// Problem 1: O(n) time, O(n) space
// Problem 2: O(n^2) time, O(n^2) space
// Problem 3: O(log x) time, O(1) space
// Problem 4: O(m) time, O(1) space (where m is the length of the column string)

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

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 Robot {
    constructor(x, y, direction) {
        this.x = x;
        this.y = y;
        this.direction = direction;
        this.commands = {
            'L': this.turnLeft.bind(this),
            'R': this.turnRight.bind(this),
            'F': this.moveForward.bind(this),
        };
    }

    // Rotate 90° left
    turnLeft() {
        const directions = ['N', 'W', 'S', 'E'];
        const currentIndex = directions.indexOf(this.direction);
        this.direction = directions[(currentIndex + 1) % 4];
    }

    // Rotate 90° right
    turnRight() {
        const directions = ['N', 'E', 'S', 'W'];
        const currentIndex = directions.indexOf(this.direction);
        this.direction = directions[(currentIndex + 1) % 4];
    }

    // Move forward in the current direction
    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;
        }
    }

    // Execute a command string
    executeCommands(commandString) {
        for (const command of commandString) {
            if (this.commands[command]) {
                this.commands[command]();
            } else {
                console.error(`Invalid command: ${command}`);
            }
        }
    }

    // Get the current state of the robot
    getState() {
        return [this.x, this.y, this.direction];
    }
}

// Example usage
const robot = new Robot(0, 0, 'N');
robot.executeCommands('FFRFF');
console.log(robot.getState()); // Expected output: [2, 2, 'E']

• Approach:
• Define a Robot class with properties for position and direction.
• Implement command methods for turning and moving.
• Use a command registry to map command characters to methods.
• Execute commands in a loop, handling invalid commands gracefully.

Complexity:

• Time: O(n) for command execution, where n is the length of the command string.
• Space: O(1) for the robot's state storage.

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.

Model answer

// Problem 1: Minimum range-increments to make an array nondecreasing
function minOperationsToNonDecreasing(power) {
    let operations = 0;
    
    // Iterate through the array from the second element
    for (let i = 1; i < power.length; i++) {
        // If the current element is less than the previous one
        if (power[i] < power[i - 1]) {
            // Calculate the difference needed to make the array nondecreasing
            operations += power[i - 1] - power[i];
            // Adjust the current element to make it equal to the previous one
            power[i] = power[i - 1];
        }
    }
    
    return operations;
}

// Problem 2: Pair servers to maximize total primary memory
function maxPrimaryMemory(memory) {
    // Sort the memory array
    memory.sort((a, b) => a - b);
    
    let maxSum = 0;
    let left = 0;
    let right = memory.length - 1;
    
    // Use two pointers to form pairs
    while (left < right) {
        if (memory[left] <= memory[right]) {
            // Add the primary memory to the sum
            maxSum += memory[left];
            // Move both pointers inward
            left++;
            right--;
        } else {
            // Move the right pointer inward to find a suitable backup
            right--;
        }
    }
    
    return maxSum;
}

// Example usage:
console.log(minOperationsToNonDecreasing([3, 1, 2, 1, 4])); // Output: 3
console.log(maxPrimaryMemory([1, 2, 3, 4, 5])); // Output: 6

• Problem 1 Approach: Traverse the array and ensure each element is at least as large as the previous one. If not, increment the current element to match the previous one, counting the increments needed.
• Problem 2 Approach: Sort the memory capacities. Use two pointers to form pairs, ensuring the primary is always less than or equal to the backup. Maximize the sum of primary memories by selecting the smallest available as primary.

Complexity:

• Problem 1: Time O(n), Space O(1) — single pass through the array.
• Problem 2: Time O(m log m), Space O(1) — due to sorting and two-pointer traversal.

Model answer

The flow

1. Clarify inputs & output shape: Understand the input format and desired output.
2. Brute force first: Implement a simple solution to convert the string to a list.
3. Optimize: Check if the solution can be improved for edge cases or performance.
4. State complexity: Analyze the time and space complexity.
5. Test the edges: Consider and test edge cases like empty strings or special characters.

The answer

1. Clarify inputs & output shape

• The input is a single string, and the output should be a list of characters from that string.

2. Brute force first

• We can use Python's built-in list() function to convert a string into a list of its characters.

# Function to convert a string to a list of characters
def string_to_list(input_string):
    return list(input_string)

# Example usage
input_string = "hello"
output_list = string_to_list(input_string)
print(output_list)  # Output: ['h', 'e', 'l', 'l', 'o']

• Approach: Use the built-in list() function which takes an iterable and returns a list.

3. Optimize

• This solution is already optimal for the task. The list() function is efficient for this purpose.

4. State complexity

• Time Complexity: $O(n)$, where $n$ is the length of the input string, as each character is iterated over once.
• Space Complexity: $O(n)$, as a new list of size $n$ is created.

5. Test the edges

• Test with an empty string: "" should return [].
• Test with special characters: "!@#" should return ['!', '@', '#'].
• Test with a single character: "a" should return ['a'].

Why this works

• Testing basic understanding: The interviewer is checking if the candidate can use basic Python functions effectively.
• Sanity check: Ensures the candidate considers edge cases like empty strings and special characters.
• Efficiency: A weak answer might involve unnecessary loops or complexity, whereas using list() is both simple and efficient.
• Edge cases: A strong answer will explicitly test and handle edge cases, demonstrating thoroughness.

Model answer

function longest_unique_substring(s) {
    let start = 0; // Start index of the current substring
    let maxLength = 0; // Maximum length of substring found
    let maxStart = 0; // Start index of the longest substring found
    const seenChars = new Map(); // Map to store the last index of each character

    for (let end = 0; end < s.length; end++) {
        const char = s[end];

        // If the character is already in the map and its index is within the current window
        if (seenChars.has(char) && seenChars.get(char) >= start) {
            // Move the start to the right of the last occurrence of the current character
            start = seenChars.get(char) + 1;
        }

        // Update the last index of the current character
        seenChars.set(char, end);

        // Update the maximum length and starting index if a longer substring is found
        if (end - start + 1 > maxLength) {
            maxLength = end - start + 1;
            maxStart = start;
        }
    }

    // Return the longest substring found
    return s.substring(maxStart, maxStart + maxLength);
}

// Example usage:
console.log(longest_unique_substring("abcabcbb")); // "abc"
console.log(longest_unique_substring("bbbbb"));    // "b"
console.log(longest_unique_substring("pwwkew"));   // "wke"
console.log(longest_unique_substring(""));         // ""

• We use a sliding window approach with two pointers (start and end) to track the current substring.
• A Map keeps track of the last seen index of each character, allowing us to efficiently update the start pointer when a repeated character is found.
• The maxLength and maxStart variables are updated whenever a longer unique substring is found.
• The function returns the longest substring by slicing the original string from maxStart to maxStart + maxLength.

Complexity:

• Time: O(n), where n is the length of the string s, as each character is processed at most twice.
• Space: O(min(n, m)), where m is the size of the character set (ASCII), due to the storage in the Map.