Question #1. Finding all leaders in a array. An element in array is called leader if all following elements are smaller than it.
Example: 10,5,6,4,9,5,4,3,2,1. 9 is a leader as all elements after 9 are less than it.
Approach I: Parse from last element (i=n;i>0;i--) to first element. If a[n] < a[n-1] then a[n] it is a leader. This will complete in O(N) time
Approach II: Follow the same bubble sort approach. O(N2)
Max Value in an Array. O(N) Time
using System;{
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MaxValue
class Program
{
static void Main(string[] args)
{
int[] numbers = new int[10] {100, 10, 5, 4, 20, 40, 90, 88, 99, 1 };
int currentmax = new int();
currentmax = numbers[0];
for(int i = 1; i < 10; i++)
{
if(currentmax < numbers[i])
currentmax = numbers[i];
}
Console.WriteLine("Max Value is " + currentmax);
Console.ReadLine();
}
}
}
Question #2, You have an Integer Array {1,2,3,4,5,6}. A function which accepts integer array and a number. You need to find atleast 2 possible combinations in the array which produce sum equal to the numberExample: For Array {1,2,3,4,5,6,7} and Number 8. The two possible pairs are {6,2}, {7,1}
Approach 1: Take every element in the array and sum it up with all elements in array and see does it equate to the number.
Example: 1+2, 1+3, 1+4....1+7...If its equal to 8 set it to flag = 1. Same do for next element 2...When flag is 2 (2 elements found) skip the loop. This is again O(N2)
Question#3, How to find whether a string is Palindrome without extra space
Example: LIRIL. This is a palindrome. Start comparision from N to 0 until half of length of message
int palflag = 0
for(i=0;j=strlen(message)-1; i< strlen(message)/2+1;i++,j--)
{
if(a[i]!= a[j])
{
palflag = 1
}
}
if palflag==0 then Palindrome
Yeah ! Time to relearn and refresh Data structures. Posting below working example and code....
/* C++ Program to Simulate Stack Operations - Program written using C Free 5.0*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 5
#define TRUE 1
#define FALSE 0
struct stack
{
int top;
int items[MAX];
};
/* Declare Functions */
int overflow(struct stack *);
int empty(struct stack *);
/* Add-push element to stack */
void push(struct stack *, int);
/* Remove-pop element from stack */
int pop(struct stack *);
/* Display elements in stack*/
void display(struct stack *);
int main()
{
int x, choice;
struct stack s1, *s;
s = &s1;
s->top= -1;
do
//loop to provide options on operations on stack
{
printf("\n 1.PUSH \n 2.POP \n 3.Display \n 4. EXIT \n");
printf("Enter your choice \n");
scanf("%d",&choice);
printf("Choice is %d\n", choice);
switch(choice)
{
case 1:
if(overflow(s))
{
printf("STACK OVERFLOW \n");
}
else
{
printf("Enter element to be pushed \n");
scanf("%d",&x);
printf("%d\n",x);
push(s,x);
}
break;
case 2:
if(empty(s))
printf("STACK UNDERFLOW \n");
else
printf("the popped element is %d", pop(s));
break;
case 3:
if(empty(s))
printf("STACK EMPTY\n");
else
display(s);
break;
case 4:
printf("EXITING \n");
exit(1);
default:printf("Enter 1,2,3 or 4 ONLY \n");
}
}while(choice!=4);
return 0;
}
/* check for overflow */
int overflow(struct stack *s)
{
printf("value of top variable is %d \n", s->top);
if(s->top ==(MAX-1))
return(TRUE);
else
return(FALSE);
}
/*check if stack is empty */
int empty(struct stack *s)
{
return((s->top==-1)?TRUE:FALSE);
}
/* pop element from stack */
int pop(struct stack *s)
{
return(s->items[(s->top)--]);
}
/* push an element into stack */
void push(struct stack *s, int x)
{
s->items[++(s->top)]=x;
printf("value of top variable is %d \n", s->top);
}
/* Display elements from stack */
void display(struct stack *s)
{
int i;
printf("The stack is \n");
for(i=s->top;i>=0;i--)
{
printf("Element is %d\n",s->items[i]);
printf("value of top variable is %d \n", s->top);
}
}
Running time of push and pop function is O(1)
#include<stdio.h>
#include<process.h>
#include<stdlib.h>
#include<conio.h>
#define QF 10
/* Program to demonstrate simple circular queue */
/* 0(1) or fixed amount of time for addition and deletion */
/*in order to insert and delete, rear and front are advanced one position clockwise*/
/* Method to check queue is full */
int qfull(int count)
{
return(count==QF-1)?1:0;
}
/* Check if queue is empty */
int qempty(int count)
{
return(count==0)?1:0;
}
/*Insert element at rear(last) position */
void insert_rear(int item, int *count, int *r, int *q)
{
if(qfull(*count))
{
printf("Queue is full \n");
return;
}
//Element assigned at last position
*r = (*r+1)%QF;
q[*r]=item;
(*count)++;
}
/* Delete element in front position of queue */
void delete_front(int *f, int *count, int *q)
{
if(qempty(*count))
{
printf("QEmpty\n");
return;
}
printf("Element deleted is %d \n",q[(*f)]);
(*f)=(*f+1)%QF;
(*count)--;
}
/*Display elements in the queue */
void display(int f, int count, int *q)
{
int i;
printf("In display loop f=%d, r=%d",f,count);
if(qempty(count))
{
printf("Q is Empty \n");
return;
}
printf("Contents of Queue are \n");
for(i=f;i<=count;i++)
{
printf("%d\n",q[i]);
}
}
int main()
{
int choice, f,r,q[10],item;
int count=0;
f=0;r=-1;
for(;;)
{
printf("\n 1.Insert in Front of Queue ");
printf("\n 2.Delete from Front of Queue ");
printf("\n 3.Display\n ");
printf("\n 4.Exit\n ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter element to be inserted\n");
scanf("%d",&item);
insert_rear(item,&count,&r,q);
break;
case 2:
delete_front(&f,&count,q);
break;
case 3:
display(f,count,q);
break;
case 4:
printf("EXITING \n");
exit(1);
default:printf("Enter 1,2,3,4 ONLY \n");
}
} return 0;
}
Merging two sorted Arrays. Wikipedia & algolist.net I referenced to explain examples for bubble, selection & O(N) optimized solution
#include<stdio.h>
int main()
{
int a[5]={90,100,190,300,1000};
int b[5]={10,80,380,390,1100};
int i=5;
int c[10];
int d[10];
int e[10];
int min, temp=0;
int k=0,l=0;
int iPos,iMin,j;
for(i=0;i<5;i++)
{
c[k]=a[i];
d[k]=a[i];
k++;
c[k]=b[i];
d[k]=b[i];
k++;
}
printf("Merged Array is \n");
for(i=0;i<10;i++)
{
printf("%d\n",c[i]);
}
/* Bubble Sort O(N2)*/
for (iPos = 0; iPos < 10; iPos++)
{
for (i = iPos+1; i < 10; i++)
{
if (c[iPos] > c[i])
{
temp = c[iPos];
c[iPos]=c[i];
c[i]=temp;
}
}
}
printf("Sorted Array -Bubble Sort is \n");
for(i=0;i<10;i++)
{
printf("%d\n",c[i]);
}
/* Selection Sort O(N2)*/
/*http://en.wikipedia.org/wiki/Selection_sort */
for (iPos = 0; iPos < 10; iPos++)
{
iMin = iPos;
for (i = iPos+1; i < 10; i++)
{
if (d[i] < d[iMin])
{
iMin = i;
}
}
temp = d[iPos];
d[iPos]=d[iMin];
d[iMin]=temp;
}
printf("Sorted Array -Selection Sort is \n");
for(i=0;i<10;i++)
{
printf("%d\n",d[i]);
}
/* O(N) Logic - http://www.algolist.net/Algorithms/Merge/Sorted_arrays */
/* int a[5]={90,100,190,300,1000};
int b[5]={10,80,380,390,1100};
*/
i = 0;
j = 0;
k = 0;
int m=5,n=5;
while (i < m && j < n)
{
if (a[i] <= b[j])
{
e[k] = a[i];
i++;
}
else
{
e[k] = b[j];
j++;
}
k++;
}
if (i < m)
{
for (int p = i; p < m; p++)
{
e[k] = a[p];
k++;
}
} else
{
for (int p = j; p < n; p++)
{
e[k] = b[p];
k++;
}
}
printf("Sorted Array - O(N) is \n");
for(i=0;i<10;i++)
{
printf("%d\n",e[i]);
}
}
/* Program to swap Pair of words */
#include<stdio.h>
#include<string.h>
int main()
{
char a[100]="abcdefgh";
int len = strlen(a);
printf("length of A is %d\n",len);
int i,j;
char c;
/* Input abcdefgh, output cdabghef */
for(i=0;i<len;i+=4)
{
c = a[i+2];
printf("%c\n",c);
a[i+2] = a[i]; //Assign 2 with 0
a[i] = c; //Assign 0 with 2
c = a[i+3];
printf("%c\n",c);
a[i+3] = a[i+1];//Assign 3 with 1
a[i+1]=c;//Assign 1 with 3
}
printf("Modified string is %s\n",a);
}
/* C Program - Longest Palindrome in given string O(N2) Solution*/
Program to calculate size of tree
Program to determine if two trees are identical
/* C Program - Longest Palindrome in given string O(N2) Solution*/
#include<stdio.h>
#include<string.h>
char s[100]="MaxLengthStringAAAAA";
int length;
int checkpalindrome(int, int);
int main()
{
length = strlen(s);
int i,j;
int count,currentcount;
int startpos, endpos;
count=0, currentcount=0;
printf("length is %d\n",length);
for(i=0;i<length;i++)
{
for(j=i+1;j<length;j++)
{
printf("i value is %d, j value is %d\n",i,j);
if(checkpalindrome(i,j))
{
currentcount = j-i;
if(currentcount > count)
{
count=currentcount;
startpos =i;
endpos = j;
}
}
}
}
printf("\nResult is Start %d, End is %d\n",startpos,endpos);
printf("Longest palindrome in a string Result \n");
for(i=startpos;i<=endpos;i++)
{
printf("%c",s[i]);
}
return 0;
}
int checkpalindrome(int start, int end)
{
int a,b;
int flag=1;
for(a=start,b=end;a<b;a++,b--)
{
printf("character at postion a is %c, b is %c\n",s[a],s[b]);
if(s[a]!=s[b])
{
flag=0;
break;
}
}
printf("Flag value is %d\n",flag);
return flag;
}
C Program convert Numbers into wordsProgram to calculate size of tree
Program to determine if two trees are identical
There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full round of the circle. Mileage of car is fixed
1: Choose any node to start;
2: Get fuel;
3: Go clockwise;
4: If fuel is over, go to 5, else go to 6:
5: Move your car clockwise to the next node;
6: Check if it is the start node;
7: If it isn’t, go to 2, else STOP;
Happy Reading!!
2: Get fuel;
3: Go clockwise;
4: If fuel is over, go to 5, else go to 6:
5: Move your car clockwise to the next node;
6: Check if it is the start node;
7: If it isn’t, go to 2, else STOP;
Happy Reading!!
No comments:
Post a Comment