Thursday, May 17, 2012

To decide whether the stream of 0 and 1 is divisible by 3 or not

Problem Statement :-  Stream of bits are being received on a network port. As obvious, each bit is either 0 or 1. Incoming stream is a never ending sequence of such 0's and 1's and we want to check at any given time that whatever stream received so far is divisible by 3 or not.  So let say we have got 110010101000101....0, then we want to have an answer ready for whether the decimal number formed by taking this input will be divisible by 3 or not. Least position value is the latest/last bit received.


As soon as port starts receiving the bit values, Use the first three bits to decide whether its divisible by 3 or not. If its divisible by 3 then consider it to be at state "3x" else based on the reminder consider it to be "3x+1" or "3x+2" state. For example if first three digits are 110 then its equal to 6 and should be considered as state "3x" else if its 111 then its 7 and should be considered as state "3x+1"(for 7 = 3*2+1).

Now we just need to follow the state transition diagram below to keep track of on which state we are right now. As depicted by the State Transition Diagram, State change happens based on considering the next bit arrived. for example if we are at state "3x" at any given moment and we receive 0 as next bit then the new state we are in is state "3x" only....But if we get next bit as 1 then we move to state "3x+1". This way, no matter how many bits have been received so far(million...trillion or whatever..) we just need constant space to save the current state. Now, If at any point someone asks that if the sequence of bits received is divisible by three or not....We just need to see the current state and if its "3x" then its divisible otherwise its not. This logic can be extended for checking the divisibility by any number and not only three. Its a classical example of usage of DFA or Deterministic Finite Automaton.


Why this state transition diagram is correct? If we have a number divisible by 3 and we get one additional bit at the last as 0, then its simple left shift which makes the number to get doubled i.e. its still divisible by 3 and hence the state is named as "3x" as this number can be represented by 3x for some positive value of 'x'. But if the new bit is 1, its double the number and adds 1 to it making the remainder as 1 when the number is divisible by 3 and hence the state name is kept as "3x+1". same argument follows for state "3x+2".

Friday, March 25, 2011

The Biker's Freaking Mind, Cabs and Interceptors

4:50 AM…. pleasant morning…. Bangalore airport…

I closed wiser of the helmet…tighten the flap of my gloves…some movement in my hands and my black beauty wake up, staring at me for my next command… she was excited and so was I.
I pressed my gear paddle and a sweet melody of her gearbox made me remember about all good time we have enjoyed in past.

From last one month or so, I was not riding that frequently. All sincere thanks to our company’s cab facility. But with all new environment and load of work at my new company, I never got time to think what I was missing …that was my daily rides with her. She never complains nor do I try to get into any conversation. But today she is in great mood. I was riding her past 60KMPH when I came out of the airport area and hit the high way.

There was very less traffic and that made us a bit greedy. I accelerated a bit more and she touched 80KMPH mark. As she started rolling fast on the road, my freaking mind started rolling back in to memories of my last bike trip. It is more than 6-8 months now, we three friends planed for COORG trip. In fact, it was Nayan sir and Sanjo(please use American accent to pronounce ;) ) who did all the planning. It was a great trip…. everything went smooth and we enjoyed a lot. It was so well planned that we never felt any type of tiredness, what so ever. Plan was simple…. daytime: - ride and site seeing and nighttime: - booze and sleep ;) . We never tried to ride late in night nor did we booze in daytime i.e. before riding…. Coorg is awesome place and the occasional heavy rain were refreshing at times…. but most of the time, it caused lot of inconvenience only but that is part and parcel of excitement on road and in any case, our trip was all about enjoying nature beauty! Well that was the only intension but that never stopped us from praising any other beauty in our way ….and please don’t get any ideas, it was just to put some smile on your serious face ;) :P We had lot of photo sessions and video recordings on the way…all thanks to our no-so-bad photographer/cameraman - Nayan Sir (I hope that some how, he skip reading this line otherwise he will never click my photos again :P ). Hey, he even promised to write about this trip but I never heard from him on this……zoooooommmmmm….A high speeding cab just over took me from my right….though it was quite far from me, but its high speed was enough to bring me in present…I looked at my speedometer – 80KMPH and thought that the cab must be at around 120-130KMPH…..am I riding SLOW!!!!

