CareerCup

It is working fine for your given test-case.....
In this case function will return false.... Which is correct...

It is correct, str="1234" is 3 only.... ABCD, LCD, AWD,
34 does not represent any character.
This is correct implementation.

Simple Recursive method

isBST(Node *root)
{
	bool l = r = true;
	if( (root == NULL) || (root->left == NULL && root->right == NULL) )
		return true;

	if(root->left != NULL)
	{
		if(root->data > root->left->data)
			l = isBST(root->left);
		else
			l = false;
	}
	
	if(root->right != NULL)
	{
		if(root->data < root->right->data)
			r = isBST(root->right);
		else
			r = false;
	}
	return (l && r);
}

class Marks
{
	private int marks1;
	private int marks2;
	private int marks3;
	private int maxMarks;
	public Marks(int m1, int m2, int m3)
	{
		marks1 = m1;
		marks2 = m2;
		marks3 = m3;
		maxMarks = (m1>m2?m1:m2)>m3?(m1>m2?m1:m2):m3;
	}
	public int gerMaxMarks()
	{
		return maxMarks;
	}
	
	public bool isPass()
	{
		return ((marks1+marks2+marks3)/3)>=40?true:false;
	}
}

class StudentList
{
	private List<Marks> allMarks;
	public StudentList()
	{
		allMarks = new ArrayList<Marks>();
	}
	public int totalStudents()
	{
		return allMarks.length;
	}
	public int passCount()
	{
		int count=0;
		for(Marks m : allMarks)
			if(m.isPass())
				count++;
		return count;
	}
}

This can be done in two steps.
1. Reverse the entire string.
2. Reverse each word (separated by space).

Ex..
Input : "This is test"
After step 1: "tset si sihT"
After step 2: "test is This".

This can be done by bit modification in binary search with O(logN) time.
Please find the working code below....
INPUT : baseAddressOfArray, sizeOfArray, numToSearch.
OUTPUT : Index of element (-1 if element is not present)

int binarySearchOnRotatedArray(int arr[], int arrSize, int key)
{
    int mid, start=0, end1=arrSize-1;
    int index=-1;
    if(arr[start] == key)
        index = start;
    else if(arr[end1] == key)
        index = end1;

    while(index == -1 && start != end1 -1)
    {
        mid = (start+end1)/2;
        if(arr[mid] == key)     //If found the element
            index = mid;
        else if (arr[mid] < arr[start]) //Right part of mid is sorted array...
        {
            if(key > arr[mid] && key < arr[end1])
                start = mid;
            else
                end1 = mid;
        }
        else    //Left part of mid is sorted array....
        {
            if(key > arr[start] && key < arr[mid])
                end1 = mid;
            else
                start = mid;
        }
    }

    return index;
}

I don't think MS can ask this kind of easy question.

Can you explain you question clearly with example....??

Sort the array and find the mid point which will be the median of the series....
complexity : O(nlogn)

Calculate the total number of distinct row where demons preset say "count_row"
Calculate the total number of distinct col where demons preset say "count_col".
Now
Output = min(count_row, count_col);

This is working code.
Please check it and give any comment if you have.

int binarySearchOnCircularArray(int arr[], int arrSize, int key)
{
    int mid, start=0, end1=arrSize-1;
    int index=-1;
    if(arr[start] == key)
        index = start;
    else if(arr[end1] == key)
        index = end1;

    while(index == -1 && start != end1 -1)
    {
        mid = (start+end1)/2;
        if(arr[mid] == key)     //If found the element
            index = mid;
        else if (arr[mid] < arr[start]) //Right part of mid is sorted array...
        {
            if(key > arr[mid] && key < arr[end1])
                start = mid;
            else
                end1 = mid;
        }
        else    //Left part of mid is sorted array....
        {
            if(key > arr[start] && key < arr[mid])
                end1 = mid;
            else
                start = mid;
        }
    }

    return index;
}

