CareerCup

What if one word doesn't fit into memory at a time?

The memory for string is allocated in the read only area of the data region.While memory for the pointer p is allocated in the stack. Hence compiler doesn't permit us to the the string to which the pointer is pointing. To understand & see how it is happening, see the below program & try to analyze how the memory is allocated.

int main()
{
        int i;
        char *p="Hello";
        int j;
        printf("%p %p %p %p",&i,&p,&j,p);
        return 0;
}

ideone.com/qNREi

int findDiff(root)
{
	if(!root)
		return 0;
	l=0;r=0;
	l=findDiff(root->left);
	r=findDiff(root->right);

	root->val=l-r;
	return l+r+1;
}

Please let me know if anything is missing.

Its a huge pointer. Remember always the last type is taken into account.

It is the simplest:

int main()
{
        char *s="int main(){char *s=%c%s%c;printf(s,34,s,34)}";
        printf(s,34,s,34);
}

see here:ideone.com/iZvI3

The size of the ready queue is a constant factor for any processor. So, picking out a process for execution by the scheduler is a constant factor. Hence, O(1) process.

Here is my approach.
Note that i have not handled the case of negative numbers.

int binaryD(char *bin,int n,int depth)
{
        static int count;
 
        if(n)
        {
                count++;
                binaryD(bin,n/2,depth+1);
                bin[depth]=(n&1)?'1':'0';
        }
        return count;
}
 
int binaryF(char* bin,float f,int *depth)
{
        int count=0,i;
 
        if(f<=0.0f)
                return 1;
        if(f==1.0f)
        {
                bin[*depth]='1';
                return 1;
        }
        while(f)
        {
                f*=2;
                if(f==1.0f)
                {
                        bin[++*depth]='1';
                        return 1;
                }
                i=f;
                if(f>1.0f)
                {
                        bin[++*depth]='1';
                        f=f-i;
                }
                else
                        bin[++*depth]='0';
                if(++count>32)
                        return 0;
        }       
}       
 
void toBinary(char *s)
{
        int num=0,i,depth=0,po=10,count;
        char bin[50];
        float f=0.0f;
 
        for(i=0;s[i] && s[i]!='.';i++)
        {       
                if(s[i]>='0' && s[i]<='9')
                        num=num*10 + s[i]-'0';
                else
                        return;
        }
 
        if(s[i]=='.')
        {
                for(++i,po=10;s[i];i++,po*=10)
                        if(s[i]>='0' && s[i]<='9')
                                f=f+ (s[i]-'0')/(float)po;
                        else
                                return;
        }
 
        i=binaryD(bin,num,depth);
 
        for(count=i-1;count>=0;count--)
                printf("%c",bin[count]);
 
        count=i;
        if(f!=0.0f)
        {
                bin[i]='.';
                binaryF(bin,f,&i);
 
                for(;count<=i;count++)
                        printf("%c",bin[count]);
        }
}

ideone.com/GElaE

Please let me know if any corner cases are missing

Test cases:
Negative number.
Positive number.
Are white spaces allowed: " 123.45".

Modified Kadane algorithm can perform the task.
Time Complexity: O(M^2*N)
Space Complexity: O(M)// number of rows
Check for each sub-array starting with column number i to column number j. Store the sum[elements with row 0 will be summed & stored in temp[0] & so on] in the temporary buffer. Apply kadane algorithm on the temp[] to find the maximum sum contiguous subsequence. Let maximum sum subsequence in temp[] lies between y1 & y2. Keep updating the maximum sum till now as well as y1,y2,i&j.

Here is the function:

void printV(struct node *root,int *arr,int *depth)
{
        if(root)
        {
                arr[++(*depth)]=root->data;
                printV(root->left,arr,depth);
                
                if(!(root->left || root->right))
                {
                        while((*depth)>=0)
                                printf("%d ",arr[(*depth)--]);
                }
                
                printV(root->right,arr,depth);
        }
}

Complete code: ideone.com/IAKcD

