CareerCup

I have updated my post. Please read it again.

i=0;weight=1;
while(new bits are coming)
{
          i=(weight*bit + i)%5;
          weight<<=1;
}

Use a finite automata [DFA] & keep changing the states. At the end of the stream, if final state is reached, it is a divisible by 5.
Here is the complete code.

#include <stdio.h>
 
int getState(int state,char bit)
{
        if(state==0)
                return bit==0?0:1;
        else if(state==1)
                return bit==0?2:3;
        else if(state==2)
                return bit==0?4:0;
        else if(state==3)
                return bit==0?1:2;
        else if(state==4)
                return bit==0?3:4;
}
 
int isDivisible(char *seq)
{
        int state=0,i;
        
        for(i=0;seq[i];++i)
        {
                state=getState(state,seq[i]);
        }
        return state==0?1:0;
}
 
int main()
{
        char seq[20];
        fgets(seq,20,stdin);
        
        isDivisible(seq)?printf("Yes"):printf("No");
 
        return 0;
}

It is better than the above approaches because it works on bits & we do not require any arithmetic(modulo & + to calculate the remainder)

@eugene, if the phone numbers be sorted then how the TRIE is going to be handy.
Say numbers are 9657 & 9756.
After sorting both reduce to same number. How you are going to store them in TRIE.

just data structure

of course, its an operator.
In almost all cases, sizeof is evaluated based on static type information (at compile-time, basically).

One exception (the only one, I think) is in the case of C99's variable-length arrays (VLAs).

1. Make a TRIE of all the words to be searched.
2. Now, find the first segment which contains all the words.Mark its length
3. Take two pointers, one pointing to the start of the above segment & other pointing to the end.
4. Increment the end pointer to point to the next word. Check whether both start & end pointer point to the same word. If yes, increment the start pointer to point to next word.[We will also perform the same while findin the first segment]
Now, remove all the extra words from the starting that are not in the TRIE.
5. Proceed above steps until EOF is not encountered, meanwhile also keep updating the minlength if length of the newly found segment is less.

If there are any issues, let me know.

@enihgad, i have modified the code. Now, its working for trees with one child also.
@vineetsetia009, call should be made as:
printBoundaryEdges(root);
I don't think there is any need of main function.

Because characters are stored in ASCII format. i.e. 1 is stored as 49. We do not need the ascii values rather need the exact values. So, 48 is subtracted. Since,two characters are being extracted, so rather than subtracting 48 two times, 96 is subtracted directly.
Hope this is clear.

void calExpr(char *str,int *Op1,char *Op2,int top1,int top2)
{
	int i=0;
	char c;
	for(;str[i];i++)
	{
		c=str[i];
		if(c=='(' || c=='+' || c=='-' || c=='*' || c=='/')
			Op2[++top2]=c;
		else if(c==')')
		{
			if(Op2[top2]=='(')
				top2--;
			else
			{
				cout<<"Invalid Expression ";
				return;
			}
		}
		else
		{
			if(Op2[top2]=='+' || Op2[top2]=='-' || Op2[top2]=='*' || Op2[top2]=='/')
			{
				int y=atoi(&c);
				int x=Op1[top1--];
				char ch=Op2[top2--];
				if(ch=='+')
					Op1[++top1]=x+y;
				else if(ch=='-')
					Op1[++top1]=x-y;
				else if(ch=='*')
					Op1[++top1]=x*y;
				else if(ch=='/')
					Op1[++top1]=x/y;

			}
			else
				Op1[++top1]=atoi(&c);
		}
	}
	while(top2>=0)
	{
		if(Op2[top2]=='+' || Op2[top2]=='-' || Op2[top2]=='*' || Op2[top2]=='/')
		{
			int y=Op1[top1--];
			int x=Op1[top1--];
			char ch=Op2[top2--];
			if(ch=='+')
				Op1[++top1]=x+y;
			if(ch=='-')
				Op1[++top1]=x-y;
			if(ch=='*')
				Op1[++top1]=x*y;
			if(ch=='/')
				Op1[++top1]=x/y;
		}
	}
	cout<<Op1[0];
}

int main()
{
	int Operator[5],top1=-1,top2=-1;
	char Operand[5];
	char str[20];
	cout<<"Enter the Infix Expression ";
	cin>>str;
	calExpr(str,Operator,Operand,top1,top2);
	return 0;
}

@gk, can you explain the third one with an example?