Use a ASCII array of integer of length 256, it represent the of character of its corresponding index. Initially it contains value -1 as absence of character of corresponding index.
Read character from stream and update ASCII array as
If index of corresponding ascii value of character is -1 then update with its position in the stream.
If index of corresponding ascii value of character is +ve(char has already came) then update it with -2 (Means Not unique)

Finally after getting all the value from stream, trace the array and get min +ve value and its corresponding ASCII char will be the unique char
If array contains only -ve value then # as result

In C++ you can have virtual destructors but NOT virtual constructors. This is because when an object has virtual functions it must have an associated v-table which keeps track of the addresses to the virtual functions for that class. That would mean that an object must be instantiated firstly before a v-table for that object could exist. Since constructors are intended to instantiate and create the object there can be no virtual constructor.

On the other hand a virtual destructor is allowed and should be used when ever there are virtual methods in the base class. The misuse of virtual destructors can lead to memory leaks and bad side effects

Please explain the question clearly....

This is permutation problem where we need to form the number with all the digit given in the array. Below is the working code for the same.
Call the function with "permute(arr, 0, sizeOfArray);"

void permute(int *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%d\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));	//Here swap function will swap the value of its argument.
          permute(a, i+1, n);
          swap((a+i), (a+j)); 	//Here swap function will swap the value of its argument.
       }
   }
}

@bigphatkdawg
I m counting the frequency of each word is which is not required for this problem. so we can use as this array as boolean but in 'c' we don't have this datatype so i used int.
Yest "ASCII[ ]+=1" can be put outside the if statement. Like

if(ASCII[input[i]] == 0)
                        output[j++] = input[i];
 ASCII[input[i]] += 1;

And if string has no duplicate char then same string will be returned back.

This can be solved by o(n) by taking an extra array of size 256 to count the frequency of the character.
Please find the working function below.
Input : string, length,
Output : string

char* removeDupFromString(char input[], int len)
{
        char output[len];
        int ASCII[256] = {0};
        int i, j;
        for(i=0, j=0; i<len; i++)
        {
                if(ASCII[input[i]] == 0)
                {
                        output[j++] = input[i];
                        ASCII[input[i]] += 1;
                }
                else
                        ASCII[input[i]] += 1;
        }
        output[j] = '\0';
        return output;
}

@Subbu2637
This is not just outline of program it is working program...... Try to run it, it will give result not error. Only things need to add is #include<stdio.h> & define SIZE with ur choice.
@DeeKaE
Yes i m using middle element but see the if condition and based on that i am calculation final sum after removing this element.

sum += matrix[i][i] + matrix[i][N-i];
is not correct it should be
sum += matrix[i][i] + matrix[i][N-i-1];

This is very easy question....
We know that there are two diagonal of a matrix and both intersect at one(element) point if matrix is of size odd only.
Based on the above fact. Give below is working code of it.

int main(void)
{
    int mat[SIZE][SIZE] = { ..........................  };
    int i, j, dig1=0, dig2=0, sum=0;

    //Sum of First diagonal.
    for(i=0; i< SIZE; i++)
        dig1+=mat[i][i];

    //Sum of Second diagonal.
    for(i=0; i< SIZE; i++)
        dig2+=mat[i][SIZE-(i+1)];

    if(SIZE % 2)
        sum = dig1 + dig2 - mat[SIZE/2][SIZE/2];
    else
        sum = dig1 + dig2;

    printf("\nSum of Digonal Elements of Matix without repeatation : %d\n", sum);

    return 0;
}

This is very interesting question. Please find my generic working solution upto number of 4 digit.... In this program input parameter is String-Input, String-Lenght and digit.
Please give your comment about the solution

