CareerCup

Whats the time complexity of this code?
When I told him its O(N^3), he told me to look carefully, its O(N^2),
I dont know why? Any idea?

for (int i = 0; i < n-2; ++i)
    {
    	//some code
        for (int j = i+1; j < n-1; ++j)
        {
        	//some code
        	for (int k = j+1; k < n; ++k)
        	{
        		//some code
        	}
        }

}

Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.*

Example:

Input:  arr[] = {1, 2, 3, -4, -1, 4}
    Output: arr[] = {-4, 1, -1, 2, 3, 4}
    
    Input:  arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
    output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}

Limitations:
a) Use O(1) extra space
b) Time Complexity should be O(N)
c) Maintain the order of appearance of elements as in original array.

while(scanf("%d,",&a))
{
//store a as you wish to

}

Input given is : 1,2,3,4,5,6,7,8,9

while(scanf("(%d,%d),",&a,&b))
{
//store a and b as you wish to

}

Input given is : (1,5),(8,11),(3,6),(10,20)


EXPLAIN INTERNAL WHOLE MECHANISM IN BOTH CASES

Given a binary tree, change the value in each node to sum of all the values in the nodes on the left side of the node.

Eg 1
/ \
2 3

3
/ \
2 6

solved this question using int* he asked me to do it without integer pointer.

An array contain 6 different numbers, only 1 number is repeated for 5 times. So now total 10 numbers in array, Find that duplicate number in 2 steps only?

You are given a mxn grid arr[][] and you stand at cell arr[p][q]. In 1 'move' you can either go up, down , left or right. Tell the probability that after taking 'k' moves, you are still inside the grid.

CODE:
(Can you point out any mistake)

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


void traverse(int m, int n,int cur_x,int cur_y,int moves,int * in,int * tot)
{
	if(moves==0)
	*tot = *tot+1;
	if(moves==0 && !(cur_x>=m||cur_y>=n||cur_x<0||cur_y<0))
	*in = *in +1;
	
	traverse(m,n,cur_x,cur_y+1,moves-1,in,tot);
	traverse(m,n,cur_x+1,cur_y,moves-1,in,tot);
	traverse(m,n,cur_x,cur_y-1,moves-1,in,tot);
	traverse(m,n,cur_x-1,cur_y,moves-1,in,tot);
}

int main()
{
    int m = 5, n = 5;
    int in=0,tot=0;
    int k,p,q;
    scanf("%d%d%d",&k,&p,&q);
    traverse(m,n,p,q,k,&in,&tot);
    printf("%d/%d ",in,tot);
	return 0;
}

