Posts

  • Element Exchanges

    Given two multisets of integers, give the minimum cost of exchanging elements so that both multisets become equal. The cost of exchanging $@N@$ and $@M@$ is $@max(N, M)@$.

  • Prefix Median

    Given a sequence of integers, print the median for each non-empty prefix of the sequence.

  • Maximum Occupancy Revisited

    We revisit problem Maximum Occupancy and give a simpler solution.

  • The Watermark Problem

    Calculate how much water a histogram can hold.

  • Shortest Substring That Contains Given Letters

    You are given a string and a set of characters. Your task is to return any shortest substring that contains all the characters in the set.

  • Index Of

    When a pattern string occurs in a text, return the start index of the first occurrence.

  • Travel Itinerary

    Given the legs of an itinerary, determine the origin and destination of the trip.

  • The Game of Life

    The Game of Life is a popular celular automaton that simulates the births and deaths of a population over time. Your task is to code an efficient implementation of the transition function.

  • Most Recent Common Ancestor

    Given two nodes of a tree, find their most recent common ancestor.

  • Path between Nodes

    Given an undirected graph, determine if there is a path from one node to another.

  • BST: All Possible Arrays

    Given a binary search tree, print all possible arrays that produce the tree.

  • Netmask

    Determine if a given string corresponds to a netmask.

  • Alternative Approach: All Balanced Parentheses Strings

    We explain another approach to solving All Balanced Parentheses Strings and implement the approach in Ruby and Golang.

  • All Balanced Parentheses Strings

    Print all strings consisting of n balanced parentheses.

  • Merge by Buffer

    Write a function that merges two sorted integer arrays using no other buffer than the one you are given.

  • The Large Directory

    You are given a bucket with four directories in a very limited imitation of Amazon S3. Your task is to find the directory that has more files than any of the other three by issuing a given CLI command only once.

  • Shortest Substring Made of Allowed Letters

    You are given a string and a set of letters. Your task is to return any shortest substring that consists of all and only the letters in the set.

  • Production Line With Cooldown

    You are given a work list that must be processed in the given order in such a way that no two identical items are processed within a given cooldown period. Compute the amount of time that takes processing the work list.

  • Dominant Palindromes

    Given a string, find all dominant palindromes. For a given string, a dominant palindrome is a palindrome ocurring in the string that is longer than 1 letter and is not a substring of another palindrome in the string.

  • Longest Word

    Given a set of strings, find the length of any longest word you can make with the letters that are common.

  • Maximum Occupancy

    You work for a chain of hotels. The central management asks you to make a report that includes some metrics for each month and hotel. The report must include the maximum occupancy. Given that the only data you have that is related to occupancy is a list of room reservations for each month and hotel, how do you obtain the maximum occupancy?

  • The Parentheses Problem

    You are given a string that may contain any number of parentheses “(“ and “)”. Remove from the string the minimum number of parentheses so that the remaining parentheses are balanced.

  • Equilibrium Index

    Given an array of integers, find an equilibrium index. An equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

  • Count Pairs with Difference

    Given a set of integers, count the pairs where the difference equals a given integer d.

  • Count Anagrams in String

    Given a strings s and p, count the anagrams of s that occur in p.

  • Book review: A/B Testing: The Most Powerful Way to Turn Clicks Into Customers

    I recommend this book as an introduction to A/B testing for non-technical people. If you are looking for theory and practice, you may want to look at another book.

  • ProTip: Poor man's pomodoro timer for Mac OS X

    One Bash command for timing regular 25 minutes pomodoro session and one for 5 minutes breaks. Because, why use a fancy app or website when you can use an arcane piece of AppleScript in your beautiful Mac?

  • First Non-Repeated Character For Each Prefix

    For each non-empty prefix of a given string consisting of lowercase English letters, find the first non-repeated character if any.

  • First Non-Repeated Character

    For a given string consisting of lowercase English letters, find the first non-repeated character if any.

  • Unique Substrings in Wraparound String

    Given a strings s and p, find how many unique non-empty substrings of p appear in s.

  • Tallest Trees

    Given a list of people and a parent-child relation, find the tallest family trees.

  • Corner to Corner Matrix Traversal

    Given a square matrix of integers, find the maximum sum of elements on the way from the top-left cell to the bottom-right cell.

  • Longest substring with at most k different characters

    For a given string, find the length of the longest substring that contains at most k different characters.

  • Substring with Concatenation of All Words

    Given a string and a list of words of the same length, find all start indices in the string of concatenations of each word.

  • Maximum Number of Points on a Line

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

  • Number of Islands

    A popular problem associated with Leetcode’s online judge. Determine the count of islands in a grid of locations that are either land or water.

  • Binary Tree Upside Down

    A popular problem associated with Leetcode’s online judge. You are given binary trees of a very particular form and you are asked to flip them upside down. A problem not too easy and not too hard.

  • The Pattern Matching Problem

    Find a match, any match. You will be given very simple patterns. But, how fast can you come up with a solution when you are not allowed to use your regexp library? And yes, you might find this in your next interview.

  • The Category Problem: graph traversal by recursive SQL queries

    An interview question in the wild, the Category Problem asks to model a graph of categories of goods in SQL. The sample solution involves a couple of recursive SQL queries that traverse the edges of the model graph. The sample solution works in PostgreSQL 9.6. This post includes a reference implementation in Ruby.

  • The Stock Profit Problem

    The Stock Profit Problem is an interview question you can find in the wild. The problem asks for the biggest profit given a sequence of stock prices. As usual, there is a naive solution that won’t cut it. I explain an efficient solution in 6 different programming languages and give you a hint for further study.

  • Why use Planning Poker cards instead of saying your estimate out loud?

    This article helps you understand why you really want to follow all steps of Planning Poker and use the right tools, specially when you run a distributed Scrum team. This article makes for a good reference that you can share with any team member.

  • The Special Offer Problem

    A problem for the unsuspecting programmer. Makes for a great interview question.

  • ProTip: Automagically setup PhantomJS for Capybara+Poltergeist

    This ProTip explains how to install PhantomJS automatically on program start. This way, running one-off programs that exercise your web application becomes super easy.

  • How to do before(:all)/after(:all) in minitest

    Minitest does not come with before(:all)/after(:all). For flat describe blocks, extension minitest-hooks is the way to go. For nested describe blocks, minitest-hooks may not behave as you want. This article provides two alternatives to minitest-hooks for nested describe blocks and points to examples that you can run for 16 cases, 11 of them not covered here.

  • Correole: The minimum feature newsletter in Ruby

    Correole is a minimum feature newsletter written in Ruby. Correole is ideal for a new blog when you just want to offer a minimal newsletter service. Correole plays nice with Heroku and only requires a confirmation page on the side of your blog.

  • Why does Heap's algorithm work?

    Heap’s algorithm for constructing all permutations is efficient and simple but not easy to understand. This article explains Heap’s algorithm by example.

  • How to count cycles in a complete graph

    An example of a question whose answer is an exponential function.

  • Arbitrage

    Do you want to make easy money? Maybe currency trading is what you are looking for.

  • Release ActiveRecord connections in Sinatra + Thin

    Are you experiencing database connection timeouts in your Sinatra + Thin + ActiveRecord application? Then you want to have a look at this.

  • Stacking Boxes

    Finding a way to fit a given set of boxes one inside the other is easy even for more than 3 dimensions. Finding a way to fit those boxes by contorting them, not so.

  • Ecological Bin Packing

    Group bottles with the least movements possible.

  • The Blocks Problem

    Interpret a language of four commands to model the interaction of a robot arm with its environment. An exercise in keeping your solution simple.

  • The 3n + 1 Problem

    A classical programming problem. The problem statement will tell you an answer, just not a fast one.

  • ProTip: Redirect stdout and stderr to console and different files in Bash

    When you troubleshoot command execution, sometimes you need to analyze standard output and standard error side by side. Here is how to distribute output amongst multiple files and the console.

  • Jill Rides Again

    Jill wants to know where to bike. Can you see past the straightforward solution to figure out the fastest solution possible?

  • The Captured Wise Men

    Two wise men are prisoners in a tower in solitary confinement. Each holds half of an answer that would save their lives. Eventually, they put together the answer. But how?

  • The Adjacent Coins Problem

    Choose a coin that maximizes your gain or minimizes your loss, but you have to do it in linear time and constant memory.