Trie data structure

• Trie is a multi-way search tree where each node represents each character and all the children of the same will be having a same prefix.

 

• Rather than storing the character each node will be storing the prefix.
• Structure of the Node :

                   String prefix;

Node[26] children;

Each node will hold an array of 26 nodes where each node represents the each    letter. If some letter is not present then that will be empty. It is an overhead of trie because it used extra memory which is not using.

• Now we have to think about how to organize or store the array of nodes.

     

   Two possibilities are 1) Store as array

                                     2) Store as linked list

If you store as array we can access it in a indexed way,but we have to waste much memory.

if you store as linked list then access time of the search string will increase( search in linked list of 26 nodes is O(26) and we need to travel m levels where m is the length of search string, that sums to O(m*26)) but memory usage will be optimal.

But if we use HashMap then you can get the time complexity O(1) and memory also will be optimal O(n).

Shortest path algorithm

You might have searched for different routes between two locations in google maps, but have you ever  thought about how would they do this ? finding all those small junctions and even tracking traffic in real time. Sounds crazy !!

Computer Science will have answer to each and every question !! The above scenario can be done with graphs. Say we find all the junction in the map and put those in a graph vertex. now we need to find the shortest path between 2 nodes. We are Done !!. One more application of the same will be in networking finding the shortest path to reach from one computer to another.

In the above image if i want to travel from “u” to “z” then what will be the shortest path ??

u + x + y + z will cause only 3 , if you see all the other paths will be causing more cost.

But what if there  1000 nodes we cannot count it and find which is the best path available. So we have to come up with some algorithm to do this.

There are many algorithms doing the same :

• Dijkstra’s algorithm
• Bellman-ford algorithm
• Floyd Algorithm.

Dynamic Programming

It is considered as a careful bruteforce. And interestingly we will get it in polynomial time.What it does is divide the problem into sub problem and solve the same and reuse the same for larger problem.

Lets take the example of fibonacci number !!

F(n) : if(n <= 2) :      f = 1; else :      f =  f(n-1)+f(n-2); return f;

Looks like neat !! But it is not because it running in an exponential time, because each time recalculating many functions.

Eg : F(4) :

f = [ F(3) + F(2) ]

 = [ F(2) + F(1) ] + 1

 = [ 1 + 1 ] + 1

 = 2 +1

 = 3

Here we can see that F[2] is calculated 2 times. Like that there may be many situations where we are recalculating.

Proof exponential time :

T(n) = T(n-1) + T(n-2)+ O(1)

      > 2T(n-2)

          = O(2^(n/2))