NaiveCoder
BAN USER- 2of 2 votes
AnswersYou are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
- NaiveCoder in India
eg :
Matrix
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
And pattern is microsoft.
It's funny when google looks for pattern of microsoft ;)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
Answers|_|
- NaiveCoder in India
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C) will be divided equally to left and right child cup of next level
i.e. C/2 to left child and C/2 to right child
Write a function which takes input parameter as amount of liquid poured at top (L) and height of particular cup (h) index of that cup (i) and it should return amount of liquid absorbed in that cup.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
@All
there should be exactly N chords and all are non intersecting
if you take diagonal points they will intersect each other
Common Ancestor of given two nodes ...sorry for inconvenience...
for eg
1
2 3
4 5 6 7
8 9
common ancestor of 8 and 5 is 1 and 2
so o/t shld be 1, 2
Stack : Static allocation
Heap: Dynamic allocation of memory
#include<stdio.h>
#include<stdlib.h>
#include<string>
char RCODE[13][3] = {"M", "CM", "D", "CD", "C", "XC", "L","XL", "X", "IX", "V", "IV", "I"};
int BVAL[] = {1000, 900, 500, 400, 100, 90, 50,40, 10, 9, 5, 4, 1};
int main()
{
int n;
int i;
scanf("%d",&n);
while(n>0)
{
for(i=0;i<13;i++)
{
while(BVAL[i]<=n)
{
n=n-BVAL[i];
printf("%s" ,RCODE[i]);
}
}
printf("\n");
scanf("%d",&n);
}
getchar();
return 0;
}
Can you give some example???
- NaiveCoder March 06, 2012For search O(n)
then you can use array of fixed size.
And collision can be avoided by chaining (using link list)
in this case worse case when all n elements maps to the same index , linear search will take O(n) time to find the element.
In order to get the O(1) search
Create an array of size max( all a[i]) and then map each element corresponding to their index.
void FindPair(int a[],int x,int i,int j)
{
int n=a.length();
quicksort(a);
int q,w;
q=0;w=n-1;
while(q<w)
{
if(a[q]+a[w]==x)
{
i=a[q];
j=a[w];
return;
}
else if(a[q]+a[w]<x)
q++;
else
w--;
}
//pair not found
i=INT_MIN;
j=INT_MAX;
}
void par(int open,int close,int n,int idx)
{
static char a[1000];
if(close==n)
{
printf(a);
return;
}
if(close<open)
{
a[idx]=")";
par(open,close+1,n,idx+1,a);
}
if(open<n)
{
a[idx]="(";
par(open+1,close,n,idx+1,a
}
}
This can be solved in n +logn -2 comparision using tournament method
- NaiveCoder March 03, 2012void Level(root)
{
int h=height(root);
for(i=1;i<=h;i++)
{
LEVELORDER(root,i);
printf("\n");
}
}
void LEVELORDER(root,level)
{
if(!root)
return NULL;
if(level==1)
printf("%d ",root->data);
else if(level>1)
{
LEVELORDER(root->left,level-1)
LEVELORDER(root->right,level-1)
}
}
Oops i modified the original list ....any way
the other list can be formed from "temp" idea will be similar
for the last two if ...we have to traverse the rest of the either list..
Merge(node L1, Node L2)
{
if(!L1)
return L2;
if(!L2)
return L1;
Node head,tmp;
if(L1->data <L2->data )
{
tmp=L1;
L1=L1->next;
}
else
{
tmp=L2;
L2=L2->next;
}
head=tmp;
while(L1&&L2)
{
if(L1->data <L2->data )
{
tmp->next=L1;
L1=L1->next;
tmp=tmp->next;
}
else
{
tmp=L2;
L2=L2->next;
tmp=tmp->next;
}
}
if(L1)
tmp->next=L1;
if(L2)
tmp->next=L2;
return head;
}
Rather than sorting u can create the min heap with those distance in O(n)
And then u can exatract min k time .... well this will give (O(n) + klogn)
The other way is to find first k node(distance) is using variation of quick sort ..... this can be done in O(n) .... check out careercup.com/question?id=4356905
start summing up value from leaf to root and while summing these value keep track of node largest sum up value. and passing this value to parents node.
int Max (node *root)
{
static node tmp=NULL ;
static int check=INT_MIN
if(!root)
return 0;
if(root->left ==NULL && root->right==NULL)
return root->data;
int L=Max(root->left);
int R =Max(root->right);
if( (root->data + L +R) >check)
{
tmp=root; //store the node with max value;
}
return (root->data +L +R) ;
}
tmp node will have largest sum up value.
//tmp node can be pass as a reference node also
}
in O(mn) can be done but it will be naive approach.
the other way is to use kmp .... but we have to first generate all the pattern of second string of contniues character of len(m to 2)
then find that pattern in the first string
this will again take O(mn) in worse case
#include<stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int prod(int a[],int n)
{
int min1,min2,max1,max2,max3;
min1=min2=32767;
max1=max2=max3=-32767;
int i;
for(i=0;i<n;i++)
{
if(a[i]>max1)
{
max3=max2;max2=max1;max1=a[i];
}
else if(a[i]>max2)
{
max3=max2; max2=a[i];
}
else if(a[i]>max3)
max3=a[i];
if(a[i]<min1)
{
min2=min1; min1=a[i];
}
else if(min2>a[i])
min2=a[i];
printf("%d %d %d %d %d\n",max1,max2,max3,min1,min2);
}
if(min1<0 && min2 <0)
return max(min1*min2*max1, max1*max2*max3);
else
return max1*max2*max3;
}
int main()
{
int a[]= {8,4,3,5,2,-1,-9,-10,11};
printf("%d\n",prod(a,9));
return 0;
}
if all numbers are +ve just find three max number (n+2logn ) comparison.
return their product.
if some numbers are negative then find find two minimum and 3 maximum number (n+4logn)
return product of
Max( product of two negative and one +ve or product of three + numbers)
start looking for the node whose value lie between given two node ....that node will be common ancestor
- NaiveCoder February 27, 2012If modification is allowed the reverse the half list accross to it's center and and check for the palindrome....
Other wise hashing will do if modification is not allowed
We have to store two traversal one of the following
1> inorder, preorder
2> inorder, postorder
If the right subtree is not null then find the min of right subtree.
Other wise start from root (since the parent pointer is not given (assumption)
find the first node who is the left child of it's parent and return the parent of that node.
if parent pointer is given then
if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do x ← y
y ← p[y]
return y
If modification is allowed the reverse the half list accross to it's center and and check for the palindrome....
Other wise hashing will do if modification is not allowed
If the right subtree is not null then find the min of right subtree.
Other wise start from root (since the parent pointer is not given (assumption)
find the first node who is the left child of it's parent and return the parent of that node.
if parent pointer is given then
if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do x ← y
y ← p[y]
return y
Print(char a[], int n, int open,int close,int i)
{
if(close==n)
{
print(a)
return;
}
if(close<open)
{
a[i]=")";
Print(a,n,open,close+1,i+1);
}
if(open<n)
{
a[i]="(";
Print(a,n,open+1,close,i+1);
}
}
thanks for pointing out
in the end of function you can add the statement
return -1;
Another recursive method... use inorder traversal
BST2DLL(node *root, List ** head,List **tail)
{
if(!root)
return Null;
//convert left subtree
BST2DLL(root->left,&head,&tail);
//add the root node to the list
if(!*last) // if this is the left most node
{
*head=root;
*last=*head;
}
else
{
*tail -> right=root;
root->left=*tail;
*tail=root;
}
BST2DLL(root->right,&head,&tail);
}
A recursive solution can be found
Use Kmp and keep track of no of occurrence
- NaiveCoder February 25, 2012Apply binary search with extra concern that check the right and left element.
int Bin(int a[],int i,int j)
{
if(i>j )
return -1;
mid=i+ (j-i)/2;
if(mid==0 && a[mid]==1)
return 0; //first element
if(mid>0)
if(a[mid]==1 && a[mid-1]==0 )
return mid;
if(a[mid]==0)
return bin(a,mid+1,j);
if(a[mid]==1)
return bin(a,i,mid-1);
}
Count the number of occurences of each letter in the input string [numA, numB, numC]
If two of these counts are 0, then return string.length
Else if (all counts are even) or (all counts are odd), then return 2
Else, then return 1
can be slightly modified the node of tree if yes then i will add a flag to each node
from first pointer move towards it's parent till root
while moving
set the flag value
now start moving from second pointer to it's parent while moving chek the flag value
if it's already set then return that value otherwise keep on moving towards root until u get a node with flag value has been set.
U don't have parent pointer....
- NaiveCoder May 01, 2012and u don't have extra space...