Won't work. Lets say you have pushed 2,3 &5.
Now the root becomes NULL, print it & return. However you are not emptying the stack.So, 2,3 remains in stack & again you push 6 to stack. The root becomes NULL in next call. You print 6,3,2.

In simple, you have written the program to print all leaf to root paths.

The problem can be approached as follows:
If a number has odd number of factors, then that numbered door will be open.
Now, since only perfect squares have odd number of factors, all the doors with numbers as perfect square will be open.

Even if the thread is implemented as a user level thread, if the processing of the threads is not serialized,the processor can be assigned to the other thread.

The output is undefined. There is no sequence point defined between the two expressions ++i & i++. Even if the expression is written like i=i++, the output is said to be undefined. A sequence point is also needed betwwen the two expressions i & i++, as the evaluation order of the expression is uncertain & varies from compiler to compiler based on parsing algorithm it follows to parse the instructions to be executed.
In simple words, if the value of the same variable is changed more than once in a statement, then it is said to be UNDEFINED BEHAVIOUR(UB).
A semi-colon is a sequence point where as +(plus) is not.

ideone.com/LGFEm

void correctList(struct node *root)
{
        struct node *cur,*prev,*mark1,*mark2,*p,*q,*r;
        if(!root || !(root->next))
                return;
 
        cur=root;prev=NULL;
        while(cur->next && cur->data<cur->next->data)
        {
                prev=cur;
                cur=cur->next;
        }
        mark1=prev;
        prev=mark1->next;
        while(cur->next && cur->data>cur->next->data)
                cur=cur->next;
        mark2=cur->next;
        
        p=r=NULL;q=mark1->next;
        while(q!=mark2)
        {
                r=q->next;
                q->next=p;
                p=q;
                q=r;
        }
        mark1->next=p;
        prev->next=mark2;
}

here is a backtracking approach which prints the solution as well.

#include <stdio.h>
 
void coinDenomination(int *coin,int size,int *sol,int depth,int tofind,int start)
{
        int i;
        if(tofind<0)
                return ;
        if(tofind==0)
        {
                for(i=0;i<depth;i++)
                        printf("%d ",sol[i]);
                printf("\n");
        }
        else
        {
                for(i=start;i<size;i++)
                {
                        sol[depth]=coin[i];
                        coinDenomination(coin,size,sol,depth+1,tofind-coin[i],i);
                }
        }
}
 
int main()
{
        int coin[]={1,5,10,25},size,sol[50]={0},tofind;
 
        size=sizeof(coin)/sizeof(coin[0]);
 
        scanf("%d",&tofind);
 
        coinDenomination(coin,size,sol,0,tofind,0);
        
        return 0;
}

ideone.com/0ioYp

Cut the parallel sides [each side] into 4 equal parts. Now join the corresponding points so that the line joining them do not cross each other.

Its not mentioned that the tree is BST. It may be binary only.

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
        int data;
        struct node *next;
};
 
void createList(int *arr,int size,struct node **root)
{
        int i;
        struct node *tail;
        for(i=0;i<size;i++)
        {
                if(!(*root))
                {
                        *root=(struct node*)malloc(sizeof(struct node));
                        (*root)->next=NULL;
                        (*root)->data=arr[i];
                        tail=*root;
                }
                else
                {
                        tail->next=(struct node*)malloc(sizeof(struct node));
                        tail=tail->next;
                        tail->next=NULL;
                        tail->data=arr[i];
                }
        }
}
 
void traverse(struct node *root)
{
        for(;root;printf("%d ",root->data),root=root->next);
        printf("\n\n");
}
 
struct node *updateList(struct node *root)
{
        struct node *p,*cur,*tail;
        static struct node *newroot=NULL;
        if(root==NULL)
                return NULL;
 
