CareerCup

Node* copy(root)
{
	Node* cur,*tail,*newroot=NULL;

	cur=root;
	while(cur)
	{
		temp=getNode(cur->data);

		if(!newroot)
			newroot=tail=temp;
		else
		{
			tail->random=temp;
			tail=tail->random
		}
		cur=cur->random;
	}
	return newroot;
}

It doesn't work when the size of input data is even. In this case, median is the average of the two middle items.

Static variables are by default initialized by NULL.
See here: ideone.com/I39Ne

Use modified Inorder traversal.

correctBST(root)
{
	static Node* temp1,*temp2,*prev;
	static int found;
	if(root)
	{
		correctBST(root->left);
		if(!temp1 && prev && root->data<prev->data)
                {
			temp1=prev;
                        temp2=root;
                 }
		else if(prev && root->data<prev->data)
			temp2=root;
		else if(temp1 && temp2 && !found)
		{
			swap(&(temp1->data),&(temp2->data));
			found=1;
			return;
		}
		prev=root;
		correctBST(root->right);
	}
}

BST2DLL(root,start)
{
        static Node* prevNode;
	if(root)
	{
		BST2DLL(root->left);
		if(!start)
			start=root;
		else
		{
			prevNode->next=root;
			root->prev=prevNode;
		}
		prevNode=root;
		BST2DLL(root->right);
	}
}

Call BST2DLL(root,start);
Where start is the head of the DLL.

1. Create a BST from the numbers. Print the N/2 node of the BST.

2. Create a min-heap of size N/2. Populate with first N/2 numbers.For each new number, if it is larger than the head value, replace & update the heap. At the end, head will indicate the N/2 node.

LCA(root,a,b)
{
	if(a==root || b==root) return root;
	if(a->data < root->data && b->data < root->data)
		return LCA(root->left,a,b);
	if(a->data > root->data && b->data > root->data)
		return LCA(root->right,a,b);
	return root;
}

CountHops(root,a,b)
{
	if(!root || !a || !b) return INT_MIN;
	temp=LCA(root,a,b);
	hopa=-1;hopb=-1;
	p=temp;
	while(p!=a)
	{
		if(a->data < p->data)
			p=p->left;
		else
			p=p->right;
		hopa++;
	}
	p=temp;
	while(p!=b)
	{
		if(b->data < p->data)
			p=p->left;
		else
			p=p->right;
		hopb++;
	}
	return hopa + hopb + 1;	
}

1. Yes, you have a good thought. Three positions are redundant to check. These are (-1,-1),(-1,0) and (0,-1).

2. static is chosen to avoid the memory allocation in each recursion. Yes, we can make them global. But, r[] & c[] are needed in this function only. So, static.

3. Yes, i am modifying the original input here. If we are not allowed to modify it, sure, take an auxiliary visited array. .

ConstructBST(int pre[],int l,int h)
{
	if(l>h) return NULL;
	temp=getNode(pre[l]);
	if(l==h) return temp;
	for(i=l+1;i<=h;i++)
		if(pre[i]>pre[l])
			break;
	temp->left=ConstructBST(pre,l+1,i-1);
	temp->right=ConstructBST(pre,i,h);
	return temp;
}

Choose a slot with value 1, Perform DFS from here & set all slots to 0 while visiting to avoid them in the further visits.

int isSafe(int (*M)[COL],int r,int c)
{
        return r>=0 && r<ROW && c>=0 && c<COL && M[r][c];
}
 
void DFS(int (*M)[COL],int i,int j)
{
        static int r[]={-1,-1,-1,0,0,1,1,1};
        static int c[]={-1,0,1,-1,1,-1,0,1},k;
 
        M[i][j]=0;
        for(k=0;k<8;++k)
                if(isSafe(M,i+r[k],j+c[k]))
                        DFS(M,i+r[k],j+c[k]);
}
 
int countImage(int (*M)[COL])
{
        int count=0,i,j;
 
        for(i=0;i<ROW;i++)
                for(j=0;j<COL;j++)
                        if(M[i][j])
                        {
                                DFS(M,i,j);
                                count++;
                        }
        return count;
}