I accelerated…and the free road gave me full freedom to go past 110KMPH in no time….I don’t know how but suddenly a deadly thought invaded my already shaken mind “wowww, its time to go for my personal high speed record!”. With this beautiful thought, I could not able to stop myself from thinking about my fast and furious Chennai Bike trip with Patwal sir….In 24 hours we went Chennai and came back …..Around 800KM, taking the fact that Chennai is 350 from here and we had rode quite a distance within Chennai too. That was damm tiring trip boss… we started late in night and rode overnight to hit Chennai in 5.5 hrs which includes our 2-3 half an hour breaks!!!
The most memorable part of that trip was my eagerness to hit the top speed possible with Pulsar 150cc. It was Patwal sir’s new bike and both of us tried our best to reach the highest but never able to cross 116KMPH mark. And then came a stretch where I was riding and speedometer touched 123KMPH…I was so excited that I kept the acceleration at full to see if it will go further but it didn’t. Nevertheless, I was happy to touch that high speed and also show it to my pillion rider………

OOOOOOhhhhh NO…as I came out of my memory lane, I saw at my speedometer and it was 132KMPH…It could have went well above it in few more seconds but Sadly, I had to press break. I don’t know from which part of the universe, around 10-20 cabs suddenly came on the road as if it’s some political party rally! Best part was that all were Meru cabs and all were driving at around 80 KMPH!!!

Shittttt….not again ….I was thinking to get my new highest speed today…Plan was to hit above 144KMPH as this is what Bajaj claims as highest speed but I am confident that highest will go around 150KMPH.

I was furious and more than that I was curious! What the hell is going on…how come these many cabs are going together and that too with almost same speed i.e. 80KMPH? It seems that all of the drivers are inspired from Dravid’s style of batting: - Even if it’s flat pitch and ball is nicely coming on bat, try to play defensive…. Or may be some traffic police squad have broken 20-30 bamboo sticks on their bums!!! But little I knew that soon, I was going to be thankful to them.

Mystery Solved, Within 100 meters I saw an Interceptor, Police vehicle that is deployed to stop and fine (plus they will loot :P ) high speeding vehicles on highway, was standing on extreme left of the highway. Suddenly I realized that how lucky I was, thanks to these cab drivers. They knew that Interceptor is waiting out there…Great sigh of relief. After that I kept my speed at 80KMPH only and not to my surprise, 2 more Interceptors were seen in next 5-8 KMs, waiting for some prey like me. It seems that I am getting quite famous these days...or it should be infamous! ;)

I was entering my locality highway, bole toh, main road of it…stopped at tea stall for favorite recipe we have in our bike trips: - Tea and ciggi . It was 5:15 in the morning…its still dark but I had lost my sleep somewhere on Highway and was feeling very refreshed after such a cool bike ride. For the 10th time, I took the vow that I will never ride with this high speed again. I wanted to sleep but could not resist myself from writing and result is this small boring to read, blog….Hope that you all who have read till end will spare me, taking into account that I am not at all a student of literature ;) :P

7:47 AM….Still pleasant morning ….Bangalore city

----Signing Off

Saturday, May 8, 2010

Choosing between Abstract Class and Interfaces...

Before I take the topic head on head, let’s understand, or I should say re-understand, what an object oriented programming language has to offer and why it’s preferable in most of the real world software development cases. While citing advantages and positive aspect of java in particular and Object oriented programming in general I would not consider any serious comparison with the procedural languages like c etc. As I believe it may be out of track for the topic I have chosen. As we all know we can model anything which we can see/feel/foresee/want to see etc as an object, this is how our world is planned or organized.... Confused! Lets take some instances....
I say I am working with a ‘private company’ called ‘NDS’. Look at the lines, that how we mostly tell to the people who ask us what we do? Do you see the important words... What exactly we have done in this sentence. We said we are working with a ‘Private Company’, which is a type of classification for generalised thing called ‘company’. So we can model the hierarchy as follows:-

Company --------> Private Company ---------> NDS

