Interview Questions That Stumped Me

At the start of a 4-hour-long series of back-to-back coding interviews (with the same employer), I was asked to write a function that takes in a list and finds the 'pivot index' where the sum of all indices leading up to it and the sum of all indices after are equal. If no such index exists, the function should return -1. I tackled the problem confidently, explaining my thought process and solution. Feeling like hot shit, I was caught off guard when the interviewer followed up with another question "How would you describe the complexity of your function using big-o notation?". I had heard the term before, but I wasn't well-versed in the concept enough to confidently answer that question. The planets aligned, the perfect series of synapses fired off in my cerebral cortex, and I managed to muster up a coherent relevant response to his question. "Linear complexity, this won't be an issue as input grows". The interviewer seemed satisfied and moved on. At that moment I was elated. I had avoided catastrophe early on in the 4-hour process, or so I thought. A week later I received a call from the recruiter at that company, giving me the bad news that I had been passed on for not meeting their standards for senior developer, womp womp.

Looking for new opportunities after working for the same employer for half a decade was both a humbling and eye-opening experience. I've logged mountains of time absorbing as much information as possible, continously expanding my knowledge in as many domains as I could to make up for lost time, but it still wasn't enough to protect me from inevitable stumping. Whiteboarding, and code challenges during interviews often fail to accurately reflect a candidate's ability to perform on the job. You're in a high-pressure environment, you're nervous and can easily make mistakes. You are also challenged to solve problems that you will rarely actually encounter on the job, like building a binary tree from scratch, converting roman numerals, palindromes. Regardless of that fact though, interviews like this do reinforce the importance of having a good grasp on computer science fundamentals, and being able to operate in highly stressful situations. A couple examples of questions that stumped me during recent interviews.

Big-O Notation

Big-O notation, represented by a capital O, stands for 'order of magnitude' and is a theoretical measure of an algorithm's complexity relative to the size of its input. In web development, big-O notation is often used to evaluate the scalability of solutions based on execution time and memory usage. Results of a big-O analysis won't be an exact number, like 1.4 seconds, rather an algebraic expression that describes the function's rate of growth (constant, linear, quadratic, exponential, etc).

Understanding big-O notation is crucial for programmers considering scalability. For web developers, this could mean scaling websites to accommodate higher levels of traffic, or scaling ETL processes that handle larger datasets. In the aforementioned "pivot index" challenge, the most scalable solution would've been to iterate over the list once, adding each index value to a running total and subtracting it from the total sum of all items in the list. Each step is evaluated for execution frequency, resulting in a notation. After evaluating all steps, notations are combined, constants are dropped, and the highest order of magnitude is used to describe the complexity.

Optimal Solution ( Linear )
O(2n + 6)   ---->  O(n)

def pivot_index(nums):
    total_sum = sum(nums)    ----------------------------------  O(n)
    left_sum = 0      -----------------------------------------  O(1)

    for i, val in enumerate(nums):   --------------------------  O(n)
        total_sum -= val     ----------------------------------  O(1)
        if left_sum == total_sum:    --------------------------  O(1)
            return index      ---------------------------------  O(1)
        left_sum += val    ------------------------------------  O(1)

    return -1          ----------------------------------------  O(1)

My solution ( Cubic )
O(1) + O(n) * (O(index) + O(n - index - 1) + O(1))   --- reduced --->  O(n^3)

from functools import reduce

def pivot_index(nums):
    n = len(nums)      -----------------------------------------  O(1)
    
    for i in range(n):        ----------------------------------  O(n)
        left = reduce(lambda a, b: a + b, nums[:i], 0)   -------  O(index)
        right = reduce(lambda a, b: a + b, nums[i + 1:], 0)  ---  O(n - index-1)
        
        if left == right:   ------------------------------------  O(1)
            return index      ----------------------------------  O(1)
            
    return -1          -----------------------------------------  O(1)

Postgres Index Types

This came up during one of the final interviews I managed to reach for an open position with a fintech company. It was with the team lead of the department looking to add a new developer too, easily the most technical of the bunch, with a strong database administration background. He prompted me to describe what my process would look like to improve poor database performance, what I knew about indexes, so forth, and so on. My responses were clear, concise, and accurate. I flowed through query plans, explain analyze statements, b-tree index optimization, how RDBMS utilize b-tree indices, how data is stored for b-tree indexes, lots of good bits, but all b-tree. The interviewer was very satisfied with this answer. He asked me what I knew about other index types. Stumped. Deer in the headlights, no clue. Luckily he laughed and said something like "Well, who really knows that much about database indices anyway?".