Complete working code: ideone.com/RhZcU

I would just say how is the tree implemented?
1. Using child-sibling concept?
2. Using only child concept & no sibling?

my_delete(root) //case 1
{
	if(root)
	{
		my_delete(root->child);
		my_delete(root->sibling);
		free(root);
	}
}

Assume N -ary tree.

my_delete(root) //case 2
{
	if(root)
	{
		for(i=0;i<N;i++)
			my_delete(root->child[i]);
		free(root);
	}
}

A brief description of Pointers vs References.

1. Memory is allocated when a pointer is defined. A reference however, is a name alias & hence no memory is allocated for it[in most of the cases, memory is not allocated. However it is implementation defined.The compiler might be able to avoid storing the address, if it's a reference to local object for instance.].

2. Reference is bound to be initialized at the time of definition because, a reference is implemented with a constant pointer & hence cannot be made to point to the other object.
A pointer however, is not necessary to be initialized at the time of definition & hence can also be changed to point to some other object.

3. A reference automatically gets de-referenced. When you write cout<<p;
It is automatically de-referenced by the compiler & treated as cout<<*p; by the compiler.

Here, p is the reference.

4. A reference to a reference is not possible.Whenever, you declare a reference to a reference, its actually the reference to the same variable.
e.g.


int i;
int &r1=i;
int &r2=r1; <-------------------2


Compiler interprets the statement 2 as:
int &r2=(*r1)
and (*r1) is nothing but the variable i itself.

A pointer to a pointer is however possible.

5. Array of pointer is possible while array of references is not possible(Why?).

6. Address of pointer is possible. Address of reference is not possible. It gives of the address of the variable.

7. There are situations where you are bound to use references.You cannot use pointers there.
Consider the below example:


A a=b+c;

Where a,b,c are objects of class A.
The operator '+' is overloaded as follows:


const A& operator+(const A& o)
{
return A(i+o.i);
}


See sample code here: ideone.com/Q0pE1
Here the reference in the argument list is used to save the memory footprints.
You cannot use pointer in the argument list as you are bound to pass the address of object in the operator function.
A a=&b + &c;
However, if pointer is used in the parameter list, then we will end up adding the addresses rather than object itself.

Any other reason??

@eugene.yarovoi, you might be interested,
follow this link:
leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html

Use DP.

void foo(int n)
{
        static int ind2,ind3,ind5;
        static int arr[30],depth;
        int num2,num3,num5,num,flag=0;
        if(n<=0) return;
        if(depth==0)
        {
                ind2=ind3=ind5=0;// i know this is redundant
                arr[depth++]=1;
        }
        num2=arr[ind2]*2;
        num3=arr[ind3]*3;
        num5=arr[ind5]*5;
 
        num=min(num2,min(num3,num5));
 
        if(num==num2)
        {
                ind2++;
                if(arr[depth-1]!=num2)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num2;
                }
        }
        else if(num==num3)
        {
                ind3++;
                if(arr[depth-1]!=num3)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num3;
                }
        }
        else
        {
                ind5++;
                if(arr[depth-1]!=num5)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num5;
                }
        }
        if(flag)
                foo(n-1);
        else
                foo(n);
        
}

Complete working code: ideone.com/qz4Py

It prints first n ugly numbers.
Note: I have also considered 1 as part of the ugly number series.

void foo(int* arr,int size)
{
        int i=0,j=size-1;
 
        while(i<j)
        {
                if(i&1)
                {
                        if(!(arr[i]&1))
                        {
                                while(!(arr[j]&1)) j--;
                                arr[i]^=1;
                                arr[j]^=1;
                        }
                }
                else
                {
                        if(arr[i]&1)
                        {
                                while(arr[j]&1) j--;
                                arr[i]^=1;
                                arr[j]^=1;
                        }
                }
                i++;
        }
 
        for(i=0;i<size;i++)
                printf("%d ",arr[i]);
 
}

