Print the objects of an array in the order of decreasing frequency. PS: Please make sure order of object should remain same

E.g. if array is of integer is given as  5 2 2 8 5 6 8 8, then we should get 8 8 8 5 5 2 2 6 , here freq. of 5 and 2 are same but 5 comes before 2 in array thus its should come before in output as well.

Here is the working code , let me know if it will fail for any test case and  if we can improve it?

/********************************************************

Time Complexity :  O(n)+O(nlogn)+O(n)=O(nlogn)

Space Complexity : Auxallery Space O(2n)= O(n)

*********************************************************/

 Run Here http://ideone.com/FQ65xM

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized

#include<stdio.h>
#define MAX(a,b) ((a>b)?(a):(b))
main()
{
  int arr[]={-2, -3, 4, -1, -2, 1, 5, -3};
  int len,i;
  int max=0;
  len = sizeof(arr)/sizeof(arr[0]);
  max=arr[0];
  int finalmax=0;
  int start=0,end=0;
  for(i=1;i<len;i++)
  {
    max = MAX(max+arr[i], arr[i]); 
      
        finalmax=MAX(max,finalmax);
    
  }
 
    
      printf("MAX:%d %d %d \n",finalmax, start ,end);
 
   
   
}

Example if you want to print array http://codepad.org/BhYxSlp4

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from given elment

Count maximum number of "connected 1" in given matrix

you have a matrix of N x N filled with 1 or 0. you can move only 1 step either right or 1 step down. you need to count maximum number of "connected 1" in given matrix. for example
0 0 1 1
1 1 1 0
1 0 1 0
0 1 0 1

[Start from top left] maximum no. of 1 is 4
[1,0][1,1][1,2][2,2]


Source -: Commented by a user "rakesh"

A legend among a group of n people is a person who is top rated in all respects.The task is to identify a legend by asking a single question of the form "who deserves it?" Design an efficient algorithm to identify a legend or determine if the group has no such person.How many questions does your algorithm need in the worst case??

Convert Prefix expression to postfix expression

In a binary tree replace each node's value (except leaf node) with the sum of left and right subtree's value.

Write a function to convert Hexadecimal number (String) to Decimal Number (Int)

Maximum Sum Subsequence in an unsorted array of size n

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are  possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to  by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let  denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

 (for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over  for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array  where  would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes  time and  space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all  values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes  time and  space.

Given list of words in the order as in the dictionary, find the order of the alphabets.

Example:
 
Suppose you are given words in the same order as in the dictionary like a, ant, ball, cat, do, dog, fog, frock etc.
From these words you know that there are alphabets a, n, t, b, l, c, d, o, g, f, r, k.
You don't know the order of these alphabets before hand.
You will have to find the order of these alphabets based on the order of the given words.
 
Some Analysis :
 
From a and ant you cannot make out anything.
From ant and ball you can make out that a comes before b in the order.
From ball and cat you can make out that b comes before c in the order.
From cat and do you can make out that c comes before d in the order.
From do and dog you cannot make out anything.
From dog and fog you can make out that d comes before f in the order.
From fog and frock you can make out that o comes before r in the order.
From these clues you should make out the order of the alphabets.
Not necessarily you will be given all the dictionary words, but the words which are sufficient enough to make out the order of the alphabets.
You can always say you cannot make out the order if the words given are not sufficient.

Why don't make hands little dirty  , give it a try , shoot me comment :)

Given a array, find the largest contiguous sub-array having its sum equal to N.

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are  possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to  by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let  denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

 (for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over  for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array  where  would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes  time and  space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all  values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes  time and  space.

Given Preorder can you make BST from it then print the sorted output from BST

#include<iostream>
#include<stdlib.h>
using namespace std;
 
typedef struct tree{
int val;
struct tree *left;
struct tree *right;
}tree;
 
tree* insert(tree* root, int val)
{
if(root == NULL)
{
tree* temp = (tree*) malloc(sizeof(tree));
temp->val = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
 
tree* node = (tree*) malloc(sizeof(tree));
if(root->val < val)
root->right = insert(root->right, val);
else
root->left = insert(root->left, val);
return root;
}
 
tree* buildBST(int preOrder[], int length)
{
tree* root;
if(length != 0)
{
root = (tree*) malloc(sizeof(tree));
root->val = preOrder[0];
root->left = NULL;
root->right = NULL;
}
else
return NULL;
 
for(int i = 1; i < length; i++)
{
root = insert(root, preOrder[i]);
}
 
return root;
}
 
void printInOrder(tree* BST)
{
if(BST == NULL) return;
printInOrder(BST->left);
cout << BST->val << " ";
printInOrder(BST->right);
}
 
void printPreOrder(tree* BST)
{
if(BST == NULL) return;
cout << BST->val << " ";
printPreOrder(BST->left);
printPreOrder(BST->right);
}
 
int main(void)
{
int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12};
tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int));
printInOrder(BST);
cout << endl;
printPreOrder(BST);
cout << endl;
}

 Time Complexity O(N^2) in Case of Skewed Tree
 Space Complexity O(1)
Run Here http://ideone.com/KVDrB

Given an array of length n, print all sub arrays of length r

Fill next with node pointers which represent Inorder Successor of every node in BSTin BST

You are given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.
In a binary tree, inorder successor of a node is the next node in inorder traversal of the binary tree. Inorder successor is NULL for the last node in inorder traversal.

PS: In BST, inorder successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.

you have to print all possible combination of a given length let's say 'k' of a string in lexicographic order.

for Example:- input String=az k=2;
output
aa

az

za

zz..