But do we see any of these in real world? I mean show me something just an entity called Company....You will beat me till I die for asking this question :P.
But If I ask you to show me anything which can be considered as private company..then you can show me a lot of these. Right! Same goes true for Company also....you can show a lot of real life entities which can be considered as Company.
So we know that though we cannot see PrivateCompany itself....We can see something which is a TYPE-OF PrivateCompany and hence, a TYPE-OF Company.
Now while modelling this relationship in programming can we make an abstract class called Company and an other Abstract Class PrivateCompany extending Company. Now we can make a concrete class which can be instantiated as NDS. Its very very simple description of what can be done as we are not considering behaviour of the Company and PrivateCompany nor we are going deep into analysing these but then also we can see how easily we modelled the real world scenario in an object oriented design    . This is what we lack in procedural languages :- Easy and simple modelling of real life objects in coding/design. This is one of the good features which OOP offers and it is one of the biggest reasons why OOP is so famous in software development community. So we are done with small and sweet warm up and time has arrived to go into deep with the concept of Abstract class and Interfaces in OOPs

What is an abstract? Well, most of us misunderstand the meaning of abstract as far as programming is concerned. Think what abstract means in day to day life? Remember our standard 3-4 english questions
“Give an abstract of your long journey on a train. 4 marks” ;)
In simple words, Abstract means brief description/ part of /summary . What we programmers think about abstract is ‘hiding’. We think that anything has been made abstract for hiding but true is that something has been made abstract for ‘exposing’ HOW? Let us find it out. See above English question, it meant that you have to write a brief description of any of your long train journey. When you write that what you do? You hide the information or you expose the information? You expose the information.....right! But you expose only what is IMPORTANT and REQUIRED. Same goes right for programming, when you make something abstract you actually expose it to the outer world for implementation but at the same time you strictly tell them what the method/class is supposed to do i.e. signature and leave it to others on how they want to implement them. Amazed!!!

If you have got this meaning of ABSTRACT correctly, you will find things pretty simple and easy from here. One thing which we should never forget is that both Interfaces and Abstract Classes are using ABSTRACT concept i.e. expose the usage and leave the actual implementation. If you want an Interface then make any abstract class or concrete class pure Abstract i.e. only expose the signature (and eventually the expectation i.e. expected end result...) but not the implementation. I am not going to tell the syntax of abstract class or interface here, rather I expect you all to be well versed with it.

Everyone knows HOW to write and WHAT to write while writing interfaces and abstract classes. Let’s talk about WHERE to use and WHY to use these. “Life is simple, only we make it complicated”. So before I make it a bit complicated I should give the simple rule which can be consulted while thinking about interfaces and abstract classes:
Well, the simple rule seem to be a bit complicated in itself so let us go for complicated description to understand this simple rule ;) ;) ;) just kidding....Let us elaborate the rule. I am sure that if I will be able to explain this rule appropriately then only thing you will require afterwards is this simple rule and not the description 

