WAP to Find equilibrium index in Unsorted Array of Size N, Efficiently

The equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:
A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:
A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(The sum of zero elements is zero) 7 is not an equilibrium index - because it is not a valid index of sequence A. If you still have doubts, here is a precise definition: The integer k is an equilibrium index of a sequence A[0],A[1]..,A[n-1] if and only if 0<= k and sum(A[0..(k-1)])=sum(A[(k+1)..(n-1)]). Assume the sum of zero elements is equal to zero.

Write a function
int equi(int A[], int n)

that, given a sequence, returns its equilibrium index (any) or -1 if no equilibrium index exists. Assume that the sequence may be very long.

The problem can be solved by using various approaches, the most common being simply to follow the equilibrium definition:

int equi ( int A[], int n ) {
int k, m, lsum, rsum;
for(k = 0; k < n; ++k) {
lsum = 0; rsum = 0;
for(m = 0; m < k; ++m) lsum += A[m];
for(m = k + 1; m < n; ++m) rsum += A[m];
if (lsum == rsum) return k;
}
return -1;
}

Time Complexity o(N^2)
Space Complexity O(1)
Run Here https://ideone.com/fThsV

Unfortunately, this approach has two disadvantages:

* it fails on large input data sets, since the time complexity is O(n2)
* it fails on large input values (for example if the input array contains values like MIN/MAX_INT) due to the arithmetic overflows

The solution analysis will detect such problems in submitted code:

Optimized Solution

We can fix the first problem with a better algorithm, and the second problem with a better data-type (for example, using long long type instead of int for sum computations). The key observation for better running time is to update the left/right sums in constant time instead of recomputing them from the scratch.

int equi(int arr[], int n) {
if (n==0) return -1;
long long sum = 0;
int i;
for(i=0;i
long long sum_left = 0;
for(i=0;i long long sum_right = sum - sum_left - (long long) arr[i];
if (sum_left == sum_right) return i;
sum_left += (long long) arr[i];
}
return -1;
}


Using this solution, you can obtain a perfect answer:

To return all equilibrium index we can print instead of returning the single index

Time Complexity O(N)
Space Complexity O(1)
Run Here https://ideone.com/OKM8d

Construct Binary Tree From Ancester Matrix Efficiently

You are given a matrix M[n, n] for a tree with n nodes. In the given matrix M, M[i, j] is true iff node j is an ancestor of node i. Construct the tree from the given matrix.

For example, you are given below matrix.

1 2 3 4
1 0 1 1 0

2 0 0 1 0

3 0 0 0 0

4 0 1 1 0

You need to construct the below tree. In the constructed tree ancestor relationship should be correct. A node can come on left or right of its parent as you cannot determine this information from the ancestor matrix

Node numbers used in matrix are in bracket
5(3)
/
/
10(2)
/ \
/ \
12(1) 13(4)


Data Structure Used: 2-D Array , Binary Tree

Algorithm


Time Complexity
Space Complexity

Given an array and an integer k, find the maximum for each and every contiguous sub array of size k.

Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]

Sample Output :
3
3
4
5
5
5
6

This Question is Asked By Google Indirectly for Maximum in window or subarray of size k in array of size n, yes it is sliding window problem, as window slides we need to find out the maximum in each window. is it ??

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

Solution: It Can Solved By Two Ways in This Question Data Structure Plays Important Role

The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window & n is size of array

1st Method(Naive Approach)

Data Structure Used : Array
Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window)
B.for all j=i to i+w (keep incrementing windows size form left to right)
C find maximum inn each window & print it or put in array (Auxiliary)

#include

void printMaxInSlidingWindows(int a[],int n,int w)
{

int max=0;
int i=0,j=0;

for (i = 0; i max)
}
max=a[j];

}

}
printf( " %d ", max);
}

}

int main()
{
int a[]={1,3,-1,-3,5,3,6,7};
printMaxInSlidingWindows(a,8,3);
}

TC O(nw)
SC O(1)
Run Here http://ideone.com/7o3Ta


