In Memory Hashtable

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

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

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...

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)

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

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

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 :)