Compressed Trie Tree

Hello, people! In this post, we will discuss a commonly used data structure to store strings, the Compress Trie Tree, also known as Radix Tree or Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) Tree. If you remember, the problem with a Trie Tree is that it consumes a lot of memory. So, due to its memory consumption, developers prefer using a compressed trie tree to get the same functionality at the same runtime complexity in memory-critical situations such as in android apps.

“Compress”-ing the tree

Now, the idea of the compressed trie tree is to convert long chains of single-child edges to one single edge. Example, suppose we have two words “facebook” and “facepalm” in our regular trie tree, it would look like –

Trie Tree

It’s a pretty long one, isn’t it? Now, how about this one below?

compressed trie tree

This one surely looks a lot compact! This is the compressed trie tree. As you can see what we do here is to make long chains of single-child edges into one edge. Unlike a regular trie tree, in a compressed trie tree, the edge labels are strings.

Node in Compressed Trie Tree

For a regular trie tree, our tree node looked something like this –

class Node {
    Node[] children = new Node[26];
    boolean isWordEnd;
}

So, in every node, we had an array of references. The first references corresponded to ‘a’, the second to ‘b’, and so on. So, essentially, we had a mapping of alphabets to references. We had a way of saying, “An edge ‘a’ is denoted by this particular element in the array of references”. Now, in a compressed trie tree, the edges are labeled by strings. Now, we need a way of saying, “An edge ‘face’ is denoted by this particular element in the array of references”. To accomplish this, we re-design our tree node as follows –

class Node {
    Node[] children = new Node[26];
    StringBuilder[] edgeLabel = new StringBuilder[26];
    boolean isEnd;
}

So, what we did is that we added an additional array of Strings along with the array of references. Now edgeLabel[0] will denote the string starting with ‘a’, edgeLabel[1] will denote the string starting with ‘b’, and correspondingly, children[0] will denote the edge with the label edgeLabel[0].

Example, in the above diagram, the root node will have edgeLabel[5] = “face” and children[5] will point to the internal node. The internal node will have edgeLabel[1] = “book” and children[1] will point to the leaf node which will denote the occurrence of the word “facebook”. The same internal node will also have edgeLabel[15] = “palm” and children[15] will point to the leaf node which will denote the occurrence of the word “facepalm”. The rest of the values of edgeLabel and children in the internal node will be null.

The above code is written in Java. For Java, it is much better to use StringBuilder rather than String because we would be doing a lot of string manipulation. Using String will heavily slow down your program. If you are not familiar with StringBuilder, you can refer to my post.

insert() operation

All operations in the compressed trie tree are similar to what we would do in a regular trie tree. Insert operation is the one which will differ the most. In the insert operation, we need to take care of a few cases, they are –

  1. Inserting new node for a new word – This occurs when the starting character of the word is new and there’s no edge corresponding to it. This may occur at root, or after traversing to an internal node.compressed-trie-tree-4
  2. Inserting a prefix of an existing word – Inserting prefix into compressed trie tree
  3. Inserting a word which has a partial match to an existing edge – This occurs when we are trying to insert “this” when “there” is already inserted into the tree. Remember that “there” can have further children too, like if “thereafter” and “therein” are already inserted.breaking words during compressed trie tree insertion

So, for these cases, we would have to break the existing word or the newly inserted word accordingly. The faster we perform these string operations, the faster the insert operation will be.

search() operation

Searching in a compressed trie tree is much like searching. Here, instead of comparing a single character, we compare strings. The following cases will arise –

  • The string we want to search does not exist. Example, searching for “owl” when the tree only has “crow” in it.
  • The string we want to search exists as a prefix. Example, searching for “face” when the tree only has “facebook”.
  • Only the prefix of the target string exists. Converse of the previous case. Searching for “facebook” when the tree only has “face”.
  • The string we want to search matches partially with an existing string. Example, searching for “this” where the tree only has “there”.
  • Another case is when the edge label fully matches to the starting portion of the string. Example, searching for “thereafter” when “thereafter” and “therein” exist in the tree. For this, after a full match with “there”, we traverse to the node which corresponds to that label and then resume our search (searching for “after”).

If we are able to fully traverse the tree via the target string and arrive on a tree node, we check if that node is a word ending or not. If yes, we return true or, we return false. For rest of the cases, return false.

startsWith() operation

The startsWith() operation is a popular operation performed on the compressed trie tree which checks if there’s any word in the tree which starts with the target word. This method would be exactly as the searching method. The minor change with the search operation would be, in this operation, we will just check if we are able to fully traverse the tree via the target string and arrive on a node (which may be the root). If we can we return true, regardless of whether the current node is a word ending or not. This is because, even if it is not a word ending, its children will lead to a node which would be a word ending.

Printing the compressed trie tree

For each edge traversed, add its label to a variable and recursively do this for the child node. While traversing another edge, remove the previously added label and add the new label of the new edge traversing. Print the variable only if the current node is a word ending.

This recursive method should print all the words in the compressed trie tree in a lexicographical order.

Code

Start with your existing trie tree code, modify the node definition and then work on the insert method cases. Once you get the insert correctly, then the rest will work out easily. For the insert cases, you just have to do the string operations and change the references carefully. Try to code those cases. Come back and have a look at the diagrams if you need to.

You can check your code’s correctness with LeetCode’s Implement Trie problem. Try to solve that question using a compressed trie tree. Once you solve it, try to reduce the runtime of your program.

You can refer to my code if you get stuck. 🙂

    

This is the Java implementation. I will update this post with the C/C++ implementation soon.

In terms of runtime complexity, compressed trie tree is same as that of a regular trie tree. In terms of memory, a compressed trie tree uses very few amount of nodes which gives you a huge memory advantage especially for long strings with long common prefixes. In terms of speed, a regular trie tree would be slightly faster because its operations don’t involve any string operations, they are simple loops.

I hope my post has demystified everything regarding a compressed trie tree. Tutorial and code for a compressed trie tree are hard to find. I hope my post saved you the effort of finding further tutorials. Do comment below if you have any doubts. Keep practising! Happy Coding!! 😀

Jump Search Algorithm