Complete code here: ideone.com/HHAja

int findMSBPos(int n)
{
        int count=0;
        while(n)
        {
                count++;
                n>>=1;
        }
        return count;
}
 
int countSetBits(int n)
{
        int pos,num;
 
        if(!n) return 0;
 
        pos=findMSBPos(n);
        num=1<<(pos-1);
        return ((num*(pos-1))>>1) + (n-num+1) + countSetBits(n&~(1<<(pos-1)));
}

Complete code here: ideone.com/yHSNA

It distorts the stability order. Cannot be used.

public is necessary so that JVM could call the method from outside the package.
static is necessary so that JVM would not require any object to call this method.

One can also go for TRIE. Store all the 100 words in TRIE in sorted form.
As a new word comes, search for its sorted sequence in the TRIE.
The time complexity would be O(length of the word to be searched).
However, it is space consuming.Ternary search trees can be used to reduce the space..

Use DP.

void foo(int n)
{
        static int ind2,ind3,ind5;
        static int arr[30],depth;
        int num2,num3,num5,num,flag=0;
        if(n<=0) return;
        if(depth==0)
        {
                ind2=ind3=ind5=0;// i know this is redundant
                arr[depth++]=1;
        }
        num2=arr[ind2]*2;
        num3=arr[ind3]*3;
        num5=arr[ind5]*5;
 
        num=min(num2,min(num3,num5));
 
        if(num==num2)
        {
                ind2++;
                if(arr[depth-1]!=num2)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num2;
                }
        }
        else if(num==num3)
        {
                ind3++;
                if(arr[depth-1]!=num3)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num3;
                }
        }
        else
        {
                ind5++;
                if(arr[depth-1]!=num5)
                {
                        flag=1;
                        printf("%d\n",arr[depth-1]);
                        arr[depth++]=num5;
                }
        }
        if(flag)
                foo(n-1);
        else
                foo(n);
        
}

Complete working code: ideone.com/qz4Py

It prints first n ugly numbers.

Are we allowed to move balls between the jars?

Edit: Fresh Solution
Let P(1) is probability of choosing jar 1,
P(2) is probability of choosing jar 2,
X is the probability of choosing a red ball in jar1.
Y is the probability of choosing a red ball in jar2.

Total probability= P(1)*X + P(2)*Y
Where P(1)=P(2)=1/2

What is the maximum number of balls a jar can have??

If its 100, move 49 red balls from jar1 to jar2.
Now, jar 1 contains 1 red ball & jar 2 contains 50 blue balls & 49 red balls.
Total probability of drawing a red ball is 1/2 + 0.5*49/99= 74/99=74.74%

Suppose node p is to be deleted.

if(!(p->next)) {free(p); return; }
while(p->next)
{
      p->data=p->next->data;
      if(p->next->next)
              p=p->next;
      else
            break;
}

free(p->next);
p->next=NULL;

This won't work if the node to be deleted is the last node.This problem can be easily solved with the help of dummy node.

void HuffmanTraverse(struct node* root,int* arr,int depth)
{
        int i;
        if(root)
        {
                if(root->left)
                {
                        arr[depth]=0;
                        HuffmanTraverse(root->left,arr,depth+1);
                }
 
                if(!(root->left || root->right))
                {
                        printf("%d: ",root->data);
                        for(i=0;i<depth;i++)
                                printf("%d",arr[i]);
                        printf("\n");
                }
 
                if(root->right)
                {
                        arr[depth]=1;
                        HuffmanTraverse(root->right,arr,depth+1);
                }
        }
}

Complete code here: ideone.com/FHzHI

a) int temp=a;
a=b;
b=temp;

b) a=(a+b)-(b=a)

c) a^=b^=a^=b

The first method can be used even with user defined type however, it takes a temp variable.
The second method doesn't work with user defined types as arithmetic is not possible in case of user defined types.. However, after overloading arithmetic operator[like in C++], it is possible.
The third method is the best as it works on the bits at H/W level & thus doesn't require any temporary register. It thus, guarantees faster operation. However, it fails when the situation needs swapping user defined types.

