CareerCup

Base 26 representation

@BABA, its better to cite some examples where the code fails than to writing sarcastic comments. Thank you.

@BABA, inefficient code. Doesn't handle various cases.
Try the below tree:

10
	        / \
              15   12
              \    /
               7  10
              /   /
             2   25

Also take care if b is negative.
if(b<0) call res=divide(a,-b) & if a is negative call res=divide(-a,b). The answer is -res.
If both are negative call divide(-a,-b)

int divide(a,b) {
          if (b == 0) print "Invalid";
           else if (a < b) return 0;
           else return(1 + (divide(a-b, b));
}

Brute-force approach.

int subString(char *p,char *q)
{
        int i,j;
        if(!p || !q) return 0;
        for(i=0;i<strlen(p)-strlen(q)+1; ++i)
        {
                j=0;
                while(j<strlen(q) && p[i+j]==q[j]) j++;
        
                if(j==strlen(q))
                        return i;
        }
        return 0;
}

Assuming both arrays are sorted.
a[] is of size M & b[] is of size N.
c is the third array which contains the sorted data avoiding duplicates.

i=0;j=0; top=-1;
while(i<M && j<N)
{
	if(a[i]<b[j])
		c[++top]=a[i++];
	else if(a[i]>b[j])
		c[++top]=b[j++];
	else
	{
		c[++top]=a[i++];
		j++;
	}
}
while(i<M)
	c[++top]=a[i++];
while(j<N)
	c[++top]=b[j++];

I think radix sort would be the best. As its complexity is O(N*d) where d is negligible as compared to N.
Here is the implementation.

#include <stdio.h>
#include <limits.h>
#include <math.h>
 
int findMaxDigit(int *arr,int size)
{
        int i,max=INT_MIN,n=0;
        for(i=0;i<size;i++)
                if(arr[i]>max)
                        max=arr[i];
        
        while(max)
        {
                n++;
                max/=10;
        }
        return n;
}
 
int isEmpty(int *r,int j)
{
        return r[j]==-1;
}
 
void Enqueue(int (*Q)[10],int *f,int *r,int digit,int n)
{
        if(f[digit]==-1)
                f[digit]++;
        Q[++r[digit]][digit]=n;
}
 
int Dequeue(int (*Q)[10],int *f,int *r,int digit)
{
        int n=Q[f[digit]][digit];
        if(f[digit]==r[digit])
                f[digit]=r[digit]=-1;
        else
                f[digit]++;
        return n;
}
 
void radixSort(int *arr,int size)
{
        int i,j,k,Q[size][10],f[10],r[10],d,digit,top=-1;
        
        d=findMaxDigit(arr,size);
 
        for(i=0;i<size;i++)
                f[i]=r[i]=-1;
 
        for(i=0;i<d;i++)
        {
                for(j=0;j<size;j++)
                {
                        digit=(arr[j]/pow(10,i));
                        digit%=10;
                        Enqueue(Q,f,r,digit,arr[j]);
                }
                top=-1;
                for(j=0;j<10;j++)
                {
                        while(!isEmpty(r,j))
                                arr[++top]=Dequeue(Q,f,r,j);
                }
        }
        for(i=0;i<size;i++)
                printf("%d ",arr[i]);
}
 
int main()
{
        int arr[]={4,2,6,1,5,5,1,2,45,444,44,45,4,1};
 
        radixSort(arr,sizeof(arr)/sizeof(arr[0]));
 
        return 0;
}

As the questions speaks about finding the count of a particular word.
So, a buffer can be maintained for each word & matched with the word to be searched.

An alternate way is to use TRIE & at the leaf nodes, count the number of occurrences. If words are to be outputted in sequence with the sentence, search for each word in the TRIE else do an inorder traversal.

The main idea is to take care of the rows & columns which have been finished, thereby reducing the size of the matrix to be printed.
p denotes the lower boundary row & k denotes the lower boundary column.

#include <stdio.h>

void printSpiral(int (*arr)[4],int row,int col)
{
	int i,j,k=0,p=0;
	while(p<row)
	{
		for(j=k;j<col;j++)
			printf("%d ",arr[p][j]);
		p++;
		
		for(j=p;j<row;j++)
			printf("%d ",arr[j][col-1]);
		col--;

		for(j=col-1;j>=k;j--)
			printf("%d ",arr[row-1][j]);
		row--;
			
		for(j=row-1;j>=p;j--)
			printf("%d ",arr[j][k]);
		k++;	
	}
}

int main()
{
	int arr[][4]={{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};

	printSpiral(arr,4,4);
	return 0;
}

We need two different cases to handle:
1. Both the characters are same.
2. Both characters are different.

Moreover, we also need to take care whether the ordering of the characters matter.

case 1. Both chars are same

for(i=0,pos=-1,mindist=INT_MAX;i<N;i++)
{
	if(arr[i]==c)
	{
		if(pos!=-1)
		{
			if(mindist>abs(pos-i))
				mindist=abs(pos-i);	
		}
		pos=i;
	}
}

case 2: Both chars are different

int i,minc1=-1,minc2=-1,minpos=INT_MAX;
        
        for(i=0;arr[i];i++)
        {
                if(arr[i]==c1)
                {
                        if(minc2!=-1)
                        {
                                if(minpos>abs(minc2-i))
                                        minpos=abs(minc2-i);
                        }
                        minc1=i;
                }
                else if(arr[i]==c2)
                {
                        if(minc1!=-1)
                        {
                                if(minpos>abs(minc1-i))
                                        minpos=abs(minc1-i);
                        }
                        minc2=i;
                }
        }

Consider the example 5,4,3,2,1.
Your approach fails. It gives 5 as median.

@shashank, The DLL can again be converted back into BST in O(N). But, the problem is that the structure of the BST will change as DLL to BST conversion will result into balanced BST.

merge(head1,head2)
{
	if(!head1)
		return head2;
	if(!head2)
		return head2;
	p=head1->next;
	head1->next=head2;
	merge(head1->next,p);
	
	return head1;
}

Corner cases have been handled.
I/p: ixi
o/p: Roman Num: ixi
Decimal Num: 10

Giving wrong outputs

#include <stdio.h>
 
int findLocation(int i)
{
        return (i%4)*3 + (i/4);
}
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void arrange(int *arr,int h)
{
        int i,j=1,loc=1;
        for(i=1;i<h-1;i++)
        {
                loc=findLocation(loc);
                if(loc!=j)
                        swap(&arr[loc],&arr[j]);
                else
                {
                        loc++;
                        j=loc;
                }
        }
}
 
int main()
{
        int arr[]={1,2,3,4,5,6,7,8,9,10,11,12},i;
 
        arrange(arr,12);
        for(i=0;i<12;i++)
                printf("%d ",arr[i]);
 
        return 0;
}

Time complexity will be O(K*N logk) because, each time, a new element is inserted in the min-heap, the heap needs to be heapified so that at each time during extraction, we get the minimum element only.As heapify takes logk time & it is done K.N times, so O(k*N logk)

#include <stdio.h>
 
void par(int open,int close,int n,int idx)
{
        static char a[100];
        int i;
        if(close==n)
        {
                for(i=0;i<2*n;i++)
                        printf("%c",a[i]);
                printf("\n");
        }
 
        if(open<n)
        {
                a[idx]='(';
                par(open+1,close,n,idx+1);
 
        }
        if(close<open)
        {
                a[idx]=')';
                par(open,close+1,n,idx+1);
        }
}
 
int main()
{
        par(0,0,3,0);
        return 0;
}

Check you output for:
a[]=8,3
b[]=7,3;
c[]=6

The approach may be cost effective depending on how the numbers are stored on the servers.
What if the numbers are stored in the linked-list or file.
This approach seems to be good only in case of array where access to a median takes only one operation.

What about duplicates digits? Phone numbers can also contain duplicates,right.
Also , user may want to type number like 2324

Ok, to print all pairs. when a pair is found ,don't stop continue the search by incrementing i & decrementing.[i++,j--]

Not working for:
a[]=3,5
b[]=1,6
c[]=6,18

1.Take two pointers, i pointing to the start of a[] & j pointing to the start of b[].
2. for every item in c[], find a pair of items in a[] & b[](O(m+n)).
So, time complexity is: k(m+n) where c[] contains k elements.

Option 3 is also correct if we include *.

p=root;prev=NULL;
 
        if(p->alph=='A' || p->alph=='O')
                cur=root;
        else
                cur=NULL;
 
        while(p)
        {
                if(p->alph=='A' || p->alph=='O')
                {
                        if(prev!=NULL)
                        {               
                                prev->next=p->next;
                                if(cur==NULL)
                                {
                                        p->next=root;
                                        root=p;
                                }
                                else
                                {
                                        p->next=cur->next;
                                        cur->next=p;
                                }
                                cur=p;
                        }
                }
                prev=p;
                p=p->next;
        }

So, according to this approach, there will be n array of 10[for digits-0 to 9]probably an array of linked list. Whenever a phone number needs to be inserted, we will take out each digit & associate its pointer[through which we can display the phone number] to the linked list. Good thinking, But what to do when the phone number contains duplicates.

Also, don't you think that we will be storing the same phone numbers multiple times?

Its not a warning. Its compile time error in latest version compilers(C-99 onwards).

The output of first program is undefined. There is no sequence defined in the statement:
x = y++ + x++;
y = ++y + ++x;

In the older version compilers, the output is 13.......21, but the newer version compilers(c-99 onwards) define the behavior as undefined.You will get the error.
See here: ideone.com/mEqiP

If the value of the same variable is changed more than once, then it is called as UB(undefined behavior).
For more details, search sequence point on wiki.

Here is the iterative approach.
Space : O(1)
Time: O(N)

connectNodesatSameLevel(root)
{
	if(!root)
		return;
	root->nextRight=NULL;

	while(root)
	{
		p=root;
		while(p)
		{
			if(p->left)
			{
				if(p->right)
					p->left->nextRight=p->right;
				else
					p->left->nextRight=findNextRight(p);
			}
			if(p->right)
				p->right->nextRight=findNextRight(p);

			p=p->nextRight;
		}
		if(root->left)
			root=root->left;
		else if(root->right)
			root=root->right;
		else
			root=findNextRight(root);				
	}
	
}

findNextRight(root)
{
	root=root->nextRight;
	while(root)
	{
		if(root->left)
			return root->left;
		if(root->right)
			return root->right;
		root=root->nextRight;
	}
	return NULL;
}

Here is the recursive approach which takes O(1) space & O(N) time complexity.

connectNodesatSameLevel(root)// call it after making root->nextRight=NULL
{
	if(root)
	{
		if(root->nextRight)
			connectNodesatSameLevel(root->nextRight);
	
		if(root->left)
		{
			if(root->right)
			{
				root->left->nextRight=root->right;
				root->right->nextRight=findNextRight(root);
			}
			else
				root->left->nextRight=findNextRight(root);
			connectNodesatSameLevel(root->left);
		}
		else if(root->right)
		{
			root->right->nextRight=findNextRight(root);
			connectNodesatSameLevel(root->right);
		}
		else
			connectNodesatSameLevel(findNextRight(root));
	}	
}

findNextRight(root)
{
	root=root->nextRight;
	while(root)
	{
		if(root->left)
			return root->left;
		if(root->right)
			return root->right;
		root=root->nextRight;
	}
	return NULL;
}

Follow this link for more details: en.wikipedia.org/wiki/3SUM

We can further reduce the space to 24 bytes. Lets see how.
There can be only 8 information: pawn,king,queen,bishop,knight,rook,no piece[empty] & color of piece.
So, we need 3 bits to represent to represent these information.
We can design a 8x8 chessboard with each slot occupying exactly 3 bits using bit-field[can represent range from 0 to 7].So, the space reduces to 64x3bits=24bytes.

I think We can also do it with 3 bits using bitmask. The range of values can range from 0 to 7 by using 3 bits.
So, the space is further reduced to: 64x3bits=24byte.

One more thing needs to be added, the color information.

We can take a 2D array[8x8], where each slot can contain one of the 7 things.
rook,bishop,king,queen,knight, pawn & empty.
So, the pieces can be represented by a single integer using bit vector.

Why not use only min-heap where pages with least recently used can be extracting the head of the min-heap. Heap will be formed based on the time of use. Say we use a variable clock which represents the time of use. A new page will be inserted in logn time.
I don't see any use of hash-map there.

1. Build a minleft[] which contains the element less than arr[i] from 0 to i-1 ,else -1.
2. Build a maxright[] which contains the element greater than arr[i] from i+1 to N-1 ,else -1.
3. run a loop from 0 to N-1,stat cheching the elements of minleft[] & maxright[].
if(minleft[i]<maxright[j]) j++ update maxdiff(j-i)
else i++

x x a x a x b x b x c x a b x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lets say we need to search for segment containing a,b,&c.
1.start pointer is at 0, last pointer is at 0.
2.start pointer is at 2, last pointer is at 2.
3.start pointer remains at 2, last pointer is at 4.
4.Both words[start & last pointer ] are same, update start pointer to 4[since word at index 3 has no purpose].
5.start pointer is at 4, last pointer is at 12.
6.Both words are same, update start pointer to 8, last pointer remains at 12.
7.start pointer is at 8, last pointer is at 13.
8. Found both words equal,update start pointer to 10,last pointer being at 13[this is the smallest segment.]
9. start pointer is at 10,last pointer is at 14.
10. The file is finished. So, the smallest segment is from 10 to 13.

I don't know what issues are you finding in this approach.
To me, its working perfectly.

easy, we will keep on searching until we do not find 456.

If the get() & reverse is O(1), then the sorting reduces to O(N).
No, pan cake is different from insertion sorting.
In insertion sorting, an element is inserted at proper place while it is comparing with every other element. Here elements are inserted at their proper place usin reverse() method.

This is a version of Pan-Cake sorting where we are allowed to reverse the array from i to j.

1. Find the minimum element say its index is j.
2. reverse(i,j) where i represents how many elements have sorted till now starting from 0 to N-1. So, the minimum element will come to its position.
3. Increment i. Again find the minimum element from i to N-1.
4. Repeat above steps until i is not equal to N-1.

Here is the complete code.

#include <stdio.h>
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void reverse(int *arr,int l,int h)
{
        while(l<h)
        {
                swap(&arr[l],&arr[h]);
                l++;h--;
        }
}
 
int findMin(int *arr,int l,int h)
{
        int min=0,i;
        for(i=l+1;i<h;i++)
                if(arr[i]<arr[min])
                        min=i;
        return min;
}
 
void sort(int *arr,int N)
{
        int i,j;
        for(i=0;i<N;i++)
        {
                j=findMin(arr,i,N);
                reverse(arr,i,j);
        }
 
        for(i=0;i<N;i++)
                printf("%d ",arr[i]);
}
 
int main()
{
        int arr[]={2,1,5,4,6},size;
        size=sizeof(arr)/sizeof(arr[0]);
        sort(arr,size);
        return 0;
}

A graph is called as disconnected if there exists at least one pair of vertices (u,v) such that there is not any path between them.
To make the above definition correct, Separate one vertex & join the remaining n-1 vertices.
So, it can be done in n-1C2=(n-1)*(n-2)/2

@eugene, LOC doesn't matter at all.
You can also write a complex for loop in a single line which does the same work if it was written in a simpler version of 5 lines.
Better code means processor will take less clock cycles to execute the instructions.
Have you ever thought why bit-wise operations are assumed to be better?
Suppose we need to check whether a number is even or odd,Which of the two version would you prefer?
if(n%2==1)//for odd
or
if(n&1)//for odd
The same explanation also lies here.

I have thought one approach.More like as suggested by @eugene.
Let me know whether it is efficient.

Use TRIE data structure where phone numbers will be inserted in sorted order. In the leaf nodes, we will have pointers to the original phone number[the phone numbers will be in the form of strings right!].
In order to handle collisions[two different phone numbers after sorting may represent the same leaf node],
we can have linked list at the leaf nodes. Whenever a new phone number is being inserted & the leaf node is already having pointer to some other phone number, we will chain this phone number[create a new node in the linked list & insert its pointer there].
Now, During search operation, lets say 321, first sort the string to be searched[say 123 in this case].
After reaching 123, an inorder traversal would be sufficient.Whenever a leaf node is encountered, all the strings[phone numbers] can be accessed through single linked list.
Comments are welcome.

Its already present in this example. x92xxx6x.

Sort the intervals in order of increasing finish times.
If the current interval start time is >= previous interval finish time, include it,else leave it.
Do the above steps until no more intervals are left. Meanwhile keep incrementing number of classes.

I think the choice depends upon whether the threads shared data & code or not. If the threads are independent, then multiple processes with single thread would be better.
However,if the threads are inter-related, i would prefer process with multiple threads.
Also, as pointed by rukawa, if the threads are independent & one process with multiple threads are used, then one thread can make the entire process go down.

The outputs are not clear. If the path from 12 to 3 is 12,4,3
Then the path from 12 to 9 should be 12,8,9 & not 12,4,8,9

EDIT:
The previous algo failed for some input cases. Thanks to @ buckCherry for pointing it out. Below is the fresh algo.

Find the start of the cycle through Floyd cycle detection algorithm. The total number of nodes is the count of nodes that form cycle and count of nodes that are not part of cycle. If the list doesn't contain cycle, count of nodes that are part of cycle is zero.
1. Maintain two pointers called hare & tortoise.
2. move hare two steps & tortoise one step until either both become equal or hare reaches NULL.
3. Move tortoise to the start of the list. Move tortoise and hare step by step until their next node don't point to the same node( in case there is no cycle , hare will point to NULL. Ignore step#4 in this case). This next node is the starting node of the cycle. Meanwhile count the number of nodes that are not part of the cycle.
e.g. A->B->C->D->E->D
The number of nodes that don't form cycle is 3.

4. Count the number of nodes in the cycle. Start tortoise from the starting node of the cycle and keep on moving until it doesn't reach its initial position.
In the example explained in step#3, the number of nodes in the cycle is 2.

5. The answer is count in step#3 + count in step#4.