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

WAP to Find Two Nodes Into Binary Search Tree such That they are equals to given number

Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space

Data Structure Used: Binary Search Tree

Algorithm:
1.Convert BST into sorted DLL which Will Take O(N) Time(Check previous Posts Already Coded) you can see here "cslibrary.stanford.edu/109"
2.take find sum into DLL two pointer start,end which points to starting & end position of DLL.
3. start from start->data & end->data , keep checking until we get all the number that sums to
given value as shown
while(ptr1->data < ptr2-> data)
{
if ((ptr1->data + ptr2-> data )>k)
ptr2= ptr2->prev;
else if ((ptr1->data + ptr2-> data )
ptr1= ptr1->next;
else if ((ptr1->data + ptr2-> data ) == k)
{
print_data_of_ptr1_and_ptr2;
ptr2= ptr2->prev;
ptr1= ptr1->next;
}
}
it will take O(N) time


Working Code (Need to Verify getting TLE)??

#include
#include
#include

/* The node type from which both the tree and list are built */
struct node {
int data;
struct node* small;
struct node* large;
};
typedef struct node* Node;



/*
helper function -- given two list nodes, join them
together so the second immediately follow the first.
Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b) {
a->large = b;
b->small = a;
}


/*
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
Node aLast, bLast;

if (a==NULL) return(b);
if (b==NULL) return(a);

aLast = a->small;
bLast = b->small;

join(aLast, b);
join(bLast, a);

return(a);
}


/*
--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
Node aList, bList;

if (root==NULL) return(NULL);

/* recursively solve subtrees -- leap of faith! */
aList = treeToList(root->small);
bList = treeToList(root->large);

/* Make a length-1 list ouf of the root */
root->small = root;
root->large = root;

/* Append everything together in sorted order */
aList = append(aList, root);
aList = append(aList, bList);

return(aList);


}

/* Create a new node */
static Node newNode(int data) {
Node node = (Node) malloc(sizeof(struct node));
node->data = data;
node->small = NULL;
node->large = NULL;
return(node);
}


/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data) {
Node root = *rootRef;
if (root == NULL) *rootRef = newNode(data);
else {
if (data <= root->data) treeInsert(&(root->small), data);
else treeInsert(&(root->large), data);
}
}


void findNums(Node head,int k)
{
Node ptr1,ptr2;
ptr1=head;
while(ptr1->large!=NULL)
ptr1=ptr1->large;
ptr2=ptr1->small;

while(ptr1->data < ptr2-> data)
{
if ((ptr1->data + ptr2-> data )>k)
ptr2= ptr2->small;
else if ((ptr1->data + ptr2->data)large;
else if ((ptr1->data + ptr2-> data ) == k)
{
printf("%d %d", ptr1->data,ptr2->data);
ptr2= ptr2->small;
ptr1= ptr1->large;
}
}

}
static void printList(Node head) {
Node current = head;

while(current != NULL) {
printf("%d ", current->data);
current = current->large;
if (current == head) break;
}
printf("\n");
}


/* Demo that the code works */
int main() {
Node root = NULL;
Node head;
treeInsert(&root, 6);
treeInsert(&root, 4);
treeInsert(&root, 2);
treeInsert(&root, 1);
treeInsert(&root, 3);
treeInsert(&root, 5);
treeInsert(&root, 7);

head = treeToList(root);

printList(head); /* prints: 1 2 3 4 5 6 7 */// int sum=9 ;
findNums(head,9);
return(0);
}



Time Complexity O(n)
Space Complexity O(1)
Run Here http://ideone.com/clone/Sf884

2nd Method (Awesome) Because it Doesn't modify The Tree Structure

Algorithm;
Do two inorder traversals, one in the usual (descend to the left
before descendung to the right) direction and the other in the
reversed(descend to the right before descending to the left)
direction. Let u and r be the current nodee of the two traversals,
respectively. If u + r < x, then advance the usual traversal and repeat the comparison. If u + r > x, advance the reverse traversal and
repeat the comparison. If u + r = x, and if u != r, then terminate
with success. If u = r, then terminate with failure.

Busy Will Try ton Code it Asap...:)

WAP to

Binary Matrix Problem

Problem: An NxN binary Matrix is given. If a row contains a 0 all element in the row will be sent to 0 and if a column contains a 0 all element of the column will be set to 0. You have to do it in O(1) space.

Example:
Input array:
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
Result array:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0


Solution:
Step 1: Store matrix [0][0] value in a temporary variable (Space Complicity: O(1) ).


Step 2: Apply & operation on first column and save it into Temp.


Step 3: Apply & operation on first row and save it into matrix [0][0].



Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
And value in Temp = 0

Step 4: Apply & operation on each row and save the result in the first cell of each row. Here i starts from 1 to n-1.





Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
And value in Temp = 0

Step 5: Apply & operation on each column and save the result in the first cell of each column. Here j starts from 1 to n-1.





Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0
Step 6: Now to find the value at matrix[i][j], you have to do a[i][0] & a[0][j]. Here I and j start from 1 to n-1




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 1 1 1 1
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0





Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 0 0
1 1 1 1 1
And value in Temp = 0




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 0 0
1 0 1 1 0
And value in Temp = 0
Step 7: Now to find the value at matrix [0][i] and matrix[j][0]. If matrix [0][0] is equal to 0 then make value 0 all the matrix[0][i] else remain unchanged. If Temp is equal to 0 the make value 0 all the matrix [j][0] else remain unchanged.
If (matrix [0][0] == 0)
Then



If (Temp == 0)
Then




Now 2D Matrix Array becomes:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
And value in Temp = 0

Step 8: Now to find the value at matrix [0][0], you need to do matrix [0][0] & Temp and save it into matrix [0][0].

Now 2D Matrix Array becomes:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
And value in Temp = 0
Step 9: Print your matrix and exit.
Result 2D Matrix array:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0


Working Code

WAP to Find Path of Minimum Sum in Binary Tree Efficiently

Data Structure Used:Binary Tree

Algorithm(Recursion)
For each node use two variable left & right for left & right subtree
find minimum in left & right sub tree & add root value to minimum
this algorithm requires two passes over binary tree with constant spaces.


#include
#include


struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int minSuminBT(struct node* t, int print)
{
if(t == NULL)
return 0;

left=t->left->data;
right=t-right->data;

int lsum = minSuminBT(t->left, 0);
int rsum = minSuminBT(t->right, 0);

if(print)
printf("%d ", t->data);

int sum = t->data;

if(lsum <= rsum) sum += minSuminBT(t->left, print);
else
sum += minSuminBT(t->right, print);

return sum;

}

/* Driver program to test mirror() */
int main(void)
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(3);
root->left->right = newNode(2);
root->right->left = newNode(1);
root->right->right = newNode(2);

minSuminBT(root,1);//answer 1-2-2
getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/RWbhP