void foo(char *str)
{
        int i,j;
        for(i=0;str[i];++i)
        {
                j=i+1;
                while(str[j] && str[j]==str[i]+1)
                {
                        printf("%c",str[i]);
                        i++;j++;
                }
                printf("%c\n",str[i]);
        }
}

Complete code here: ideone.com/okAES

@ eugene.yarovoi, there seems to be issues with the binary search also.
Suppose, we want to perform binary search in a 2D array which is sorted row-wise as well as column wise.

------------
|  1 |	2  |
|    | 	   |
|----X-----|
|  3 |	 4 |
|    | 	   |
------------

Suppose the middle element is X. If the item to be found is less than X, only part 1 needs to be searched. However, if the item is larger than X, all the parts 2,3,& 4 need to be searched.
So, the array is not equally distributed in two halves as mentioned in the approach.
What do you think?

Steps:
1. Take two auxiliary arrays r[] & c[].
r[i] would be containing the column number of the largest number in the row i.
c[i] would be containing the row number of the smallest number in the column i.

Now find a i such that arr[i][r[i]] is equal to arr[col[j]][j].
This would give the intersection of the row having largest number with column having minimum number.

Here is the sample code:

void foo(int (*arr)[COL])
{
        int r[ROW],c[COL],i,j,max;
        for(i=0;i<ROW;i++)
        {
                max=0;
                for(j=0;j<COL;j++)
                        if(arr[i][j]>arr[i][max])
                                max=j;
                r[i]=max;
        }
 
        for(i=0;i<COL;++i)
        {
                max=0;
                for(j=0;j<ROW;++j)
                        if(arr[j][i]<arr[max][i])
                                max=j;
                c[i]=max;
        }
 
        for(i=0;i<ROW;++i)
                for(j=0;j<COL;++j)
                        if(arr[i][r[i]]==arr[c[j]][j])
                                printf("%d ",arr[i][r[i]]);
}

Complete code here: ideone.com/1OYSZ

Sorry, very true.. Was in a hurry & missed the point.
Does it make any sense to ask for avoiding mutual exclusion when there is only one resource?

First of all, What is the difference between mutex & semaphore.
Binary semaphore is also called MUTEX as per their values but their purposes are different..
Semaphore is used for signalling purpose. A thread waiting for a semaphore might be signalled by the other thread.
Mutex is used for Blocking purpose.
Mutex is used to provide synchronization on same block of code.
An ownership kind of thing is attached with a MUTEX. The lock is released by the object which has acquired it.
While semaphore is used to control the access to finite number of resources.

Since, here is only queue,
Hence, i feel that MUTEX would be a better choice.

A recursive approach:

void print(int* res,int depth)
{
        int i;
        for(printf("\n"),i=0;i<depth;printf("%d ",res[i]),++i);
}
 
void foo(int sum,int N,int* res,int depth)
{
        int i;
        if(sum<0) return;
        if(!sum)
                print(res,depth);
        else
                for(i=1;i<N;i++)
                        if(!depth || i>=res[depth-1])
                        {
                                res[depth]=i;
                                foo(sum-i,N,res,depth+1);
                        }
}

Complete code here: ideone.com/z2rcm

Good answers.
However, some points are missing. I am re-writing including the missing ones.

1. Memory is allocated when a pointer is defined. A reference however, is a name alias & hence no memory is allocated for it.

2. Reference is bound to be initialized at the time of definition because, a reference is implemented with a constant pointer & hence cannot be made to point to the other object.
A pointer however, is not necessary to be initialized at the time of definition & hence can also be changed to point to some other object.

3. A reference automatically gets de-referenced. When you write cout<<p;
It is automatically de-referenced by the compiler & treated as cout<<*p; by the compiler.

Here, p is the reference.

4. A reference to a reference is not possible.Whenever, you declare a reference to a reference, its actually the reference to the same variable.
e.g.

int i;
       int &r1=i;
       int &r2=r1; <-------------------2