Hello, people…! In this post, we will discuss a new search algorithm, Jump Search, which searches for an element in a sorted array in O(√N) time. It is slower than binary search, then why learn it? What if the interviewer purposely asks you to write a search algorithm with O(√N) worst case complexity? You would be banging your head to cook up a new algorithm 😛 . Anyways, it’s fun learning new stuff, isn’t it?

Algorithm

Imagine you are given a sorted array, and you are applying linear search to find a value. Jump Search is an improvement to this scenario. Instead of searching one-by-one, we search k-by-k. Let’s say we have a sorted array A, then jump search will look at A[1], A[1 + k], A[1 + 2k], A[1 + 3k] … and so on.

As we keep jumping, we keep a note of the previous value and its index. Once we get a situation where A[i] < searchValue < A[i + k], then it means the value we want is in between the previous jump ends. So now we could simply perform a linear search between that A[i] and A[i + k].

Jump Search

Sound too boring? Here’s where things get interesting! How will we know the most optimal value of the jump size?

Optimal Jump Size

If we try to write down the complexity of the algorithm we described above.


\frac{n}{m} + m - 1
Now, let’s see for which value of ‘m’ does this expression have a minimum. To do this we differentiate with respect to ‘m’ and equate it to 0


\frac{n}{ -m^{2} } + 1 = 0 \newline \newline  n = m^{2} \newline \newline  n = \sqrt{m}
So, the optimal jump size is √N.

Code

It is a pretty simple algorithm to code. Try it by yourself. You can refer to my code below if you get stuck 🙂 .

CJava
    
    

Faster Jump Search

How can we make this version of jump search faster? A few people might have guessed it by now! 😉 In the above algorithm, once we find the jump ends which contains the value we need, we are performing a linear search. But we could perform another jump search between these two jump ends! And then recursively perform jump search until we are left with only one element.

Implementing this version is more challenging. Firstly, you need to modify your above method to something which looks like this –

public Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
    // return jump ends if condition meets
    // return null or a -1 otherwise
}

We must return the i and j between which the value is found or return null. And then call this from another method jumpSearch() which keeps calling jumpSearchUtil() until the jump interval has only 2 elements or it returns a null. We will need to return 2 values, the left end and the right end of the jump. So, we will use a structure in C, or a class in Java.

Try to code this version of Jump Search algorithm. If you get stuck, you can use my code below as a reference –

CJava
    
    

This optimised version has the following complexity –


\sqrt{N} + \sqrt{\sqrt{N}} + \sqrt{\sqrt{\sqrt{N}}} + ... + 1

This is still O(√N) in the worst case. But it is much faster because, in the previous version, the complexity was √N + √N, which made it O(√N), but here the additional terms have very low values.

I hope you’ve understood about the jump search algorithm. If you did, let me know by commenting! Keep practising! Happy Coding! 😀

Dynamic Programming – Edit Distance

Hello people..! In this post, we will see another dynamic programming based problem, finding the minimum edit distance between two strings.

Problem – Given two strings A and B, we need to find the minimum number of operations which can be applied on A to convert it to B. The operations are –

  • Edit – Change a character to another character.
  • Delete – Delete a character.
  • Insert – Insert a character.

Normally I would take a brute force solution and reduce it to a dynamic programming solution, but in this case I’m not sure how I can do that 😛 . So, I will straight away explain the dynamic programming solution in the best way I can.

Example

Let’s take an example. Let the string A = “this”, and let string B = “there”. Now we will perform a very simple pen-and-paper exercise. Please draw the chart given below in your rough notes –

Edit distance matrix

The Y axis denotes the source string A and the X axis denotes the target string B.

  • Empty cell at 1st row, 1st column denotes the situation when A = ∅ and B = ∅. The edit distance would be 0.
  • Empty cell at 1st row, 2nd column denotes the situation when A = ∅, B = “t”. We would need 1 insertion to convert A to B. Here, the answer is 1.
  • Empty cell at 1st row, 3rd column denotes the situation when A = ∅, B = “th”. We would need 2 insertions to convert A to B. Here, the answer is 2.
  • Empty cell at 1st row, 6th column denotes the situation when A = ∅, B = “there”. We would need 5 insertions to convert A to B. Here, the answer is 5.

This is the trivial case when A = ∅. The other trivial case is when B = ∅, which is denoted by the empty cells in the first column.

  • Empty cell at 2nd row, 1st column denotes the situation when A = “t” and B = ∅. We would need 1 deletion to convert A to B. Here, the answer is 1.
  • Empty cell  at 3rd row, 1st column denotes the situation when A = “th” and B = ∅. We would need 2 deletions to convert A to B. Here, the answer is 2.
  • Empty cell  at 5th row, 1st column denotes the situation when A = “this” and B = ∅. We would need 4 deletions to convert A to B. Here, the answer is 4.

So, now after the trivial cases our matrix should look like this –

Edit distance matix with trivial cases

Now that you know what this matrix really means, it shouldn’t be difficult to understand that what we actually want is the value of the last empty cell, which denotes the situation when A = “this” and B = “there”.

  • Empty cell at 2nd row, 2nd column denotes the situation when A = “t” and B = “t”. The answer is 0.

Now take a moment and think, when A = “t” and B = “t”, the last characters match. Wouldn’t the answer be same as when the last characters were removed? That is, when A = ∅, B = ∅? Yes! Of course! Take another example, let A = “ste”  and B = “sto”, the edit distance currently is 1. Now, if A = “step” and B = “stop” isn’t still the edit distance 1? Yes! So, if the ending characters are same, then the edit distance is same as when these two were removed.

Looking at the matrix, if you are at the cell (i, j) can you tell which cell would be the situation when the last characters of both the strings were removed? It is the cell (i – 1, j – 1)! Moving forward,

  • Empty cell at 2nd row, 3rd column denotes the situation when A = “t” and B = “th”. The edit distance is 1.

We know that the answer is 1. But how do we derive this using the solutions we already have? Let us say the empty cell is (i, j). We can arrive at (i, j) using the result at (i – 1, j), (i – 1, j – 1) and (i, j – 1).

edit-distance-3

