## 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.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

U don't have parent pointer....

- NaiveCoder May 01, 2012and u don't have extra space...