String combinations using Brute force algorithm.

I have received requests in the past, to post answers for my interview questions (To find my interview questions, search for the tag "interview" in the right side pane under Ram cloud).

I thought let me write this one, string combination. One can find many different implementations through iteration to the permutation and combination of string in the internet.My code below; implements Brute force algorithm to find the string combination and prints them.

[The iterative pattern for the same, is considered to be one of the tough interview questions.]

Language: C#
Compiler: .NET framework 3.5
Platform: Windows server 2008, Intel Core2Duo X64.

// ****************************************************************************
//
// Copyright (C) Global Handler. All rights reserved.
//
// ram@globalhandler.com
//

// This file implements the brute force algorithm to find the string combinations.
// Note: The code is not warranted and not tested.
//

// ****************************************************************************

namespace StringCombination
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

///

/// Functionality to find the string combinations.
///

public class StringCombo
{
#region -= Variables =-

///

/// Dictionary to hold the unique strings.
///

private Dictionary stringDictionary = new Dictionary();

#endregion -= Variables =-

#region -= Constructor =-
///

/// Constructor of
///

/// The input string.
public StringCombo(string givenString)
{
if (String.IsNullOrEmpty(givenString))
{
throw new ArgumentNullException(givenString, "The given string is either Null or Empty");
}

//Find if the given string has unique characters
if (!FindForDuplicatesInString(givenString))
{
throw new ArgumentException("The string contains duplicate characters, please enter a string with unique characters");
}

int dictLimit = FindTheFactorial(givenString.Length);

GetTheCombinationsForAString(givenString, dictLimit);

PrintTheStringCombinations();
}

#endregion -= Constructor =-

#region -= Private Methods =-

///

/// Method to find the unique string combinations.
///

/// The given string.
/// The maximum combinations.
private void GetTheCombinationsForAString(string givenString, int dictionaryLimit)
{
Dictionary dictionaryForControllingRandomValues = null;

do
{
dictionaryForControllingRandomValues = new Dictionary();

do
{
DateTime currentDate = DateTime.Now;

Random rnd = new Random((int)currentDate.Ticks);

int number = rnd.Next(0, givenString.Length); //max number is the input string length.

if (!dictionaryForControllingRandomValues.ContainsKey(number))
{
dictionaryForControllingRandomValues.Add(number, givenString[number]); //char at the given index.
}

//repeats until the count of dict reaches the input string length.
} while (dictionaryForControllingRandomValues.Count != givenString.Length);

StringBuilder sb = new StringBuilder();

foreach(KeyValuePair stringForAddingToMainDict in dictionaryForControllingRandomValues)
{
sb.Append(stringForAddingToMainDict.Value);
}

if (!this.stringDictionary.ContainsKey(sb.ToString()))
{
this.stringDictionary.Add(sb.ToString(), null);
}

//repeats until the string dictionary count reaches the maximum combinations expected.
}while(this.stringDictionary.Count != dictionaryLimit);
}

///

/// Method that finds if the given string contains unique set of characters.
///

/// The given string.
/// Result of evaluation.
private bool FindForDuplicatesInString(string givenString)
{
Dictionary duplicateCharTracker = new Dictionary();

for (int i = 0; i < givenString.Length; i++)
{
char value = givenString[i];

if (duplicateCharTracker.ContainsKey(value))
{
return false;
}
else
{
duplicateCharTracker.Add(value, null);
}
}

return true;
}

///

/// The method that prints the string output.
///

private void PrintTheStringCombinations()
{
foreach (KeyValuePair uniqueString in this.stringDictionary)
{
Console.WriteLine(uniqueString.Key);
}
}

///

/// Method that gets the factorial.
///

/// Lenght of the string.
/// The factorial value.
private int FindTheFactorial(int lengthOfString)
{
if (lengthOfString == 0)
return 0;

int factorial = 1;

for (int i = lengthOfString; i > 1 ; i--)
{
factorial *= i;
}

return factorial;
}
#endregion -= Private Methods =-
}