What does each arrow mean?

  • Insert – Cell at 2nd row 2nd column denotes A = “t” and B = “t”. So we know that the edit distance to convert “t” → “t” is 0, which is the value of the cell. Now, if we insert a character at the end, we can get “th”. So, we are doing “t” → “t” → “th”. We already know the cost of “t” → “t” and we add the cost of “t” → “th” to it. So, the value is 0 + 1.
  • Delete – Cell at 1st row 3rd column denotes ∅ → “th”. But we want “t” → “th”. If you observe, we start with A = “t” for the 2nd row. So, imagine we have A = “t∅” and we used ∅ → “th” to get “t∅” → “tth”. Now, deleting a ‘t’ would give us “tth” → “th”. It might sound really confusing, but the chain of conversions is, “t∅” → “tth” → “th”. The cost of “t∅” → “tth” is given by the cell at 1st row 3rd column and “tth” → “th” is a delete operation which costs 1. So, the value is 2 + 1.
  • Edit – Cell at 1st row 2nd column denotes the cost of ∅  → “t”. As said previously, we start with A = “t” in the 2nd row. So consider A = “t∅” and use the above conversion to get, “t∅” → “tt”. Now we apply edit operation to convert “tt” → “th”. So, the chain of operations are “t∅” → “tt” → “th”. Cost of “t∅” → “tt” is given by the value of cell at 1st row 2nd column and “tt” → “th” costs 1 edit operation. So, the value is 1 + 1.

I know the delete and edit operations sound extremely confusing, please ignore them if you don’t understand. Most tutorials just put the dynamic programming formula for the edit distance problem, write the code and be done with it. But I wanted to go one step deep and explain what that matrix meant and what each term in the dynamic programming formula (in a few moments) will mean.

So, now we had 3 options, insert, delete and update. We have calculated the total cost of choosing each option. Now which one will we choose? The one which has the least cost! If you notice in my explanation above, the cost is = 1 + value_of_respective_cell. So, now the dynamic programming formula to calculate the value of any cell is –

Edit distance formula

Where dp is the matrix. We already know the values for the first row and the first column, and the rest of the matrix can be generated using the above formula. If you notice, we are using the previous results to build the current result. This is a form of bottom-up dynamic programming.

If you fill all the cells of the matrix, it would look like –

Edit distance final matrix

The final edit distance is the last cell which is 3.

Code

If you have understood the above formula, then coding is pretty simple. You construct a 2-D array of size |A| + 1 and |B| + 1, where |A| and |B| are lengths of the strings respectively. Initialize the fist row and first column with its row and column number respectively and apply the formula above.

The code for edit distance is pretty simple. Try to code it with a clear head. It is a kind of code which people generally code without logical errors in the first go. The trick is in that formula above. If you get stuck you can use my code below as a reference.

CJava
    
    

Optimized Edit Distance Algorithm

If you have noticed, we just need the (i – 1)th row to calculate the ith row. Which means that we need not store the entire array, we could just store the previous row only. This drastically reduces the memory complexity.

Try coding using only one array of auxiliary space. You can use my code below as a reference –

CJava
    
    

Edit Distance Algorithm Complexity

The time complexity for both versions of the algorithm is O(|A| × |B|) and the memory complexity of the normal version is O(|A| × |B|) and the memory complexity of the optimized version is O(|A|) where A would be the shorter string.

Practice

Edit distance is very useful in competitive coding. You can solve these questions to get a hang of the algorithm –

I hope you have understood a little about the algorithm. The low level details of this algorithm sound very confusing, so try learning it on a high level ignoring the details if you don’t understand them yet. But do come back and take a look at my explanation! Keep practicing! Happy Coding! 😀

Binary Search Algorithm

Hello people…! In this post we will discuss one of the most commonly used search algorithm, the Binary Search. In a search algorithm, we are given an element and a collection or a set of elements. If the given element exists in the given set, we must return where it is located, or otherwise, if it does not exist, our algorithm must be able to say it does not exist.

Binary Search Conditions

The given set must obey the following rules if we want to apply binary search –

  1. All pairs of elements in the given set must be comparable. Mathematically, this is called a totally ordered set.
  2. The given set must be sorted, in ascending or descending order.

Algorithm

Let’s say we are looking for 7 in an array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Binary search compares the middle element (here 5) and the element to be searched (here 7). So, 5 is less than 7. Binary search says, “Okay so 5 is less than 7, so don’t bother about the elements left of 5 because they are less than 5 anyway. It will never be equal to 7. Continue the same job with the right half instead!”. So, now we will look at the elements right of 5 only.

Now, let’s sat the middle element is 8. This time Binary Search says, “Elements right of 8 are more than 8, they will never be equal to 7, so neglect the elements right of 8, carry on with the elements left of 8.”

So if you analyse this carefully, we are cutting the size of elements we are supposed to look at by half for each step.

To implement this algorithm, we use 3 variables –

  • low – the lowest index of the searching range.
  • high – the highest index of the searching range.
  • mid – which is calculated by the formula below

binary-search-equation-1

 

 

Let us take the previous example array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This time let us search for 9, and this time we will find the middle element using the formula above.

binary search

Initially, low = 0 and high = 8, which gives mid = 4. The middle element is not 9, but 5 which is less than 9, so we might find 9 only to the right of 5. So, we will assign low = mid + 1.

binary search

Now, low = 5 and high = 8, which gives mid = 6. Value 7 is less than 9, so we search in the right half of 7. We do this by low = mid + 1. (If we wanted to search in the left half, say for 6 example, we would do high = mid – 1).

binary search

Even now, the middle element is less than the required element, so we must search in the right half. So we do low = mid + 1.

binary search

Now our middle element is equal to what we want, so we return this index! So basically Binary Search goes up to when there’s only one element left. If that remaining element is not the element we want, then we can claim that the given set does not contain it.

Just imagine if we were searching for 10 in the above case, we would go up to the last element and find that even the last element is not equal to 10, so we return a -1 or some value which denotes that the element is not found.

The reason the formula for calculating the middle element isn’t a simple average is to avoid an integer overflow error. If we try to calculate,

binary-search-equation-2

when low and high are close to maximum values of an integer, they can cause an integer overflow. This is why we use the formula mentioned above.

Complexity

We make one comparison per iteration. So what is the worst case? Worst case occurs when the element is not present in the given set. Then we need to iterate until we have one element left. At each iteration, we reduce the range by half, so how many iterations should we perform to reach a single element?

Binary Search complexity

It is log2 N! So the worst case complexity of binary search is O(log2 N). The best case would be if the middle element of the set is itself is the value we want to find, then, the complexity would be O(1).