        cur=root;
        while(cur)
        {
                if(cur->next && cur->data!=cur->next->data)
                {
                        if(!newroot)
                        {
                                newroot=cur;
                                tail=cur;
                        }
                        else
                        {
                                tail->next=cur;
                                tail=tail->next;
                        }
                        cur=cur->next;
                }
                else
                {
                        p=cur;
                        while(cur->next && cur->data== cur->next->data)
                                cur=cur->next;
                        if(p==cur)
                        {
                                if(!newroot)
                                {
                                        newroot=cur;
                                        tail=cur;
                                }
                                else
                                {
                                        tail->next=cur;
                                        tail=tail->next;
                                }
                        }
                        cur=cur->next;  
                }
        }       
        tail->next=NULL;
        return newroot;
}
 
int main()
{
        int arr[]={1,1,1,2,3},size;//{1,2,3,3,4,4,5},size;
        struct node *root=NULL;
        createList(arr,sizeof(arr)/sizeof(arr[0]),&root);
        traverse(root);
 
        traverse(updateList(root));
        return 0;
}

ideone.com/QVsBy

#include <stdio.h>
#include <stdlib.h>

int my_atoi(char *s)
{
	int i,num=0,sign=1;

	for(i=0;s[i];i++)
        {
                if(s[i]==' ')
                        continue;
                else if(s[i]=='-') sign=-1;
                else break;
        }
        
        for(;s[i] && s[i]>='0' && s[i]<='9';i++)
                num=num*10 + s[i]-'0';
        return num*sign;
}

int main()
{
	char s[]="-12a4";

	printf("%d %d",atoi(s),my_atoi(s));

	return 0;
}

ideone.com/QiIS3

#include <stdio.h>
#include <limits.h>
 
void find(char *s)
{
        int hash[256]={0},i,min=INT_MAX;
 
        for(i=0;s[i];i++)
                hash[s[i]]++;
 
        for(i=0;s[i];i++)
        {
                if(hash[s[i]]==1 && i<min)
                        min=i;
        }
        if(min!=INT_MAX)
        printf("First non-repeating character: %c",s[min]);
        else
                printf("No non-repeating character");
}
 
int main()
{
        char ch[10];
        fgets(ch,10,stdin);
 
        find(ch);
        return 0;
}

ideone.com/WuUQq

The question is to in place sort the string not output it online.

TRIE

Use template metaprogramming.

I explained the reason why only printf inside main() is working.
And how compiler is able to calculate size of return type of the function fun().

Did you check my answer. I have also said 4.

Output is 100.
A little tricky question.
The conditional operator has right to left associativity.
So, it considers "20:10&&y>x?50" in if part & 100 in second part. In our case, the logical && is never getting evaluated as the condition is false.(x<z)

Output will be 4. An expression is never evaluated inside sizeof operator.
So, the function will not be called. However, you must be surprising that how the compiler is able to output 4. Its because compiler sees the signature of the function. Change the return type to double & you will see the output 8.

#include <stdio.h>
#define ROW 4
#define COL 5

void findMaxSumSubset(int *temp,int *x1,int *x2,int *sum_till_now)
{
	int i,j,max_sum=0;
	
	for(i=0;i<ROW;i++)
	{
		(*sum_till_now)+=temp[i];
		if((*sum_till_now)<=0)
		{
			*sum_till_now=0;
			*x1=i+1;
		}
		
		if((*sum_till_now)>max_sum)
		{
			max_sum=*sum_till_now;
			*x2=i;
		}
	}
	*sum_till_now=max_sum;
}

void display(int (*arr)[COL],int x1,int y1,int x2,int y2)
{
	int i,j;
	printf("\n--------------------------------\n");
	printf("%d %d %d %d\n",x1,y1,x2,y2);
	printf("\n--------------------------------\n");
	for(i=y1;i<=y2;i++)
	{
		for(j=x1;j<=x2;j++)
			printf("%d  ",arr[i][j]);
		printf("\n");
	}
}

