1. Implement merge, quick, insertion, selection, bubble sorts.
Merge Sort
#include<iostream>
2. Using the phone keypad return all possible words that can be produced given input digits. e.g. 23 > “ad, ae, af, bd, be, bf, cd, ce, cf”
3. Given a input number in array form. Push all the zeroes to the end maintaining the order of rest of elements.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
main(){
int n,i,j=0,k=0,a1[100],h[100],*p1,*p2;
cin>>n; // size of array
for(i=0;i<n;i++){
cin>>a1[i];
if(a1[i]==0){
k++;
}
}
p1=&a1[0];
for(j=0,i=0;i<n;i++){
if(a1[i]==0){
p1++;
}
else{
a1[j]=*p1;
p1++;
j++;
}
}
for(i=j-1;i<n;i++){
a1[i]=0;
}
cout<<"\n";
for(i=0;i<n;i++){
cout<<a1[i]<<"\t";
}
}
4. Given a number find next palindrome number. e.g. 119 > 121
#include<iostream>
using namespace std;
bool palindrome(int n){
int arr[100],temp=n,i=0;
while(temp>0){
arr[i]=temp%10;
temp=temp/10;
i++;
}
int s=0,r=i-1;
while(s<r){
if(arr[s]!=arr[r]){
return false;
}
s=s+1;
r=r-1;
}
return true;
}
main(){
int n,t=1;
cin>>n ;
n=n+1;
while(t){
if(palindrome(n)==true){
t=0;
}
else{
n++;
}
}
cout<<"Next No which is palindrome is = "<<n;
}
5. A sorted array has been rotated by some number k in clockwise direction. How can we find k efficiently.
#include<iostream>
using namespace std;
int count(int arr[],int end){
int i=end;
while(end>=0){
if(arr[end]<arr[end-1]){
return end;
}
end--;
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
int x =count(arr,n-1);
cout<<"\narray is rotated "<<x<<" times";
}
6. You are given with an array containing only 0’s and 1’s. Write a function to sort this array. Find a solution which scans the array only once.
#include<iostream>
using namespace std;
void diffSort(int arr[], int startIndex, int endIndex){
int pindex=startIndex;
for(int i=startIndex;i<=endIndex;i++){
if(arr[i]==0){
swap(arr[pindex],arr[i]);
pindex++;
}
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
7. What if the array has 0’s, 1’s and 2’s. Find another solution which scans the array only once.
#include<iostream>
using namespace std;
int hash[1000];
void diffSort(int arr[], int startIndex, int endIndex){
for(int i=0;i<1000;i++){
hash[i]=0;
}
for(int i=startIndex;i<=endIndex;i++){
hash[arr[i]]=hash[arr[i]]++;
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<hash[0];i++){
arr[i]=0;
cout<<arr[i]<<"\t";
}
for(j=0;j<hash[1];j++){
arr[j+i]=1;
cout<<arr[j+i]<<"\t";
}
for(k=0;k<hash[2];k++){
arr[j+i+k]=2;
cout<<arr[j+i+k]<<"\t";
}
}
8. Reverse a string keeping the words intact. e.g. Welcome to Coding Blocks > Blocks Coding to Welcome.
9. Print all substrings of a string.
10.Print all subsequences of a String
11.Print all permutations of a String
12.Given an array find all subsets of A which sum to K.
#include<iostream>
using namespace std;
void subset(int arr[],int temp[],int index,int subindex,int len,int sum){
if(index==len){
int t =0;
for(int i=0;i<=subindex;i++){
t=t+temp[i];
}
if(t==sum){
cout << "{ ";
for(int i=0;i<=subindex;i++){
cout << temp[i] << ", ";
}
cout<<" }\n";
}
return;
}
temp[subindex+1]=arr[index];
subset(arr,temp,index+1,subindex+1,len,sum);
subset(arr,temp,index+1,subindex,len,sum);
}
main(){
int n,sum;
int arr[100],temp[100];
cin >> n; //size of array
cin>>sum; //sum of subset
for (int i = 0; i < n ; i++) {
cin >> arr[i];
}
subset(arr,temp,0,-1,n,sum);
}
Merge Sort
#include<iostream>
using namespace std;
int temp[1000];
void merge(int a[],int startIndex,int endIndex){
int mid=(startIndex+endIndex)/2;
int i,j,k;
i=startIndex;j=mid+1;k=0;
while(i<=mid&&j<=endIndex){
if(a[i]<a[j]){
temp[k]=a[i]; i++;k++;
}
else{
temp[k]=a[j]; j++;k++;
}
}
while(i<=mid){
temp[k]=a[i]; i++;k++;
}
while(j<=endIndex){
temp[k]=a[j]; j++;k++;
}
}
void mergesort(int a[],int startIndex,int endIndex){
if(startIndex<endIndex){
int mid=(startIndex + endIndex)/2;
mergesort(a,startIndex,mid);
mergesort(a,mid+1,endIndex);
merge(a,startIndex,endIndex);
}
}
main(){
int arr[100], n;
cin >> n;
for (int i = 0 ; i < n; i++) {
cin >> arr[i];
}
mergesort(arr,0,n-1);
cout <<"\n";
for (int i = 0 ; i < n; i++) {
cout << temp[i]<<"\t";
}
}
quick Sort
#include<iostream>
using namespace std;
int partion(int arr[],int startIndex,int endIndex){
int pindex=startIndex+1;
int pivot=arr[startIndex];
int i;
for(i=startIndex+1;i<=endIndex;i++){
if(pivot>arr[i]){
swap(arr[i],arr[pindex]);
pindex++;
}
}
swap(arr[startIndex],arr[pindex-1]);
return pindex-1;
}
void quicksort(int arr[],int startIndex,int endIndex ){
if(startIndex>=endIndex){
return;
}
int x= partion(arr,startIndex,endIndex);
quicksort(arr,startIndex,x);
quicksort(arr,x+1,endIndex);
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
quicksort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
Selection Sort
#include<iostream>
using namespace std;
void selectionSort(int arr[],int startIndex, int endIndex){
int temp=arr[0];
for(int i=0;i<=endIndex;i++){
int minIndex=i;
for(int j=i+1;j<=endIndex;j++){
if(arr[minIndex]>arr[j]){
minIndex=j;
}
}
swap(arr[i],arr[minIndex]);
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
selectionSort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
Insertion Sort
#include<iostream>
using namespace std;
void shift(int arr[],int start,int hole){
int temp;
for(int i=hole;i>start;i--){
arr[i]=arr[i-1];
}
}
void insertionsort(int arr[],int endIndex){
int temp=0;
for(int i=1;i<=endIndex;i++){
int temp=arr[i];
int j=i-1;
while(arr[i]<arr[j]&&j>=0){
j--;
}
if(j==-1){
shift(arr,0,i);
arr[0]=temp;
}
else{
shift(arr,j+1,i);
arr[j+1]=temp;
}
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
insertionsort(arr,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
3. Given a input number in array form. Push all the zeroes to the end maintaining the order of rest of elements.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
main(){
int n,i,j=0,k=0,a1[100],h[100],*p1,*p2;
cin>>n; // size of array
for(i=0;i<n;i++){
cin>>a1[i];
if(a1[i]==0){
k++;
}
}
p1=&a1[0];
for(j=0,i=0;i<n;i++){
if(a1[i]==0){
p1++;
}
else{
a1[j]=*p1;
p1++;
j++;
}
}
for(i=j-1;i<n;i++){
a1[i]=0;
}
cout<<"\n";
for(i=0;i<n;i++){
cout<<a1[i]<<"\t";
}
}
4. Given a number find next palindrome number. e.g. 119 > 121
#include<iostream>
using namespace std;
bool palindrome(int n){
int arr[100],temp=n,i=0;
while(temp>0){
arr[i]=temp%10;
temp=temp/10;
i++;
}
int s=0,r=i-1;
while(s<r){
if(arr[s]!=arr[r]){
return false;
}
s=s+1;
r=r-1;
}
return true;
}
main(){
int n,t=1;
cin>>n ;
n=n+1;
while(t){
if(palindrome(n)==true){
t=0;
}
else{
n++;
}
}
cout<<"Next No which is palindrome is = "<<n;
}
5. A sorted array has been rotated by some number k in clockwise direction. How can we find k efficiently.
#include<iostream>
using namespace std;
int count(int arr[],int end){
int i=end;
while(end>=0){
if(arr[end]<arr[end-1]){
return end;
}
end--;
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
int x =count(arr,n-1);
cout<<"\narray is rotated "<<x<<" times";
}
#include<iostream>
using namespace std;
void diffSort(int arr[], int startIndex, int endIndex){
int pindex=startIndex;
for(int i=startIndex;i<=endIndex;i++){
if(arr[i]==0){
swap(arr[pindex],arr[i]);
pindex++;
}
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
7. What if the array has 0’s, 1’s and 2’s. Find another solution which scans the array only once.
#include<iostream>
using namespace std;
int hash[1000];
void diffSort(int arr[], int startIndex, int endIndex){
for(int i=0;i<1000;i++){
hash[i]=0;
}
for(int i=startIndex;i<=endIndex;i++){
hash[arr[i]]=hash[arr[i]]++;
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
diffSort(arr,0,n-1);
for(i=0;i<hash[0];i++){
arr[i]=0;
cout<<arr[i]<<"\t";
}
for(j=0;j<hash[1];j++){
arr[j+i]=1;
cout<<arr[j+i]<<"\t";
}
for(k=0;k<hash[2];k++){
arr[j+i+k]=2;
cout<<arr[j+i+k]<<"\t";
}
}
8. Reverse a string keeping the words intact. e.g. Welcome to Coding Blocks > Blocks Coding to Welcome.
9. Print all substrings of a string.
10.Print all subsequences of a String
11.Print all permutations of a String
12.Given an array find all subsets of A which sum to K.
#include<iostream>
using namespace std;
void subset(int arr[],int temp[],int index,int subindex,int len,int sum){
if(index==len){
int t =0;
for(int i=0;i<=subindex;i++){
t=t+temp[i];
}
if(t==sum){
cout << "{ ";
for(int i=0;i<=subindex;i++){
cout << temp[i] << ", ";
}
cout<<" }\n";
}
return;
}
temp[subindex+1]=arr[index];
subset(arr,temp,index+1,subindex+1,len,sum);
subset(arr,temp,index+1,subindex,len,sum);
}
main(){
int n,sum;
int arr[100],temp[100];
cin >> n; //size of array
cin>>sum; //sum of subset
for (int i = 0; i < n ; i++) {
cin >> arr[i];
}
subset(arr,temp,0,-1,n,sum);
}
No comments:
Post a Comment