Code

It is a fairly simple algorithm to code. Please try to write the code by yourself. If you get stuck, you can use my code below as a reference.

CJava
    
    

You can code the binary search using recursion too. But I prefer the iterative version as it does not have the recursion overhead and it will not produce a stack overflow error for large arrays.

Keep practicing! Happy Coding! 🙂

Dynamic Programming – Kadane’s Algorithm

Hello people..! In this post, we will look at a simple dynamic programming based algorithm which is the optimal solution to the Maximum Sum Subarray Problem. Try to focus on how the approach of dynamic programming is applied rather than just trying to understand the main algorithm. Now, let us define the problem.

Maximum Sum Subarray – Given an array A[1, 2, 3, … n]. We need to find that subarray A'[i, i + 1, i + 2, … j] where 1 ≤ i ≤ j ≤ n, where the sum of all the elements in A’ is maximum.

In simpler terms, we need to find that contiguous portion of an array where the sum is maximum.

Brute force approach

Brute force approach would be to look at all the sub-arrays starting with A[i] –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to n
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

This is algorithm is simple but it takes O(N²) time. The problem with this algorithm is that we are not able to save computation by using the solutions to the problems we already solved.

Let us re-write this algorithm slightly differently! Pay attention! Instead of starting from A[i] and going forward looking for maximum, this time, let us start at A[i] and go backward doing the same thing, finding the maximum. Here is the algorithm –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to 1   // decrement j
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

What we are doing is instead of looking at all the sub-arrays starting with A[i], we will look at all the sub-arrays ending with A[i]. This still runs in O(N²) time. So, what’s so special about this? Let is say we have an array A = {-1, 2, 3, -4}. The above algorithm would work on this algorithm something like this –

  • for i = 1 ⇒ max( sum(-1) )
  • for i = 2 ⇒ max ( sum(2), sum(2, -1) )
  • for i = 3 ⇒ max ( sum(3), sum(3, 2), sum(3, 2, -1) )
  • for i = 4 ⇒ max ( sum(-4), sum(-4, 3), sum(-4, 3, 2), sum(-4, 3, 2, -1) )

The solution would be the maximum of all iterations. If you notice, in each iteration, we are finding the maximum sum of all the sub-arrays ending with A[i]. Let us say we store this result in an array maxSum[i].

Kadane’s Algorithm states that,

kadane-algorithm-equation

In simple terms, it states that, the maximum sum sub-array ending with A[i], is either the element A[i] itself, or A[i] combined with the maximum sum sub-array ending with A[i – 1], whichever is the greater one.

Ponder upon this for a while. Using the above intuition we can re-write the above iterations as –

  • for i = 1 ⇒ max ( -1 ) ⇒ maxSum[1] = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum[2] = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum[3] = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum[4] = 1

And as before, the solution would be the maximum of all the elements in maxSum array. For the sake of simplicity, we used the array maxSum[], but we only need the previous iteration’s result to compute the current iteration result. So, we can make it a variable. So our iterations change into –

  • for i = 1 ⇒ maxSum = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum = 1

Why was the first iteration written like that? It is the trivial case. The maximum sum sub-array ending with the first element is the first element itself. And for each iteration, we could keep a global variable, say maxGlobalSum, which keeps track of maximum of all maxSum values.

If you have understood everything up to now, you should be able to code the algorithm very easily. If you didn’t understand, please give a couple more readings and try to code again. Feel free to ask your doubts in the comments!

If you are stuck with the algorithm, you can use my code as a reference –

CJava
    
    

This algorithm runs in O(N) time and uses O(1) space. I hope you have developed an idea of how to think in the dynamic programming way. To get a dynamic programming algorithm, we just have to analyse if where we are computing things which we have already computed and how can we reuse the existing solutions. Keep practising..! Happy Coding! 😀

Java Tutorials – Constructor and Overloading Methods

Hello, people..! In this post, we will explore some more aspects of object-oriented programming, which is overloading methods, but before that, I thought it is the right the time to tell you about what a constructor is.

Constructor

The constructor is a special method which is written in a class. This is called exactly once at the time of instantiating an object of that class. Why do we need a constructor anyway? A constructor is meant to have the code for initializing the instance variables or any such process which we wish to do before we start using the object. A constructor looks just like a method, with a few rules. The rules for writing a constructor are –

  1. It is a method with the same name as the class name.
  2. It does not have any return type. Not even void.

Now, keep those two rules in mind, as I show you what a constructor exactly looks like –

class Classroom {
    int capacity;
    
    // This is a constructor!
    //
    // 1. Same name as class name
    // 2. No return type
    public Classroom() {
        capacity = 35;
    }
}

That is a constructor. It is automatically called by the JVM when an object of that class is created. To demonstrate this, have a look at the code below –

class Classroom {
    int capacity;

    public Classroom() {
        System.out.println("Inside Classroom's Constructor...");
        capacity = 35;
    }
}

public class Test {
    public static void main(String[] args) {
        System.out.println("Inside main()...");
        Classroom obj1 = new Classroom();
        System.out.println("Creating another object...");
        Classroom obj2 = new Classroom();
        System.out.println("Done with main()...");
    }
}

The output of the given code is –

Inside main()...
Inside Classroom's Constructor...
Creating another object...
Inside Classroom's Constructor...
Done with main()...

I hope this makes the flow of execution clear. Feel free to comment if you have any doubts!

Constructor with Parameters

So, we’ve seen that a constructor pretty much resembles a method. But like methods, can it take arguments? Yes! We can mention parameters for a constructor just as we do for a method in java. These values must be passed at the time of creating the object. Have a look at the code below –

class Person {
    String name;
    int age;
    
    // A constructor with parameters
    public Person(String personName, int personAge) {
        name = personName;
        age = personAge;
    }
}

class Test {
    public static void main(String[] args) {
        // Providing the arguments while creating object
        Person p = new Person("Chloë Grace Moretz", 19);
    }
}

Overloading Methods in Java

Now let us look at the OOP feature of overloading methods in java. We will come back to the constructor in a minute! Now, imagine you wanted to create a utility class which has a lot of frequently used functions. Let’s say we wanted to create a utility class which has the method for returning the index of the maximum element in an array. So this is how you would normally do it –

