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

WAP to Delete a Character before the Given Index in Character Array (You Have Given Array of Ascii & kanji Characters)

First some definitions for this problem: a) An ASCII character is one byte long and the most significant bit in the byte is always '0'. b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is '1'.

Now you are given an array of a characters (both ASCII and Kanji) and, an index into the array. The index points to the start of some character. Now you need to write a function to do a backspace (i.e. delete the character before the given index).

We have to write an algorithm & a quality working code for this.


Explanation

1. Look at MSB of the previous character. If 1, then delete the previous two bytes. This is because an MSB of 1 can only be part of a Kanjii character.
2. If the MSB is 0 then all you know is that the previous byte ENDs a character. The previous byte could be an Ascii character, the single byte is the start and the end of the character OR the previous byte is the second byte of a Kanjii character. Look the following figures which show the characters to the left the given character, denoted by ‘|’.

xxx10|xxxxx. You cannot decide on the previous character based on the scan so far because there are two possibilities after this
1. xx010|xxxxx - The previous character is a Kanjii character. After first 0 from left we are left with ‘10’ which is Kanjii.
2. xx110|xxxxx - We have to scan even further. Leads to two choices
x1110|xxxxx - We have to scan even further.
x0110|xxxxx - after leftmost 0, we have ‘110’ which break into ‘11’ and ‘0’. So the previous character is Ascii.

Continuing on this logic you will notice that you have to first find the end byte of a previous character and the only way to do that is to find the previous ‘0’ OR start of the file. After you have found the previous end byte of a character, you count the number of ‘1’ in between the 0 before the cursor and the previous end byte.
1. If number of ‘1’s is even then the previous character is Ascii so the backspace should delete one byte.
2. If the number of ‘1’s is odd then the previous character is Kanjii and two bytes should be deleted.


Data Structure Used: Array

Algorithm

Working Code(In progress)


Time Complexity
Space Complexity
Run Here

WAP to Calculate Maximum Height & Depth of Tree With & Without Recursion

Height/Depth of Tree Without Recursion


Data Structure Used:Queue

Algorithm
1.Insert Root Node in Queue & NUll After root Node.Inserting NULL will help us in measuring height of tree.
2.do remove front element from the queue until its is empty
if(front==NULL)
increment height=height+1;
check queue is empty or not if not insert NULL every time at this step.
else
insert root->left & root->right node into queue.

repeat above step 2 until queue is empty



#include
#include
#include

typedef struct TreeNode {
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns height of a binary tree without recursion

We are using level order traversal
*/

int Height(Tree t) {

int height = 0;//-1;

if(t != NULL) {

std::list q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty

height++;

if(!q.empty())
q.push_back(NULL);

}
else {

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}

}

}

return height;
}


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

return(node);
}

int main()
{
Tree root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Height of tree is %d", Height(root));

getchar();
return 0;
}



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


Maximum Height/Depth of Tree Using Recursion

Algorithm

1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth



#include
#include
#include

struct node
{
int data;
struct node* left;
struct node* right;
};
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{ int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

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 main()
{
struct node *root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Hight of tree is %d", maxDepth(root));

getchar();
return 0;
}

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

WAP to Implement the hash Function For String Variable Which Act as a Key in hashTable

The String hash function

In the String class, for example, the hash code h of a string s of length n is calculated as

hash=a[0]*31^n-1+a[1]*31^n-2+........a[n-1]*31^0

or, in code,

int h = 0;
for (int i = 0; i < n; i++)
 {
     h = 31*h + s.charAt(i);

}
 For example the hash code of hello uses the Unicode values of its characters
h e l l o
  h      e     l      l       o
 104 101 108 108 111(ASCII Values) to give the value 99162332=104*31^4+101*31^3+108*31^2+108*31^1+111
benefits of Doing This is that we won't get same hash values for anagram string e.g. hello & olhel, helol etc.

 In general the arithmetic operations in such expressions will use 32-bit modular arithmetic ignoring overflow. For example Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
 where Integer.MAX_VALUE =2147483647 Integer.MIN_VALUE =-2147483648 Note that, because of wraparound associated with modular arithmetic, the hash code could be negative, or even zero. It happened to be positive in this case because hello is a fairly short string. Thus, for example, the hash code for helloa, which is 31 times the hash code for hello plus 97, would not be , which is outside the range of 32-bit signed integers, but 3074032079-2^32=-1220935217 (which is in the range)

 so After All The Basic & Efficient has Function For String Looks Like
int hash(String key)
{ int h = 0;
  for (int i = 0; i < key.length; i++)
 {
     h = 31*h + s.charAt(i); }
     if(h>INT_MAX)
     return h-INT_MAX // or h % table_size
     else if(h<INT_MIN)
       return h+INT_MAX;

return h; //else return h
}

Another Hash Function Cloud be if consider string only combination of alpha-bates so base 26

if we simply use the sum or crc type hash function we will get the same hash value thus collision.

see hash function

int hash (String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i);
return ( k%m );
}

it will return same hash value for all anagram string as explained above .

