Trie Operations Complexity
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Now that we’ve seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.
INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings.
[Read More]Trie : Searching in Trie
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed.
Consider the following TRIE as usual.
The search alogirthm involves the following steps
For each character in the string, see if there is a child node with that character as the content. If that character does not exist, return false If that character exist, repeat step 1.
[Read More]Trie : Inserting in Trie
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.
Before we begin, assume we already have an existing TRIE as shown below.
Lets see the steps on how to insert a word “bate”. Any insertion would ideally be following the below algorithm.
If the input string length is zero, then set the marker for the root node to be true.
[Read More]Implementing the TRIE ADT in java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present.
Node.java
package com.vaani.ds.trie; import java.util.Collection; import java.util.LinkedList; /\*\* \* @author kc \*/ public class Node { char content; boolean marker; Collection<Node> child; public Node(char c){ child = new LinkedList<Node>(); marker = false; content = c; } public Node subNode(char c){ if(child!
[Read More]Trie ADT
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as ‘try’) has a wide variety of applications in
Spell checking Data compression Computational biology Routing table for IP addresses Storing/Querying XML documents etc., We shall see how to construct a basic TRIE data structure in Java.
The main abstract methods of the TRIE ADT are,
[Read More]Globe Walker
Posted on October 8, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?
Solution : The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again!
Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile.
[Read More]Trains and Birds
Posted on October 8, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem : A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth.
[Read More]Gold for 7 days of work
Posted on October 8, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)
[Read More]The Ant Collision Problem
Posted on October 8, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : There are three ants on different vertices of a equilateral triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle?
Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.
Solution : Note that equilateral has nothing to do with how they will collide. Also, ants are allowed to move on the sides only.
[Read More]Is Your Husband a Cheat?
Posted on October 8, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells another woman if her husband is cheating on her. So every woman in the town knows about all the cheating husbands in the town except her own.
[Read More]