class Utility {
    public int max(int[] arr) {
        if (arr == null || arr.length &lt; 1) {
            return -1;
        }
        
        int index = 0;
        int max = arr[0];
        
        for (int i = 1; i &lt; arr.length; ++i) { if (arr[i] &gt; max) {
                max = arr[i];
            }
        }
        
        return index;
    }
}

This is fine, but it can only accept an array of integers, what if you needed to find the index of the maximum element in an array of doubles or long or short or any other data type? Would you create other method named “max2”, “max3”, “max4” and so on..? No, you would have to remember a lot of names. Here’s where overloading helps you! Overloading allows you to create two or more methods of the same name but different signatures. Now, recall from our discussion on Enums and Methods in Java. We defined method signature as, name of the method + the list of parameters. We want the method names to be the same, so we will only alter the list of parameters. Overloading needs no special syntax, it’s just as simple as writing another method with a few restrictions. Let us look at an example –

class Utility {
    public int max(int[] arr) {
        System.out.println("public int max(int[] arr)");
        
        if (arr == null || arr.length &lt; 1) {
            return -1;
        }
        
        int index = 0;
        int max = arr[0];
        
        for (int i = 1; i &lt; arr.length; ++i) { if (arr[i] &gt; max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
    
    // Overloaded method max, to
    // accept an array of double
    public int max(double[] arr) {
        System.out.println("public int max(double[] arr)");
        
        if (arr == null || arr.length &lt; 1) {
            return -1;
        }
        
        int index = 0;
        double max = arr[0];
        
        for (int i = 1; i &lt; arr.length; ++i) { if (arr[i] &gt; max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
    
    // Overloaded method max, to
    // accept an array of long
    public int max(long[] arr) {
        System.out.println("public int max(long[] arr)");
        
        if (arr == null || arr.length &lt; 1) {
            return -1;
        }
        
        int index = 0;
        long max = arr[0];
        
        for (int i = 1; i &lt; arr.length; ++i) { if (arr[i] &gt; max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
}

class Test {
    public static void main(String[] args) {
        Utility obj = new Utility();
        
        int[] intArray = {1, 2, 3, 4, 5, 0, -1, -2};
        double[] doubleArray = {1.2, 2.3, 3.4, 4.5, 5.6, 6.7};
        long[] longArray = {1, 2, 3, 4, 5, 6, 124578};
        
        System.out.println(obj.max(intArray));
        System.out.println(obj.max(doubleArray));
        System.out.println(obj.max(longArray));
    }
}

Can you pause for a moment and guess what the output could be? The output of the code above is –

public int max(int[] arr)
4
public int max(double[] arr)
5
public int max(long[] arr)
6

So what happened here is that, based on the number of arguments passed (here 1) and on the basis of the data type of the arguments passed, Java decides for itself which is the best method to call. When we passed an array of doubles, the method which takes an array of doubles is called. If you can notice, we are not reducing the amount of code written, but it makes our job easy as we have to remember only one name, and based on the data type of the argument passed, the corresponding method is called. This is called Overloading methods. Some rules to keep in mind regarding overloading are –

  • We can overload methods only based on different data type of parameter or different number of parameters. Everything else is irrelevant.
  • So, we cannot overload methods based on return type, or access modifiers (public, private, etc.), or specifiers (static), or exception list.

Well, leave exception lists for now, we’ll look at it later. So based on these rules you could run into overloading problems. Given below are some examples of invalid overloads –

/* ===== ===== ===== ===== */
public void foo(int var) { }
public int foo(int var) { }


/* ===== ===== ===== ===== */
public static int foo(int var) { }
public int foo(int var) { }


/* ===== ===== ===== ===== */
public void foo(int var) { }
private void foo(int var) { }

Overloading is heavily used in the Java library. In fact, we’ve been using it right from our first hello world program! How? The println() method we use has a lot of overloaded methods. If you are working in NetBeans or any other IDE, you can see all these methods. This is how it looks in my NetBeans IDE – Overloading - Overloaded Methods of System.out.println()

Overloading Constructors

So we saw what a constructor was and we saw that it resembles a method in many aspects. So as we can overload methods, can we overload constructors too? Yes! How? It’s just like overloading methods, we just alter the number of parameters or change the data type of the parameters. Have a look at the example below to make things clear –

class Time {
    int hours, minutes, seconds;

    public Time(int hrs) {
        hours = hrs;
    }

    // Overloaded Constructor
    public Time(int hrs, int min) {
        hours = hrs;
        minutes = min;
    }
    
    // Overloaded Constructor
    public Time(int hrs, int min, int sec) {
        hours = hrs;
        minutes = min;
        seconds = sec;
    }
}

class Test {
    public static void main(String[] args) {
        Time t1 = new Time(10);
        Time t2 = new Time(10, 20);
        Time t3 = new Time(10, 20, 30);
        
        System.out.println(t1.hours);
        System.out.println(t1.minutes);
        System.out.println(t1.seconds);
        
        System.out.println(t2.hours);
        System.out.println(t2.minutes);
        System.out.println(t2.seconds);
        
        System.out.println(t3.hours);
        System.out.println(t3.minutes);
        System.out.println(t3.seconds);
    }
}

So that’s how we overload constructors on Java. Using overloaded versions of the constructor, we can initialize selected fields of the object while instantiation. The output of the code above is –

10
0
0
10
20
0
10
20
30

We have also used overloaded constructors before. The Scanner class has many overloaded versions of constructors. We can see it all in NetBeans IDE – Overloading - Overloaded Constructors in Scanner class While there are a lot more things to discuss about the constructor we won’t do it in this post as the requires the knowledge of some other concepts. So, if all I explained above made sense to you, then I will definitely have happy tears! 😛

Order of Preference in Overloading

This is a very advanced concept. Beginners can skip this, but do come back again because this is very interesting! Now we know that an integer value is a match to long data type, as well as for Integer class (for those who know it). So, if all these appear in the form of different overloads, which method would be called? What is the order which Java uses to choose an overloaded method if all the methods are actually a match to the argument provided? Well, let’s say there’s a function named “foo” which is provided with 2 integers, then the order which Java uses is –

Exact Match by Data Type
public void foo(int i, int j) {}
A Larger Primitive Data Type
public void foo(long i, long j) {}
Autoboxed Type
public void foo(Integer i, Integer j) {}
Varargs
public void foo(int... args) {}

To better understand this concept take the code below and run it on your PC –

class OverloadingOrder {
    public void foo(int i, int j) {
        System.out.println("public void foo(int i, int j)");
    }
    
    public void foo(long i, long j) {
        System.out.println("public void foo(long i, long j)");
    }
    
    public void foo(Integer i, Integer j) {
        System.out.println("public void foo(Integer i, Integer j)");
    }
    
    public void foo(int... args) {
        System.out.println("public void foo(int... args)");
    }
}

class Test {
    public static void main(String[] args) {
        OverloadingOrder obj = new OverloadingOrder();
        
        obj.foo(1, 1);
    }
}

Now, try commenting out a few versions of the overloads and observe which function is called. Try it for a few minutes and I’m sure you will understand it! You might think Java follows the order which you write it in the class, but that is irrelevant. Now another thing to note here is that Java will only do at most one implicit conversion while finding the right overloaded match. Take a look at the code below –

class OverloadingOrder {
    public void foo(Double f) {
        System.out.println("public void foo(Double f)");
    }
}

class Test {
    public static void main(String[] args) {
        OverloadingOrder obj = new OverloadingOrder();
        
        obj.foo(1f);    // Compilation error
    }
}

This gives a compilation error saying that Java wasn’t able to find a suitable overloaded method. This is because conversion from float to double value is one implicit conversion but that’s the end of it. Java will not perform another implicit conversion from double to Double. Try such examples in your PC. Try the same thing with int and Long, short and Integer, and so on. I’m sure you’ll get the hang of it after a few tries. 🙂 The last concept I want to discuss in overloading is, overloading in the context of variable number of arguments. An array of integers is a match to both the overloaded methods below –

public void count(int... args) { }
public void count(int[] arr) { }

So, which one is called?? It gives a compilation error! Java cannot differentiate between those two. Of course, the way we normally call those methods is different, but still, Java doesn’t take risks as we could pass an array and wreak havoc! 😛 … So that is a nice little thing to remember. I hope my post gave you a fair understanding of what constructors are and what overloading is. If you have any doubts, feel free to comment them! Keep practicing! Happy Coding!! 😀

Encapsulation in Java

Hello, people..! Now we are going to look at the most basic and the first major topic in Object Oriented Programming, Encapsulation. For those who don’t know OOP, it is very important that you spend a lot of time trying to understand these concepts. Because once you learn these concepts, it will be exactly the same in any other OOP language (like C++, C#, etc.), only the syntax changes.

Code without Encapsulation

Let us first understand what happens when we don’t follow encapsulation. Let’s say you created the Person class where all the instance variables were public. The code would look like –

class Person {
    public String name;
    public int age;
}

Now, since it was public, somebody used it in this way in his main() method –

public static void main(String[] args) {
    Person p = new Person();

    p.name = "Vamsi Sangam";
    p.age = -1;
}

Okay, so doing that is legal. Neither the compiler nor the runtime complaints anything about it. But we all know that it’s not sane, right? Seriously, some values can’t be negative, like age, or length, or size etc. It’s like we created this class which everybody is using… Which we are happy about… But they can misuse it, or do stuff not meant for that class. So, we don’t have control.

Encapsulation

So how do get control over things? By implementing encapsulation. So, what’s encapsulation really? It is a set of rules, or a protocol, which we must follow to get more control over our data. Now, what are those rules which we must follow? They are –

  1. Keep instance variables private.
  2. Make public accessor methods.

So, let’s look at it one-by-one. Firstly, we must keep the instance variables private. What does that mean? Well, we just have to write “private” in the place of  “public” before we write the data type of our instance variable. That restricts the scope of the instance variable. Now, the instance variable has scope only inside the class. It cannot be accessed by making an object and referencing it. So, if we implement our rule 1 to Person class, it would look like –

class Person {
    private String name;
    private int age;
}

So, if you tried to use this class from another class’ main() method, and try to access those variables, it will give you a compilation error, saying “age has private access in Person”. The code is –

class Person {
    private String name;
    private int age;
}

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person();
        
        p.age = -1;    // error
    }
}

Great! So it looks like things went from bad to worse! We can’t even use those variables. Well, just wait till we implement the second rule. 😉

The second rules ask us to implement accessor methods. As the name suggests, accessor methods, are meant to access the variables which were marked private. These are also called Getter and Setter methods, or sometimes called as Mutator methods. Oracle thought the name “mutate” sounds bad, so we’ll stick to Getter and Setter methods. So, we will implement Getter and Setter methods for our Person class. As the name suggests the Getter method gets the value of the variable and the Setter method sets the variable to some value. The Person class with Getter and Setter methods would look like –

class Person {
    private String name;
    private int age;
    
    // Getter method for variable name
    public String getName() {
        return name;
    }
    
    // Setter method for variable name
    public void setName(String newName) {
        name = newName;
    }
    
    // Getter method for variable age
    public int getAge() {
        return age;
    }
    
    // Setter method for variable age
    public void setAge(int newAge) {
        age = newAge;
    }
}

As you can see that is the format in which we write the getter and setter methods for a variable. What you write inside the function is your wish, but the access modifier “public”, return type, name, or arguments must be in that format. We’ll talk a little about the naming conventions in a few minutes.
Well, you could ask, what’s changed, you could still do the same cruel stuff we did above to your Person class! 😛 Well, look closely, things have changed! You can do the validation stuff in the setter method of ‘age’ variable. To avoid negative values you could do something like –

// Setter method for variable age
public void setAge(int newAge) {
    if (newAge > 0) {
        age = newAge;
    }
}

So, if the input is a valid one you set the ‘age’ variable to the new value, otherwise you ignore. Not just this, you can do any amount of validation you want. You could keep an upper cap of 125 years or anything like that. So you have complete control. Lastly, you would use the encapsulated class like this –

public static void main(String[] args) {
    Person p = new Person();

    p.setName("Vamsi Sangam");
    p.setAge(-1);   // Ignored, so still 0
    p.setAge(19);
}

You can print the values of the variables using the getter methods if you want to. 🙂

JavaBeans Naming Convention

JavaBeans is a standard set by Oracle. It defines a few rules. We will only concern ourselves with the rules regarding the naming of getter and setter methods, commonly known as JavaBeans Naming Convention. It defines the naming conventions we must follow while naming the getter and setter methods. All classes in the Java library follow this convention strictly. JavaBeans calls an instance variables as a “property”. So the rules are –

Rule Example
Properties are private.
private int age;
private boolean happy;
private int numberOfChildren;
Getter methods begin with is if the property is boolean.
public boolean isHappy() {
    return happy;
}
Setter methods begin with set.
public void setAge(int newAge) {
    age = newAge;
}
The method name must have a prefix of set/get/is, followed by the first letter of the property in uppercase, followed by the rest of the property name
public int getNumberOfChildren() {
    return numberOfChildren;
}

Well, that was the convention rules. The first rule isn’t a naming rule, but it’s a part of JavaBeans so I saw it fit to keep it there.

Encapsulation with Mutable Classes

This is a little advanced topic in Encapsulation. Feel free to skip this part if you are new to OOP. But do check this later because it is an important pitfall! Now, mutable classes are those classes whose data can be changed after the object is created. Example, we saw that String objects are not mutable, whereas the objects of StringBuilder are. We must be careful when encapsulating mutable objects. Check out the class below. Do you think it is perfectly encapsulated?

class Person {
    private StringBuilder name;
    
    public Person(StringBuilder name) {
        this.name = name;
    }
    
    // Getter method for variable name
    public StringBuilder getName() {
        return name;
    }
}

So, let’s say we have this class. We don’t have a setter here, but that’s fine, the class is still considered to be encapsulated (for now :P). So, it pretty much looks like we can’t change the value of the variable ‘name’ after we initialize it with a constructor. Now, check this out –

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person(new StringBuilder("Vamsi Sangam"));

        // variable name will hold Vamsi Sangam
        System.out.println(p.getName());
        
        // Storing the return value
        StringBuilder var = p.getName();
        
        // Changing the object returned
        var.append("! Are you confused?");
        
        // Printing the object inside encapsulated class
        System.out.println(p.getName());
        // Prints "Vamsi Sangam! Are you confused?"
    }
}

We’ve somehow managed to change the object held by the encapsulated field which doesn’t even have a getter method! This happens because, the variable name, is a reference to an object. In the getter method, we are returning the same object which name is pointing to. So if you return the reference to that object, you can actually manipulate it as you want, because it’s a mutable object. Changes made to the object returned by the getter method will reflect in the object held by name because they are exactly the same object.

I hope this made sense. Please go through what I said once more if you didn’t understand it. It’s a fairly simple concept. So what do we do in such a situation? We clone that property and return the clone. Cloning means creating a new object of the same data type as the property which has the same content.

So, a proper getter method for name would be –

class Person {
    private StringBuilder name;
    
    public Person(StringBuilder name) {
        this.name = name;
    }
    
    // Getter method for variable name
    public StringBuilder getName() {
        return new StringBuilder(name);
    }
}

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person(new StringBuilder("Vamsi Sangam"));

        // variable name will hold Vamsi Sangam
        System.out.println(p.getName());
        
        // Storing the return value
        StringBuilder var = p.getName();
        
        // Changing the object returned
        var.append("! Are you confused?");
        
        // Printing the object inside encapsulated class
        System.out.println(p.getName());
        // Prints "Vamsi Sangam"
    }
}

All this nuisance is because the property is of a mutable class. If it were something like a String, we wouldn’t have this problem. Because even if two references point to the same object, we cannot change the content of that object they are pointing to.

So, that was Encapsulation! It is a matter of 2 simple rules. Easy! Isn’t it..?! Keep practicing… Happy Coding..!! 😀

Arrays Interview Questions

Hello, people..! In this post, I will discuss some of the arrays interview questions (coding and conceptual), which you must solve before you attempt any technical interviews. The questions are given below. You may click on the question to see its solution. But, it is extremely recommended to think about how you would give your approach to solve a particular question before looking at its solution. And if you are reading this post, I assume that you have pretty good amount of experience with algorithms.. 😛

Coding Questions

Find the missing number in an array which has numbers from 1 to N, but with one number missing.
Find the element in an array which is occurs only once while all the other elements occur twice.
Intersection of two sorted arrays.
Find the top K numbers in an integer array of size N.
Given a 2D array, print it in spiral form.
Find the first occurrence of an element in a sorted array which contains duplicate elements.
Find the last occurrence of an element in a sorted array which contains duplicate elements.
Find any one peak element in an unsorted 1-D Array.
Find the number of times the array is rotated, the pivot element in the sorted and rotated array.
Search for an element in a sorted and rotated array.
Sum of 2 numbers which are equal to a given value.
Sum of 3 numbers which are equal to a given value.
Sum of 4 numbers which are equal to a given value.
Find the kth smallest/largest element in an array.
Find the majority element in the array
Find the maximum contiguous sum of an array.

This post is a little dynamic. More questions will be added as soon as the solutions are made, some of the questions which will come in the near future are –

  • Median of two sorted arrays.
  • Find the smallest positive integer that cannot be represented as the sum of any subset of the array.
  • Find the number of duplicates in an array using O(1) space.
  • Given an array with +ve and -ve numbers. Rearrange such that +ve and -ve numbers appear alternatively, maintaining the relative order, using O(1) space.

Conceptual Questions

Difference between an array and a linked list.
Why does it take constant time for accessing array elements?
What is the difference between int[] arr, and int arr[] in Java?
From where is the memory allocated for arrays in Java?
In C, what is actually passed when you pass an array to a function?
What are the strategies involved in growing the size of arrays in the case of dynamic growing arrays?
How can you pass a 2D array to a function in C ?

I hope these questions help you. These are pretty base level interview questions. Nothing too great. But if you can solve these it will give you a great confidence boost and, what’s more, is that you can use these techniques to solve bigger problems based on arrays. Do leave a comment if you liked my post or if you have any queries… 🙂 … Keep practising… Happy Coding.. 😀

Trie Tree Practise – SPOJ – DICT

Hello people..! In this post we will talk about solving another competitive programming question based on trie tree. I will take up the SPOJ problem – DICT. This is a little harder than the previous trie tree practise problem, PHONELST. Now, read the problem statement carefully a couple of times. Just so that you don’t need to open SPOJ in another tab, I have posted the problem statement below –

Problem Statement
Input Specification
Output Specification
Sample Input
Sample Output

Problem in terms of Trie Tree

Firstly, we will insert the N words into a trie tree. Then, for each K prefix words –

  • We will traverse the trie tree for this word.
  • If it exists, we will lexicographically print the trie tree, with that node as the root. And obviously, we add the prefix to whatever we will print.
  • If the word doesn’t exist at all, that is, while traversing, we would reach a dead-end (no children) node before the prefix word is fully processed, we will simply return from our traversal and print “No match.”.

So, what all do you need to solve this?

  • Trie Tree insertion method.
  • Trie Tree inorder traversal method (lexicographical print)

We can discard any other methods such as delete. We will need another method for searching whether a given word is present in the trie tree or not, in O(L) time, where L is the length of the word. So, take your implementation of trie tree and get it ready for solving the question by making these changes.

searchWord() Method

This is a simple trie tree traversal method, where we traverse the trie tree based on a given word. We look at each character of the word and go to the corresponding edge, in the trie tree. If there is no edge, we return null. If we have reached the end successfully, we return the node where the word ends. Try to code this procedure, you can refer to my code if you are stuck.

C++
struct node * searchWord(struct node * TreeNode, char * word)
{
    while (*word != '\0') {		// while there are alphabets to process
        if (TreeNode->children[*word - CASE] != NULL) {
        	// there is an edge corresponding to the alphabet
            TreeNode = TreeNode->children[*word - CASE];
            ++word;
        } else {
        	// there is no edge corresponding to the alphabet
            break;
        }
    }
 
    if (*word == '\0') {
    	// the word was completely processed
        return TreeNode;
    } else {
    	// word is not there in trie tree
        return NULL;
    }
}

lexicographPrint() Method

This method will have very minor changes from your original method. According to our intuition, we will call this method based on the output of the searchWord method. If it is null, then it is “No match.”. If it is not null, then we begin the lexicographPrint from that node.
This method will carry an extra parameter, which will be the prefix word. Everytime we hit a leaf node, we first print the prefix word and then the remaining word traversed in this method.
Example, in the sample test case, the prefix word was “set”, so, the searchWord would return us, the location of the T node in S → E → T traversal. Then, we begin our lexicographPrint, and when we hit the end of “setter” word, we will print the “set” prefix, and the “ter” word which we gained from the lexicographPrint method.
Try to code these modifications in your code, you can refer to my code if you are stuck.

C++
 
void lexicographPrint(struct Node * trieTree, vector<char> word, char * prefix)
{
    int i;
    bool noChild = true;
 
	if (trieTree->wordEnding && word.size() != 0) {
        vector<char>::iterator itr = word.begin();
		
		printf("%s", prefix);	//	print the prefix
        
		while (itr != word.end()) {
			// print the rest of the word
            printf("%c", *itr);
            ++itr;
        }
        
        printf("\n");
    } 
 
    for (i = 0; i < ALPHABETS; ++i) {
        if (trieTree->children[i] != NULL) {
            noChild = false;
            word.push_back(CASE + i);
            lexicographPrint(trieTree->children[i], word, prefix);
            word.pop_back();
        }
    }
 
    word.pop_back();
}

Putting the pieces together

Now combine your modules and prepare your main function as per the problem statement. You can refer to my code if you are stuck.

    

Word of Caution –

  • The output in the case of a mismatch is “No match.”, not “No match”.
  • The time limits are pretty tight, so your methods should be tidy.

I hope that you were able to solve this problem using a trie tree. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 🙂

Trie Tree Practise – SPOJ – PHONELST

Hello people..! In this post I will show you how to get started with solving Trie Tree based questions in competitive programming. Learning a data structure is different from solving competitive coding questions based on that data structure. In this post, I take up a very simple question so that your confidence is boosted.
We will look at the SPOJ problem – Phone List. It is a very straight forward problem. Just so that you don’t need to go to SPOJ in a new tab, I’m putting the problem statement here.

Problem Statement

Phone List Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

• Emergency 911

• Alice 97 625 999

• Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

The Problem in terms of Trie Tree

We are supposed to check if any word is a prefix of any other or not. Now, there might be a hundred ways to solve this problem, but we will do this using a trie tree so that we can get confident in using the data structure, and so that we can attempt tougher ones based on a trie tree. All throughout my explanation, I will be referring to the implementation in my post on Trie Tree.
What we will do to solve this problem is that, we will insert the words into the trie tree one-by-one, and we will check for the prefix word criteria as we are inserting. Now, there are 2 cases.

Case – 1 – Prefix word is already inserted

This is the sample test case. Consider this test case –

Input
face
facebook

So, what I said we will do is that, we will be inserting the words one-by-one. So, when we insert the word “face”, no problems occur. But while inserting the word “facebook”, we would travel to the nodes F → A → C → E. And at the node E, we would have some indication that this node is a leaf node, that is, some word ends here. In my implementation, this can be indicated by –

if (temp->occurrences.size() == 0) {
	// not a leaf node
} else {
	// a leaf node, thus this is
	// the end of the prefix word
}

If we encounter this situation, we know that the result will be NO.

Case 2 – Prefix word is about to be inserted

This is just the opposite of the previous case, consider the test case –

Input
facebook
face

We won’t have any issues while inserting “facebook”. But when inserting “face”, we traverse F → A → C → E. And in the end of insertion, we see that there is a child node to the node E. Which means that there is a bigger word which ends somewhere deep down the trie tree. Which means that we just inserted the prefix word. We could check this by traversing the children array –

for (i = 0; i < ALPHABETS; ++i) {
	if (temp->children[i] != NULL) {
		// The newly inserted word is
		// prefix to another word
	}
}

In this case too, the answer would be a NO. For every other case, the answer would be a YES.

So, try to code this problem. Take your code of the trie tree, remove the unnecessary things first, like the delete function or print function or any others which we won’t need. As fas as I know, the insert function is all that you will need. And try to make the changes required for the test cases.
Your insert function could return a true or a false, depending on whether the insertion encountered a prefix test case or not. Take time to think about it and try to code it. If you get stuck, you can refer to my code below –

    

A word of caution –

  • Even if you did encounter a prefix word very early, don’t break out of the input, as you will disturb the input for the next test case.

I hope that you were able to solve this problem using a trie tree. It is simple and a prefect problem to start your trie tree streak in competitive coding. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 😀