void my_add(char *n1,char * n2,char *n3)
{
 
        int top=-1,carry,sum;
        int i=0,j=0;
        carry=0;
        while(n1[i] && n2[j])
        {
                sum=n1[i] + n2[j] - 96 + carry;
                printf("%d .. ",sum);
                carry=sum/10;
                sum%=10;
                n3[++top]=(char)(sum+48);
                i++;j++;
        }
        while(n1[i])
        {
                sum=n1[i] -  48 + carry;
                carry=sum/10;
                sum%=10;
                n3[++top]=(char)(sum+48);
                i++;
        }
        while(n2[j])
        {
                sum=n2[j] -  48 + carry;
                carry=sum/10;
                sum%=10;
                n3[++top]=(char)(sum+48);
                j++;
        }
        if(carry)
                n3[++top]=(char)(carry+48);
        n3[++top]='\0';
                printf("%s",n3);
        printf("Add\n");
}

void zigZagTraversal(struct node *root)
{
	struct node *Stack1[20],*Stack2[20],*temp;
	int top1=-1,top2=-1,LeftToRight=1;
	
	Stack1[++top1]=root;
	
	while(top1>=0 || top2>=0)
	{
		if(LeftToRight)
		{
			while(top1>=0)
			{
				temp=Stack1[top1--];
				printf("%d ",temp->data);
				
				if(temp->left)
					Stack2[++top2]=temp->left;
					
				if(temp->right)
					Stack2[++top2]=temp->right;
			}
			printf("|");
		}
		else
		{
			while(top2>=0)
			{
				temp=Stack2[top2--];
				printf("%d ",temp->data);
				
				if(temp->right)
					Stack1[++top1]=temp->right;
					
				if(temp->left)
					Stack1[++top1]=temp->left;
			}
			printf("|");
		}
		LeftToRight=1-LeftToRight;
	}
}

I can think of one approach. First run a loop to ensure that date in an interval ranges from lower to higher[this is a test case].
Now, sort the data in increasing order higher range. nlogn
run a loop & check whether lower of an interval is smaller than the previous higher of interval. If yes, this is the overlapping interval.

int bin(int *arr,int l,int h,int k)
{
        int mid;
        if(l>h)
                return -1;
        if(l==h)
        {
                return arr[l]==k?l:-1;
        }
        else
        {
                mid=(l+h)>>1;
                if(arr[mid]==k)
                        return mid;
                else if(k>arr[mid])
                        return bin(arr,mid+1,h,k);
                else
                        return bin(arr,l,mid-1,k);
        }
}

@banerjee36, did you try below approach

Here is the logn approach

int power(int n,int k)
{
        int p;
        if(k==0)
                return 1;
        else
        {
                p=power(n,k/2);
                p*=p;
                if(k&1)
                        p*=n;
                return p;
        }
}
 
int main()
{
        int n=3,k=27;
        power(n,n)==k?printf("Yes"):printf("No");
        return 0;
}

***ideone.*com/oEpgE***

Here N=9

int isSafe(int (*maze)[N],int x,int y)
{
	if(x>=0 && x<N && y>=0 && y<N && !maze[x][y])
		return 1;
	return 0;
}

void Maze(int (*maze)[N],int x,int y,int (*sol)[N])
{
	static int i,j;
	if(x==N-1 && y==N-1)
	{
		printf("\n\nSolution\n\n");
		sol[x][y]=1;
		for(i=0;i<N;i++)
		{
			for(j=0;j<N;j++)
				printf("%d ",sol[i][j]);
			printf("\n");
		}
	}
	else
	{
		if(isSafe(maze,x,y))
		{
			sol[x][y]=1;

			Maze(maze,x+1,y,sol);
			Maze(maze,x,y+1,sol);

			sol[x][y]=0;
		}
	}
}

isIsotropic(root1,root2)
{
	if(!root1 && !root2)
		return true;
	if(!root1 || !root2)
		return false;
	return root1->data==root2->data && ( (isIsotropic(root1->left,root2->left) && isIsotropic(root1->right,root2->right)) || (isIsotropic(root1->left,root2->right) && isIsotropic(root1->right,root2->left)) )
}

1. Use augmented BST where each node will contain two extra fields, one keeping track of the index of the element, another keeping track of the largest index of element less than this node's element.
Making clarifications, while inserting a value in BST, if it is less than root node, update the second field only if it is larger than the field stored there. If the field value is not set, then store this index.
2. Insert the elements into BST, if we use self balancing BST, the running time complexity is O(nlogn).
3. For each element in the array, search it in BST & print its corresponding field .

Let me know if i am missing anything.

k=0;p=0;
	for(i=p;i<row;i++)
	{
		for(j=k;j<col;j++)	//k represents column
			printf("%d ",arr[i][j]);
		p++;
		for(m=p;m<row;m++)
			printf("%d ",arr[m][col-1]);
		col--;
		for(l=col-1;l>=k;l--)
			printf("%d ",arr[row-1][l]);
		row--;
		for(n=row-1;n>=p;n--)
			printf("%d ",arr[n][k]);
		k++;
	}