I born as a Human Being and it have been confirmed by the world that I am a human being as I fulfil all criteria of being an Human. So the only thing which the outer world was aware of me is that I am a human and hence they expect me to behave purely like human. They knew how human behave or what human behaviour should be. How? Because god has published API’s and java doc for human class :P :P sorry...I mean the world has seen human for long. It knows how human look like, how they conduct, how they talk, and other such complicated behaviours. It is more or less like knowing the API doc for human class. You know that if you are going to give milk to human and if this human is hungry it will drink it using its hand and mouth unlike any Dog which will use only its mouth/tongue.
Most of you have already got this point that if there is some class which I may belong to is human. But human can be again classified accurately among three categories and I will be taking only two of them for this example. MAN and WOMAN. I am a boy and I will fall to Man category. Human class should be concrete as Man and Woman seems to differ a lot and are more complete classification than Human itself. So what we can do is that we can take common properties of Man and Woman, Put them in Human Class.But Man and Woman completely divides the whole Human in exactly two parts and after this classification there will be none left which cannot be put either under Man or Woman. So what I am trying to say is that all Human are going to be either a Man or Woman i.e. We will never need to instantiate any object of type Human but only Man and Woman. So here We got the reason to not keep Human as concrete class as someone latter may instantiate it and it will be against nature law and hence We will have to make it abstract class. We got our abstract class called Human which will be extended by the concrete classes Man and Woman. GOOD ENOUGH....BUT QUESTION IS WHY CAN NOT WE MAKE Human AN INTERFACE AS IN ANY CASE WE DO NOT REQUIRE IT TO INSTANTIATE????
Here comes the first part of the rule which I gave early.
Abstract Class is what the object will born like and will eventually die like. I born as Human but can I die like tiger. NO ...No way Its not possible. Once born as Human I am going to remain or remembered as Human forever. This identity of being Human is tightly coupled with me and I cannot change this fact. Same goes for the code. Once an object has been instantiated as a type of a class, it should and it will be always of that type. If you will try to play with its original type then chances are there that you may corrupt the whole design and may get exceptions like ClassCastException etc. Interfaces do not contain any implementation but we know that Abstract Classes can have some implementation. There will be a lot of common code in Man and Woman which can directly got to Human but it is only possible if the class is an Abstract Class. Then where to use interface?
I am a man, so what big deal!!! Think what all we did right from the childhood till date. We went to school, college, played cricket for school team, started working in a PrivateCompany etc. So should these all functionality like playing cricket, studying etc. Should go into Man class or Human Class? Well not definitely in Man class as Woman also does similar activities. Then in Human abstract class should contain all these....But i know a lot of human who does not do any of these or some of these, and if we keep at Human Abstract Class then through inheritance all will get these which is not at all right! Okay then what to do?
Let’s analyze the problem, what we did when we went to school....Studied. What noun can be used for us when we were studying in school? STUDENT right? No matter a girl or a boy, in school we have been referred as Student. Can we say that we played the role of a student when we were in the school? Yes...and similarly, we can say that we play role of a son, employee, student, teacher, actor, model etc.
Now remember the second line of the rule.
So we have our reason to make an interface each for these all roles which we play for short or long span . We may have an interface called Son which will have abstract methods applicable for this role. Now only those who may play this role can implement it. Man may implement this interface but can Woman also do the same....hmmmm not exactly. They may require a new interface called Daughter.
These all roles does not put any implementation but leave it on other classes to implement. Lets say that both Man and Woman has implemented Student interface and there be a method wearSchoolDress(). Now do you think that both will wear same dresses :P :P nops... So its upto the implementing classes that how they want to to something but at the end they should stick to the API signature and expectation. For example, though boys will wear pant, shirt, tie, shocks and shoe but at the end of the API call they should be well dressed   otherwise they will be sent back from the school :P :P.

With this example I would like to conclude the blog. I would love to know more on this from the readers of this blog and will appreciate any piece of suggestion whole heartily.


Wednesday, August 26, 2009

Approach to Estimate SQL Query RunTime


This blog is not from an expert who claims to know everything, but is from a curious developer who wants to find a way to know more…

The abstract, written here may sound really weird to experts, but at the same time they may feel good about the curiosity I have for the subject.

The content of this blog is just a theoretical/conceptual description of the solution, which uses the concepts of statistics and mathematics.

Please feel free to add your comments/criticism, so that we can either discard this whole theory with some other suggestion from the readers or move forward in order to implement this theory in practical.

Thanks in advance for your comments/criticism, if you bother to write one….


To estimate the time, which a query may take when we execute it over a huge database.


Divide and Rule, Sampling, Basic Mathematics


Assumptions: We have updated estimate of the size of sample space.

Lets, say we have a finite sample space (S1)

And there be an experiment (E) that we want to carry out on this space.

(S2) be a sample space and has been derived (randomly or intentionally, based on our requirement) from (S1) in such a way that (S2) divides (S1) completely.

i.e. There be a finite number (N) of (S2) sample spaces present in (S1) and completely constituting (S1).

We can denote this relationship as

(N)*(S2) ~ (S1)

Now, lets say that (T2) be the time required by the experiment (E) in order to get executed completely over (S2).

(This, we will calculate by executing the experiment (E) on (S2), as (S2) is very small so response time should be very small too.)

Now based on relationship (N)*(S2) ~ (S1)

We may say that if (T1) were the total time which experiment (E) would have taken, if it would have been executed completely over sample space S1 then

(N)*(T2) ~ (T1)

And if we have a constant (C)(behavior of which should be defined latter), then we can say that