void findMaxSumSubsetRectangle(int (*arr)[COL])
{
	int i,j,k,x1,x2,fx1,fx2,fy1,fy2,sum_till_now,max_sum,temp[ROW];
	
	max_sum=0;
	for(i=0;i<COL;i++)
	{
		for(k=0;k<ROW;k++)
			temp[k]=0;
		x1=i;
			
		for(j=i;j<COL;j++)
		{
			sum_till_now=0;
			for(k=0;k<ROW;k++)
				temp[k]+=arr[k][j];
				
			findMaxSumSubset(temp,&x1,&x2,&sum_till_now);
			
			if(sum_till_now>max_sum)
			{
				fy1=x1;
				fy2=x2;
				fx1=i;
				fx2=j;
				max_sum=sum_till_now;
			}
		}
	}
	printf("Max Sum = %d\n",max_sum);
	display(arr,fx1,fy1,fx2,fy2);
	
}

int main()
{
	int arr[ROW][COL],i,j;
	
	for(i=0;i<ROW;i++)
		for(j=0;j<COL;j++)
			scanf("%d",&arr[i][j]);
	
	findMaxSumSubsetRectangle(arr);
	
	return 0;
}

/************************************  SAMPLE OUTPUT  ****************************

1 2 -1 4 -20
8  -3  4  2  1  
3  8  10  -8  3  
-4  -1  1  7  6  
Max Sum = 37

--------------------------------
0 1 4 3
--------------------------------
8  -3  4  2  1  
3  8  10  -8  3  
-4  -1  1  7  6  

*/

An approach without backtracking with O(1) space.

#include <stdio.h>
#include <string.h>
#include <math.h>
 
void comb(char *str)
{
        int n,i,j,top,wt;
        n=strlen(str);
        n=pow(2,n);
 
        for(i=1;i<n;i++)
        {
                for(j=i,wt=1,top=0;j>0;j>>=1,top++)
                {
                        if(j&wt)
                                printf("%c",str[top]);
                }
                printf("\n");
        }
}
 
int main()
{
        char str[]="ABCD";
        comb(str);
        return 0;
}

ideone.com/A5Ucq

This approach uses only minus operator to calculate gcd.

int gcd(int a,int b)
{
        int r;
        r=a>b?(a-b):(b-a);
        while(r)
        {
                a=b;
                b=r;
                r=a>b?(a-b):(b-a);
        }
        return a;
}
 
int main()
{
        int a=12,b=27,r;
        
        printf("%d ",a*b/gcd(a,b));
        return 0;
}

I have modified the code & it prints the encodings too.

#include <stdio.h>
 
void encoding(char *s,char *str,int depth)
{
        int i;
        if(*s=='\0')
        {
                str[depth]='\0';
                printf("%s\n",str);
        }
        else
        {
                str[depth]=*s-48 + 64;
                encoding(s+1,str,depth+1);
                
                if(*(s+1)!='\0')
                {
                        i=( (str[depth]-64)*10 + (*(s+1)-48) );
                        if(i<=26)
                        {       str[depth]=i+64;
                                encoding(s+2,str,depth+1);
                        }
                }
        }
}
 
int main()
{
        char s[]="12121",str[10];
        encoding(s,str,0);
        return 0;
}

ideone.com/1MIff

Here is a recursive one.
The idea is very simple. If we know the number of solutions for n-1 characters, we can extend it for n characters. How? Lets see.
Say the number of solutions for n-1 characters is p, then if by combining n-1th character with nth character gives an integer <=26, it also leads to another possible solution.\
Based on same idea, here is the simple code.

#include <stdio.h>
#include <string.h>
int count_decode(char s[10],int n)
{
    int x1,x2,z,res;
    if(n<0)
        return -1;
    if(n==0)
        return 1;
    else
    {
        res= count_decode(s,n-1);
        x1=s[n]-'0',x2=s[n-1]-'0';
        z=x2*10 + x1;
        return (z<=26?(res+1):res);
    }
}
int main()
{
    int i,j,n;
    char S[10];
    gets(S);
    n=strlen(S);
    printf("< %d >",count_decode(S,n-1));
return 0;
}

@Barney, @luv, I want to share some of my concepts.
I request you to get your basic concepts clear & brushed up.
When you are calling f(), then memory is being allocated for array a[] on the stack, where you are initializing its sots with 1. Now, since this array has been allocated on the stack, the scope is local. When you return from the function, the memory gets freed up. However memory doesn't go anywhere. The OS maintains a free list of all the memory which has been freed & so, can be used by any other process. By garbage value, the process means that it is expecting any unusual value[it may mean 1 or value with figure like 84638290(Both are considered as garbage for that process)].
Now, coming to the point, When you call function g(), memory is being allocated for array b[], However, its just an accident that the same memory gets allocated that was being allocated to a[] & so, it contains all 1.
However, its never safe to rely upon such type of allocation[as its just an accident].
A different compiler, a different optimization settings would trap you.

Hope everything is clear.

Yes, you are correct. Augmented BST will definitely handle this case. But it won't handle the case of intersecting intervals.

Use Augmented BST where each node will have three child.
An interval with end time less than the start time of the root will serve as the left child.

An interval with start time greater than the start time of the root & end time less then end time of the root will serve as the middle child.

An interval with start time greater than the end time of the root will serve as the right child.

Now insert all intervals in the BST. Print all the middle children.
But the problem is that it won't allow the insertion of the intersecting intervals.Do the presence of intersecting intervals really change the solution?

Garbage value.

I think the buffer should be considered as circular queue.
Initialise the tokennumber with -1.
and inside allocatetoken()
tokennumber=(++tokennumber)%1000 + 1001.

Maintain a BST of customers. The node will contain customer id & a hash of size 2[2 days are there]. when a new customer logs in, search its existence in BST. If its there update the corresponding hash. If no,insert a new node in BST & update the corresponding hash entry.
Finally traverse the BST & output all customers with both days visited.
Note that i think this approach is dynamic because there is no limit on the number of customers. So, it would be better than hash where initially size is fixed[may be resized later but takes time to copy the enteries].

See this example:

#pragma pack(1)
 
struct s
{
        char c;
        int i;
};
 
int main()
{
        printf("%d ",sizeof(struct s));
        return 0;
}

The output is 5 because i have changed the alignment to 1 byte.
So, 1byte for char + 4 bytes for int. ideone.com/2Gg6n

#pragma directive can be used to change the word alignment of the user defined type.
Used as: #pragma pack(1).
Hope its clear.

yeah sure. There is a concept called as memory banking which is undertaken by the microprocessor for faster memory access. In INTEL micro-processor, an address always starts from the even one. If it starts from the odd address, then the micro-processor will take two clock cycles to access a memory.
I am not talking about the word alignment in case of fundamental types. Word alignment plays a very vital role in case of use defined types for faster memory access.

Now, coming to your issue. Your output is correct but you are missing some points. Word alignment is never done based upon the size of biggest type. Consider the below example:

struct s
{
        int i;
        double d;
};
 
int main()
{
        struct s s1;
        printf("%d ",sizeof(s1));
 
        return 0;
}

The output is 12 & not 16. See here: ideone.com/uVdlU

One more point must be noted. Alignment is also done based on the structure variables.

The output depends upon the architecture i.e. word length of the micro-processor.
If the word length is 16 bits, then the output is 4 bytes.
If the word length is 32 bits, then the output is 8 bytes.
One more factor that may affect the output is the word alignment which can be changed by #pragma. By default, in turbo-c, the word alignment is 1 byte.There is no effect of #pragma directive. So, there you will find the output as 3 bytes.

int isValid(int (*sudoku)[SIZE],int row,int col)
{
	int i,j,start_row,start_col;
	// initialise a hash of size 10 with each slot containing 3.

	for(j=0;j<col;j++)
	for(i=0;i<SIZE;i++)// checking each column
		if(hash[sudoku[i][j]]==3)
			hash[sudoku[i][j]]--;
		else return 0;
	
	for(j=0;j<row;j++)		
	for(i=0;i<SIZE;i++)// checkin each row
		if(hash[sudoku[j][i]]==2)
			hash[sudoku[j][i]]--;
		else
			return 0;
		
	return 1;
}

If all the rows & all the columns have been checked for correctnes, then there is no need to check correctness of each grid.

The behavior is undefined.The explanation goes as follows:
If you want to change the pointer p to point to another memory location, you must use &p in scanf.
However, if you write p, then you must supply the format specifier as %d, because by p, you are actually passing the memory location where the pointer p is pointing[i.e. i]. So, whatever you input that gets stored in i indirectly.
Note that in printf, if the format specifier is changed then the programmer is responsible for all kinds of side effects.

@Barney, My program is working correctly for the input set given by you.
I request you to check it again. Can you provide the link where you tried it & it failed[like ideone]?
Here is the link where i have tried.
Please see: ideone.com/9c0A6
Note: Here i am not able to figure out why it is showing runtime error. The program is working perfectly under the ubuntu [gcc] platform without reporting any run-time error or segmentation fault[memory access violation exception].

Here is the backtracking approach:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
 
 
void back(int *arr,int *sol,int N,int tillnow,int sumtillnow,int remainsum,int *finalsol)
{
        static int mindiff=INT_MAX;
        int i;
        if(tillnow==N/2)
        {
                if(abs(sumtillnow-remainsum)<mindiff)
                {
                        mindiff=abs(sumtillnow-remainsum);
                        for(i=0;i<N;i++)
                                finalsol[i]=sol[i];
                }
        }
        else
        {
                for(i=0;i<N;i++)
                {
                        if(!sol[i])
                        {
                                sol[i]=1;
                                back(arr,sol,N,tillnow+1,sumtillnow+arr[i],remainsum-arr[i],finalsol);
                                sol[i]=0;
                        }
                }
        }
}
 
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10},sol[10]={0},finalsol[10],i,sum=0;
        for(i=0;i<10;i++)
                sum+=arr[i];
 
        back(arr,sol,10,0,0,sum,finalsol);
 
        for(i=0;i<10;i++)
        {
                if(finalsol[i])
                        printf("%d ",arr[i]);
        }
        printf("\n");
 
        for(i=0;i<10;i++)
        {
                if(!finalsol[i])
                        printf("%d ",arr[i]);
        }
}

@Luv, i think Tournament tree takes (3xN/2)-1 comparisons.

Note: After deleting the BST make root=NULL

void deleteBST(root)
{
	if(root)
	{
		deleteBST(root->left);
		deleteBST(root->right);

		free(root);
                root=NULL;
	}
}

#include <stdio.h>
 
void change(int (*M)[5])
{
        int flagrow=1,flagcol=1,i,j;
 
        for(i=0;i<5;i++)
                flagrow&=M[0][i];
 
        for(i=0;i<5;i++)
                flagcol&=M[i][0];
 
        for(i=1;i<5;i++)
        {
                for(j=1;M[i][0] && j<5;j++)
                        M[i][0]&=M[i][j];
        }
 
        for(i=1;i<5;i++)
        {
                for(j=1;M[0][i] && j<5;j++)
                        M[0][i]&=M[j][i];
        }
 
        for(i=1;i<5;i++)
        {
                for(j=1;j<5;j++)
                        if(M[i][j]==1 && M[i][0]==0 || M[0][j]==0 )
                                M[i][j]=0;
        }
 
        if(flagrow==0)
                for(i=0;i<5;i++)
                        M[0][i]=0;
 
        if(flagcol==0)
                for(i=0;i<5;i++)
                        M[i][0]=0;
 
        for(i=0;i<5;i++)
        {
                for(j=0;j<5;j++)
                        printf("%d ",M[i][j]);
                printf("\n");
        }
}
 
int main()
{
        int arr[][5]={{1, 1, 1, 1, 1 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 1, 1, 0, 1 },
                        { 1, 1, 1, 1, 1 }};
 
        change(arr);            
        return 0;
}

No, the algo will not change. When updating place 1 in place with 0.