Compiler interprets the statement 2 as:
int &r2=(*r1)
and (*r1) is nothing but the variable i itself.

A pointer to a pointer is however possible.

5. Array of pointer is possible while array of references is not possible(Why?).

6. Address of pointer is possible. Address of reference is not possible. It gives of the address of the variable.

7. There are situations where you are bound to use references.You cannot use pointers there.
Consider the below example:

A a=b+c;

Where a,b,c are objects of class A.
The operator '+' is overloaded as follows:

const A& operator+(const A& o)
        {
                return A(i+o.i);
        }

See sample code here: ideone.com/Q0pE1
Here the reference in the argument list is used to save the memory footprints.
You cannot use pointer in the argument list as you are bound to pass the address of object in the operator function.
A a=&b + &c;
However, if pointer is used in the parameter list, then we will end up adding the addresses rather than object itself.

Any other difference??

There are multiple ways.
1. Use vector STL.

class A
{
        int p;
        public:
        A(int i)
        {
                p=i;
                cout<<"Called"<<endl;
        }
        A(const A & rhs) :p(rhs.p) {
                cout << "Copied\n";
        }
 
};
 
int main()
{
        vector<A> v(5,A(1));<-------5 objects are constructed.
        return 0;
}

output here: ideone.com/lHX5W

2. Call constructor for each object.
A arr[3]={A(1),A(2),A(3)};
This would be better if we want to initialize different objects with different values.
The first object is initialized with1, second with 2 & so on.

However,in the first method using vector, only one object is constructed & initialized with 1 [in our case], & copy constructor is called 5 times to copy that object.

We need max 4 bits to represent digits from 1 to 9.
Use a structure with bit-field.

struct b
{
        unsigned int num:4;
};

Use an array of such structure where each slot will be handling each digit.

This will conserve memory.

Do merge sort.Yes strcmp() will be used for comparing two strings.
That is how time complexity comes out to be N*d*log(N).
I have taken care of time complexity of strcmp(). Here its 'd'.

@Anonymous, updated the post.
Hope its clear.

O(N^2) approach
For each 2D array, search an item in O(N).
How?
Let the matrix be ABCD sorted from A to B & from A to C & C to D & B to D.

A            B
------------
|           |
|           |
------------
C            D

Start searching the item at point C. If the item is greater,we can ignore the column AC. If its less, we can ignore row CD.
In this way, based on the comparison one of the row or column gets rejected. So, time complexity will be O(N+N)=O(N).

-1 for wrong answer. Its undefined behavior.

See here: stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points

How will you print the anagrams if you are making change in the original array?

This has not been asked in the question.
The array contains "abc","cdb","bac","abd"
and you have to output
abc
bac

1. Take an auxiliary array & copy all the strings of the original array.
2. Sort each of the string in auxiliary array.
3. Take another auxiliary array keeping track of the indices of the original array.
4. Sort auxiliary array & simultaneously change the index array.
5. Print the original array according to the index array[while checking contents of the auxiliary array, we want only anagrams right.].
Time complexity: O(N*d*log N)
where d is the max number of chars in a string.
EDIT:
Taking an example:

Lets say, the array contains "abc","abd","bac","bca"
Aux array after sorting each slot: "abc","abd","abc","abc"
The index array would be: 0,1,2,3
After sorting aux array: "abc","abc","abc","abd"
Corresponding Index array: 0,2,3,1

Print Original array a/c to Index array:
abc[at index 0]
bac[at index 2]
bca[at Index 3]
Don't print "abd" [Index 1], it hasn't any anagram.

@sophia, please provide some counter example.

Exhaustive backtracking approach:

void foo(int* arr,int k,int* res,int depth,int N,int sum,int dec)
{
        int i;
        if(sum>N) return;
        if(depth==k)
        {
                if(sum==N)
                        print(res,N);
        }
        else
        {
                if(dec<N)
                {
                        if(!res[dec])
                        {
                                res[dec]=1;
                                foo(arr,k,res,depth+1,N,sum+arr[dec],dec+1);
 
                                res[dec]=0;
                                foo(arr,k,res,depth,N,sum,dec+1);
                        }
                }
        }
}

