Given an array A of integers, find the maximum difference between two indexes j-i such that A[i] < A[j].

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Algorithm:
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;

for (i = 0; i < n; ++i) { for (j = n-1; j > i; --j)
{
if(arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; } Time Complexity: O(n^2) Space Complexity O(1) Method 2 Given by celicom

Algorithm

we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

You Know Ultimate Things we have to found out is maximum distance between minimum element from Lmin array to Maximum element in RMax Array isn't it :)

Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(j

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x < y? x : y; } /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;

int *LMin = (int *)malloc(sizeof(int)*n);
int *RMax = (int *)malloc(sizeof(int)*n);

/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i-1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n-1] = arr[n-1]; for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);

/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j-i); j = j + 1; } else i = i+1; } return maxDiff; } /* Driver program to test above functions */ int main() { int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}; int n = sizeof(arr)/sizeof(arr[0]); int maxDiff = maxIndexDiff(arr, n); printf("\n %d", maxDiff); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(2n)..........................!!!!!!!!! Optimization in 2nd Method we can do it without using lmin array #include
#include

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x < y? x : y; } int maxIndexDiff(int arr[], int n) { int maxDiff; int i, j; int LMin; int *RMax = (int *)malloc(sizeof(int)*n); LMin = arr[0]; /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n-1] = arr[n-1]; for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);

/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LMin < RMax[j])
{
maxDiff = max(maxDiff, j-i);
j = j + 1;
}
else
{
LMin = min(LMin,arr[i+1]);
i = i+1;
}
}

return maxDiff;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {2, 9, 3, 4, 5, 6, 7, 8, 18, 8,0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("\n %d", maxDiff);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)..........................!!!!!!!!!
Run Here http://ideone.com/tNF7Q

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other. Input: { a, b, b }, distance = 2 Output: { b, a, b }

Question Asked in Google Telephonic Round!!!!!!!!!!!

Here we find 2 ranges for which all the integers in these ranges are present in the array.

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. Have to do it in linear time. May use extra memory. But Hashing is not the correct solution.
eg. arr = {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15}

Here we find 2 ranges for which all the integers in these ranges are present in the array.
namely: [2,8] and [10,12]
out of these [2,8] is the longer one. So we need to output that.


Basic Solution

First sort the array.
Have 3 integers - start, end and len. Initialize to 0. Have another variable "first" to point to the first element in the current set.

Loop the sorted array from start to end. Assign "first" to first element. Keep looping as long as the next element is contiguous. As soon as continuity breaks, subtract current number with "first". If it is more than "len", store "first" and current number in "start" and "end" respectively. Store the length calculated in "len". Continue this process.

You'll finally have the largest range in "start" and "end".

But Constraints is O(N)???

Write an algorithm to print out all the valid permutations that can be created using a stack and deque given an array of n integers.

This is a question from TAOCP,Google and I found it very interesting.

Given an array of integers, we can use stacks or deques (doubly ended queues) to output the numbers in certain permutations. For e.g. given an array {1, 2, 3, 4}, we can output it as {2, 3, 1, 4} by pushing down 1, pushing down 2, popping out 2, pushing down 3, popping out 3, popping out 1, pushing down 4 and then finally popping out 4. However, there are certain permutations that are not possible using a stack. For e.g., given an array {1, 2, 3, 4, 5, 6}, we can't create a permutation of {2, 1, 4, 6, 3, 5} using any sequence of push and pop operations on a stack. Using a deque however, it is possible. Write an algorithm to print out all the valid permutations that can be created using a stack and deque given an array of n integers.

WAP to Find The Minimum Number of Character Required from 1 String to Other String

For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:
kitten → sitten (substitution of 's' for 'k')
sitten → sittin (substitution of 'i' for 'e')
sittin → sitting (insertion of 'g' at the end).

Data Structure Used: 2 D Array

Algorithm:

A straightforward implementation, as pseudocode for a function LevenshteinDistance that takes two strings, s of length m, and t of length n, and returns the Levenshtein distance between them:
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)x(n+1) values
declare int d[0..m, 0..n]