2nd Method

Data Structure Used: Queue(More Efficient)

We need a data structure where we can store the candidates for maximum value in the window and discard the element, which are outside the boundary of window. For this, we need a data structure in which we can edit at both the ends, front and back. Deque is a perfect candidate for this problem.

We are trying to find a way in which, we need not search for maximum element among all in the window. We will make sure that the largest element in the window would always appear in the front of the queue.
While traversing the array in forward direction if we find a window where element A[i] > A[j] and i > j, we can surely say that A[j], will not be the maximum element for this and succeeding windows. So there is no need of storing j in the queue and we can discard A[j] forever.
For example, if the current queue has the elements: [4 13 9], and a new element in the window has the element 15. Now, we can empty the queue without considering elements 4, 13, and 9, and insert only element 15 into the queue.

Every time, we move to a new window, we will be getting a new element and leave an old element. We should take care of:
Popping elements outside the window from queue front.
Popping elements that are less than new element from the queue.
Push new element in the queue as per above discussion.

Note:Optimization Done In Done so that we can Find The Maximum of Each Window in O(1)

Here Is Tunning Code

import java.util.*;

class Maximumin_SlidingWindow
{

public static void main(String ar[])
{

Integer a[]=new Integer[]{1,3,-1,-3,5,3,6,7};
int w=3,i=0;
int size=a.length;
Integer b[]=new Integer[size-w+1];

maxSlidingWindow(a,size,w,b);

for(i=0;iQ=ar[0];

//Initilize deque Q for first window
for (int i = 0; i < w; i++) { while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();
Q.offerLast(i);
}

for (int i = w; i < n; i++) { B[i-w] = A[Q.peekFirst()]; //update Q for new window while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();

//Pop older element outside window from Q
while (!Q.isEmpty() && Q.peekFirst() <= i-w)
Q.pollFirst();

//Insert current element in Q
Q.offerLast(i);
}
B[n-w] = A[Q.peekFirst()];
}

}

TC O(n)n Since Eacj Array Element is Inserted & deleted At-Most Once
SC O(1)
Run Here http://ideone.com/KLIpO
http://ideone.com/TftYg

Which is the Best Data structure which is supposed to log number of user requests per second.

Make a Data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds. It can be at any time for example he will say at 71st second that tell me how many hits for past 30 seconds or something, but this window can go maximum upto 60 seconds to in the previous example 11 to 71.


Data Structure Used: Queue(Basic Approach),Circuler Queue,Binary Index Tree(Most Efficient)

Algorithm & Solution

Take a queue of length 60. Each second do a Deque() and enque(#of users logged this second). For query traverse from tail of the queue to that many seconds as asked and sum all of those.

Algorithm: (Optimized with array)

N <- 60
A is an array of length N. holds the queue. Initialized to 0.
p is the pointer to head of the queue
tick is the system clock whose value increases by 1 each second

enque (n) // does a simultaneous deque()
{
p <- (p+N-1) mod N
A[p] <- n
}

update()
{
n <- 0
t <- tick
while true
{
if( t == tick && new user has logged in)
{
n <- n+1
}

else if (t < tick)
{
enque(n)
n <- 0
t <- tick
}

}
Query(t)
{
sum <- 0
for i <- 0 to t-1
{
sum <- sum + A[ (p+i) mod N]
}

return sum
}

where tick is the memory/register where system keeps track of each second passed by incrementing its value by 1 every second. tick can be read by any program in the system but can be written only by system clock hw/sw. Now, in the 'while' loop, eventually tick will be incremented by system clock hw/sw each second behind the scene, while, t will remain at previous value and an enque() will happen along with update of t.
This algorithm is optimized for enque() since this happens every second while a Query happens asynchronously and its frequency might be too less than frequency of enque() operations.

Time Complexity
Space Complexity

Optmization

We can use Binary Indexed Tree/ Fenwick Tree. Updating the array as well cumulative sum will be of O(log n) complexity.

Of course we have to put a limit to after which time(i/p) we cant query as we cant store infinite amount of data, or if yes partioning of data would be needed(if thats the intention the above is not efficient).

Feel Free to Comment or Optimize The Solution

WAP to Find Maximum Windows of Matching Character , You Given two Sequences

Given two sequences of length N, how to find the max window of matching patterns. The patterns can be mutated.

For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (ABCD from seq1 and DBCA from seq2)

Data Structure :Hash Table

Algorithm:

INDEX:01234567
SEQ1 = "ABCDEFGK";
SEQ2 = "ZGEDFBAP";

here the expected answer is window of size 4
DEFG
GEDF

we use a map to store the characcters indices of SEQ1
then we search for windows of matching characters from SEQ2
only when the window size is >1, we need to use an temporary array...
we push the indices of the matchin chars from SEQ1 into this array...
here we hav arr = 6 4 3 5 1 0
sort this array, 0 1 3 4 5 6
test for maximum window in this array
3 4 5 6 of size 4


Working Code:

#include
#include
#include

Given two sequences of length N, how to find the max window of matching patterns. The patterns can be mutated.

For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (ABCD from seq1 and DBCA from seq2)

Given two sequences of length N, how to find the max window of matching patterns. The patterns can be mutated.

For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (ABCD from seq1 and DBCA from seq2)

Given 3 arrays, pick 3 nos, one from each array, say a,b,c such that |a-b|+|b-c|+|c-a| is minimum

Data Structure Used: Arrays of Integer

Algorithm:
1.Sort all 3 arrays (Using Heap or Quick Sort) , take min = INFINITY
2.Take pointer to start of all the three arrays
3.compute sum = |a-b|+|b-c|+|c-a| where a,b,c are elements pointed to by d pointers
4.if sum < min then sum = min.save a,b,c too 5.increment the pointer of (min (a,b,c)) 6. if not the end of any array. repeat from step 3 Working Code:Java class QuickSort { static int min(int a, int b, int c) { int m = a; if (m > b) m = b;
if (m > c) m = c;
return m;
}


static int findMinof_abc(int a[],int m,int b[],int n,int c[],int l)
{

int min = Integer.MAX_VALUE;
int i = 0, j = 0, k = 0;

while( i < m && j < n && k < l) { n = Math.abs(a[i]- b[j]) + Math.abs(b[j] - c[k])+ Math.abs(c[k] - a[i]); min = n pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}

public int[] sort(int[] input)
{
quickSort(input, 0, input.length-1);
return input;
}

public static void main(String args[])
{

QuickSort mNew = new QuickSort();

int a[]={11,13,22,31};
int b[]={18,26,36};
int c[]={28,29,30,33};
mNew.sort(a);
mNew.sort(b);
mNew.sort(c);

int x=4,y=3,z=4;
System.out.println(findMinof_abc(a,x,b,y,c,z));

}


Time Complexity O(NlogN)
Space Complexity O(logN)
Run Here http://ideone.com/eCrlJ

WAP to Convert Infix Expression into PostFix Expression Effciiently

Example a+b*c =abc+*
Data Structure:Array

Algorithm: let Q be the Arithmetic Expression
1.Push ( in to Stack.n ) in end of the Q.
2. Scan Q from left to right & repat stpe 3 to 6 fro each elemnt of Q untill stack is
emptty.
3.if an operand encountered ad it to p.
4. if ( encountered push it into stack.
5.if an operator encountered then
a.add operator to stack.
b.repeatedly op from the satck & add P each char (on top of the stack) which has
the same or higher precendence than operator .
6.if ) encountered then
a. repeatedly pop from the satck & add p to each opeartor (on top of stack untill
a ' (' encountered.
b. remove '(' (do add '(' to the P.

Working Code:

#include
#include
#include
#include
#include
#define MAX 100


/*this is the structure of the stack used to save operators in the expression*/
struct stack
{
char elem[MAX];
int top;
};
struct stack stk;


void convert(char *infix, char *postfix);
int prcd(char op1, char op2);
void create();
void push(char op);
char pop(int *und);
int empty();
int full();
int isopnd(char ch);
int isoprtr(char ch);



int main()
{
char ch, infix[MAX], postfix[MAX];

create();

printf("Enter the infix expression\n");
scanf("%s", infix);

convert(infix, postfix);

printf("\n\nThe postfix expression is :\n");
printf("%s\n", postfix);

getch();
}

return(0);
}




void convert(char *infix, char *postfix)
{
int i, pos=0, over, und, n;
char ch, op;

for(i=0; (ch=infix[i]) != '\0' ; ++i)
{
/*
operands are entered directly into the postfix expression

*/

if(isopnd(ch))
{
postfix[pos++] = ch;
}

/*
if an operator is encountered, insert it into the stack or the postfix expression according to the precedence wit rspect to previous operators(if any) in the stack
*/
else if(isoprtr(ch))
{
op = pop(&und);

while(!und && prcd(op, ch))
{
postfix[pos++] = op;
op = pop(&und);
}

if(!und)
push(op);

if(und || ch != ')')
push(ch);
else
pop(&und);
}

/*
if we get some other character than an operand or an operator, then the infix expression is invalid.
*/
else
{
printf("\n\nThe infix expression is not valid\n");
getch();
return(0);
}
}

while(!empty())
{
postfix[pos++] = pop(&und);
}

postfix[pos++] = '\0';
}


/*function to check precedence of different operators*/
int prcd(char op1, char op2)
{
if(op1 == '(' || op2 == '(')
return 0;

if(op2 == ')')
return 1;

if(op1 == '^')
{
if(op2 == '^')
return 0;
else
return 1;
}

if(op1 == '/' || op1 == '*')
{
if(op2 == '^')
return 0;
else
return 1;
}

else
{
if(op2 == '^' || op2 == '/' || op2 == '*')
return 0;
else
return 1;
}
}




void create()
{
stk.top = -1;
}


void push(char op)
{
stk.elem[++(stk.top)] = op;
}



char pop(int *und)
{
if(empty())
{
*und = 1;
return('0');
}

*und = 0;
return(stk.elem[stk.top--]);

}



int empty()
{
if(stk.top == -1)
return 1;
else
return 0;
}


int full()
{
if(stk.top == MAX - 1)
return 1;
else
return 0;
}


/*check whether the given char is an operand or not*/
int isopnd(char ch)
{
if((ch>=48 && ch<58) || (ch>64 && ch<=90) || (ch>96 && ch<=122))
return 1;
else
return 0;
}


/*check whether the given char is an operator or not*/
int isoprtr(char ch)
{
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' || ch == '(' || ch == ')')
return 1;
else
return 0;
}

Time Complexity O(n)
Space Complexity O(n) Stack Space
Run Here https://ideone.com/cQAJP

Game of Master Mind !!!!!!!!!!!!!!

Game of master mind: you have four balls, and four different colors, as a
solution. The user tries to guess the solution. If they guess the right
color for the right spot, it counts as a 'hit'. If it's the right color, but
the wrong spot, it counts as a psuedo-hit. For example: if the solution is
'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit.
Write a program to, given a solution and a guess, calculate the number of
hits and pseudo hits.

Data Structure Used: Array

Algorithm:
1.Take an temp array of length ascii chars(256) , although we need array of length of 4 here
taking above array will give advantage so that we set/reset the 1 or 0 at particular character
position according to their ascii value.
2.scan solution & guess string & set value to 1 in temp array for each matching character of
solution & guess string also increment the hits counter.else increment temp array location of
corresponding character location.
3.in 2nd pass over temp array check for each location if that location value is not equal to 1 &
also temp[location]>0 if yes then increment pseudo-counter & decrement corresponding character
count in temp array.

Above algorithm will take O(N) time & constant space with two passes over three arrays.1 pass over solution & guess string
2nd pas over temp string



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