Time-space Trade-off in Radix Sort

In Radix Sort,

Time Complexity : O(nd)

Space Complexity: O(n+RADIX)

However, by changing RADIX, one can reduce d and get as low as O(n) which is similar to counting sort which uses the RADIX size equal to the range of array (Normalization or pull up is required if there are some negative numbers).

But that will cause rise in Space Complexity that is directly proportional to RADIX.

Careful selection of RADIX for a particular problem will help in sorting close to linear time and less space.

Please feel free to comment if you feel any error in it.

Radix Sort: C Implementation

Radix sort is one of the most popular algorithms and is used to sort the integers. It is based on counting sort and that makes it different from other algorithms which are based on comparison sorting. It gets name Radix sort because radix means digit. In this, stable counting sort runs on each radix position to sort the integers.
E.g.
I = {10,123,39,9,1234,56} and radix = 10
For I, first we run count sort on unit digit position and the output will be
I0 = {10,123,1234,56,39,9}
Then count sort is run on 10th position of I0 and output will be
I1 = {9,10,123,1234,39,56}
Please note that upto 2nd digit, whole array is sorted.
Similarly, for 100th position
I2 = {9,10,39,56,123,1234}
For 1000th position
I3 = {9,10,39,56,123,1234}
And I3 is sorted.
It is done by using Radix 10. Count sort employed here must be stable. Otherwise, whole array may not be sorted.
To extract ith digit from x use
x*RADIX/(RADIX^i)%RADIX

C Implementation:

