nihaldps
BAN USER- 0of 0 votes
AnswersGiven a queue with functions as enqueue(), dequeue(), and findmax(). You can use these functions any time. The findmax() should return the largest value in the queue at that point. You can use auxiliary space.
- nihaldps in India
Implement the queue with given operations. Find the max value in the queue.| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Data Structures - 0of 0 votes
AnswersDelete a given node of a linked list, when you do not have info about the head or any other node.
- nihaldps in India
The prototype of the function is -
void delete (Struct node* x)
where x is any arbit node of a linked list.| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Linked Lists - 0of 0 votes
AnswersGiven a graph (consider it to be a mxn grid). The nodes are node of a binary tree with left and right pointers. The start point (A) is at the left upper corner and the end point (B) is at right bottom corner. Each node points to its adjacent nodes in the grid (the right pointer points to the node on the right and the left points to the node just below it). The nodes at the lower and right edges will have child as null (right null for the right side edge and left null for the bottom edge). The end node at B is having both as null.
- nihaldps in India
How many paths are possible which can lead you to B, if you start from A?| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Trees and Graphs
@ashish, you are right !!
#include "stdio.h"
#include<conio.h>
#define size 11
using namespace std;
int main()
{
int arr[size] = {1,9,8,4,0,0,2,7,0,6,7};
int cur = size-1,current;
for(int j=size; j>0;j--)
{ if(arr[j]==0)
{
current=j;
break;
}}
int copyPos = current;
while( current >= 0 ){
if( arr[current] != 0 && current != copyPos )
{
arr[copyPos] = arr[current];
--copyPos;
}
--current;
}
while( copyPos >= 0 )
{
arr[copyPos] = 0;
--copyPos;
}
for(int i=0;i<size;i++)
printf("%d",arr[i]);
getch();
return 0;
}
#include "stdio.h"
#include<conio.h>
using namespace std;
int main()
{
int arr[6] = {4,15,6,0,2,3};
int max=0,smax=0;
for(int i= 0;i<6;i++)
{
if(arr[i]>max)
{
smax=max;
max=arr[i];
}
else if(arr[i]>smax)
{
smax=arr[i];
}
}
printf("\n%d\n",smax);
getch();
return 0;
}
The code that works !!!!
#include "stdio.h"
#include<conio.h>
#define ROW 4
#define COL 4
using namespace std;
void searchfrom2d(int a[4][4], int num)
{
int j=COL-1;int i=0;int done =0;
while(i<ROW && j>0)
{
if(a[i][j]<num)
i++;
else j--;
if(a[i][j]==num)
{
done =1;
printf("num is in row-%d and in col-%d\n",i+1,j+1); }
}
if(done==0)
printf("not found");
}
int main()
{
int arr[ROW][COL] = {
{1,3,5,6},
{2,4,7,8},
{9,10,12,14},
{11,13,15,16},
};
searchfrom2d(arr,15);
getch();
return 0;
}
one can do an insertion sort kind of thing. The following code does the sorting of 0 and non-0 elements.
#include "stdio.h"
#include<conio.h>
using namespace std;
void sortarrayinorder(int arr[],int size)
{
int i,j,tem,k;
for(i=1;i<size;i++)
{
for(j=0;j<i;j++)
{
if(arr[j]!=0 && arr[i]==0)
{
tem=arr[j];
arr[j]=arr[i];
for(k =i;k>j;k--)
arr[k]=arr[k-1];
arr[k+1]=tem;
}
}
}
}
int main ()
{
int arr[7] = {2,0,3,0,1,0,6};
sortarrayinorder(arr,7);
for(int t=0;t<7;t++)
printf("%d ",arr[t]);
getch();
return 0;
}
This code handles everything one wants.
#include <stdio.h>
#include<conio.h>
using namespace std;
void convert(char *s) {
char *p = s;
char *q = s;
int c,n;char ch;
int counter;
while (*p) {
ch = *p;
counter = 0;
while (*p && *p == ch)
{
p++;
counter++;
}
*q++ = ch;
c = counter;
n = 0;
do
{
c /= 10;
n++;
} while (c != 0);
for (c = 0; c < n; c++)
{
q[n - 1 - c] = counter % 10 + '0';
counter /= 10;
}
q += n;
}
*q = '\0';
}
int main(void)
{
char s[] = "aaaabbbbcccccccccccdddddddddddd";
printf("%s -> ", s);
convert(s);
printf("%s\n", s);
getchar();
return 0;
}
Here is a working code in C. The complexity is of O(n).
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#define COL 4
#define ROW 4
using namespace std;
int main()
{
int arr[ROW][COL]= {
{1,1,1,1},
{1,1,0,0},
{1,0,0,0},
{1,1,0,0},
};
int rownum;
int i = 0, j = COL-1;
while(i<ROW && j>0)
{
if(arr[i][j]==0)
{
j--;
rownum=i;}
else
i++;
}
printf("%d",rownum);
getch();
return 0;
}
- nihaldps February 29, 2012but when you implement such functionality using another queue, you will not get max value all the time. With stack it works properly.
for example take queue data - 2 7 5 13 7 and maxqueue will have - 2 7 7 13 13. When you dequeue both queues for getting max value - the last values of the both queues will have end values as 7 and 13 resp. There is the issue.
If complexity is not to be worried about, the following code works for the given question(for all cases).
#include<stdio.h>
#include<string.h>
void searchithoccur(char *pat, char *txt, int location)
{
int m = strlen(pat); int n = strlen(txt);
int array[9];
int count = 0; bool found=0;
for (int i = 0; i <= n-m; i++)
{
int j;
for (j = 0; j < m; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == m)
{
array[count]=i;
count++; found = 1;
}
}
if(found==1 && location<count+1) //checking if ith occurrence is there in the text string
found =1;
else found=0;
if(found==1)
printf("for the ith occurrence where i= %d, pattern found at position %d of the text\n",location, array[location-1]);
else if(found==0 ||location>count )
printf("the i=%d occurrence of pattern not found in the text", location);
}
int main()
{
char *text = "abdabcsbbabcsabcbasbbabcbsdabasbabcbsb";
char *pattern = "abc";
int location=2; //ith occurrence of the pattern
searchithoccur(pattern, text, location);
getchar();
return 0;
}
Reverse the both lists and then send them as argument of the below function. Again reverse the list for the final result. The function handles every case.
struct node* addTwoLists (struct node* first, struct node* second)
{
struct node* res = NULL;
struct node *temp, *prev = NULL;
int carry = 0, sum;
while (first != NULL || second != NULL) //while both lists exist
{
sum = carry + (first? first->data: 0) + (second? second->data: 0);
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
temp = newNode(sum);
if(res == NULL)
res = temp;
else
prev->next = temp;
prev = temp;
if (first) first = first->next;
if (second) second = second->next;
}
if (carry > 0) // when additional carry generated, make a new node with data as carry value.
temp->next = newNode(carry);
return res;
}
struct node *newNode(int data)
{
struct node *new_node = (struct node *) malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
simple code for the second largest value.
#include "stdio.h"
#include<conio.h>
using namespace std;
int main()
{
int a[10] = { 11, 2, 9, 13, 33, 25, 17, 1, 90, 3 } ;
int fmax = 0; int smax = 0;
for(int i=0; i<10;i++)
{
if(a[i]>fmax)
{
smax=fmax;
fmax=a[i];
}
else if (smax<a[i])
smax = a[i];
}
printf("%d, %d", fmax, smax);
getch();
return 0;
}
using quicksort for finding nth largest value.
Here is a working c code
#include "stdio.h"
#include<conio.h>
using namespace std;
int quicksort ( int *, int, int, int ) ;
int split ( int*, int, int ) ;
int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
int nth = 5; //finding 5th largest value
int num = quicksort ( arr, 0, 9, nth-1 ) ;
printf ( "%d\t", num ) ;
getch();
return 0;
}
int quicksort ( int a[ ], int lower, int upper, int nth)
{
int i ;
if ( upper > lower && i !=nth )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1, nth ) ;
quicksort ( a, i + 1, upper,nth ) ;
}
return a[nth];
}
int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;
p = lower + 1 ;
q = upper ;
i = a[lower] ;
while ( q >= p )
{
while ( a[p] < i )
p++ ;
while ( a[q] > i )
q-- ;
if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}
t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;
return q ;
}
working c code -
#include <stdio.h>
#include<conio.h>
using namespace std;
void increaseby1(int[], int);
int main()
{
int a[4]={9,9,9,9};
increaseby1(a, 4);
getch();
return 0;
}
void increaseby1(int a[], int n)
{
int i;
int carry=1;
for(i=n-1; i>=0;i--)
{
a[i]=a[i]+carry;
if(a[i] >= 10)
{
carry = 1;
a[i] = a[i] % 10;
}
else
carry = 0;
}
if(carry == 0) // no need to make any extra space for case as 2789
{
for(i=0; i<n; i++)
printf("%d", a[i]);
}
else //make extra space for case as 9999
{
int result[n+1];
result[0]=1;
for(i=1;i<n+1;i++)
{
result[i]= a[i-1];
}
for(i=0; i<n+1; i++)
printf("%d", result[i]);
}
}
Morris algorithm -
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
}
}
}
}
In a normal level order traversal you call the recursive function traverse() from inside a for loop in some other function, say, calltraversal() - which runs h times (height of the tree).
So in the spiral (zig-zag) manner traversal you have to just flip the pattern of traversing every time you are calling the function from the for loop. It can be done by providing a bool value in the argument, the value is 0 in one call, and then 1 in the next.
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
bool value = 0;
for(i=1; i<=h; i++)
{
printGivenLevel(root, i, value );
value = ~value ;
}
}
void printGivenLevel(struct node* root, int level, int value )
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
if(value)
{
printGivenLevel(root->left, level-1, value );
printGivenLevel(root->right, level-1, value );
}
else
{
printGivenLevel(root->right, level-1, value );
printGivenLevel(root->left, level-1, value );
}
}
}
The code that works !!! Time complexity- 0(n).
- nihaldps March 11, 2012