class Program
{
static void Main(string[] args)
{
StringCombo stringCombo = new StringCombo("abc");

stringCombo = new StringCombo(null);

stringCombo = new StringCombo(string.Empty);

stringCombo = new StringCombo("aaabc");

stringCombo = new StringCombo("12345");
}
}
}

--------------------------------------------------------------------------------
For any questions and comments, please log the comments in the blogpost or alternatively email me at ram@globalhandler.com

Adding the below approach from the comment section:

say you are given a string "abc"

now, make 2 strings (clone and combine & reverse, clone and combine)
abcabc and cbacba
read out them like
abcabc -> abc, bca and cab
cbacba -> cba, bac and acb
combine them
abc bca cab cba bac acb

You know, space is no more a constrain for devs its the parallelism that matters - all that we can do is fork two threads to read them out.

This could very well be tailored using Map/Reduce for large scale clouds and clusters.

Choosing what you worship

I was confused looking in to the program "god vs Satan" in the History channel, the confusion is that most of the major religions treat snake/serpent as the first incarnation of Satan in this world. But Hinduism treats snake as god, at least a considerable sect of Hindus do so. So is Hinduism a contrast to others?
I was curious to know why is snake worship followed by Hindus?

I started my search in the search engines to get more answers...

And from what I read I was able to deduce that humans tend to submit themselves to the ones that are mightier in some way to them. A snake in nature is poisonous, but humans are forced to live in the same ecosystem as the snake, this creates the classic problem of man vs animal and who survives over the other?. In almost all the cases in the present days we win, but that was not the same in the olden days. So humans developed a habit of pleasing the ones that they could not withstand.
To give an analogy, If I were to fight a boxer, either I have to die or please him for my survival. And guess what, humans wanted to live and chose the later. This practice put them to please the snakes and treating them as gods.

More on animal worship - http://en.wikipedia.org/wiki/Animal_worship

Why so many definitions for one? Cloud computing.

There are hundreds of definition for cloud computing, lying around in the internet. I was just wondering why do people give so many defitions for the same thing.

Only after couple of minutes, was I able to figure out that the definitions are targeted for different audience, and not necessarily defined because of the people who were involved in creating the definition could not understand/get it correct.

Then I thought of a common example, rather than a technology.

It's like if I were to define an elephant, one could say it is a animal > mamal > and go on to define it's properties/attributes like it has legs, tusk, eyes, etc. Another definition could be that, an elephant is a domesticated animal in the temple, which is a vital part of the ceremonies in the temple. The later definition is just a subset of the earlier definition. The later may well fit the definition of an temple elephant but not the elephant as a whole.

Now the analogy, the various subsets of the cloud computing could be,
[1] Building data centers and running software to be consumed.
[2] Running all the applications online and using browser as the interface to work.
[3] Flexibility to store any of your data, somewhere in the cloud and pull it out as and when required.
And there are much more of these definitions, let me leave it at that.

The three different definitions of cloud computing above, are all like defining what a temple elephant is. The definitions itself could not be called invalid, say the audience for the definition #2 could be the end users who do not have to worry about the data center or virtualization or what goes behind or beyond their scope.

But for a company that is part of the cloud computing paradigm, all the three definitions are subsets of what cloud computing is in a whole.

Levels of programming, based on design principles.

Just a small writeup based on the programming design style, that I commonly come across with various programmers.
To give some context, let's take an example of creating an object called car (automobile).

Level 0 programmers are those who think, writing more common code is better and generalize them in to static methods that take numerous parameters.

public static void CreateACar(Engine engine, Color color)
{
//rest of the code here;
};

The problem is if the car needs to be created with a new property like sedan/coupe, then a new parameter needs to be added and this keeps growing. If the arguments grow then they add a structure to encompass all these arguments and pass them.

The next level of programmers are those who treat each of attribute of the object as it's property and create a class like the below:

class Car : IAuto
{
private Color color;
private Engine engine;

public Engine Engine
{
get
{
return this.engine;
}
set
{
this.engine = value;
}
}


Public IAuto CreateACar()
{
//rest of the code;
}
}

