Thursday, July 10, 2008

"Brute force" as a last option.

Brute force is not a highly recommended method to solve a problem. But it comes handy at times, when you want to have a solution and do not care about the time and space complexity.

Often during interviews you would be asked for questions such as find the combinations, permutation, choices, etc for a given string/number. You are now being tested to think logically to get the combinations in a simple and effective way. An effective way is to split solution in to number of patterns for example: one pattern might have to do with reversing the locations of the previously considered number and the current number and continue to the next; another could be looping through only the positions that are even etc. Finally the combination of these patterns could give you the whole solution.

But even after thinking hard and if you are not very confident about the solution, then it is OK to ask the interviewer that does (s)he care about the solution or a solution with effective algorithm for time and space complexity. Often (99%) the answer would be yes give the solution first and I might ask you to improve the performance later. Remember you do not have plenty of time in an interview, so impressing the interviewer with a solution often would work. (But you must genuinely try for the best solution and only if not possible go to other options)

The easy way to apply brute force in a typical problem like permutation combination would be that,
Identify how many number of combinations would result first. For example: with the number 123 you can form 123, 132, 213, 231, 312, 321 are the possible combinations and it is as easy as 3! (Factorial -> 3*2*1 = 6). You must figure out the logic for the given problem to get the number of resultant combinations.

Build a dictionary (hash table) say a .NET dictionary, such that when the dictionary reaches the maximum limit of the number from step1 you are done with the combinations itself. Now how do you populate the key and values in the dictionary?
The key will be the combination itself; like 123/231/321 from the above example. To get that combination of numbers you can loop through a random number logic which will pick a random number each time, controlled by a limit. In this case it could be get three random numbers and if a random number is already obtained go and fetch another which is unique. After you keep repeating this and get the number, verify if that number is present in the dictionary or not, if not update the dictionary with the key and store a dummy value like 0 or 1 (unless you wanted some logic in the value field too).
At the end of iterations you will get the dictionary with all the combinations you need, but who knew off the CPU cycles that your algorithm consumed.

Applying brute force helps, but find a better way!

No comments: