while(1);

In Memory Hashtable

2011-12-31T02:04:00.001-08:00

In web applications you mostly get into this kind of situations where you need a code or API which acts as Hashtable and since you want it lightning fast, it must be in the memory instead of disk storage. So how would you create an In Memory Hashtable for Strings for a large set.

I had enough experience with hashtable to understand that the whole bottleneck is going to be the hash function which maps Strings to LongInts. After some brainstorming I got the solution. So here we go:
1. Create a Trie and provide to methods to set and retrieve the values. Something like this:
bool insert(String s)
long retrieve(String s)
bool exist(String s)

2. Create a list of String to be inserted in the beginning and use a file to perform the operation.

3. Once you are done with the initial setup now you can put your Hashtable live to answer your queries.

4. Create a daemon and put the above code into it.

5. Whenever you want to shoot a query invoke the daemon and call the retrieve function.

I hope the main problem would be figuring out the appropriate solution and writing a code for daemon and hashtable won't be a problem.

This can be implemented in many ways and on any architecture. But since mostly the servers are located on Linux machines, mostly it'll be useful on Linux environment with C being the underlying language. However I admit that if you use Java or Python it will be much easier to code. I used unix message passing mechanism to handle IPC.

Anybody wants the working code then write to me here

Science of Computer Science

2011-06-23T13:06:00.000-07:00

With increasing number of students getting out of college with the same Bachelor degree of Computer Science, its important to focus of some key area of Computer Science to get an edge over others. I created a list (or a wish list in some sense) of topics that I promised myself to learn. However the list itself was volatile and this excuse was sufficient enough to not abide to the promise :D. Finally it is now in stable state. So here we go...

> Good command over a couple of Programming Languages ( C/C++ and/or Java would do)
> One Scripting Language. (Python (preferred), Java Script, Bash anyone)
> Good understanding of OS (Life is as simple as Unix)
> Database handling (need not be an expert but capable of understanding/performing normalizations and basic queries)
> Basic Networking concepts (If time permits and unless your only goal is to get into Cisco :) )
> Finally Data Structures and Algorithms with Coding (No limits)

With these Arms and Ammo in your disposal, you are ready to face any challenge. But war does not always win by the tangible things.
You can apply in Google/ Facebook/ Twitter/ Microsoft/ Adobe etc or better go for research in any of the topic you liked.

Disclaimer: This list is prepared by me, being an average student throughout. It includes only my thoughts & is not targeted towards outstanding and brilliant students. :P

code for fun

2011-06-18T13:31:00.000-07:00

Program to Add/Subtract/Multiply 2 numbers..
Sounds pretty easy, so is the code for it.

#define s(c) if(scanf("%c",&c)){}
#define p(b) if(b+=(c-'0')){} if(b*=10){}
#define w(a,b) while(a>b){
#define i(a,b) if(a=b){}
main(int a,int b,int n,char c,char o)
{
if(scanf("%d",&n)){}
s(c)
w(n--,0)
i(a,0)
i(b,0)
s(c)
w(c,47)
p(a)
s(c)
}
if(a/=10){}
i(o,c)
s(c)
w(c,47)
p(b)
s(c)
}
if(b/=10){}
if(o=='+')
if(a=a+b){}
if(o=='-')
if(a=a-b){}
if(o=='*')
if(a=a*b){}
if(printf("%d\n",a)){}
}
}

However if you have noticed it correctly you would have found it unusual in the sense that it does not have any single semicolon. The unnecessary directives are to make the code shorter but it made the code ugly nevertheless.
I am still trying to make it smaller. If any one has better idea regarding it then comments are welcome.
You can compile the code successfully on any GCC compiler and run it as described below:
3 (3 test cases)
123+456
output: 579
456-123
output:333
123*45
output: 5535

happy coding!

When pointer to functions fascinated me...

2011-06-09T10:46:00.000-07:00

Some time back I was fascinated by pointer to function concept. Not only it gives the flexibility of CallBack, its more faster nevertheless. But instead of writing plain code I thought to write a code that looks different. Here it is...

void _(int *_o,int o_){o_<7?printf("%c",o_[_o]),o_++,_(_o,o_):printf("\n");}
void o_o(void (*_)(int*,int),int *_0,int __){_(_0,__);}
main(){int _O_[]={83,104,117,98,104,97,0x6d},_i_=0;
void (*_o_)(int*,int)=&_;
void (*_0_)(void(*__)(int*,int),int*,int)=&o_o;
_0_(_o_,_O_,_i_);}

All it does is print my name.

interview(s), job(s) and offer(s)

2010-08-13T08:00:00.000-07:00

I had been rigorously interviewed by some of the most high profile software developing firms in India including GE India, Slide Share, Oracle and Amazon.
Here are the stats
Slide share : interviewed by tech expert, tech lead India, India Head, CTO. Finally Not selected!!
Amazon.com : cleared 3 rounds. Finally Not selected!!
GE India : cleared all 5 rounds. Finally In.
Oracle India : cleared all 6 rounds. HR asked to wait for final approval, which is happened to be in US. Finally got the offer letter.
Had I not been selected by two companies, I would have appeared for SlideShare with much more sincerity and would have cracked it too.. probably :)
All in all I didn't let down myself. I'm kinda happy with the result. I was able to clear all the coding and aptitude rounds and was able to convince almost all of my interviewers. Details about the interviews and questions they asked will be covered in subsequent posts :)
Ok finally I settled down in GE India, which has great work culture, people and also the work. I like it more because I have bad experience from my old employer.

Linux Experience

2010-05-23T12:56:00.000-07:00

Hi, I am writing after a long time and of course my life has changed big time. During the last post I was in college and now it's been around 7 months or so since I have been working in an IT company, however the main thing that I am gonna discuss here, is the change of the machine I posses. I had AMD Athlon and now its Dell i5. I wanted it to be Open Source so I installed Fedora. I started with Fedora 8 then 9 and 11 until I had settled with 12.

Previous versions were not compatible with the machine given the latest hardware I had. The distro seemed nice and complete but I was unable to listen to music since media players do not have codecs sufficient enough to play media. Finally I found mplayer that was perfect and since then I had been using it without a problem. It's been playing all the extensions and all the types of media. However it was a command line player and didn't come up with a GUI. Ultimately I got smplayer which was a wrapper over the mplayer. It was just a GUI and used mplayer to play the media behind the scene.
I did many experiments with it but thats for subsequent posts.
Happy Gnuing

Repeated Squaring: You will love it

2009-01-15T05:18:00.000-08:00

This time I want to write something about the calculation of large powers of any number. For example say we want to calculate 13 to the power 1000. This is indeed a huge number and there is no data type in C/C++ or even in java that can hold such a huge number. So this is a problem unless you are a python user. Well I am not interested in talking about BigInt class but how to perform such calculation efficiently. In a scenario like when you need to find the last digit of the above mentioned number (13^1000) you can use it since you have to save only one digit throughout the calculation ( of the last digit).
More precisely let l(n)=last digit of n
13^1=13 l=3
13^2=13*13=169 l(13*13)=l(3*13)
13^3=169*13=2197 l(169*13)=l(9*13)
13^4=2197*13=28561 l(2197*13)=l(7*13)
means you need not save all the intermediate huge numbers along the way but just their last digit

Now come back to our business of calculation of 13^1000.
There are 2 approaches
1. Naive method
2. Repeated Squaring

1. Naive method is to calculate straight forward 13*13*13.... (1000 timess)13
something like this
a=1;
for(i=0;i<1000;i++)
{
a=a*13;
a=a%10;
}
it requires 1000 multiplications!!

2. Repeated squaring
we will calculate 13 to the power multiples of two...
here we go
a=13*13
b=a*a=(13*13)*(13*13)=13^4
c=b*b=(13*13)*(13*13)*(13*13)*(13*13)=13^8
using a loop we can proceed
13^16, 13^32, 13^64, 13^128, 13^256, 13^512
now just multiply (13^512)*(13^256)*(13^128)*(13^64)*(13^32)*(13^8)=13^1000
512+256+128+64+32+8=1000
so totally 14 multiplications!!!!
So you can check by yourself how beautiful this method is :)

fastest i/o methods

2008-12-01T20:13:00.000-08:00

Almost all the problems involve some kind of input and output processing. Unless your code is of O(n^2) or above, more than 70% of the running time goes for IO processing. So it is important to perfrom these operation efficiently in order to make the entire program efficient. here are some tips regarding input and output...
1. More overloaded a function the more time it takes
It means if you use overloaded function or stream opreator then it will take more time than an ordinary function, in short cin is slower than scanf() which in turn is slower than gets()
2. Input and output usually involves peripheral hardwares which make them slow.
If you are taking input from file then its ok otherwise you have to use keyboard which can slow down the speed not because you cant type fast(even thats also true) but because it has to check the buffer of keyboard and same in case output.
3. String and character arrays are easy to handle in case of input and output because the compiler just has to use them exactly as they are. Int, Long and Floats have to be transformed before printing or before storing.

Here is a hierarchy of the methods to take the input:
> fread() or read() system call
> gets() or getchar()
> scanf()
> cin>>
these are the methods in the increasing order of processing time with fread() is the fastest and cin being the slowest.

similarly you can figure out for the output:
> fwrite() or write()
> puts()
> printf()
> cout<<

now choose any one option according to the situation. Choose from the bottom if you want good looking but relatively slower code and choose from the top if you want complex but faster code... as always choice is yours :)
happy coding

get the input from a file

2008-09-14T13:56:00.000-07:00

there are lots of problems on SPOJ that require input must be taken from an input file. Those types of problems require that you get input till the end of input file and you cant use simple while or for loop to get input say 'n' no of times or until a particular number is entered. i tried so many things like finding EOF or checking for (!scanf()) but none of them worked and finally i had to keep my working codes for those problems aside since if i cant take inputs as described i will either get Time limit exceeded or runtime error.
after a long searching of such code i finally got perhaps the easiest way to get around that problem of getting input. it is damn simple. all you need to do is to make an object(e.g. string s;) of string type in CPP of course and then simply initialize a loop as
string s;
while(getline(cin,s))
{
use s as you wish
print result
}
that was a normal code but if you dont know this in prior then you cant do anything since it is not very common code. few examples of those problems which require this type of implementation are encondin, javac, bishops

it was sensational :)

2008-09-12T14:25:00.001-07:00

when on sep 03 i got my code for generation of prime number accepted on SPOJ i felt like i have achieved something very special. its not that very few people have solved it or it was a great problem but its in that sense that i made more than 20 unsuccessful attempts before finally cracked it. i was simply jumped from my chair when i saw the time taken by my code it was showing 0.21 secs when the time limit is 6 secs. indeed it was great feeling because i could not able to do it even for 6 secs few days before now fucked it up for 0.21 secs :)
there was nothing special in that code i just implemented Sieve's algorithm for generation of prime number but improved it a little bit.
what i done is not at all significant but still i explain it here. here we go...
i created an array of 32000 and applied sieve on it to get a list of all the primes from 1 to 32000 now processed the input. if the larger number is less than 32000 then simply printout what we already have in our pocket.
else created another array of size that is the difference between the larger(h) and smaller(l) input. now besides small manipulations, i found the square root of larger number then from 2 to that square root took each number(lets say 'd') and for each such number i took another number(lets say 'n') in the given range(l to h) but instead of dividing it for modulus(as per Sieves algorithm) i used a trick here.
i found a number that is nearest to the first number of the input(smallest int greater than l) which is a multiple of 'd' and then simply added d till it was less than h to find all its multiple and then simply applied remaining sieves algorithm.


// AC
#include<iostream>

#include<math.h>
#include<stdio.h>
using namespace std;
int main()
{
    bool a[32010]={0},*p;
    int i,j,s,k,t=0,rem,rem1;
    cin>>t;    
    long long n1[t],n2[t],m;
    long d;
    //int z=0;

    double x;
    for(i=2;i<32002;i++)
    {
          if(a[i]==0)
          {
               for(j=i+i;j<32002;j+=i)
               a[j]=1;
          }
    }
    for(i=0;i<t;i++)
    {
        cin>>n1[i]>>n2[i];
        if(n2[i]<=32000)
        {
            for(j=n1[i];j<=n2[i];j++)
            if(a[j]==0 && j>1)
            cout<<j<</*"   "<<++z<<*/endl;
            goto done;
        }
        if(n1[i]==1)
        n1[i]=2;
        n2[i]+=2;
        d=sqrt(double(n2[i]))+1;
        p=new bool[n2[i]-n1[i]+1];
        for(j=0;j<n2[i]-n1[i]+1;j++)
        p[j]=0;
        for(j=2;j<d;j++)
        {
         if(a[j]==0)
            {
                rem=n1[i]%j;
                if(rem==0)
                rem=j;
                k=n1[i]+j-rem;
                while(k<=n2[i])
                {
                    p[k-n1[i]]=1;
                    k+=j;
                }
                if(j==n1[i]+j-rem)
                p[j-n1[i]]=0;
            }
        }
        s=n2[i]-n1[i];//getchar();

        for(j=0;j<s;j++)
        {
            if(p[j]==0 && j+n1[i]<n2[i]-1)
            cout<<j+n1[i]/*<<"   "<<++z*/<<endl;
        }
      done: cout<<"\n";
    }
    return 0;
}

besides this i have come across few other cool programming problems and concepts but thats not for now....

tips 4 neophytes like me

2008-08-06T05:12:00.000-07:00

programming is the only thing that i do in my college with (extreme) regularity. i think i need not mention that i m a registered user at SPOJ. i've solved a handful of problems there. here is my profile at spoj. it was not so long when i was happy with my Turbo-C compiler... i was asked by my senior to switch to GCC and i m very grateful to him [:)].
things you need to keep in mind while solving problems.

they check your efficiency not your language knowlegde.
they run your programs at extreme cases.
finally you need a gud algorithm and proper implimentation.

thats it and you will make it Ac ( @ spoj, Ac means your solution to a particular problem has got accepted by online judges).
mostly problems are based on number theory, string matching, sorting, graph and others but the input range and time limit makes it harder to solve.
if you want to start with some easier ones then go to my profile. i usually solve easier first [:)].
thats enuf for today next time i will tell you explanation to few problems so you can solve them quite easily.

Introduction

2008-07-27T13:48:00.000-07:00

hi all. this is me out here with a brand new blog. before i come to my business, let me introduce myself. This is Shubham Dave pursuing my btech with CS stream n currently studying in final year. my subjects of interest are data structures and algorithms and i just love writing programs in c/c++, java and python...
ps: as midsem tests are scheduled from tomoro onwards i cant continue right now [;)]