Mukesh Kumar Verma
BAN USERI guess we can apply hashmap funda here............take the sitename as input to hasfunction ...the output of the hashfunction is your tinyURL and map it to the IP address in the hashtable..... :-/
- Mukesh Kumar Verma September 12, 2012Yes that is possible but what I am trying to do here is avoid extra usage of extra O(n) space everything is done inplace.
- Mukesh Kumar Verma September 12, 2012consider this you have this stream of numbers in the link list
1220022111001010101020201022210011012........now my theory says have a temp pointer and this will require atleast 3 pass that is 3n=~O(n).... zeroTemp pointer is for Zero's oneTemp is for One's and twoTemp is for Twos's and Temp is general for the linkList...................so in first pass keep looking for zero's that is
1-->2-->2-->0-->0-->2-->2-->1-->1-->1-->0-->0...........
^ ^
Temp zTemp
Temp points to 2 and zTemp points to 0..........now you encountered first zero at 4th location have a backup of its location in Temp pointer that is Temp.next and set zTemp as this zero's location . let it be there , now proceeding we find that next is also a Zero so no circus here just increment zTemp to next zero....coming to 6th location we see '2' so here what we do is we want to continue the chain of non Zero's with Temp pointer so we point Temp.next to this '2' . Now zTemp is pointing to 2nd Zero and and Temp is pointing to 6th location that is at '2'........proceeding in this faishon we seprated the zeros and non zeros at the end we have 0-->0-->0-->0->0-->.......1-->2-->2-->2-->2-->1-->1 and so on.........now we one oneTemp and seprate 1's from the list and then we are left with '2'......just merge them.
Assumption : I kept head pointer each for 0's 1's and two's
Cooooool one!!!
- Mukesh Kumar Verma September 08, 2012
Everything is supercool if you have considered that when you encounter the two's which you have updated at the end belongs to the sorted list or not or else you will end up in infinite loop never finding tail since for every 2 you add it and update the tail.......0->0->0->1->1->2->2->2->tail......here look whthr your algo terminates or not :-/
- Mukesh Kumar Verma September 12, 2012