char* findMissingEle(char str[], int len, int digit)
{
    char *output;
    int diff=0, place, i=0, j=0;
    int num1, num2;
    while(i<len-digit)
    {
        switch (digit)
        {
            case 1:
                num1 = str[i];
                num2 = str[i+1];
                break;
            case 2:
                num1 = str[i];
                num1 = num1*10 + str[i+1];
                num2 = str[i+2];
                num2 = num2*10 + str[i+3];
                break;
            case 3:
                num1 = str[i];
                num1 = num1*10 + str[i+1];
                num1 = num1*10 + str[i+2];
                num2 = str[i+3];
                num2 = num2*10 + str[i+4];
                num2 = num2*10 + str[i+5];
                break;
            case 4:
                num1 = str[i];
                num1 = num1*10 + str[i+1];
                num1 = num1*10 + str[i+2];
                num1 = num1*10 + str[i+3];
                num2 = str[i+4];
                num2 = num2*10 + str[i+5];
                num2 = num2*10 + str[i+6];
                num2 = num2*10 + str[i+7];
                break;
        }
        i = i + digit;
        diff = num2 - num1;
        if(diff != 1)
            break;
    }
    if(diff)
    {
        place = i;
        len = len + digit;
        output = (char*)malloc(sizeof(char)*len);
        for(i=0, j=0; j<len; j++, i++)
        {
            if(i!=place)
                output[i] = str[j];
            else
            {
                switch (digit)
                {
                    case 1:
                        output[i] = str[j]-1;
                        break;
                    case 2:
                        output[i++] = str[j];
                        output[i] = str[j+1] -1;
                        break;
                    case 3:
                        output[i++] = str[j];
                        output[i++] = str[j+1];
                        output[i] = str[j+2] - 1;
                        break;
                    case 4:
                        output[i++] = str[j];
                        output[i++] = str[j+1];
                        output[i++] = str[j+2];
                        output[i] = str[j+3] - 1;
                        break;
                }
                j--;
            }
        }
    }

    return output;
}

First place question should be "Given if the element is 1 we can move Right or down, if it is 0 we can only proceed downward".
Then find the working code.......
Plz give any comment....

#include<stdio.h>

#define ROW 3
#define COL 3
#define MAX ROW*COL

int NextDistance(int, int);

int arr[3][3] = {1, 1, 0, 0, 0, 0, 1, 0, 0};

int main(void)
{
   int i, j, dist;
   printf("\nOrigina Array......\n");
   for(i=0; i<ROW; i++)
   {
        for(j=0; j<COL; j++)
           printf("\t%d", arr[i][j]);
        printf("\n");
   }

   dist = NextDistance(0, 0);
   if(dist < MAX)
        printf("\nShortest Distance : %d\n\n", dist);
   else
        printf("\nThere is no path exist from start element to end element....\n\n");

   return 0;
}

int NextDistance(int i, int j)
{
    int slen=MAX, slen1=MAX, slen2=MAX;
    if(i==ROW-1 && j==COL-1)
        return 0;
    else if(i==ROW-1 && arr[i][j]==0)
        return MAX;
    else if(arr[i][j] == 0)
    {
        if(i < ROW-1)
            slen = 1 + NextDistance(i+1, j);
    }
    else
    {
        if(j < COL-1)
            slen1 = 1 + NextDistance(i, j+1);
        if(i < ROW-1)
            slen2 = 1 + NextDistance(i+1, j);
        slen = slen1<slen2 ? slen1 : slen2;
    }
    return slen;
}

Put elements in hashtable and while putting value check if it is present in the hashtable or not. If element is not present in the hashtable put it and print it. If it is present the simply leave this element and move forward. Repeat this process till the end of list.

Create class-B as base of class-A with public access. So all the things happening in base class(B) can be visible to derive class(A).

This question has already discussed with Id : 5901448273461248

@Nitin Plz explain your algo..

This will not work correctly if sequence contains -ve numbers.
Ex: -1, -2, -3, 4, 5

There is no need to use any extra stack or other DS..
simple O(n) solution without extra space....
Please comment on it.

#include<stdio.h>

#define SIZE 10

