CareerCup

"The statement I am making is false."

Let the probabilty of passing of bus in the time intersection of 5 min be X.
Then the probabilty of not passing of bus in the same 5 minute intersection is Y=1-X.

Let the bus not pass for 4 '5 min intersection', i.e, for 20 mins.
The probablity of above will be Y^4.

Then as per question,

1 - Y^4 = 0.9
Y^4 = 0.1
(1-X)^4 = 0.1
X = 0.4377

#include<stdio.h>

int main()
{
     char arr[][5] = { 'i', 'l', 'o', 'v', 'e', 
                  'd', 'i', 'n', 't', 'e', 
                  'n', 'e', 'w', 'e', 'p', 
                  'a', 'i', 'v', 'r', 'i', 
                  'm', 'a', 'x', 'e', 'c', 
                    };
     int i, j, k,middle,size = 5;
     for(i=size-1, j=0; i>j; i--, j++)
     {
            for(k=j; k<i; k++) printf("%c", arr[j][k]);
            for(k=j; k<i; k++) printf("%c", arr[k][i]);
            for(k=i; k>j; k--) printf("%c", arr[i][k]);
            for(k=i; k>j; k--) printf("%c", arr[k][j]);
     }
     middle = (size-1)/2;
     if (size % 2 == 1) printf("%c", arr[middle][middle]);
     printf("\n\n");
     return 1;
}

I have implemented the logic of DFS. The complexity is the size of given matrix as the algo explore each cell just once.

The numbers will be stored in a,b and c.

void find_numbers(int array[], int n, int* a, int* b, int* c)
{
     int* less = new int[n];
     int* more = new int[n];
     less[0] = -1;
     more[n-1] = -1;
     for(int i = 1; i < n; i++)
     {
             less[i] = INT_MIN;
             for(int j = i-1; j >= 0; j--)
             {
                   if((array[j] < array[i]) && (array[j] > less[i])) 
                               less[i] = array[j];
             }
     }
     
     for(int i = n-2; i >= 0; i--)
     {
             more[i] = array[i];
             for(int j = i+1; j < n; j++)
             {
                   if((array[i] < array[j]) && (more[i] < array[j]))
                               more[i] = array[j];
             }
     }
     
     int product = 0;
     for(int i = 0; i < n; i++)
     {
             if(less[i]*array[i]*more[i] > product)
             {
                      *a = less[i];
                      *b = array[i];
                      *c = more[i];
             }
     }
}

The answer should be
4->5->6->7->8->7->6->5->4->5->6->7
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(3,3)->(2,3)->(1,3)->(1,2)->(1,1)->(0,1)

#include<iostream>
#include<math.h>

using namespace std;

int array[][4] = {{4,	7,	9,	8 },
              {5,	6,	5,	4 },
              {6,	7,	8,	5 },
              {10,	9,	7,	6 }};
int processed[][4] = {{0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 }};
int in_stack[][4] = {{0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 },
              {0,	0,	0,	0 }};
int** solution;
int record[4*4];

void dfs(int i, int j, int* n, int* len, int count)
{
     if(processed[i][j] == 1)
                        return;
                        
     processed[i][j] = 1;
     in_stack[i][j] = 1;
     record[count++] = array[i][j];
     

     if(i+1 < 4)
     if(!in_stack[i+1][j] && (abs(array[i+1][j] - array[i][j]) == 1))
                          dfs(i+1, j, n, len, count);
     if(j+1 < 4)
     if(!in_stack[i][j+1] && (abs(array[i][j+1] - array[i][j]) == 1))
                          dfs(i, j+1, n, len, count);
     
     if(i-1 >= 0)
     if(!in_stack[i-1][j] && (abs(array[i-1][j] - array[i][j]) == 1))
                          dfs(i-1, j, n, len, count);
     
     if(j-1 >= 0)
     if(!in_stack[i][j-1] && (abs(array[i][j-1] - array[i][j]) == 1))
                          dfs(i, j-1, n, len, count);
     
     if(count > *len)
     {            
              if((*n != 0) && solution != NULL)
              {
                           if(*n > 1)
                           {
                               for(int i = 0; i < *n; i++)
                                       delete [] solution[i];
                           }
                           delete solution;
              }
              
              *len = count;
              *n = 1;             
              solution = new int*;
              *solution = new int[count];
              for(int i = 0; i < count; i++)
                      (*solution)[i] = record[i];     
     }
     if(count == *len)
     {
              int** temp = new int*[*n+1];
              for(int i = 0; i < *n; i++)
              {
                      temp[i] = new int[*len];
                      for(int j = 0; j < *len; j++)
                              temp[i][j] = solution[i][j];
              }
              temp[*n] = new int[*len];
              for(int j = 0; j < *len; j++)
                      temp[*n][j] = record[j];
                      
              if((*n != 0) && solution != NULL)
              {
                           if(*n > 1)
                           {
                               for(int i = 0; i < *n; i++)
                                       delete [] solution[i];
                           }
                           delete solution;
              }
              solution = temp;
              
     }            
     
     in_stack[i][j] = 0;
     count--;
}