#define SIZE 256
#define RADIX 10 //We are using 10 as base
void countsort(int *x,int n,int range,int *o,int digitposition)
{
int temp[RADIX];
int i;

for(i=0;i
    temp[i] = 0;
for(i=0;i
    temp[(x[i]*RADIX/digitposition%RADIX)]+=1;

for(i=1;i
    temp[i] += temp[i-1];

for(i=n-1;i>=0;i--)
    o[temp[(x[i]*RADIX/digitposition%RADIX)]-- -1] = x[i];
}

void radixsort(int *x,int n,int *xo)
{
int i,digex,j,digitcount;
int max=x[0];

for(i=1;i
    {
    if(x[i]>max)
        max = x[i];
    }
digitcount = 0;
//To count the number of digits
while(max)
    digitcount++,(max/=RADIX);
//Starting digit that is at unit place
digex = RADIX;
for(j=1;j<=digitcount;j++)
    {
    countsort(x,n,RADIX,xo,digex);
    for(i=0;i
        {x[i] = xo[i];//Copy the output to make it input for next iteration
        }
    digex *= RADIX;
    }
}

int main()
{
int x[SIZE],ox[SIZE];
int n;
int i;
scanf("%d",&n);
for(i=0;i
    scanf("%d",&x[i]);
radixsort(x,n,ox);
for(i=0;i
    printf("%d\n",ox[i]);
return 0;
}

Time Complexity: O(n*d) where n is the size of input and d is the number of digit
Space Complexity: O(n+RADIX)
Please feel free to comment if you find anything wrong. 

Count of an Element in a Sorted Array.

Problem: Given an array a1,a2,a3…an which is sorted in the non-decreasing order. Given an element e, find its number of occurence in the array.

For example: (1,1,1,2,2,3,3,3,4,4) is the given array and let the given element is 3. Its count is 3. For 4, it is 2.
One can think what is so difficult in the problem. It can be solved in more optimised way one can think of.
Method 1:
Simple, but not efficient.
Search for an element linearly. When it is encountered, then count it.
Complexity:

Method 2:
Efficient but consuming space.
First it involves preprocessing of O(n) and will space of O(n). In preprocessing, store the element and its count in another array
keeping its order. When, the element is to be found, it can be found in O(logn) using binary search alongwith its occurence.

Method 3:
Tricky, but efficient.
Use binary Search method to find leftmost and rightmost indices of the element.
Then use the formula right-left+1 to get the count.
Complexity: O(logn)

Code:
#include

#define PRINTRESULT(array,n,c)  printf(“%d%d\n”,c,getcountinsorted(array,n,c))
#define SIZE 16
int binarysearch(int *array,int n,int value)
{
int low=0,high=n-1,mid=(low+high)/2;
while(low<=high)
{
if(array[mid]==value)
return mid;
if(array[mid]
low = mid+1;
else
high = mid-1;
mid = (low+high)/2;
}
return -1;
}

int getcountinsorted(int *array,int n,int value)
{
int low,high,mid;
mid = binarysearch(array,n,value);
if(mid<0)
return 0;
int right,left;
//Search for the rightmost index
right = mid;
low = mid+1;high = n-1;
int mid1;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{right = mid1;low=mid1+1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
//Search for the leftmost index
low=0;high = mid-1;
left=mid;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{left = mid1; high=mid1-1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
return right-left+1;
}

/* Driver Program to test the above routine */
int main()
{
int array[SIZE] = {1,1,2,2,2,3,4,5,6,7,7,7,7,8,11,11};
PRINTRESULT(array,SIZE,1);
PRINTRESULT(array,SIZE,2);
PRINTRESULT(array,SIZE,3);
PRINTRESULT(array,SIZE,4);
PRINTRESULT(array,SIZE,5);
PRINTRESULT(array,SIZE,6);
PRINTRESULT(array,SIZE,7);
PRINTRESULT(array,SIZE,8);
PRINTRESULT(array,SIZE,9);
PRINTRESULT(array,SIZE,10);
PRINTRESULT(array,SIZE,11);
PRINTRESULT(array,SIZE,12);
return 0;
}

Output:
1 2
2 3
3 1
4 1
5 1
6 1
7 4
8 1
9 0
10 0
11 2
12 0

Sort in odd increasing even decreasing linked list

In the given linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How it can be sorted in increasing order?

Solution is very easy and is in linear time.

Given linked list

a1->a2->a3->......an

a1, a3, a5... are in increasing order.
a2, a4, a6... are in decreasing order.

First step is to get the linked list of odd numbered nodes only.
Means a1->a3->a5->...
This can be done in O(n)

Similar for even numbered nodes, a2->a4->.... This is again in linear time.
Now reverse the a2->a4-> list. It can be done in O(n).

Merge it with a1->a3->... It also has linear complexity.

And you will get a sorted linked list in linear time. 

Deletion of arbitrary node in the linked list

Given any node in a liked list without start pointer, how will you delete that node?
And what problem(s) will arise?

Solution is swap content of it with the next node (pointed by next pointer). And delete next node instead.
Problem will arise when this will be a terminal node (node with null next pointer). It will free a memory location that is longer used and still pointed by a node of linked list.

Yahoo interview questions

Yahoo visited our campus on 26th Oct. 2010. Its selection process consists of
1. Written Objective Test
2. Coding Round
3. 2 Technical Interviews
4. 1 HR Interview

Written Objective is pretty simple. One can easily get through with sound knowledge of Data structures, Algorithms, Operating Systems, Database Management Systems and little bit Discrete Mathematics.

In coding round, two problems were given which were simple if you are a regular programmer.
First one is to implement GREP without using any API/Library that supports such functionality.

Second one was level order traversal of a binary search tree. It concerned with finding sum at each level of tree that stores integers at each node.

Technical round were not that tough.

Questions are:

In first round:

1. Print linked list in reverse order using a recursive function. A code is to be written.
2. Given any node of a linked list (but not the start node), how that node can be deleted. And what problems can be faced later?
3. Two blind people are sitting near a table top. On table, there are n head faced coins and n tail faced coins. How they can distribute such that each one have equal number of heads and tails?
4. Solve f(n) = f(n-2)+2 and f(n) = f(n/2)+2 and similar RRs.

In second round:

1. Given a linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How can linked list be sorted in increasing order?
Solution is pretty simple and is in linear time.

2. How map (in C++) guarantees search in O(logn) in worst case?

Questions are quite easy.
Still I was unable to answer few one. Solution to someone I will post in my next blog.

Technical Interview

It is a hurdle which everyone has to cross to get technical position in the company. However, when it comes to a software company, it is much more of fun for techies.

What makes it different from an ordinary interview? Ordinary interview means interviewer(s) throw(s) questions on you and you reciprocate it with your answer.
Does it mean that there is no question from interviewer to interviewee? No.
Definitely there are questions. But how these questions are different from ordinary interview?

Here questions are technical one. They not only scan your technical knowledge but your other aspects.
These questions are meant for conversation as well.

At the outset, you will come to know the problem. That is "what to be done?".
And you have to discover the solution? That is it.
Perhaps not.

It is more than just "proposing a solution".


Solution is to be discussed and loud thinking is encouraged here.
The "road to the solution" is much more important than its destination.
Therefore it is conversation and discussion rather a conventional interview.
To interviewer, it is the only way to judge the candidate. However, he/she is restrained to ask any personal question which are also necessary to check the suitability of the candidate.

Hence, instead of transforming yourself into problem solving mode, you need the best of  both world. Means of technical and as well as of so called normal human being.
Candidate has to prove his both facets.
But the focus is still on the technical part but instead of solution, interviewer is much more interested in the path through which you walk towards to the solution and if that is scintillating then it is the right path you have chosen.

logn Search in rotated sorted array

Lets have a sorted array like 1 2 3 4 5 6 7 8 9. Lets rotate it arbitrary number of times. It is like 5 6 7 8 9 1 2 3 4.

Now, can element still be searched in O(lgn) time?

Limit crossed

Everyone is revered.
You will find this problem pretty interesting. Computer has some limitation on the size of number and your requirement has reached to that limit. So write a program (essentially in C/C++) which add, multiply, subtract and divide any arbitrarily large integer.

Inside or Outside?

How will you know that you are inside in a building of a polygon? Consider also concave polygon as well.