Given 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.
(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN

Why is returning pointer to a node in linked list from a pointer is unsafe and sometimes gives wrong answers.

Most efficient way to check whether a number is Prime or not.

struct node
{
     int data;
     struct node* left;
     struct node* right;
};

void Postorder(struct node* root,struct node** leaf)
{
     if (root == NULL)
        return;
	
	if(root->data%2==0)
	*leaf->left=root;		//WHY I'M GETTING PROBLEM IN THIS LINE
    						//[Error] request for member 'left' in '* leaf', which is of non-class type 'node*' 
	Postorder(root->left,leaf);
    Postorder(root->right,leaf);
}

int main()
{
     struct node *root  = newNode(1);
     root->left         = newNode(2);
     root->right        = newNode(3);
   
     struct node* leaf=root;
     
     Postorder(root,&leaf);
   	 getchar();
     return 0;

}

print all the binary values of number from 1 to n , each number’s binary should be printed in 0(1).
for eg: n = 6
then print 1 10 11 100 101 110. printing 1, 10 ,11 ,100,101,110 should be in o(1) each

Given the integers from 1 to n, determine how many valid binary heaps can be constructed with these numbers.

. If a/b is recurring like 10/3, print 10/3 as 3.(3), 16/6 as 2.(6), 3227/555 as 5.8(144)

Sherlock rolls a N faced die M times. He adds all the numbers he gets on all throws. What is the probability that he has a sum of K.

A N faced die has all numbers from 1 to N written on it and each has equal probability of arriving when dice is thrown.

2
1 5 2
2 3 2

For first testcase, sum=1,2,3,4,5 are all equally probable. Hence probability is 0.2.
For second testcase:
(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) are all possible ways.
Out of these 1 has sum 2. So 1/9 is the answer.

I was asked to design an application that sends a message to two friends if they come within two miles of each other.
I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .
He pointed out the cons of the solution and I modified the data structure

I was asked to design an application that sends a message to two friends if they come within two miles of each other.
I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .

A quadra tree is a tree where each node has atmost 4 child nodes(similar to a binary tree which has atmost 2 child nodes).

A monitor screen (black and white) is represented by a qudra tree in the following way:

case 1: If the entire screen is white then the value in the root node is white.
similarly if the entire screen is black then the root stores black.
case 2: If the screen is neither completely black nor white then the screen is divided into 4 quadrants and the node has 4 child nodes each representing one of the quadrants.( the screen is recursively divided into subscreens).

Now given two screens represented by two quadra trees, return a quadra tree which represents the overlapping of the two screens.( assume when white and white overlaps results in white,black and white overlap results in black , black and black overlap results in black).
algo and code both have to be given.

Given A Binary Tree of size n , Find Out a Matrix M[n][n], where M[i][j]=1 if i is predecessor of j, else M[i][j]=0.
Try to do in better than O(N^2) time.

(Bar Raiser Round)
Divide the array(+ve and -ve numbers) into two parts such that the average of both the parts is equal.

Input:
[1 7 15 29 11 9]

Output:
[15 9 1 7 11 29]

Explanation:
The average of first two elements is (15+9)/2 = 12, average of remaining elements is (1+7 +11 +29)/4 = 12

• Suppose we need a service to perform certain task every day at some specified time. How do we ensure that everyday at the specified time the service will do that task?

Given a singly linked list, modify the value of first half nodes such that 1st node’s new value is equal to the last node’s value minus first node’s current value, 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes.
(No extra memory to be used)

Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.

I. moveLeft() // robot moves to left by 1 unit in 1 unit time

II. moveRight() // robot moves to right by 1 unit in 1 unit time

III. noOperation() // robot does not move and takes 1 unit time

IV. onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false

V. didWeMeet() // returns true if the robot meets to the other robot, else false

Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function.

You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low = number of elements lower
than or equal to ar in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.

You have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.

Only XOR based solution was permitted.
Time Complexity: O(N)
Space Complexity: O(1)

Sample Input:
{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}
Sample Output:
1 6 8

What would be the O/P and why?

#include<stdio.h>
#include<conio.h>

int main()
{
	

int k = -7; 
printf("%d", 0 < !k);

return 0;

}

Explain the output of the following code:

int main( )
      {
	int x = 10, y = 20;/.
	x =!x;
	y =!x&&!y;
	printf(“x =%d y =%d”, x, y);
        return 0;
       }

why will the code show error when tried to compiled
below given is a C program snippet to get height of a binary tree.

int height (struct node * root)
{
	if(root=NULL)
	return 0;

	else
	{
		return max(height(root->left),	height(root->right))+1;
	}

}

int max(int a,int b)
{
	return ((a>b)?a:b);

}

Given an array of n distinct integers sorted in ascending order. Find an index i s.t ar[i] = i. Return -1 if no such index exists. Note that integers in array can be negative.

If we have to allocate memory to a string of size n and read the string at run time character by character?
And we write the following code then why doesn't it works properly

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
int main()
{	
	int n,i;
	printf("Enter size n: ");
	scanf("%d",&n);
		
	char* str=(char*)calloc(n+1,sizeof(char));

	for(i=0;i<n;i++)
	scanf("%c",&str[i]);		
	
	str[n]='\0';
	

	printf("%s",str);
	getch();

	return 0;
}

i wrote this but why doesnt it works properly??

If we have to allocate memory to a string of size n and read the string at run time character by character?
And we write the following code then why doesn't it works properly

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
int main()
{	
	int n,i;
	printf("Enter size n: ");
	scanf("%d",&n);
		
	char* str=(char*)calloc(n+1,sizeof(char));

	for(i=0;i<n;i++)
	scanf("%c",&str[i]);		
	
	str[n]='\0';
	

	printf("%s",str);
	getch();

	return 0;

}

i wrote this