((N)*(T2)) – (C) = (T1)

Proposed/Hypothetical Practical Use:

Think the whole table/tables on which we want to run the query as sample space (S1)

Constitute (S2) based on it

(More explanation on how to derive should be properly discussed/ would be given latter, as it is only the first draft of the abstract of the concept)

Run the query on (S2) and get the Time (T2)

Since (N) will be known so we can estimate the time using the formula above.

Constant (C), need more research to decide and is expected to vary for a particular type of DB etc.


The proper consideration of database behavior has to be concerned

Need to research a lot before going for practical implementation (Which in turn will require proper Time and tools)

The theory is very simple and not at all takes into consideration of a lot of related factors, which may come into picture while implementation.

Active participation from experts/readers who really want to solve this problem, which, at most of the sites, has been declared as not possible to break.

List is long as it is just the first draft…let see, how is the response from you guys!

Saturday, July 12, 2008

Greynets ……as we call them.....

So far the blogs I have wrote were not directly related to my field … but this one is tightly coupled, if not the only reason, with our company’s short and long-time goals. Before I start I must admit that I m not very old in this field and that’s why, I will write only what I have learned so far. If you find me at something which sounds wrong to you, I will love to know that via your comments…and I promise that I will not feel offended…. instead I will appreciate that

Greynets ……as we call them.....

You can get its proper definition on Internet, so I will just give you a brief introduction of it. Greynet sites are the Internet applications, which generally does not create a direct threat as far as security is concerned but is very evasive in nature and that’s why it’s a subject of worry for companies. As you can see its name itself tells you something very important about it. “Grey”, as far as I believe this prefix may have been used for these sites because of their unpredictable behavior and unpredictable threats they offer. Might be because of the reason that people are still researching on them and by the time they unravel some of “grey “ parts related to these sites….. Their creators add on many more of such unanalyzed patches. So far its sound a bit confusing !!! don’t worry, I will explain it…step by step, But in short

Lets start with the examples of greynets and disadvantages (at corporate level). Orkut, FaceBook and social sites like them are famous examples but greynet sites not only constrained to them but includes much more than social networking sites. Greynet sites are really entertaining if u will consider an individual…. for example, social networking sites provide a good opportunity to be in contact with our old pals (and much more than that…). If you will ask individually everyone will advocate in the support of these sites…even I m a big supporter of these sites and enjoy being online on them.

But, Now change your angle of view and think from the point of companies!!! Although these sites doesn’t poses a security threat for any organization…hardly u would have heard that someone did “data theft” using orkut!!!! Rite. But look at network level. Besides killing the valuable time of employees (which could be otherwise very productive…) it just slaughters the bandwidth. Believe me bandwidth is as important for any organization as its network itself. I mean, what is the benefit of having a good speed network connection on which half of traffic is for unproductive purposes!!!!

After citing the examples and disadvantages in as short as possible, I will move on explaining the “grey” areas involved in these applications particularly in social networking sites. After understanding that next buzz in Internet security will be Social Networking sites, almost all of the companies who are into Internet security, started analyzing these sites in as deep as possible. They also did a lot of researches and many are still going on…. But suddenly came the innovative idea of adding custom applications with your profile on these sites!!! Remember now days we get option on facebook to add “movie quiz”, or add some “market place” and applications like that…. You will think how is that a problem ???Well, without going in deep I will just give small stats: - there are about 20000 such applications, which you can add on facebook and this number is increasing like anything. Each application has its own behavior and is not similar to other one.... resulting into a need of customized analysis of them indivisually, which is not at all easy!!!!
Now I believe you will be able to understand how big this issue is for Internet community.
I will try to keep posting anything important related to this topic but will also feel great to receive comments from you guys…

Keep smiling….

Signing Off:
Dhiraj singh

Saturday, June 28, 2008

Falling in Love

Right from the beginning, I never understood the word called "Love"....although I respect all those who pretend to be in love....time and again.

so far my experience of life makes me think that love is collaboration of a lot of feelings and that’s why, What I understand is affection for someone....care for someone...Willingness to spent our whole life with someone, sharing all the moments, all the emotions, all the up and downs, all the responsibilities, all the power and... List goes on.....

