Pattern Finding – Boyer Moore

Introduction String matching problems are important part of many Programming Contests and also find applications in real world problems. Imagine you are asked to implement a text editor. What are few of the most common operations in a text editor? Copy and Paste. Search and Replace. The performance of your text editor will completely depend on how efficiently it can search and/or replace patterns in a huge text. Basics of Pattern Finding In a given pattern matching problem, we have two strings one is called the text T and the other is called the pattern P. The task is to find th...
Read More

Solving Recurrences – Master Method

Introduction This post is to be read in continuation to the Divide and Conquer methodology for e.g. the Merge Sort problem. This post is an extension over the problem of solving recurrences or recurrence equations. There are several ways of solving recurrences namely Substitution Method, Master Method and Recurrence Tree method. The most confusing one or may I say relatively complex one is the Master Theorem. Here we will discuss the same. Master Theorem What does it solve? Not all the recurrences can be solved using the Master Theorem, but it still solves a large family of recurrences....
Read More

Cloning Linked List having Next and Random Pointer

Introduction This question was asked by a colleague, although it seems to be simple at first but with given restrictions like running time and space limitations, it becomes tricky. You need to be good with Linked Lists to crack the right solution. Here we try to define the problem in more detail. Given a Linked List where each node contains two pointers next and random. The next pointer points to the immediate next node and the random pointer points to any random node in the linked list. Clone the linked list and return the head of the clone. There are definitely certain conditions impos...
Read More

PostOrder Node Iterator of Binary Tree

Introduction This is going to be a short post. The problem statement at hand is to write PostOrder Node Iterator of Binary Tree. For those who do not know the Iterator Design Pattern or Post Order Successor, check the next section. Iterator Design Pattern This pattern is used to iterate through a collection or group. The Java Iterator supports the following three methods : hasNext() : returns a boolean true if the collection has elements after the last returned element, false otherwise. next() : returns the next element in the collection. remove() : removes the element from the coll...
Read More

Find if a Tree is Subtree of another Tree

Introduction This is a simple yet non trivial problem. Given two trees we need to evaluate if one tree is the sub tree of the other. If the condition is satisfied, it returns true, else it returns false. The definition of sub tree must not be ambiguous. We say that two trees are equal if they are structurally equal and their corresponding nodes have equal keys. Equality of trees Remember that subtree and contains relation are not the same. It may be possible that a tree T1 contains another tree T2 and still T2 is not a sub tree of T1. This also means that all subtree satisfies the con...
Read More

Minimum Range over K arrays

Introduction This is one interesting problem with a non-trivial solution, this has been asked in couple of good interviews. Here goes the problem statement. "Given K positive integer arrays, each of which contains elements in sorted order. Find a range of integers such that it must contain at least one element from each array and the range is minimum." May be a diagram can make this more clear. Here you go! Understanding the Minimum Range over K arrays problem. In the above diagram we have 3 arrays each containing elements in increasing order. Now, let us identify a range which cont...
Read More

Shortest path in Binary Search Tree

Introduction Another interview question for the most interesting data structure called BST (Binary Search Tree). To know more about BSTs check my previous post. Problem Statement : Given a Binary Search Tree, keyed on positive integers. The task is to find the Shortest path in Binary Search Tree which adds up to the number K. If no such path exists, return a message accordingly. Understanding the problem A node in a binary search tree always has a higher key at its right child compared to its left child. There are many path running from the roots to the leaves. When we add up the key val...
Read More