Programs Questions and Answers
Question :: 81
Write a program to find the largest substring of a given string without repeating characters.
Input : NA
Output : NA
Answer In:
C
C++
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; /*lenght of current substring*/
int max_len = 1; /* result*/
int prev_index; /* previous index*/
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
visited[str[0]] = 0;
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
else
{
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
int min(int a, int b)
{
return (a>b)?b:a;
}
int main()
{
char str[] = "ABDEFGABEF";
cout<<"The input string is" <<str;
int len = longestUniqueSubsttr(str);
cout<<"The length of the longest non-repeating "
"character substring is "<<len;
return 0;
}
Tags:Aricent
Question :: 82
Write a program to reverse the bits in an integer.
Input : NA
Output : NA
Answer In:
C
C++
#include <stdio.h>
#include <iostream>
using namespace std;
/* Iterative function to reverse digits of num*/
int reversDigits(int num)
{
int rev_num = 0;
while(num > 0)
{
rev_num = rev_num*10 + num%10;
num = num/10;
}
return rev_num;
}
/*Driver program to test reversDigits*/
int main()
{
int num = 4562;
cout<<"Reverse of no. is"<< reversDigits(num);
getchar();
return 0;
}
Tags:Aricent
Question :: 83
Write code to find the largest substring of a given string without repeating characters.
Input : NA
Output : NA
Answer In:
C
C++
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; /* lenght of current substring*/
int max_len = 1; /* result*/
int prev_index; /* previous index*/
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
visited[str[0]] = 0;
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
else
{
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
int min(int a, int b)
{
return (a>b)?b:a;
}
int main()
{
char str[] = "ABDEFGABEF";
cout<<"The input string is" <<str;
int len = longestUniqueSubsttr(str);
cout<<"The length of the longest non-repeating "
"character substring is "<<len;
return 0;
}
Tags:Aricent
Question :: 84
Given a number, find the next smallest palindrome
Input : NA
Output : NA
Answer In:
C
C++
#include <stdio.h>
#include <iostream>
using namespace std;
void printArray (int arr[], int n);
int AreAll9s (int num[], int n );
void generateNextPalindromeUtil (int num[], int n ){
int mid = n/2;
bool leftsmaller = false;
int i = mid - 1;
int j = (n % 2)? mid + 1 : mid;
while (i >= 0 && num[i] == num[j])
i--,j++;
if ( i < 0 || num[i] < num[j])
leftsmaller = true;
while (i >= 0)
{
num[j] = num[i];
j++;
i--;
}
if (leftsmaller == true)
{
int carry = 1;
i = mid - 1;
if (n%2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else
j = mid;
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--];
}
}
}
void generateNextPalindrome( int num[], int n )
{
int i;
cout<< "Next palindrome is:";
if( AreAll9s( num, n ) )
{
cout<< "1 ";
for( i = 1; i < n; i++ )
cout<< "0 " ;
cout<< "1" ;
}
else
{
generateNextPalindromeUtil ( num, n );
printArray (num, n);
}
}
int AreAll9s( int* num, int n )
{
int i;
for( i = 0; i < n; ++i )
if( num[i] != 9 )
return 0;
return 1;
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
cout<< arr[i]);
cout<< "\n";
}
int main()
{
int num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
int n = sizeof (num)/ sizeof(num[0]);
generateNextPalindrome( num, n );
return 0;
}
Tags:Aricent
Question :: 85
Given a pattern and a text, write a program to check whether the pattern is present in the text
Input : NA
Output : NA
Answer In:
C
C++
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int i,j,temp;
char str[100]={"This is a pattern matching"};
char substr[20]={"pattern"};
for(i=0;str[i]!='\0';i++)
{
j=0;
if(str[i]==substr[j])
{
temp=i+1;
while(str[i]==substr[j])
{
i++;
j++;
}
if(substr[j]=='\0')
{
cout<<"The substring is present in given string at position "<<temp<<"\n";
exit(0);
}
else
{
i=temp;
temp=0;
}
}
}
if(temp==0)
cout<<"The substring is not present in given string\n";
return 0;
}
Tags:Aricent
Question :: 86
Write a program to find the next smallest palindromic number after k.
Input : NA
Output : NA
Answer In:
C
C++
#include <stdio.h>
#include <iostream>
using namespace std;
void printArray (int arr[], int n);
int AreAll9s (int num[], int n );
void generateNextPalindromeUtil (int num[], int n )
{
int mid = n/2;
bool leftsmaller = false;
int i = mid - 1;
int j = (n % 2)? mid + 1 : mid;
while (i >= 0 && num[i] == num[j])
i--,j++;
if ( i < 0 || num[i] < num[j])
leftsmaller = true;
while (i >= 0)
{
num[j] = num[i];
j++;
i--;
}
if (leftsmaller == true)
{
int carry = 1;
i = mid - 1;
if (n%2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else
j = mid;
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--]; // copy mirror to right
}
}
}
void generateNextPalindrome( int num[], int n )
{
int i;
cout<<"Next palindrome is:";
if( AreAll9s( num, n ) )
{
printf( "1 ");
for( i = 1; i < n; i++ )
cout<<"0 ";
cout<<"1" ;
}
else
{
generateNextPalindromeUtil ( num, n );
printArray (num, n);
}
}
int AreAll9s( int* num, int n )
{
int i;
for( i = 0; i < n; ++i )
if( num[i] != 9 )
return 0;
return 1;
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
cout<<arr[i];
cout<<"\n";
}
int main()
{
int num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};
int n = sizeof (num)/ sizeof(num[0]);
generateNextPalindrome( num, n );
return 0;
}
Tags:Aricent
Question :: 87
Write a program to sort an array containing only 0's and 1's in random order.
Input : 1 0 1 1 0 1 0 1 0 0 0 1 0 1
Output : 1 1 1 1 1 1 1 0 0 0 0 0 0 0
Answer In:
C
C++
#include<stdio.h>
#include <iostream>
using namespace std;
void segregate0and1(int arr[], int size)
{
int left = 0, right = size-1;
while (left < right)
{
while (arr[left] == 0 && left < right)
left++;
while (arr[right] == 1 && left < right)
right--;
if (left < right)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
int main()
{
int arr[] = {0, 1, 0, 1, 1, 1};
int i, arr_size = sizeof(arr)/sizeof(arr[0]);
segregate0and1(arr, arr_size);
cout<<"Array after segregation ";
for (i = 0; i < 6; i++)
cout<< arr[i];
getchar();
return 0;
}
Tags:Aricent
Question :: 88
Write a push() and pop() implementation using linked list in C.
Input : NA
Output : NA
Answer In:
C
C++
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
void push(int data);
void pop();
void create();
int count = 0;
void main()
{
int no, ch, e;
cout<<"\n 1 - Push";
cout<<"\n 2 - Pop";
create();
while (1)
{
cout<<"\n Enter choice : ";
cin>>ch;
switch (ch)
{
case 1:
cout<<"Enter data : ";
cin>>no;
push(no);
break;
case 2:
pop();
break;
default :
cout<<" Wrong choice, Please enter correct choice ";
break;
}
}
}
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
Tags:PEOL
Question :: 89
Explain Rat in a Maze problem. What data structure you will use. Can you Write code for it.
Input : NA
Output : NA
Answer In:
C
C++
#include <iostream>
#include<stdio.h>
#define N 4
using namespace std;
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout<<sol[i][j];
cout<<"\n";
}
}
bool isSafe(int maze[N][N], int x, int y)
{
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
else
return false;
}
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(solveMazeUtil(maze, 0, 0, sol) == false)
{
cout<<"Solution doesn't exist";
return false;
}
printSolution(sol);
return true;
}
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
if(isSafe(maze, x, y) == true)
{
sol[x][y] = 1;
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
sol[x][y] = 0;
return false;
}
return false;
}
/* driver program to test above function*/
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
solveMaze(maze);
return 0;
}
Tags:No Tags on this question yet!
Question :: 90
Write a recursive function to find the factorial of a number.
Input : NA
Output : NA
Answer In:
C
C++
#include<iostream>
using namespace std;
int factorial(int n);
int main()
{
int n;
cout << "Enter a positive integer: ";
cin >> n;
cout << "Factorial of " << n << " = " << factorial(n);
return 0;
}
int factorial(int n)
{
if(n > 1)
return n * factorial(n - 1);
else
return 1;
}
Tags:PEOL
