Introduction
Few days back I wrote a post about the Trie data structure. This post is a continuation to it, and intends to introduce some practical problems which Trie solves. An autocomplete system is a perfect use case.
Many of the websites use this feature to help there users with suggestions & autocomplete. Also, in this post we will define a Trie interface and then work through this problem statement.
An autocomplete system using Trie
As we know from the previous text that a Trie is a tree like data structure which stores words such that the search for a word is proportional to ...

Read More
## Paint Fill Implementation – Image Editing

Introduction
Most of the image editing software like Microsoft paint, Paint.NET, Adobe Photoshop offer features like paint fill. This post is an attempt to define a simple version of the algorithm which is used to implement paint fill. The problem definition goes like this:
There is a grid with dimensions N*M such that each cell of the grid is colored. The paint fill technique allows a user to choose a color to be filled, say K and a cell C(i,j).
If the cell C(i,j) has the same color as K, then do nothing.
If the cell C(i,j) has a color L which is different from K then find all the...

Read More
## Fastest Reach in Snakes and Ladders

Introduction
For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on.
Problem Statement - Fastest Reach in Snakes and Ladders
The problem in ha...

Read More
## Single Source Shortest Path For Undirected Graph

Introduction
Single source shortest path for undirected graph is basically the breadth first traversal of the graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. You can find posts on the same topic for weighted graphs, and that is solved using Dijkstra's or Bellman Ford algorithms. This post is written from the competitive programming perspective. Here I want to focus on the details of simplified implementations.
Problem Statement - Shortest Path for Undirected Graph
Most of the times, the probl...

Read More
## Rotating an Array by a fixed distance

Problem Statement
Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array.
Here is an example of input and output.
The problem seems very easy until s...

Read More