Author: dharam

Understanding Classes in Java

Introduction After gathering some insight into Java Reference Types in the previous posts, now understanding classes in Java has become easier. We need to understand how a Reference Type comes to existence and more. Apart from that we must also learn about Interfaces and Enums which are the building blocks of any written program. A Class in Java A class declaration defines a new reference type and describes its implementation. A class contains members which are enclosed in the body of the class. Members may also be inherited from a Super Class or Interfaces. A member can be a field, a...
Read More

Tries for Text Processing

Introduction Now that we have talked so much about efficient ways of pattern finding using Boyer Moore and KMP algorithm. Let us try and understand other aspects of Text Processing as well. This post will mostly focus on using tries for text processing, storing text efficiently and also discuss about data structures which may make more sense when we talk about storage and retrieval of text based on some given criteria. Here are some real world problems which often demand quicker answers: Ever wondered why you are able to search a word in a dictionary so fast? How do you think one w...
Read More

Pattern Finding – KMP Algorithm

Introduction Now that you are fully equipped with the Boyer Moore Algorithm and have a notion of Pattern Finding. I would suggest you to get deeper into pattern finding. You can read about the benefits of pattern finding in my previous post about Boyer Moore. This post will try to make you familiar with all the thought processes which you can use to exploit the known properties of texts and patterns using KMP Algorithm. However, Boyer Moore seems to be slightly intuitive, this one is a real geeky way of finding patterns. Knuth Morris Pratt Yes! this is what KMP stands for, you can learn ...
Read More

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