Tries (Overview)

January 27, 2012 1 comment

What is it? Trie? Did you mean “Tree”? No! I meant “Trie”. It is a data structure (also known as “prefix tree”) that is used in form of a dictionary. It is basically a way of representing data. I don’t think I can explain this without an example. So here we see the way to represent two words in English language using a trie. Shrey and Shayne.

As you can see, a trie gives us words with the same prefixes. In this example, “SH”. So that is how you represent words. You can do the same for numbers (in any format – binary, decimal, etc). Also, note that both have different “Y” nodes because a trie represents words on the base of prefixes. If we associate a count with each node, we can also tell the number of words starting with a particular prefix.

Please note that the insertion in a trie takes O(length) time where length is that of the word being inserted. We can create a trie for english language using a structure with information and 26 pointers for the corresponding letters. Easy, eh?

So a trie can be of many uses. In the next post, we’ll see an example of using Trie. 🙂

PS : For more information on Tries, visit http://en.wikipedia.org/wiki/Trie

PPS : Sorry for the long hiatus in posting!

Advertisements

Forming Cricket Teams (Balanced Partition problem)

November 29, 2011 2 comments

Problem Statement: You have been given N players, with a corresponding strength value S for each player (Minimum strength being 0 and maximum being K). You are supposed to divide them into two teams such that the difference in the total strengths of both teams is minimized.

This is an everyday problem that we tackle while forming equally matched teams. You might try a greedy approach here but in many cases it will fail. It is actually known as a Balanced Partition problem and utilizes the method we used while solving the integer knapsack (1/0) problem. Great! So you know half of it! But let us give it a quick look.

We defined a term P(i,j) which specified that I would find a subset of elements in the first ‘i’ elements which sum up to ‘j’. Now we can define the term recursively, as,

P(i,j) = maximum {P(i-1,j), P(i-1, j-Si)} 

While you can refer to the link given to the earlier post, what this formula specifies is that we either have a subset that sums up to ‘j’ in the first ‘i-1’ elements, or that we have a subset in the first ‘i-1’ elements whose sum when added to the ith value Si gives us ‘j’.

Now that we are done refreshing our memory, we’ll move on to the new problem.

We have now generated a 2D array giving us the possibility of a sum (j) being formed using some (<i) elements at each step. Now we need to divide this into 2 sets Team 1 and Team 2 such that the different of their totals is minimized.

For this, we’ll first find the mean value of the list of N elements. If a subset’s sum hits this particular value, we have found a solution with difference 0. Otherwise, we keep trying to find a solution where the sum of strengths of teams is closest to the mean. For this, we can once again check for all ‘i'<=’Mean’,

Minimum {Mean-i : P(n,i)=1}

where 1 indicates we have such a subset. What we are doing is that we are checking for every value less than the Mean it can be formed from any subset of the N elements. Checking this one by one, we land up with the required value closest to the Mean.

There it is. You have your solution! Divide you teams and game on! 🙂

(Retrieving the values for the subsets is as simple as maintaining back-pointers while creating the 2D array and filling it up.)

Doubts? Ask away!

PS: Need to be spoonfed (euphemism for “Me.Want.Code.”) ? Write it yourself! 😛 If you just can’t, drop me an email and I’ll mail it to you!

Santa Claus is coming to town. (Integer Knapsack 1/0)

November 22, 2011 1 comment

I hope you remember the US Pizza problem we talked about a while back. That wasn’t a 1/0 problem but the one we will discuss now certainly is.

Problem Statement: Santa Claus is coming to your city and needs to figure out the gifts he has to take. Since North Pole is a long way off, he can only carry gifts weighing a total of ‘C’ in his bag. He has a total of ‘N’ gifts to select from. You are supposed to help him select the gifts in a way that would use the capacity to the greatest use, i.e., the total weight of the gifts selected should be closest to C and the most number of gifts should be selected.

This is a dynamic programming problem and you should recognize it as soon as you see that the problem has optimal substructures in the fact that its solution can be built starting from 1 to i gifts. Also, this is a 1/0 knapsack problem since you can either select a gift (1) or leave it behind (0).

Let us define a term M(i,j) as the optimal way of selecting gifts in a way such that selecting 1..i gifts brings the total weight up to exactly j. So your value of i varies from 1 to N and the value of j varies from 0 to C. Hence, the time complexity of the problem is equal to O(NC). (Basically, M(i,j) in a 2D array stores the number of gifts)

At every point, there are two ways in which the value of M(i,j) can be determined.

1. Check if there was a subset of gifts from number 1 to i-1 which formed a subset with total weight equal to j. You have the value M(i-1,j) as one of your candidate values.

2. Check the M(i-1, j-Wi) value such that adding the ith gifts weight gives us j. (i.e, weight of ith gift is Wi). This value plus 1 (because we pick up this ith gift as well) is another candidate value.

Now you simply have to take the maximum of these two values and place the value at M(i,j). In this way, you end up finding M(n,C) in the generated 2D array which is the required answer that our Santa Claus requires.

Here, you should notice how we built the solution for the problem in a manner similar to what we might do for a balanced partition problem. I will discuss this problem in the next post.

Stay tuned for more Dynamic Programming solutions. 🙂

Alternative numbers and characters in Linked List problem

November 10, 2011 4 comments

Problem Statement: You have been given a linked list of the following form,