void find_longest_snake(int* n, int* len)
{
     *n = 0;
     *len = 0;
     
     for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
                if(processed[i][j] == 0)
                                   dfs(i, j , n, len, 0);
        }
        return;
}

int main()
{
    int n, len;
    find_longest_snake(&n, &len);
    cout << n << " " << len << endl;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < len; j++)
                cout << solution[i][j] << " ";
        cout << endl;
    }
    
    return 0;
}

I don't agree to the above idea of returning from a node after find that node outside range.

Consider a tree
10
| |
8 15
| | | |
7 9 13 16

and range (9,14).
With your algorithm, we will return from 8 without including 9 and similarly from 15 without including 13. :(

void find_max_profit(int array[], int n, int* min, int* max)
{
	int diff = 0;
	int m = array[n-1];
 	for(int i = n-2; i >= 0; i--)
	{
		if(array[i] >= m)
		{
			m = array[i];
		}
		else
		{
			if((m - array[i]) > diff)
			{
                 diff = m - array[i];
				*min = array[i];
				*max = m;
			}
		}
	}
}

It can be easily done using recursion.

void countInsideRange(node *root, int min, int max, int* count)
{
   if (root == NULL)
      return;
      
   countInsideRange(root->left, min, max, count);
   countInsideRange(root->right, min, max, count);
 
   if((root->key > min) && (root->key < max))
                 *count = *count + 1;
   
   return;
}

The answer will be in integer count value.

Find the shortest path between any two nodes. Let them be A and B.
Now to get second shortest path between the same nodes, remove any one edge that is involved in the shortest path between the same nodes and calculate the shortest path. Do the above process for each of the node involved in shortest path and keep track of the minimum second shortest path found.

There are k lists of sorted integers. Make a min heap of size k containing 1 element from each list. Keep track of min and max element and calculate the range.
In min heap, minimum element is at top. Delete the minimum element and another element instead of that from the same list to which minimum element belong. Repeat the process till any one of the k list gets empty.
Keep track of minimum range.

For eg.
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

Min heap of size 3. containing 1 element of each list
Heap [0, 4, 5]
Range - 6

Remove 0 and add 9
Heap [4, 9, 5]
Range - 6

Remove 4 and add 10
Heap [5, 9, 10]
Range - 6

and so on....

Finally you will yield the result.

Pick one fruit from the basket labeled "mixed". If apple comes out, tag it to "apple". Change the basket labeled as "apple" to "orange" and the basket labeled as "orange" to "mixed".
Otherwise if orange comes out, tag it to "orange". Change the basket labeled as "orange" to "apple" and the basket labeled as "apple" to "mixed".

The concept: diagonals in a square are at 90 degrees and opposite sides are parallel.

#include<iostream>

using namespace std;

typedef struct point
{
	double x;
	double y;
}point;

double find_slope(point A, point B)
{
	return (A.y-B.y)/(A.x-B.x);
}

int main()
{
	point A, B, C, D;
	A.x = 1.0;
	A.y = 1.0;
	B.x = 2.0;
	B.y = 1.0;
	C.x = 2.0;
	C.y = 2.0;
	D.x = 1.0;
	D.y = 3.0;

	double slope_A_B = find_slope(A,B);
	double slope_C_D = find_slope(C,D);
	bool is_square = false;
	if(slope_A_B == slope_C_D)
	{
		double slope_A_C = find_slope(A,C);
		double slope_B_D = find_slope(B,D);
		if(slope_A_C * slope_B_D == -1)
			is_square = true;
		if(!is_square)
        	{
                      double slope_A_D = find_slope(A,D);
                      double slope_B_C = find_slope(B,C);
                      if(slope_A_D * slope_B_C == -1)
                                   is_square = true;
        	}
	}
	else if(slope_A_B * slope_C_D == -1)
	{
		double slope_A_C = find_slope(A,C);
		double slope_B_D = find_slope(B,D);
		if(slope_A_C == slope_B_D)
			is_square = true;
	}
	if(is_square)
		cout << "They form a square" << endl;
	else
		cout << "They dont form a square" << endl;

	return 0;
}

Find the complete code here.

#include<iostream>
#include<conio.h>

using namespace std;

void isort(int* array[], int size)
{
     int min;
     for(int i = 0; i < size; i++)
     {
             min = i;
             for(int j = i+1; j < size; j++)
             {
                     if((*array)[j] < (*array)[min])
                     {
                                    min = j;
                     }
             }
             if(min != i)
             {
                    int temp = (*array)[min];
                    (*array)[min] = (*array)[i];
                    (*array)[i] = temp;
             }
     }
}
     

int main()
{
    int array[] = {1,9,5,6,4,15};
    int size = sizeof(array)/sizeof(array[0]);
    if(size%2 != 0)
    {
              cout << "Wrong input" << endl;
              return 0;
    }
    int k = 5;
    int* mod = new int[size];
    for(int i = 0; i < size; i++)
            mod[i] = array[i]%k;
    
    isort(&mod, size);
    
    int i = 0;
    
    while(mod[i] == 0)
    {
                 i++;
                 
    }
    if(i == (size-1))
    {
           cout << "pairs exist" << endl;
           getch();
           return 0;
    }
    if(i%2 != 0)
    {
           cout << "pairs does not exist" << endl;
           getch();
           return 0;
    }
    
    int j = size - 1;
    for( ; i < j; )
    {
         if((mod[i] + mod[j]) == k)
         {
                    i++;
                    j--;
         }
         else
         {
             cout << "pairs does not exist" << endl;
             getch();
             return 0;
         }
    }     
    cout << "pairs exist" << endl;
    getch();
    return 0;
}

You are right. I understood the question wrong.

Use the following code to get the answer.

#include <stdio.h>
#include <math.h>

int main ()
{
  float param, result;
  scanf("%f", &param);
  int leftmostsetbit = (int)log2(param);
  int answer = 1;
  answer =  answer << (leftmostsetbit+1);
  if(answer < 64)
            printf("64\n");
  else
            printf("%d\n", answer);
  getch();
  return 0;
}

It can be done using two stacks. One for the element and other for the min.

Else you can modify the structure.

struct node
{
	int element;
	int min;
}

If even that can't be done. You can always push the minimum element behind the element.

class stack
{
	int* array;
	int size;
	int top;
	int min;
  
	stack(int s) { size = s; array = new int[2*s]; top = -1; min = INT_MAX; }
	~stack() { delete [] array };
	int pop();
	void push(int value);
	int get_min();
};

int stack::pop()
{
	if(top == -1)
		return INT_MIN;
	else
	{
		int t = array[top - 1];
		top = top - 2;
	}
}

int stack::get_min()
{
	if(top == -1)
		return INT_MIN;
	else
		return array[top];
}

void stack::push(int value)
{
	if(min > value)
		min = value;

	array[++top] = value;
	array[++top] = min;
}

Preprocessing :
Concept: the word 'cat' maps only and only to 228.
Store the words in the list at their respective numbers.

The below data structure is similar to Trie. If the number equals current number, returns the current list. If not move to next level.

typdef struct list
{
	string s;
	struct list* next;
}list;

class node
{
	private:
		list* lt;
		struct  node* array[10];
	public:
	node()
	{
		lt = NULL;
		for(int i = 0; i<10; i++)
			array[i] = NULL;
	}
	list* search(int num)
	{
		if(num==0)
			return lt;
		if(list[num%10])
			return list[num%10]->search(num/10);
		return NULL;
	}
			
}node;

The logic should be as follows:
Maintain two queues. Q2 having one element 2. And Q5 having one element 5.
From both the queues, extract the min number that stood in front of queue. If the number comes out of Q2, append 2*number to Q2 and 5*number to Q5. If the min number is from Q5, append 5*number in Q5. Repeat the process.

For example:
Step 1: Initialization
Q2 = 2
Q5 = 5

Step 2
min is 2; print 2
Q2 = 4
Q5 = 5, 10

step 3
min 4; print 4
Q2 = 8
Q5 = 5, 10, 20

step 4
min 5; print 5
Q2 = 8
Q5 = 10, 20,25

step 5
min 8; print 8
Q2 = 16
Q5 = 10, 20, 25, 40

on and on....till we print N numbers

This can be solved using DP.

Try the following code. The data is needed to be preprocessed before using the following code. Convert the string to array.

int find(int array[], int size)
{
        int max = 0;
        int temp[size][size];
        for(int i = 0; i < size; i++)
                for(int j = i; j < size; j++)
                {
                        if(i == j)
                        {
                                temp[i][i] = array[i];
                                if(max < array[i])
                                        max = array[i];
                        }
                        else
                                temp[i][j] = 0;
                }


        for(int L=2; L<=size; L++)
                for(int i=0; i<size-L+1; i++)
                {
                        int j = i + L - 1;
                        if(L%2 == 0)
                        {
                                int mid = (i+j)/2;
                                temp[i][j] = temp[i][mid] + temp[mid+1][j];
                                if(temp[i][mid] == temp[mid+1][j])
                                        if(temp[i][j] > max)
                                                max = temp[i][mid];
                        }
                        else
                        {
                                int mid = (i+j)/2;
                                temp[i][j] = temp[i][mid-1] + temp[mid][mid] + temp[mid+1][j];
    //     If odd length of substring is also valid then uncomment the following code                      
	/*	 		if(temp[i][mid-1] == temp[mid+1][j])
                                        if(temp[i][j] > max)
                                                max = temp[i][j];*/

                        }
                }

        return max;
}

Use XOR operation.

XOR numbers 1 to N and the given list of numbers.
The resultant will contain the bits set on only in either of the missing numbers.
Consider the position of set bit. Need to do only once. Divide the numbers 1 to N in two groups, one which contains that bit set and one group which doesn't have one bit set. Similarly, divide the given numbers among those groups.
XOR the groups to get the numbers.

XOR of first group will result to first missing number and XOR of second group will result to second missing number.

Concept:
A^A = 0;

Use a hash table along with a queue.
Hash table contains the URL along with its node address.
In hash table, you can check the presence of the current URL and if it is present, move that node to front of the queue else allocate a new node to that URL and place it in front of the queue.

If we can pre-process the data, I would like to store all the dictionary words in a TRIE. While searching for the longest possible word that can be form out of given characters, we will keep refining the options available and check all the options.

If we are not allowed to pre-preprocess the dictionary data, then we can maintain two arrays.
First array : Total number of a character in the given set of characters.
Then we will have to check for the presence of each dictionary word.
Second array : Initialized as a copy of first array for each new word. For each character in the word, its count in second array should be greater than zero. If yes, decrease the count by one and move to second character else move to next word.
Keep the record of longest word found.

This question resembles "Find the subset sum problem" where sum = total_sum/2. Find the subset whose sum is as close as possible to the half of the total_sum. And produce the answer.

Here is the CPP code for the above question.
Since all the answers will be between Zero and Sum of all the weights. I initialized an array of that length of structure node. (see code). For every weight, I check the previous entries and find the every new possible answer.
The code runs in time complexity O(n^2).

#include<iostream>

using namespace std;

typedef struct node
{	
	bool present;
	int small;
	int large;
}node;

int main()
{
	cout << "Enter the number of values you want to enter\n";
	int num,sum=0;
	cin >> num;
	int* array = new int[num];
	cout << "Enter the numbers\n";
	for(int i = 0; i < num; i++)
	{
		cin >> array[i];
		sum +=array[i];
	}

	node* result = new node[sum+1];
	for(int i = 0; i <= sum; i++)
		result[i].present = false;

	result[0].present = true;
	result[0].small = 0;
	result[0].large = 0;

	sum = 0;
	for(int i=0; i<num; i++)
	{
		sum += array[i];
		for(int j = 0; j <= sum; j++)
		{
			if(result[j].present == true)
			{
				if(result[result[j].large + array[i]].present == false)
				{
					result[result[j].large + array[i]].present = true;
					result[result[j].large + array[i]].small = 0;
					result[result[j].large + array[i]].large = result[j].large + array[i];
				}
				if(result[result[j].small + array[i]].present == false)
				{
					result[result[j].small + array[i]].present = true;
					result[result[j].small + array[i]].small = 0;
					result[result[j].small + array[i]].large = result[j].small + array[i];
				}
				if(result[result[j].large + array[i] - result[j].small].present == false)
				{
					result[result[j].large + array[i] - result[j].small].present = true;
					result[result[j].large + array[i] - result[j].small].small = result[j].small;
					result[result[j].large + array[i] - result[j].small].large = result[j].large + array[i];
				}
				if((result[j].small + array[i] - result[j].large) > 0)
				if(result[result[j].small + array[i] - result[j].large].present == false)
				{
					result[result[j].small + array[i] - result[j].large].present = true;
					result[result[j].small + array[i] - result[j].large].small = result[j].large;
					result[result[j].large + array[i] - result[j].small].large = result[j].small + array[i];
				}
			}
		}
	}	
	for(int i = 0; i<= sum; i++)
	{
		if(result[i].present == true)
			cout << i << " ";
	}
	cout << endl;
	delete result;
	delete array;
	return 0;
}

Hi

Can you please elaborate ?

yes, we need to if the points are in 2-D space. In 1-D space we can sort the points on the basis of their co-ordinate and store it.