Well, there are several approaches to solve this problem.

Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list

Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.

while(head1)
{
cur2=head2;
while(cur2)
{
    if(cur2==head1)
        return cur2;
    cur2=cur2->next;
}
head1=head1->next;
}

Time Complexity: O(N*M)
Space Complexity: O(1)

Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].

Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.

Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 6: [A better approach] 1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)

Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)

Guys, we can do it without reversing the linked list.

int isPalindrome(**root,*head)
{
	if(!head)
		return 1;
	else
	{
		int res=isPalindrome(root,head->next);
		
		if(res==0)
			return 0;
		int r=(*root)->data==head->data;
		*root=(*root)->next;
		return r;
	}
}

What if the file contain duplicate integers?
Will the list of k largest elements contain duplicate elements?
If yes, then i don't think that bit vector in that case is going to work.
Because, a bit corresponds to only a single integer. I doesn't keep track of duplicate elements.

The file size is 4GB. i.e. 2^32 bytes. The number of integers would be [on 32 bit machine] 2^32/4=2^30.
The main memory size is 1GB i.e. 2^30 bytes.
So, The size is exactly the same.
We can follow one out ofthe two below approaches:

Approach 1:
Read the file in chunks say 4 chunks. Maintain a min heap of size k & update it as said by the @wgpshashank. After the file scanning is over, we are left with k largest elements.
Now, it depends whether we are using signed int or unsigned int, In simple words, it is a good point to discuss with the interviewer because overflow may occur. We will have to handle it accordingly.

Approach 2:
Instead of reading file in chunks, we can create a bit vector & mask it accordingly where each bit will represent one integer. So, the space complexity reduces by a factor of 8.
Follow the above approach of min heap afterwards.

This is basically a backtracking algorith.

void print(char *s1,char *s2,char *s3,int N1,int N2,int depth)
{
        int i;
        if(N1==0 && N2==0)
        {
                for(i=0;i<depth;i++)
                        printf("%c",s3[i]);
                printf("\n");
        }
        if(N1!=0)
        {
                s3[depth]=*s1;
                print(s1+1,s2,s3,N1-1,N2,depth+1);
        }
 
        if(N2!=0)
        {
                s3[depth]=*s2;
                print(s1,s2+1,s3,N1,N2-1,depth+1);
        }
}
 
int main()
{
        char s1[]="abc",s2[]="de",s3[10];
        
        print(s1,s2,s3,strlen(s1),strlen(s2),0);
        return 0;
}

The explanation goes as follows:
1. First include the first character of string 1 & iterate for the rest of take of the characters.
2. Apply the same for the second string.
3. If both the strings are finished, output string 3.

The approach will vary based on whether the function would be called once or multiple times.
If it is called multiple times, then below approach may be good as amortized time complexity is reduced.

Here s one approach. Make a look up table[using bit vector] of the numbers present in the set.
Apply divide & conquer technique. generate a random number & look in the bit vector whether its already present. If not,return.
else, call recursively for 0 to k-1 & k+1 to N.

Let me know if there is any better approach.

void fun(int *arr,int n)
{
        int i,j=n-1;
        for(i=0;i<=j;)
        {
                if(arr[i]==1)
                {
                        swap(&arr[i],&arr[j]);
                        j--;
                }
                else i++;
        }
        for(i=0;i<n;i++)
        {
                printf("%d ",arr[i]);
        }
}
 
int main()
{
        int arr[]={0,1,1,0,0,1};
        fun(arr,sizeof(arr)/sizeof(arr[0]));
 
        return 0;
}

Cracked it!!
Sometimes, we use to think too much. However, we already know the solution.
Modified partition algorithm of quick sort solves the problem in O(MxN) time& without using any extra space.
here is the working code:

#define M 3  //number of rows
#define N 3  //number of columns

struct Index
{
	int row;
	int col;
}ind;

void swap(int *a,int *b)
{
	int temp=*a;
	*a=*b;
	*b=temp;
}

void partition(int (*A)[N],int lr,int lc,int hr,int hc)
{
	int pivot=A[lr][lc],j,k,l,m;
	j=hr;k=hc;
	l=(lc==N-1)?(lr+1):lr;
	m=(lc==N-1)?0:lc+1;

	while(1)
	{
		while(pivot>=A[l][m])
		{
			m++;
			if(m==hc && l==hr)
				break;
			if(m==N)
			{
				l++;
				m=0;
			}
		}

		while(pivot<A[j][k])
		{
			k--;
			if(k==lc && j==lr)
				break;
			if(k<0)
			{
				j--;
				k=N-1;
			}
		}

		if(l<j || (l==j && m<k))
			swap(&A[l][m],&A[j][k]);

		else
		{
			swap(&A[lr][lc],&A[j][k]);
			ind.row=j;
			ind.col=k;

			return;
		}
	}
}