On a positive note, this actually ended up being the company that would extend an offer to me, and I accepted.

Database indexes help query performance in the same way catalog systems help readers find books at their local library. When you create a table in a Postgres db, and perform queries against it that include a where clause, Postgres by default will do a full table scan to find the matching rows. This is fine for small tables, but as the table grows, the time it takes to perform a full table scan grows exponentially. Indexes help with this by creating a data structure that stores the values of a column in a table, and the location of the corresponding row. This allows Postgres to perform a binary search on the index, which is much faster. There are several types of indexes, each with pros and cons, and use cases for each. Below are the most common index types for Postgres, brief descriptions, and some use cases.

Below is a quick glance at Postgres index types, followed by a slightly more in-depth analysis of each type.

B-Tree

The most common PostgreSQL index type, B-tree indices are the default index type and work well for most use cases. B-Tree indexes are especially effective for equality and range queries, as well as sorting operations. They store data in a sorted, tree-like structure, allowing for fast lookup times.

Use Cases:

-- Queries that involve equality and range operators

-- Your DB has a massive users table and frequently receives queries based on last_name
SELECT *
FROM users
WHERE last_name = 'Smith';

-- You're listing products on an e-commerce site and want to sort them by price
SELECT *
FROM products
ORDER BY price ASC;

Hash

Hash indexes provide efficient access to data based on exact-match queries. They use a hash function to map distinct values to distinct hash codes and store these hash codes in a way that allows for efficient retrieval. However, they are not suitable for range queries and cannot be used for sorting or ordering.

Use Cases:

-- Queries with equality comparisons
-- You are building a web application, and want to quickly search for user based on their unique username
SELECT *
FROM users
WHERE username = 'john_doe';

GiST (Generalized Search Tree) Index

GiST indexes are a flexible, balanced disk-based data structure. They can be used for different types of queries beyond simple equality and range, including multidimensional, full-text, and similarity searches. GiST is often used when a B-Tree or Hash index is not sufficient, like for indexing geometric data types or performing nearest-neighbor searches.

Use Cases:

-- Geometric operators
-- Geo-location software that can find locations within a specific radius
SELECT *
FROM locations
WHERE point '<@' box '((1,2),(3,4))';

SP-GiST (Space-Partitioned Generalized Search Tree)

SP-GiST indexes provide fast lookups for data types that can be divided into non-overlapping ranges, such as IP network addresses, and tree-like structures. SP-GiST supports more than just simple equality and range queries, including nearest-neighbor searches on applicable data types.

Use Cases:

-- IP network containment checks
-- Using a network management system, you want to find all IP addresses within a certain range
SELECT *
FROM ip_addresses
WHERE network >>= '192.168.1.0/24';

GIN (Generalized Inverted Index)

GIN indexes are designed for handling complex data types where the data items are composite values and contain multiple component values, such as arrays and full-text search vectors. They excel at queries that involve containment, overlap, or existence operators, and can be significantly smaller and faster than B-Tree indexes for these types of queries.

Use Cases:

-- Indexing array elements or full-text search vectors.
-- Blog system that provides the ability to find all posts which contain certain keywords
SELECT *
FROM blog_posts
WHERE to_tsvector('english', body) @@ to_tsquery('english', 'Postgres');

BRIN (Block Range Index)

BRIN indexes are useful for large tables where the rows are naturally sorted by some attribute, and the queries involve range conditions. They store the summary information about block ranges, namely the minimum and maximum value for each block range, which makes them especially efficient for large tables and range queries. However, they are not a good fit for tables where the order of the rows does not correlate well with the indexed column.

Use Cases:

-- Large tables with natural, sequential order.
-- Weather tracking system software that queries temperature data logged over a certain time range
SELECT *
FROM weather_data
WHERE recorded_date BETWEEN '2023-01-01' AND '2023-01-31';

...

If you're interested in learning more about big-O notation, I found these resources particularly helpful:

Big-O Notation: A Simple Explanation with Examples
Big-O Notation in 2nd Grader Terms
Big-O Cheat Sheet