I strongly believe that a relationship must be on the basis of matured decision of two and not based on only infatuation or thirst for sex.i know and accept that a relationship is bound to start from infatuation but if that is the only guiding force then I m certain it will end within flashes. We should understand that being a guy we have different way of dealing with our life (most of the time it’s a wrong way....) and at the same time our partner being a girl has their own way to deal with the same. I don't have any hesitation in accepting that personally I find myself a bit kiddish at time and wish that if I could have acted more appropriately at times, it would be great....In the same time when I remember my friends who are girls(And its not same as girl friends....),I admire their balanced life style.hmmmmmm....It may be because of attraction towards friends of opposite gender but it can't be so strong that I can just criticize myself......so there is some substance in their overall persona(at least most of them....).

After comparing mars and Venus in my own way, the second point I would like to talk on is falling in love...well as said by some unknown genius and repeated by many of my friends: - "Don't fall in love, but rise in love!!!"But how to do so??? well if I have to say then it is as simple as that ....I will love someone because she might be very beautiful(first and important reason which we all have but perhaps no one wants to accept..) then she might be different from others in the way she carries her self.....in the sense she talks, she walks and ....then all together we can say that her overall personality could be so attractive that I will feel that she might the one with whom I can forget everyone in this world.....

Now after so much of positive thoughts why is it so that most of us don't find them selves comfortable when we come to know that our partner doesn't thinks same for us???.....Because we are Human being and we have a disastrous heart to put ourselves in difficult situations, if not always then quite often!!!Rite..... But is it a strong reason to destroy our carrier....our life?

Certainly, Not...but most of us does......And I m proud to say that at least I did not.....What should be the best peel at the time when we are down with "love's hang-over"......well! Reasons may be our family...our friends and all those who loves us....have faith on us....have expectations from us...and somewhere the hope to get her back....or just to convince her that her decisions can't be always rite!!!! It might be so that by the time you prove a point it may be so late and she might have got someone in her life but then also don't u feel that at least by achieving ur goals in life you can prove a point to all.....And point is quite clear..

That You are a strong person....you feel sad for her not being with you but that can't just shatter you.....You can motivate yourself to get anything and everything and what more is that you understand your responsibilities towards your family..And your loved ones and you can fulfill them in best possible manner. It will not only prove a point to others but it will also give a big boost to your confidence,.....and success will become your habbit.I know most of you who would read this blog will say why to prove a point to a girl who doesn't love u??And my answer will be sorry but it’s a hard fact that even we can pretend not to remember her but we hardly do anything without keeping her in our mind.....

Without writing a big story on this I would love to come on the bottom line, we should be always clear what we want out of our life, no matter what!!! Believe me if some one doesn't love us in return, Theirs nothing wrong till we understand that they have their own preferences.....but what more we should understand is that its not the end, Its the beginning....its going to make You more matured more thoughtful and ultimately it will make you a person who will understand the importance and will respect his relationship a lot, in future....a person who will respect his partner and all those moments which he had miss in past....

So cheers for a bright future and don't creep on what you lost...[:)] and please let me know if you want to share something more on this....

Signing Off:

Dhiraj Singh

Friday, May 16, 2008

The power of "Hello world"

“Hello world”
We all software professionals know this phrase very well…. rite!!!!
Start learning any language (if not all then most of them…) the first practical example would be a “hello world” program. I always use to think why these all writers’ starts with this phrase only and not any other phrase. Might be the one who wrote first most famous article or book on some language would have used this as first example and then all other writers just followed, But then again question arises what made any or all of them to choose this phrase only!!!!
Well, for most of us it really does not matter… but don’t u think it will be fun to understand that what actually drove them to use it.
As far as I see it I find that it’s because of the power of this phrase …… this phrase can be seen as a declaration or a pledge from our end, as learner of any new language, that we will implement the knowledge for the betterment of this world. We are only introducing ourselves to the world with this first program And is setting an expectation that world can expect much more fruitful implementation of our knowledge in future.
But, do we really keeping up our promise??? We better know the answer….

Without digging the issue , I would like to keep it simple….What you guys feel about authors using “hello world ” example as first step towards teaching the languages? Think something wizard ;)