void findkthSmallest(int (*A)[N],int lr,int lc,int hr,int hc,int k)
{
	int i;

	if((hc<N && hr<M) && (lr<hr || (lr==hr && lc<hc)))
	{
		partition(A,lr,lc,hr,hc);

		i=ind.row*N + ind.col;

		if(i+1==k)
		{
			printf("%d ",A[ind.row][ind.col]);
			return;
		}
		else if (i+1<k)
		{
			(ind.col==N-1)?(ind.col=0,ind.row++):(++ind.col);
			findkthSmallest(A,ind.row,ind.col,hr,hc,k);
		}
		else
		{
			(ind.col==0)?(ind.col=N-1,ind.row--):(--ind.col);
			findkthSmallest(A,lr,lc,ind.row,ind.col,k);
		}
	}
	else if(lr==hr && lc==hc)
	{
		i=lr*N + lc;
		if(i+1==k)
			printf("%d ",A[lr][lc]);
	}
}

Call : findkthSmallest(A,0,0,M-1,N-1,k); where A is the 2D Matrix.

Let me know your thoughts on this approach.

Well there are multiple approaches.

Approach 1:

Take a max heap & insert first k unique elements[can be easily checked]. Heapify the heap.
Now, when a new element is smaller than the head of the heap,replace head with this new element heapify it. At the last, the head of the heap indicates kth smallest element if size of the heap is k else kth smallest element doesn't exist.

Time complexity: O(NlogK)
Space complexity: O(K)
Approach 2[A better approach]:

The elements may be duplicated right. So, check for unique elements by comparing with its previous elements & stop if unique variables found so far counts to k.
Time complexity: O(N)
Space complexity: O(1)
Approach 3[A better approach(may be)]:

A modified version of quick sort partition algorithm can also be used. But possibly it will lead to a worst case as the array is already sorted.
here two questions arise:
1. Does it work if the array contain duplicates?
2. Would it be better than my second approach?

Approach 4:
Here's an O(kLogN) solution:
Using a variation of Binary Search to find the last occurrence of a given value,
Get 1st value - O(1).
Search for last occurrence of this value O(logN), then look at next element to get 2nd value - O(1).
Repeat until kth value is found.

Use max_heap of size k.
Scan upto k elements of the matrix & insert in the max heap.
Now, for each new element of matrix, check whether if it is smaller than the head of the heap.
If it is smaller, replace the head element with this new element. Update the heap.
At last, The head denotes the kth smallest element.
Time complexity: O(M*N*log(k))
Space complexity: K

Let me know if i am missing anything.

Test cases
1. The array is sorted.
2. The array contain all duplicates.[second largest doesn't exist]
3. Array contain both positive & negative numbers.
4. A part of the array is sorted suc that both largest & second largest exists in this sorted part.

1. Make a copy of the original array.
2. Sort each string of the duplicated array.
3. Now, sort the duplicated array & while sorting, maintain the indices in another array.
4. Print the strings according to indices.

Let me know if i have mistaken anything.

The would be sorted in alternate fashion. So, it boils down to finding the element in each array using binary search.

Internet explorer has already an option to mark your favorite pages. So, i don't think Bookmarks option would be really a good choice.

This is basically a boundary edge traversal.

void printBoundaryEdgesLeft(struct node *root)
{
	if(root->left)
        {
                printf("%d ",root->data);
		printBoundaryEdgesLeft(root->left);
        }
        else if(root->right)
        {
                printf("%d ",root->data);
		printBoundaryEdgesLeft(root->right);
        }
}

void printBoundaryEdgesLeaves(struct node *root)
{
	if(root)
	{
		printBoundaryEdgesLeaves(root->left);
		
		if( !(root->left) && !(root->right) )
			printf("%d ",root->data);
			
		printBoundaryEdgesLeaves(root->right);
	}
}

void printBoundaryEdgesRight(struct node *root)
{
	if(root->right)
        {
		printBoundaryEdgesRight(root->right);
                printf("%d ",root->data);
         }
        else if(root->left)
        {
		printBoundaryEdgesRight(root->left);
                printf("%d ",root->data);
        }
}

void printBoundaryEdges(struct node *root)
{
	if(root)
	{
		printf("%d ",root->data);
		printBoundaryEdgesLeft(root->left);
		
		printBoundaryEdgesLeaves(root->left);
                printBoundaryEdgesLeaves(root->right);
		
		printBoundaryEdgesRight(root->right);
	}
}

fails when all numbers are same.