int hash(String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i) + i*(int)s.charAt (i);
return ( k%m );
}

benefits of Doing This is that we won't get same hash values for anagram string e.g. hello &
olhel, helol etc.



Some other information on String Hash Function .
http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
http://www.jchq.net/certkey/0902certkey.htm 

 
 Feel Free to Comment.

Application of Segment Tree A data Structure Which Support Update and Query Operation on Array Intervals in Logarithmic Time

A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval [i, j] in the following recursive manner:

the first node will hold the information for the interval [i, j]
if i
See the picture below to understand more :

WAP to add a Marble to Box i & sum all the Marbles from Box k to box l .You Have Given The Number of Boxes.

Let's define the following problem: We have n boxes. Possible queries are
1. add marble to box i
2. sum marbles from box k to box l

we have to write an efficient algorithm & then code so that if do m queries in 2nd operation we can efficiently find out the sum of marbles from box i to box j.

This Question is Exactly Asked in Google Interview.

Solution

The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). (BIT)Binary Indexed Trees are easy to code and have worst time complexity O(m log n).

(BIT)Fenwick tree supports the following basic operations each of which take O(log n) time:
Change the frequency at some position and update the tree
Read the cumulative frequency for a given key
Read the actual (not cumulative) frequency at a certain position
Find the index with a given cumulative frequency, if all individual frequencies are positive, or all indices with a given cumulative frequency, if all individual frequencies are non-negative
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.


Algorithm

The two major functions are

update (idx,val) : increases the frequency of index idx with the value val
read (idx) : reads the cumulative frequency of index idx
Note : tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx where r is rightmost position of 1 in the binary notation of idx, f is frequency of index, c is cumulative frequency of index, tree is value stored in tree data structure.

Notataion

BIT - Binary Indexed Tree
MaxVal - maximum value which will have non-zero frequency
f[i] - frequency of value with index i, i = 1 .. MaxVal
c[i] - cumulative frequency for index i (f[1] + f[2] + ... + f[i])
tree[i] - sum of frequencies stored in BIT with index i (latter will be described what index means); sometimes we will write tree frequency instead sum of frequencies stored in BIT
num¯ - complement of integer num (integer where each binary digit is inverted: 0 -> 1; 1 -> 0 )
NOTE: Often we put f[0] = 0, c[0] = 0, tree[0] = 0, so sometimes I will just ignore index 0.



Index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

f
1 0 2 1 1 3 0 4 2 5 2 2 3 1 0 2

c
1 1 3 4 5 8 8 12 14 19 21 23 26 27 27 29

tree
1 1 2 4 1 4 0 12 2 7 2 11 3 4 0 29

Table 1.1



Index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

tree
1 1..2 3 1..4 5 5..6 7 1..8 9 9..10 11 9..12 13 13..14 15 1..16

Table 1.2 – table of responsibility

#include
using namespace std;

template
class BIT
{
T *tree;
int maxVal;
public:
BIT(int N)
{
tree = new T[N+1];
memset(tree,0,sizeof(T)*(N+1));
maxVal = N;
}
void update(int idx, T val)
{
while (idx <= maxVal) { tree[idx] += val; idx += (idx & -idx); } } //Returns the cumulative frequency of index idx T read(int idx) { T sum=0; while (idx>0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
};

int main()
{
int a[100],cur=1,mul=2,add=19,MAX=65536,x,i;
//Initialize the size by the
//maximum value the tree can have
BIT B(MAX);
for (i=0;i<50 data-blogger-escaped-a="" data-blogger-escaped-add="" data-blogger-escaped-b.update="" data-blogger-escaped-cin="" data-blogger-escaped-cur="((cur" data-blogger-escaped-i="" data-blogger-escaped-max="" data-blogger-escaped-mul="" data-blogger-escaped-while="">>x)
{
cout< }

}

Time Complexity O(logn) fro m queries it will be O(mlogn)
Space Complexity O(1)
Source : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays

eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

Data Structure Used: 2 D Array, Hashing


Algorithm:
Find the value of each row, as in 2^(n-1)*a[0][i]+2^(n-2)*a[1][i]+...+2^(0)*a[n][i]
then compare values and write rows which have difft values (think each row as binary representation of number then we just have to convert each row to decimal representation of number)



Working Code:

#include
#include
#define N 5
int main()
{
int a[N]={0,0,0,0,0},b[N]={-1,-1,-1,-1,-1},p,i,j;
int A[][N] = {
{1,1,0,0,1},
{1,1,0,0,1},
{1,0,0,0,1},
{1,1,0,0,1},
{1,0,0,0,0}
};


for(i=0;i=0;j--)
{
if(A[i][j] == 1)
{
a[i] += pow(2,(N-1)-(j));}
}
}
}

for(i=0;i {
j=a[i] % N;
p=0;
while(b[j] != -1)
{
if(b[j] != a[i])
j = (j+1)%N;
else
{
p=1;
break;
}
}

if(p!=1)
{
for(p=0;p printf("%d ",A[i][p]);

b[j] = a[i];
printf("\n");
}
}

return 0;
}


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