Introduction If you are new to string search, I would recommend to first read the brute force approach here. Brute force as discussed in the mentioned post has time complexity of O(mn) in worst case. Rabin-Karp also has the worst case time complexity of O(mn), but it has a much better time complexity of O(mContinue reading “A Simple Explanation of Rabin-Karp Algorithm For String Search”
Tag Archives: java intervew question
Simple Explanation And Implementation Of Knuth-Morris-Pratt (KMP) Algorithm For String Search
Introduction We have seen brute force approach to string search here. Brute force approach to string search has time complexity of O(n*m). Donald Knuth and Vaughan Pratt, and James H. Morris conceived the algorithm in 1970. KMP algorithm is the first algorithm to have linear time complexity. Problem Statement We will assume text (where weContinue reading “Simple Explanation And Implementation Of Knuth-Morris-Pratt (KMP) Algorithm For String Search”
A beginner guide to Brute Force Algorithm for substring search
Introduction CONTROL + F or COMMAND + F How often do you use above keyboard shortcut? In fact, for most of us, searching a string or substring in a pile of strings/document is involuntarily action with the above key combination. This post will deal with the subject of the substring search. We will quickly defineContinue reading “A beginner guide to Brute Force Algorithm for substring search”
A complete tutorial on Binary Tree
Introduction Figure 1 shows a Binary Search Tree. This post will start with the motivation of studying BST and gradually move to the related definitions. We will do some hands on coding for simple BST operations and we will end the post by analysing the drawbacks. Where do we use Binary Search Tree? TreesContinue reading “A complete tutorial on Binary Tree”
int vs Integer – Java Application Memory Usage
Before you read further, Please answer the following question: A. int a = 100; B. Integer b = new Integer(100); There are two java statements written above. What is the ratio of memory used by b to memory used by a in a 32 bit machine? The four options are: 1 1.5 2 4Continue reading “int vs Integer – Java Application Memory Usage”
Huffman Code – An example of Greedy Algorithm
Introduction A greedy algorithm always makes the choice that looks best at the moment. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Greedy algorithms do not result in optimal solutions always but for many problems they do. A problem can be solved by GreedyContinue reading “Huffman Code – An example of Greedy Algorithm”