The above code works great, even if there are new parameters to be added. It is as simple as adding new properties and verifying them before creating the car. But some assumptions have to be made, say this car runs on a "road" and the car creation assumes the road to be some type (could be Enum) and ties the object to it. What if the road's condition changes and a car that code run while creation cannot run all the time on the road. Some cases/scenarios while creating the car is missing and it does not cover all the situations. This is what happens when the object is strongly tied and has lot of properties.

The next level of programmers are for making functionalities atomic with individual classes and then tying them together based on the scenarios or rules. The rules defines what goes in creating the car object.

say it could be class Road, class Car, Interface IAuto etc.

Looks like more classes that has smaller functionality. Yes, exactly these are all small dumb classes and are atomic. But when combined with the rules and scenarios that change time and again, they come in handy as they are very flexible and requires less change.

Take the .NET library, it exactly fits the last design model discussed, more dumb classes combined together giving a great flexibility and power for creating more applications.

This is a followup of my initial design post - http://globalhandler.blogspot.com/2007/05/software-design-goals-and-philosophies.html

Windows and services for the cloud

Microsoft Azure!




Ray Ozzie: Reflections on Azure


The technology behind Azure.

A developer look at Azure.

some useful links for setting up your Windows server 2008

setting up your windows server 2008 as workstation

Live mesh installation with Windows server 2008.

Want to know what is Live mesh?

Brain Threa(t/d)s - could be read as threads and threats!

This post is about controlling the brain to send neural waves to perform a desired action. This is not something new, but here are some unwinding topics.

Thought control headsets are used in virtual worlds for gaming. These headsets pick the brain signals and transform them in to actions.
Now let's see how can the same be put in to use in a real world.

There are numerous tests going on to identify, how the actions derived from the brain signals could be applied to the real world. In a virtual the environment is controlled, which means the actions are just simulation that is perceived by the users. Hence there is no real damage in the case of a ill action being performed. But in a real world the game is different things are real and the actions carried over will have real impacts. The human brain is known for its humongous parallelism. So how does this parallelism help or affect the actions in a real system?

So what would happen, If anyone can get on to such a brain controlling system operating (in a real world) and perform the intended actions?

To give it a shot with a better example,say if some one wants to control car driving using the brain signals.
Well, there must be a system to take care of the mind vs body reactions (heart rates etc) and then apply the actions. Based on the actual brain signal the system can decide whether or not to perform the action, to control the ill effects. In any case you would need a controller for controlling the brain signals.

So this brings the question, Is the human brain not yet mature or over mature?
Does that also mean the human brain's thought(s) are indomitable?. I could just think of techniques like meditation that would help one to focus on the brain control and help achieve what is just intended in a situation throwing the rest away. Conclusion here is, taking the risk to perform the above experiment needs to start with in some controlled environment.

To illustrate the power of the human brain and it's parallelism, here are some facts:

http://www.merkle.com/brainLimits.html
http://www.dailytech.com/Visual+Circuits+Harness+the+Power+of+the+Human+Brain/article12478.htm
http://www.transhumanist.com/volume1/moravec.htm
http://www.livescience.com/mind/
http://news.bbc.co.uk/1/hi/technology/7254078.stm

Soon to be born, with communicator

It will be no surprise to see communicator chip(s) injections. These injections will be used to embed the communicator chip(s) to the human bodies. And everyone will be a cyborg. No later will the new born babies be injected with these chips along with their regular vaccinations.

This embedded chip will bring in features to talk freely in any language (there will be real time translation), no extra hardware for making calls. You just have to think, it dials to the satellite and connects to another human/chip. No more hassle of service plans from different providers.

Just thinking on what more could be added here...?

search tip.