int main(void)
{
        int arr[SIZE];
        int i, j;
        for(i=0; i<SIZE; i++)
        {
                printf("Enter the Element for Array[%d] :  ", i);
                scanf("%d", &arr[i]);
        }
        printf("\n Original Array :  ");
        for(i=0; i<SIZE; i++)
                printf("    %d", arr[i]);

        j=0;
        for(i=0; i<SIZE-1; i++)
        {
                if(i == j)
                        for(j=i+1; j<SIZE && arr[i]>=arr[j]; j++);
                if(j > i && j < SIZE)   //Extra condition has been added to see whether have to replace or not.
                        arr[i] = arr[j];
        }

        printf("\n Modified Array :  ");
        for(i=0; i<SIZE; i++)
                printf("    %d", arr[i]);
        printf("\n\n");

        return 0;
}

This is really a great solution.

Can you plz explain your implementation....

Good one.... +1 from my side too..

Start reading the input string, navigate pointer to the trie according to the character you have read. If found word print it and/or continue reading.
Please find the pseudo code for that.

String temp, Result;
triePtr; // pointer to root of trie
while(input is not NULL)
{
	temp <- temp + Read a character from input;
	Navigate "triePtr" according to the read character in trie;
	if(Fount Valid word in trie)
	{
		Result =Result +" " + temp;
		clear temp;
		Reset triePtr to root of trie;
	}
}
if temp is not NULL
	return false;
else
	return Result;

In this case hashmap will take a lot of memories.
Also take more time because of large No. of data in it.

Can we think for any optimal solution...??

Here time and space complexity is very high...
Please see my code below which is taking O(n^2) with no extra memory except some variables.

If many subarrays are repeating with same size then in that case first repeating subarray will be returned.
Please see the above code.

Below code will take O(n^2) time without extra space except some variables....
I have testing it by many scenario, please give some scenario where it is not working.....

#include<stdio.h>

int main(void)
{
        int len, arr[100];
        int i, j, j1, start, end, st, ed, cnt;
        int count =0;

        printf("\nEnter the No of Elements : ");
        scanf("%d", &len);

        for(i=0; i<len; i++)
        {
                printf("\nEnter the Element at Array[%d] : ", i);
                scanf("%d", &arr[i]);
        }

        for(j = len-1; j>=0; j--)
        {
                st=j; ed=j; cnt=0;
                j1 = j;
                for(i=0; i<j && j1<=len-1; i++)
                {
                        if(arr[i] == arr[j1])
                        {
                                j1++; ed++; cnt++;
                        }
                        else if(j1 != j)
                        {
                                if(count < cnt)
                                {       count=cnt; start=st; end=ed-1; }
                                j1=j; st=j; ed=j; cnt=0;
                        }
                }
                if(count < cnt)
                        {count=cnt; start=st; end=ed-1; }
        }

        if(count > 0)
        {
                printf("\n Lenght of the Most Frequent non-empty subarray : %d", count);
                printf("\n Array : ");
                while(start <= end)
                        printf("\t%d", arr[start++]);
        }
        else
                printf("\nNo Frequent non-empty subarray found.....\n");

        return 1;
}

What is "count " in your program and where you are initializing it.
Can you explain you algorithm??

Working code is given below... call function using..
findCeil(root, num, num);

void findCeil(node* root, int num, int foundVal)
{
      if(*root != NULL)
      {
          if(num >= root->val)
              findCeil(root->right, num, foundVal);
          else
              findCeil(root->left, num, root->val);
       }
       else
           printf("\n Value : %d", foundVal);
}

In the above code, N total number of elements in array(Size of array), s is sum.
a[] is array, I am assuming array is sorted in increasing order.

This code will give the solution.....

int minCoinsCount(int a[], int N, int s)
{
        int i, count=0;
        while(s>0 && N--)
        {
                for(i=1; a[N]*i <= s; i++);
                if(i>1)
                {
                        count = count + i-1;
                        s = s - a[N]*(i-1);
                }
        //      N--;
        }
        if(s == 0)
                return count;
        else
                return -1;
}

Its complexity would be n^2 i guess..... Need to give most optimal solution.

This is amazon question dude......
Need to write you methods to find.

Treat n*n matrix as a single 1-D array. Access its index as "i*Col + j". So you will have kind of 1D array[0.....n*n]. Now perform heap sort on that. It will sort in O(n log n) time without any extra space............