for i from 0 to m
d[i, 0] := i // the distance of any first string to an empty second string
for j from 0 to n
d[0, j] := j // the distance of any second string to an empty first string

for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}

return d[m,n]
}

Two examples of the resulting matrix (hovering over a number reveals the operation performed to get that number):
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3

S a t u r d a y
0 1 2 3 4 5 6 7 8
S 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3


Proof of correctness
As mentioned earlier, the invariant is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. This invariant holds since:
It is initially true on row and column 0 because s[1..i] can be transformed into the empty string t[1..0] by simply dropping all i characters. Similarly, we can transform s[1..0] to t[1..j] by simply adding all j characters.

If s[i] = t[j], and we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i] and just leave the last character alone, giving k operations.
Otherwise, the distance is the minimum of the three possible ways to do the transformation:
If we can transform s[1..i] to t[1..j-1] in k operations, then we can simply add t[j] afterwards to get t[1..j] in k+1 operations (insertion).

If we can transform s[1..i-1] to t[1..j] in k operations, then we can remove s[i] and then do the same transformation, for a total of k+1 operations (deletion).
If we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i], and exchange the original s[i] for t[j] afterwards, for a total of k+1 operations

The operations required to transform s[1..n] into t[1..m] is of course the number required to transform all of s into all of t, and so d[n,m] holds our result.
This proof fails to validate that the number placed in d[i,j] is in fact minimal; this is more difficult to show, and involves an argument by contradiction in which we assume d[i,j] is smaller than the minimum of the three, and use this to show one of the three is not minimal.


Working Code

#include
#include
#include
#define MAX 2000
using namespace std;

int minimum(int a,int b,int c)
{
if(a if(b return c;
}

int LevenshteinDistance(char *a, char *b)
{
int **d;
int m=0,n=0,i,j;
char s[MAX]="0";
char t[MAX]="0";
d = (int **)malloc(MAX*sizeof(int));
for (i=0;i d[i] = (int *)malloc(MAX*sizeof(int));
strcat(s,a);
strcat(t,b);
m=strlen(s);
n=strlen(t);
printf("%s%s",s,t);
for(i=0;i<=m;i++) d[i][0]=i ;
for(j=0;j<=n;j++) d[0][j]=j;
for(j=1;j<=n;j++)
{
for(i=1;i<=m;i++)
{
if (s[i] == t[j])
d[i][j]=d[i-1][j-1];
else
d[i][j]=minimum(d[i-1][j] + (s[i]==t[i]?0:1),d[i][j-1] +
1,d[i-1][j-1] + 1 );
}
}
//TODO: Free "d"
return d[m][n];
}

int main()
{
int t,ed;
char s1[MAX],t1[MAX];
scanf("%d",&t);
while( t--)
{
scanf("%s%s",s1,t1);
//cout< ed=LevenshteinDistance(s1,t1);
printf("%d\n",ed);
}
return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Auxiliary Space O(N^2)
Run Here http://www.ideone.com/0BHid

Reorder 1st string based on 2nd string. eg: (tractor,car) output: carrtto or carrott or carrtot.

You have a stream of random numbers that are inserted into an expanding array. How can you maintain the current median and what is the complexity.

Given a linked list structure where every node represents a linked list and contains two pointers of its type: (i) pointer to next node in the main list. (ii) pointer to a linked list where this node is head. Write a C function to flatten the list into a single linked list. (from here)

Given an Sorted Array of 0s and 1s of infinite length fin the position of transition in array

e.g. 0000000....01......11111.....1.. infinite
ith position this wher 0 is converted in to 1


Data Structure Used: Array

Algorithm:(Done Will Post Soon)


Working Code:


Time Complexity O(logn) yes its logn ??
Space Complexity O(1)
Run Here

WAP to Find The Difference the between even-level-nodes sum & odd-level-nodes sum in binary tree consider root at 0th level which even level starting form 0th level

Example

Data Structure Used: Binary Tree

Algorithm:(Done Will Post Soon)


Working Code:


Time Complexity O(n)
Space Complexity O(1)
Run Here