When trying to find a tool usage, I was stubmling on how to write a phrase to get a better search result.
prelude:
I was trying to build a csharp (C#) class file using the xsd.exe tool. The tool takes in the input schema and generates a proxy class for you.
I had the schema dependent.xsd, which depends on provider.xsd. I need to know how to use the tool to consume the two schemas and generate the class. (The xsd.exe /? itself did not give the info, and I had to go to Google/Live)

I tried the query "xsd.exe /c a.xsd b.xsd", and I got the search result that I was looking for. Simply replacing the names of the files to the most simplest usage helps. It is worth trying such queries with the naming conventions "a,b,foo,bar" rather than thinking on what to write. Just my 2 cents.

I give up!

Not long before I jumped in to the geeky world. One cannot continue to live unless having updated with the inundated wealth of information. Oh that’s new you must learn it; you will be a most sort after guy. Oh no the other one is coming up you must learn that too, yep learn everything. But you cannot and you will not, is what I realized after it was already too late. And finally I gave up.

Stop all the non-sense stuff no more information can enter my brain, it is jammed and the memory is leaking. And people call me Ram (Random Access Memory), knowing this poor creature can store only less and that too not permanently, self pity?

Does the buzz of IT remain all the way same in the future? How could these people continue to invent what they invented in different ways and keep the wave of buzzing alive?

Ooops, did I sound correct? As in computers we have object oriented programming ....s for???, I do not know what does‘s’ stand for. How the hell can I forget the basics? don't tell me you work for the biggest software company.

My friend(s) come with different topics of books, hey you must read this to write solid code, complete code, secure code, and a year after with solid code II, complete code II, secure code III (The III was intentional, if you have wondered btw. And I'm sorry if I have missed some other code(s)) . All I’m gonna write is one code and why do I write it in so many different ways, to keep the code reviewers happy? Well maybe.

I understand the megalomania, as the world moves there are new IT happenings and we make it happen otherwise the world will not move. I see the vicious cycle now!!!

My rumblings :(

Do I write this blog post? I’m going all the way ironical doing so. Using the computer which I wanted to get rid of almost daily or if not so badly this week. Watching myself like an idiot, starring at the code and taking the spiting’ and puke’ of the visual studio IDE. Horrible isn’t it?

I am almost glued to this piece, do I have control or is it controlling me. Oh now I know, all the AI based movies like Terminator, Matrix are masking my brain or may be mind, huh whatever it is. Days are passing and moments are grinning, yet the sorrow continues in boredom and misfortune. Oh my god when do I get out of all these miserable stuff, am I cursed or is my karma taking me this way. I have become a grudger to the core. Oh no enough stop these rumblings tells my mind, but my computer is pulling me in to do more write up.

Enough, this time certainly! Thanks for all the associations and sharing the grievances. Now get back to work. OK Ok just read one more statement and I let you go.
No you guessed it wrong, I ‘m not writing this after a day long work, it is the first thing I have done today. What a refreshing start!!!

Has Chrome got the metal to move IE?

seattletimes.nwsource.com
www.mercurynews.com

@Velu has to say the following: (From the comments section)
Chrome is just a rip of Opera - from the Speed dial to the + button for opening the new tab. Then the devs thought they are doing injustice by just copying opera and hence picked a few from IE8 too like domain name highlighting, omnisearch and "Launch browser windows in a new process" ...

This would be a total flop release for the very reason that it lacks novelty and performs just as good as Opera7.

VS2008 SP1 RTM stops intellisense from working

Recently upgraded to VS2008 SP1 RTM, as I wanted to try SQL server 2008. VS2008 SP1 is a pre-req for the SQL server installation.

After the installation, I opened my visual studio IDE to see that the intellisense stopped working. After a day's struggle found that the Text Editor->All languages setup was screwed up like below.

Navigate to Tools->options->Text editor->All languages and just un-check and re-check the last three check boxes. Now the IDE behaves as expected.

Random number C#.NET

The following code tries to get all the possible numbers in the given range(continuous), by implementing a dictionary that keeps track of the uniqueness and the total count.

Random rnd = new Random();
int max=10, min = 1;
int maxCount = max - min + 1;
Dictionary < int, int > finalDictionary = new Dictionary < int, int > ();

while(true)
{
int newValue = rnd.Next(min, max);

if (!finalDictionary.ContainsKey(newValue))
{
//New key not found in dictionary add it, provide a dummy value
finalDictionary.Add(newValue, 0);

//Stop here, reached maximum
if (finalDictionary.Count == maxCount)
{
break;
}
}
}

Note: The above program runs infinitely, beware of out of memory!

Apparently .NET framework does not generate the max number in the range. After all MSDN says, the random number generator is not completely random. Albeit, what I do not understand is why doesn't the framework able to get the last number in the range at least once?.

If you want to over come this situation you can go by two ways,
(a) Increase the range by 1. example: make max=11 in the above case or
(b) Keep the maxCount as max-min (instead of max-min+1) and exit the while loop. Finally add the last number to the dictionary.

Revitalizing Live

Live search is remarkably being revitalized with better interface. Just navigate to live.com and search for any video. Mouse hovering on the results plays the thumbnail clip and it is seamless. I love the improvements made to live search.

Google maps gets better with camera - see the road before you drive

Click on the camera icon in the route map and play with the road!

For the fellow bloggers

I came across this interesting website http://www.blogherald.com/, read the blog disclaimers it was very helpful.

If not integrate then sync and vice versa

A lot of the technology companies are driving forces behind synchronization and integration these days.

Reason for synchronization and integration: We are clearing up the mess we generated by experimenting and developing ubiquitous things in the past decade(s). No, I didn't mean to say we should not have experimented or tried things. One part that lead us to the state is the human nature to create a unique footprint for themselves. (which resulted in many different devices doing exactly the same thing)And the other part is choice; which is very important, everyone needs variety and that is the reason for the so many flavors of the same products. We have hundreds and thousands of phone models, may be hundreds of TV models, and the list goes on. But what next?

When on the one side we are thinking to create new devices (I mean novel); on the other side we are trying to make the existing devices work better, predominantly making the existing devices works better amongst themselves and not as stand alone. (To me, the known devices are working well enough as a standalone)

So what does synchronization have to play here? Well synchronization is the way of making things look seamless and sharing the data across devices and platforms. Based on the situation a user chooses what to use, but would always want to stay updated. Meaning, if I receive a mail to my mail account and if I were at travel I want to see the message from my mobile phone.

The other part is integration, making things simpler in the front and adding complexities in the back. The devices that are built are integrating different form factors in to one and increasing their capabilities. Your TV is as intelligent as your PC, and your PC can do a lot of work as a phone and your phone can have a mini pc and a TV in it. So every device is adding a feature from other devices or the other and becoming SMARTER.

A good example for synchronization product is Apple TV and a good example of integration is smart phone.
But why two ways to solve the problem of many devices, well we like different flavors don't we? Part of the answer is yes, the other would be, we have done so many things that cannot be ripped off right away.

Things that cannot be integrated are being synchronized and things that cannot be synchronized are being integrated.

IT is a one world in many and many in one world.

Google shopping search - errors for WallE

Last week I had a chance to see Wall E, amazing movie from Disney Pixar duo. I enjoyed the movie and could not stop appreciating the creators.



I wanted to buy the WallE toy, and tried Amazon, Live and Google.

Live product search could not understand "WallE toy", it returned me two pages of search results that were not related to toys. It seems Live can only understand "wall e" or "wall-e", does not live up to expectations.
Then tried Google shopping search for "walle toy", obviously I saw huge set of search results. Then I sorted by price:low to high, waiting to see the affordable ones that I can pick. The search page started with $0.10, I kept naviagting to the next 10 pages at a time (Google also populated a set of new 10 pages at a time). When I was at page 73, I saw the link until 82nd page as below.

Then I tried to navigate to page 82, it resulted in a error. I tried the lower (< 82) pages and figured out the links were broken. It worked only until the 75th page that had the last item priced at $2.99. The first search without any sorting resulted in a $49 item, which I did not see in the sorted results. This was not just a one time issue, I was able to reproduce the same issue multiple times!


This kind off keeps me happy in a way, "software engineers still have work to do".

"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,
step1:
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.

step2:
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!