1 -> 2 -> 3-> a  -> 4 -> b -> c -> 5 -> 6 -> d -> e -> f

You are supposed to convert it to to the form,

1 -> a -> 2 -> b -> 3 -> c -> 4 -> d -> 5 -> e -> 6 -> f

Ofcourse, the numbers and characters can be anything.

It seems to be a very simple problem to me. I am sure you would can figure out the O(n) solution for the problem as well. For those weak in linked lists, here is what you have to do.

Take 2 pointers, let us name them ALPHA and NUM. Now move ALPHA till you find an alphabet and move NUM till you find a number. Once you reach these, set your links in the required way so that the start becomes NUM -> ALPHA and move both pointers to the next nodes. Now repeat the same process.

Let us apply this in the above example,

NUM at 1, ALPHA at a, modify linked list to look like,

1 -> a -> 2 -> 3-> 4 -> b -> c -> 5 -> 6 -> d -> e -> f

NUM at 2, ALPHA at b, modify linked list to look like,

1 -> a -> 2 -> b -> 3-> 4  -> c -> 5 -> 6 -> d -> e -> f

NUM at  3, ALPHA at c, modify linked list to look list,

1 -> a -> 2 -> b -> 3-> c -> 4  -> 5 -> 6 -> d -> e -> f

Proceed in a similar fashion and you end up with the required linked list. 🙂

Bingo!

Given a binary tree, find a branch whose elements sum up to a given number.

November 9, 2011 1 comment

Problem Statement: You have been given a binary tree with integer values. You are supposed to find if a branch exists  (ROOT node to LEAF node) such that the sum of all the values on this branch sums up to a given number ‘x’.

Let us work on the above binary tree. Assume x=26. Now the correct branch would be 2->7->6->11. So the answer is “Yes, such a branch exists”. I hope you understand the question now.

How would you go about solving this problem? If the first thought that came to your mind was “recursion”, kudos! That is in fact the correct way to solve this question. (And usually always the technique you use in questions involving trees)

This time we go for a top->bottom recursion and keep adding the sum everytime we move down in a branch. Now as soon as you reach the leaf, check your sum and return 1 (success) or 0 (failure) accordingly. Here is the algorithm:

int Check ( Node current, int sum ) //initial call with Check ( ROOT, 0)

{

sum = sum + current->VALUE

If ( current->LEFT != NULL)

int left = Check ( current->LEFT, sum )

If ( current-> LEFT !=NULL)

int right = Check ( current->RIGHT, sum )

If (current->LEFT == current->RIGHT == NULL )

{ //in case of LEAF nodes

If (sum==x)

return 1

Else

return 0

}

return (left || right) //return 1 IFF we receive SUCCESS (1) from any branch, left/right

}

Pretty simple to understand, right? So for the first time in the blog, we have applied recursion and used it while going it from top to bottom (if you get what I mean). 🙂

Cheerio!

PS: If you are wondering why we don’t return as soon as sum exceeds ‘x’, remember that the binary tree is said to have integers, which means negative numbers are allowed. 😉 Attention to detail!

Shuffling Numbers

I recently talked about generating random numbers. What if you are given a set of numbers and asked to shuffle the numbers randomly. What are the different methods that you can think of? There is basically one method you should remember, because finally every algorithm will take you to the same basic thing, which is,

Generate a random number between 1 and n (included), where n is size of the given set. Now put the number at that position in your array in the first place. Repeat the process for the n-1 remaining places. The randomness of the shuffling here will be decided by your random number generator’s randomness.

(A method suggested by Fisher-Yates and multiple others as well. Big deal!)

That is what most algorithms to shuffle numbers are all about. You can ofcourse fine tune your method to give you your shuffled sequence in O(n). Some old algorithms tend to run for O(n*n), but those are just too stupid and you can easily figure out how to fine tune them to O(n).

Yeah, that was as simple a post as they come!

PS: I don’t have a lot of time right now to write a full-blown algorithm for some problem right now. Sorry for the gap.

Stable Marriage Problem

Please note before diving in: This is an algorithmic problem. If you land at this page looking for solution to something different, please visit a marriage counselor. 😛

Poor jokes apart, this one is another famous problem of the computer science domain. Here is how the problem statement goes: (source: Wikipedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

So basically you have to pair people in such a way that they have no better choice. You are given the preference list of each of the n men and n women and are supposed to give the perfect pairing. Now with no other conditions imposed, you can treat this problem as a simple greedy problem. Here is what your algorithm should do:

The algorithm will work in iterations.

For the first time, each unengaged man proposed to the woman he prefers the most (i.e., woman highest on his priority list). All the women would consider their proposals and select the proposal from the man who is higher than others on her list of preferences. They are now tentatively engaged.

Now in every iteration from now on, each unengaged man will propose to the woman who is next on his list of preferences. The women will compare all the proposals they are currently getting along with the one whom they are tentatively engaged to (if any). They will again select the proposal of the man who is highest on their list of preferences.

This process stops when all men are engaged after an iteration.

This greedy method was simple to understand and hopefully you would have got it by now. This is known as the Gale-Shapley algorithm. If anyone has any trouble in figuring it out, check out the gif animation below to see a sample case.

Brilliant! So you are now equipped with another algorithm to tackle your day-to-day marital, friendship and roommate related problems. 🙂

Have fun!

%d bloggers like this: