CareerCup

As per my understanding, the solution has nothing to do with "forest of binary trees". We can just crawl the parents of both nodes n1 and n2 upwards and see if their parents are same.
Sample code module below:

Please let me know if I missed anything:

Node* findCommonParent(Node* n1, Node* n2)
{
	// Same nodes are passed
	if (n1 == n2) return NULL;
	
	// If both nodes are NULL
	if(!n1 && !n2) return NULL;
	
	// If one of the nodes is NULL
	if(!n1 || !n2) return NULL;

	Node* lca = NULL;
	while(n1->parent && n2->parent)
	{
		if (n1->parent == n2->parent)
		{
			lca = n1->parent;
			break;
		}

		n1 = n1->parent;
		n2 = n2->parent;
	}
	
	return lca;
}

A simple DP approach:
The function can be written as:
F(N, A, S) = F(N - 1, A, S - 1) + F(N - 1, A, S - 2) +........+ F(N - 1, A, S - A)
Where, The F(N, A, S) represents the number of ways of getting S with N dice each with A faces, numbered from 1 to A.
Explaining the above equation in words,
Find the number of ways of getting Sum (S - 1) from (N - 1) dice +
Find the number of ways of getting Sum (S - 2) from (N - 1) dice +
.................
..................
Find the number of ways of getting Sum (S - A) from (N - 1) dice

Carefully handle the base cases like:
1. N = 1, S > A
2. S < 1

@buckCherry,,
1) By head, i mean start/first element of the list only.

2) Sum of counts yield 4 nodes( 3 + 1 ).Step#4 outputs value of count as 1.
Explaining once again: Fix hare at node C and move tortoise to node A. Move both hare and tortoise one step. Now, hare is at node D and tortoise is at node B. Now, next of B and next of D are same node C. So, the algo stops here.
Let me know you are facing any problem.
Thank you.

@buckCherry, Apologies. The concept of Double Linked List is not correct, same for cycle concepts.
Coming back to your initial doubt, how my algo works in your example?

In step#2, hare and tortoise meet at node C. Now move tortoise to node A. So, step#3 outputs 3 nodes( A, B and C).
In step#4, fixing hare at node C and moving tortoise at node A, move hare and tortoise one step until next of both are not equal. So, move hare to node D, and tortoise to node B. Now, next of both are equal, so stop here. The total number of nodes is 4 now.
NOTE: The above algo is inspired from Floyd's Cycle detection algo.
Please let me know if you have still any doubts.

@buckCherry, you are missing a key point. A cycle must contain at least 3 nodes. The example you are using fails because it contains a cycle of two nodes. In fact, this is not a cycle, rather it becomes a partial double linked list.
Hope you got it.

Do you even know the difference between a node and a pointer?
Node doesn't exist until memory is allocated for it. Can you tell how did you count three extra nodes?

So, you think the post is not relevant.
May i ask you where did you find the post is wrong.
Do not let other people think in your way. If they want, they will read.
If you have a better solution, why don't you post it and let other readers judge it.
And its not my blog. I read it there and found it a nice solution.
So, posted the link here.
CareerCup has not well defined indentation. If i would have posted the entire content, it would be messy to read. It is better to go through the link.
If you would have been interested in the solution, you would have been read it carefully. But, i guess you are only interested in downvoting and writing sarcastic comments.

Merge sort only uses extra pointers. We are not allocating any memory for nodes in merge sort.

Merge sort is best suited for linked list.

Follow this link for explanations and implementation:
geeksforgeeks.org/archives/7740

@nitingupta180, Follow the below link::
geeksforgeeks.org/archives/23497

It has a well explanation.

Follow this link:
geeksforgeeks.org/archives/1355

Read the question carefully. It has been clearly mentioned that
"Given a singly linked list which may or may not contain loop".

How will you come to know that the linked list is not having loop?

check it here: geeksforgeeks.org/archives/22238

@Tarun.Yadav. Yes, this approach won't work. It works well for 1D points.

@Tarun.Yadav, i encourage you to give some counter examples.
Why do you think that there will always exist a triangle with those three co-ordinates? The positions can be co-linear.

@eugene.yarovoi, Before writing my thoughts, i experimented how firefox works in this respect. I found that they even keep browser history of 6 months old.
Here is my thought:
I would use a double linked list of dates. Each day, browser is accessed, i would be adding a new node to it. Now, each node of the double linked list will be another linked list for storing the URL's. I don't think timestamp is necessary here. We can add new visited pages to head of the list. In this way, the recent visited pages would be near the front of the list.
I liked your idea of treeSet. It will help if a user visits previously visited page. We need to adjust the nodes of the list.

Now, if the user wants to see the history by data, list will serve the purpose. If the user wants to search a particular URL, we can provide prefix searching like TRIE.

Let me know your thoughts.

@eugene.yarovoi, here is my approach:

void push( void** stack, int* top, void* data, size_t size )
{
    unsigned i;
    ++*top;
    stack[*top] = malloc( size );
    for( i = 0; i < size; ++i )
            ( (char*)stack[*top] )[i] = ( (char*)data )[i];
}

int main()
{
    void* stack[10];
    int top = -1, data = 10;
    char ch = 'a';
    push( stack, &top, (void*)&data, sizeof( int ) );
    push( stack, &top, (void*)&ch, sizeof( char ) );        
    printf( "%d ", *(int*)stack[0] );
    printf( "%c ", *(char*)stack[1] );
    return 0;
}

I want you to check & comment if you find any issues here.

@Andy2000, after some mathematical calculations, i concluded that the distance will be minimum if we fix the meeting point as one of the person's co-ordinates. Can the meeting point be one of the person's position? If yes, the solution goes simple. O( N^2).
Let me know if i am missing anything.

Thanks for pointing the mistake. I have corrected it.

void generateIPUtil( char* str, char* output, int depth, int countDot, int val )
{
        if( !*str )
        {
                output[depth] = '\0';
                if( countDot == 3 && output[depth-1] != '.' )
                        printf( "%s\n", output );
        }
        else
        {
                output[depth] = *str;
                val = val * 10 + *str - '0';
                if( val <= 255 )
                {
                if( countDot < 3)
                {
                        output[depth + 1] = '.';
                        generateIPUtil( str+1, output, depth+2, countDot+1, 0 );
                }
                generateIPUtil( str+1, output, depth+1, countDot, val );
                }
        }
}
 
void generateIP( char* str )
{
        char output[30];
 
        generateIPUtil( str, output, 0, 0, 0 );
}

Working code here: ideone.com/GMs87

@ Nasser Ghazali, the code is fine. You can check the output here: ideone.com/fZ8LE
Regarding direction of output, check against input 52

This can be done in O(1) space.
Time complexity: O(MxN)

Find the max item in the row. Check whether it is the smallest in the column.

void foo(int (*arr)[COL])
{
        int i,j,max, min;
        for( i = 0; i < ROW; i++ )
        {
                max=0;
                for( j = 1; j < COL; j++ ) // find max in the row
                        if(arr[i][j] > arr[i][max])
                                max=j;
 
                min = 0;
                for( j = 1; j < ROW; ++j ) // find min in the column
                        if(arr[j][max] < arr[min][max])
                                min=j;
 
                if( min == i ) // if both items are same
                        printf("%d", arr[i][max]);
        }
}

Here is the working code: ideone.com/XfGJV

@shreyans, Individual strings are being sorted so that after sorting the array, all the anagrams will be closer. Where did you find it not working?
can you provide counter example?

@Anshu Kumar, thanks for pointing out the mistake.
I have corrected the code.

1. Take a BST with extra field count of occurrence.
2. Maintain a min heap of size 2 dealing with the frequency. Whenever any item occurrence is more than the frequency of the head, replace it & update heap.
3. At the last, the top of the heap gives the required item.

@Abhishank Sahu, the algo is working well with the inut set given by you. Can you provide the link where it didn't give the correct output?

return (3*rand(3) + rand(3) -3)

int isValid(char* str,int k)
{
        int i;
        if(k<=0) return 0;
        for(i=0;i<k;++i)
        {
                if(str[i]=='0' && (i==0 || str[i-1]=='0'))
                        return 0;
        }
        return 1;
} 
 
void print(char* str,int k)
{
        int i;
        for(i=0;i<k;++i)
                printf("%c",str[i]);
        printf("\n");
}
 
int count;
 
void countValidString(char* str,int depth,int k)
{
        if(depth<0)
        {
                if(isValid(str,k)) 
                {
                        ++count;
                        print(str,k);
                }
        }
        else
        {
                str[depth]='0';
                countValidString(str,depth-1,k);
 
                str[depth]='1';
                countValidString(str,depth-1,k);
        }
}

Complete working code: ideone.com/cDPgI

Why Dijkshtra? Just do DFS from one user to other. Meanwhile, keep minimum distance so far.

What is generated as a result of inorder traversal of BST?
Of course, A sorted list of data. I am changing the pointers in midway.
What made you think that the list will not be sorted?

@mr, Can you provide one counter example?

The base representation starts from 0. Here it will be given from 1.
So, n--.

@eugene.yarovoi,Thanks for pointing out the mistake. So, While updating the maxProfit, We also need to check that whether the new profit calculated is greater than the maxProfit calculated so far.
I have updated the solution.

@Raj, did you bother running my code?
I have checked my code against the input set given by you & it is correctly outputting 5.
I have updated my solution with the link where i checked. Please have a look.

Perform binary search.

int findFirstOccurrence(int* arr,int l,int h,int tofind)
{
        int mid;
        if(l>h) return INT_MIN;
        if(l==h)
                return arr[l]==tofind?l:-1;
        mid=(l+h)>>1;
        
        if(arr[mid]==tofind && (mid==l || arr[mid]>arr[mid-1]))
                return mid;
        if(tofind<=arr[mid])
                return findFirstOccurrence(arr,l,mid-1,tofind);
        return findFirstOccurrence(arr,mid+1,h,tofind);
}

Complete code here: ideone.com/8q91s

Use references in the same way you use pointers.

class A
{
        public:
        virtual void show()
        {
                cout<<"A class show()"<<endl;
        }
};
 
class B: public A
{
        public:
        void show()
        {
                cout<<"B class show()"<<endl;
        }
};
 
int main()
{
        B b;
        A a;
        A &ref=b;
        ref.show();
        return 0;
}

Complete code here: ideone.com/Zuebz

The problem boils down to:
Given an array, find two indices min & max such that A[max]-A[min] is maximum and max>min.

int findMAxProfit(int* A,int n) // n is the number of days
{
	min=max=0;
        maxProfit=INT_MIN;
	for(i=1;i<n;++i)
	{
		if(A[i]<A[min]) min=i;
		
		if(A[i]-A[min] > maxProfit) // if you want, update buy & sell day here
			maxProfit=A[i]-A[min];
	}
	return maxProfit;
}

Complete code here: ideone.com/Xt1ZA

1. Constructor
2. Destructor
3. Copy constructor
4. Assignment operator function

#define N 1
 
char* g()
{
        char* p="Hello";
        printf("g() called\n");
        return p;
}
 
char* (*foo())()
{
        char* (*p)()=g;
        printf("foo() called\n");
        return p;
}
 
int main()
{
        char* (*(*ptr[N])())();
        char* (*p)();
        ptr[0]=foo;
 
        p=(*(ptr[0]))();
 
        (*p)();
 
        return 0;
}

Complete code here: ideone.com/3kdhv

Time complexity: O(N)

int findTrappedWater(int* H,int size)
{
        int i,j,water=0,temp;
        for(i=0;i<size;)
        {
                j=i+1;
                temp=0;
                while(j<size && H[i]>H[j])
                {
                        temp+=H[j];
                        j++;
                }
                if(j!=size) // decreasing length histogram
                        water+=(j-i-1)*H[i]-temp;
                i=j;
        }
        return water;
}

Complete code here: ideone.com/xCsHn

@codinglearner, then why the condition if(a*b==0) raised here?

There is a problem with a+b<0. Consider the below tree.

5
       /  \
      1   5

The preorder traversal is: 5,1,5
a=5-1=4
b=5-5=0
a*b==0 But a+b>0, the function returns TRUE. But, it should return FALSE.

An easy approach:
1. Name the levels as 1,2,3.... A cup numbered i will pour extra water into cups with number i+level and i+level+1.

I am using an integer array cup[] to store the amount of water in each cup. The same logic applies to the float also.

Here is the pseudo code:

void fillWater(int C,int L,int n,int* cup)
{
        int i,level=1,j,diff;
 
        cup[1]=L;
 
        for(i=1;i<=n;)
        {
                for(j=i;j<i+level;++j)
                {
                        L=cup[j];
                        diff=(L-C)<=0?-1:L-C;
                        if(diff>0)
                        {
                                cup[j]-=diff;
                                cup[j+level]+=diff/2;
                                cup[j+level+1]=diff/2;
                        }
                }
                level++;
                i=j;
        }
        for(i=1;i<=n;++i)
                printf("cup number %d has %d water\n",i,cup[i]);
}

C: Capacity of each cup
L: Water poured in the first cup.
n: Number of cups

Complete working code here: ideone.com/7u7yU

A nice non-recursive implementation.

Before using prev->data, prev must not be NULL.
See the AND condition.

We are allowed to move the balls before blindfold.

46=32+8+4+2

n<<5 + n<<3 + n<<2 + n<<1

void foo(int* res,int depth,int N,int tillnow)
{
        int i;
        if(tillnow==N)
                print(res,depth);
        else if(tillnow>N)
                return;
        else
        {
                for(i=N&1?N:(N-1);i>=1;i-=2)
                {
                        if(!depth || i<=res[depth-1])
                        {
                                res[depth]=i;
                                foo(res,depth+1,N,tillnow+i);
                        }
                }
        }
}

Complete code here: ideone.com/tyxoZ

Wrong! Merge sort needs even less number of comparisons.
It needs n ⌈lg n⌉ - 2^⌈lg n⌉ + 1 in worst case.
Which is 14 here.

void interleaving(char* s1,char* s2,char* res,int depth)
{
        if(!*s1 && !*s2)
        {
                res[depth]='\0';
                printf("%s\n",res);
        }
        if(*s1)
        {
                res[depth]=*s1;
                interleaving(s1+1,s2,res,depth+1);
        }
        if(*s2)
        {
                res[depth]=*s2;
                interleaving(s1,s2+1,res,depth+1);
        }
}

Complete code: ideone.com/35VNh