Complete code here: ideone.com/BeAnJ

Take a double linked list. The head will always contain the most recently used page & tail will contain the least recently page..
A hash where page number will be used for indexing will be taken. Whenever, a page fault occurs i.e. page is not in the memory[the hash slot will be empty], We will create a new node in DLL, put it in the head & store its pointer in the hash.
At any time, if a page needs to be referenced, it will be searched in the hash. If its there, we need to change at most 6 pointers to attach it at the head of DLL.
reqPage->next->prev=reqPage->prev;
reqPage->prev->next=reqPage->next;

reqPage->next=head;
reqPage->prev=NULL;
head->prev=reqPage;

head=reqPage;

@ shiqing881215, see my solution again. I have provided the link also where i am getting the correct output as 11.
Thanks for pointing out the mistake.

@ shiqing881215, You have not drawn the tree correctly. See the position of 1.
I am getting the output as 11 as per the solution after correcting the tree.

void print(char* op,int depth)
{
        int i;
        for(i=0;i<depth;++i)
                printf("%c ",op[i]);
}
 
int calculate(int* arr,int size,char* op,int depth,int result,int val)
{
        if(depth==size)
        {
                if(val==result)
                {
                        print(op,depth);
                        printf("\n");
                        return 1;
                }
        }
        else
        {
                op[depth]='+';
                calculate(arr+1,size,op,depth+1,result,val+*arr);
                
                op[depth]='-';
                calculate(arr+1,size,op,depth+1,result,val-*arr);
        
                op[depth]='*';
                if(val)
                calculate(arr+1,size,op,depth+1,result,val*(*arr));
 
                op[depth]='/';
                if(*arr && val)
                calculate(arr+1,size,op,depth+1,result,val/(*arr));
        }
}

Complete code here: ideone.com/XDML8

int findTriplet(int *arr,int size)
{
        int a,b,c;
        c=size-1;
        while(c>1)
        {
                a=0;b=c-1;
                while(a<b)
                {
                        if(arr[a]*arr[a]+arr[b]*arr[b]==arr[c]*arr[c])
                        {
                                printf("%d %d %d\n",arr[a],arr[b],arr[c]);
                                a++;b--;
                        }
                        else if(arr[a]*arr[a]+arr[b]*arr[b]<arr[c]*arr[c])
                                a++;
                        else
                                b--;
                }
                c--;
        }
}

Complete code here: ideone.com/Z3B5O

struct node* trim(struct node* root,int A,int B)
{
        struct node* temp;
        if(root)
        {
                if(root->data>=A && root->data<=B)
                {
                        root->left=trim(root->left,A,B);
                        root->right=trim(root->right,A,B);
                        return root;
                }
                else if(root->data<A)
                {
                        temp=root->right;
                        free(root);
                        return trim(temp,A,B);
                }
                else if(root->data>B)
                {
                        temp=root->left;
                        free(root);
                        return trim(temp,A,B);
                }
        }
        else
                return NULL;
}

Complete code here: ideone.com/xHclt

Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.

void countCoins(int* coin,int size,int tofind)
{
        int minCount[tofind+1],i,j,mintillnow;
 
        for(i=0;i<tofind+1;++i)
                minCount[i]=0;
 
        for(i=0;i<size;i++)
                if(coin[i]<=tofind)
                        minCount[coin[i]]=1;
        for(i=1;i<=tofind;i++)
        {
                if(!minCount[i])
                {
                        mintillnow=INT_MAX;
                        for(j=1;j<i;++j)
                        {
                                if(minCount[j]+minCount[i-j]<mintillnow)
                                        mintillnow=minCount[j]+minCount[i-j];
                        }
                        minCount[i]=mintillnow;
                }
        }
        printf("Minimum number of coins needed is: %d",minCount[tofind]);
}

The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.

Complete code here: ideone.com/pKEwC

It is giving linker error. Please check it.