Posts

Prefix Median
Given a sequence of integers, print the median for each nonempty 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
andp
, count the anagrams ofs
that occur inp
. 
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 nontechnical 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 NonRepeated Character For Each Prefix
For each nonempty prefix of a given string consisting of lowercase English letters, find the first nonrepeated character if any.

First NonRepeated Character
For a given string consisting of lowercase English letters, find the first nonrepeated character if any.

Unique Substrings in Wraparound String
Given a strings
s
andp
, find how many unique nonempty substrings ofp
appear ins
. 
Tallest Trees
Given a list of people and a parentchild 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 topleft cell to the bottomright 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 oneoff 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 minitesthooks is the way to go. For nested describe blocks, minitesthooks may not behave as you want. This article provides two alternatives to minitesthooks 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.