Implementing Circular Queue in C

Not full working code, but you get the idea
elements are inserted clockwise, deleted clockwise.

Basic conditions :
If rear is one position to the left of front --> queue is empty
If rear is two positions to the left of front --> queue is full

So the array of size n holds only n-1 elements at a time, so as to differentiate queue-empty and queue-full scenarios.

---------------------------------------------------------------------------------------------

front = 0;
rear = n - 1;
int A[n];

void enqueue(int elem){
if((rear+front+2)%n == 0){
printf("Queue is full");
return;
}
rear = (rear+1)%n;
A[rear] = elem;
}

int dequeue(){
if((front-rear+n)%n == 1){
printf("Queue is empty");
return;
}
int temp = A[front];
front = (front+1)%n;
return temp;
}

Implementation of Heap Sort

#include<stdio.h>

#define LEFT(i) 2*i+1
#define RIGHT(i) 2*i+2

void maxHeapify(int a[],int p,int len){
int max = p;
int temp;
if(LEFT(p) < len && a[LEFT(p)] > a[p]){
max = LEFT(p);
}
if(RIGHT(p) < len && a[RIGHT(p)] > a[max]){
max = RIGHT(p);
}
if(max != p){
temp = a[max];
a[max] = a[p];
a[p] = temp;
maxHeapify(a,max,len);
}
}

void buildHeap(int a[],int len){
int i;
for(i=(len-2)/2;i>=0;i--){
maxHeapify(a,i,len);
}
}

void heapSort(int a[],int len){
buildHeap(a,len);
int i,temp;
int heapLen = len;
for(i=0;i<len;i++){
temp = a[0];
a[0] = a[heapLen-1];
a[heapLen-1] = temp;
heapLen--;
maxHeapify(a,0,heapLen);
}
}

void printSorted(int a[],int len){
int i;
for(i=0;i<len;i++){
printf("%d\t",a[i]);
}
}

int main(){
int a[] = {9,8,7,6,5,4,3,2,1};
int len = sizeof(a)/sizeof(a[0]);
heapSort(a,len);
printSorted(a,len);
return 0;
}

All numbers are present 3 times except one number which is there only once. Find that number.

#include<stdio.h>

int findUnique(int a[],int len){
int i,j;
int x=0;
int y;
int fact = 1;
for(i=0;i<32;i++){
y = 0;
for(j=0;j<len;j++){
y += a[j] & (1<<i);
}
x += fact * (y%3);
fact *= 2;
}
return x;
}

int main(){
int a[] = {1,2,3,2,3,4,3,1,1,2};
int n = findUnique(a,sizeof(a)/sizeof(a[0]));
printf("%d",n);
return 0;
}

Amazon 1st round Telephonic Interview

1) Tell me about yourself

2) How to tell if you a binary representation of a decimal unsigned number has all 1's ?

3) Given an integer array, randomize it.

4) In C++ when do you use virtual destructor ?

5) Loop through numbers from 1 to 100 and if the number is divisible by 3, print FIZZ , If it is divisible by 5, print BUZZ, If it is divisible by 15 print FIZZBUZZ and for all other numbers just print the number itself.

Given an integer array, Find pairs of numbers which sum to a specified value

//OUTPUT : found elements 7 and 8
//         found elements 6 and 9

#include<iostream>
#include<set>

using namespace std;

int main(){
int a[] = {3,6,2,7,8,9,2,0,1,6};
int n = 15;
set<int> s;
int i;
set<int>::iterator it;
int len = sizeof(a)/sizeof(int);
for(i=0;i<len;i++){
it = s.find(n-a[i]);
if(it != s.end()){
cout<<"found elements "<<*it<<" and "<<a[i]<<endl;
} else {
s.insert(a[i]);
}
}
return 0;
}

3 SUM problem - O(n^2)

// Array is assumed to be sorted. If unsorted , sort it in O(nlogn)
// OUTPUT : -10 2 8

#include<stdio.h>

void threeSum(int arr[],int n){
int i=0;
int a,b,c,j,sum;
int k = n-1;
while(i<k-1){
a = arr[i];
c = arr[k];
for(j=i+1;j<k;j++){
b = arr[j];
sum = a+b+c;
if(sum == 0){
printf("%d %d %d",a,b,c);
return;
}
}
if(sum < 0){
i = i+1;
} else {
k = k-1;
}
}
}

int main(){
int arr[] = {-25,-10,-7,-3,2,4,8,10};
threeSum(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}

Rat in a maze - Backtracking method

#include<stdio.h>
#define ROW 4
#define COL 4

int findpath(int maze[ROW][COL],int path[ROW][COL],int i,int j){
static int found = 0;
if(i==ROW-1 && j==COL-1){
path[i][j] = 1;
found = 1;
return 1;
} else {
if(i<ROW && j<COL &&!found && (maze[i][j] == 1)){
path[i][j] = 1;
if(!findpath(maze,path,i+1,j) && !findpath(maze,path,i,j+1)){
path[i][j] = 0;
}
} else {
return 0;
}
}
}

int main(){
int maze[ROW][COL] = {{1,0,0,0},
                              {1,1,0,1},
                              {0,1,1,1},
                              {1,1,0,1}};
int path[ROW][COL] = {{0,0,0,0},
      {0,0,0,0},
      {0,0,0,0},
      {0,0,0,0}};
int i,j;
findpath(maze,path,0,0);
for(i=0;i<ROW;i++){
for(j=0;j<COL;j++){
printf("%d\t",path[i][j]);
}
printf("\n");
}
return 0;
}

First non-repeated character in a string

//INPUT: ramukhsemar
//OUTPUT: first non repeated character = u

#include<stdio.h>

char firstnonrep(char c[]){
int l = strlen(c);
int i;
static int a[256];
for(i=0;i<l;i++){
a[c[i]]++;
}
for(i=0;i<l;i++){
if(a[c[i]] == 1){
return c[i];
}
}
}

int main(){
char c[] = "ramukhsemar";
char p = firstnonrep(c);
printf("first non repeated character = %c",p);
return 0;
}

Find an element in a sorted array which is rotated.

//INPUT : {6,7,8,0,1,2,3,4,5}
//OUTPUT : number found at index 7

#include<stdio.h>

int bsearch(int a[],int low,int high,int n){
if(high-low <=1){
if(a[low] == n) return low;
else if(a[high] == n) return high;
else return -1;
}
int mid = (low+high)/2;
if(a[mid] > a[low]){
if(n>=a[low] && n<=a[mid]){
return bsearch(a,low,mid,n);
} else {
return bsearch(a,mid+1,high,n);
}
} else {
if(n>=a[mid] && n<=a[high]){
return bsearch(a,mid,high,n);
} else {
return bsearch(a,low,mid-1,n);
}
}
}

int main(){
int a[] = {6,7,8,0,1,2,3,4,5};
int i = bsearch(a,0,sizeof(a)/sizeof(a[0])-1,4);
if(i==-1){
printf("number not found!!");
} else {
printf("number found at index %d",i);
}
return 0;
}

Longest Increasing Subsequence

// INPUT = {5,8,0,3,1,9,2,4}
// OUTPUT - Length of LIS = 4 {0,1,2,4} //prints only length
// Complexity - O(n^2)
// If anyone knows about the O(nlogn) solution, feel free to
// mention it in comments section

#include<stdio.h>
#include<stdlib.h>

int maxL(int *L,int i,int a[]){
int max = 0;
int j;
for(j=0;j<i;j++){
if(a[j] < a[i] && L[j] > max){
max = L[j];
}
}
return max;
}

int lis(int a[],int n){
int *L = (int *)malloc(sizeof(int)*n);
int i;
int lis = 1;
for(i=0;i<n;i++){
L[i] = maxL(L,i,a)+1;
}
for(i=0;i<n;i++){
if(L[i] > lis){
lis = L[i];
}
}
return lis;
}

int main(){
int a[] = {5,8,0,3,1,9,2,4};
int l = lis(a,sizeof(a)/sizeof(int));
printf("length of LIS = %d",l);
return 0;
}

Reversing words in a String

//INPUT : hello the world
// OUTPUT : world the hello

#include<stdio.h>

void reverse(char *str,int i,int j){
char temp;
while(i<j){
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}

void reverseWords(char *str){
int len = strlen(str);
int start,end;
int i=0;
reverse(str,0,len-1);
while(str[i] != '\0'){
if(str[i] == ' '){
i++;
continue;
} else{
start = i;
while(str[i] != '\0' && str[i] != ' '){
i++;
}
end = i-1;
reverse(str,start,end);
}
}
}

int main(){
char str[] = "hello the world";
reverseWords(str);
printf("%s",str);
return 0;
}

Printing N X N matrix in spiral order

// OUTPUT : 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

#include<stdio.h>
#define MAX 5

void printSpiral(int a[][MAX],int n){
int loop = (n+1)/2;
int i,j,k;
for(k=0;k<loop;k++){
i=k;
j=k;
for(j=k;j<MAX-1-k;j++){
printf("%d ",a[i][j]);
}
for(i=k;i<MAX-1-k;i++){
printf("%d ",a[i][j]);
}
for(j=MAX-1-k;j>k;j--){
printf("%d ",a[i][j]);
}
for(i=MAX-1-k;i>k;i--){
printf("%d ",a[i][j]);
}
}
if(loop%2){
printf("%d",a[loop-1][loop-1]);
}
}

int main(){
        int a[][MAX] = {{1,2,3,4,5},
                      {6,7,8,9,10},
                      {11,12,13,14,15},
                      {16,17,18,19,20},
     {21,22,23,24,25}};
printSpiral(a,MAX);
        return 0;
}

Longest common prefix of a collection of strings

//INPUT : {"ac","abc","abcd"}
//OUTPUT : a

#include<stdio.h>

#define MAX 10000

char * longestcommonprefix(char *a[],int len){
char out[MAX];
// compare ith and i+1th pointers jth character
int flag = 1;
int i;
int j=0;
while(flag){
for(i=0;i<len-1;i++){
//a[i] points to the ith string
if(*(a[i]+j) == *(a[i+1]+j)){
continue;
} else {
flag = 0;
break;
}
}
if(flag){
out[j] = *(a[i]+j);
if(out[j] == '\0') break;
j++;
}
}
out[j] = '\0';
return out;
}

int main(){
char *a[] = {"ac","abc","abcd"};
char *out = longestcommonprefix(a,sizeof(a)/sizeof(char *));
printf("%s",out);
return 0;
}

Buy and Sell Stocks

You have an array for which ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best time to buy and sell.

#include<stdio.h>

void maxProfit(int a[], int len){
int buy=0;
int sell=0;
int profit = 0;
int minSoFar = 0;
int i;
for(i=1;i<len;i++){
if(a[i] < a[minSoFar]){
minSoFar = i;
}
if(a[i] - a[minSoFar] > profit){
profit = a[i] - a[minSoFar];
buy = minSoFar;
sell = i;
}
}
printf("If you buy on day %d and sell on %d, you profit will be %d\n",buy,sell,profit);
}

int main(){
int a[] = {4,2,5,6,1,6,4};
maxProfit(a,sizeof(a)/sizeof(int));
return 0;
}

Remove duplicates from sorted array of integers (in place, no extra memory)

// INPUT : {1,1,1,2,2,2,2,2,2,3,3,3}
// OUTPUT : {1,2,3}

#include<stdio.h>

int main(){
int a[] = {1,1,1,2,2,2,2,2,2,3,3,3};
int i=0,j=0,n,k;
int len = sizeof(a)/sizeof(int);
while(1){
n = a[i];
while(a[j]==n && j<len){
j++;
}
if(j>=len){
break;
}
a[++i] = a[j];
}
for(k=0;k<=i;k++){
printf("%d ",a[k]);
}
return 0;
}

Sorted array is rotated. Find starting point or the index of the minimum element

// INPUT : {7,0,1,2,3,4,5,6}
// OUTPUT : array starts at value=0 and index=1

#include<stdio.h>

int findstartRecur(int a[],int start,int end){
int mid = (start+end)/2;
if(a[start] < a[end]){
return start;
}
if(end-start < 2){
return (a[end] < a[start])?end:start;
}
if(a[mid] > a[start]){
return findstartRecur(a,mid+1,end);
} else{
return findstartRecur(a,start,mid);
}
}

int main(){
int a[] = {7,0,1,2,3,4,5,6};
int start = findstartRecur(a,0,sizeof(a)/sizeof(int)-1);
printf("array starts at value=%d and index=%d",a[start],start);
return 0;
}

Print all permutations of a string

// INPUT : abc
// OUTPUT : abc,acb,bac,bca,cab,cba

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void strpermuteRecur(char *str,int *flag,int len,char *out,int n){
int i;
if(len == n){
out[len] = '\0';
printf("%s\n",out);
} else{
for(i=0;i<n;i++){
if(!flag[i]){
out[len++] = str[i];
flag[i] = 1;
strpermuteRecur(str,flag,len,out,n);
flag[i] = 0;
len--;
}
}
}
}

void strpermute(char *str){
static int *flag;
static char *out;
int i;
int n = strlen(str);
flag = (int *)malloc(sizeof(int)*n);
out = (char *)malloc(sizeof(char)*n);
for(i=0;i<n;i++){
flag[i] = 0;
}
strpermuteRecur(str,flag,0,out,n);
}

int main(){
char str[] = "abc";
strpermute(str);
return 0;
}

Print balanced parenthesis given n

// open - if open < n
// close - if close < n and close < open

#include<stdio.h>

void printparenthesisRecur(int n,int open,int close,char *str,int len){
if(len == 2*n){
str[len] = '\0';
printf("%s\n",str);
}
if(open < n){
str[len++] = '(';
printparenthesisRecur(n,open+1,close,str,len);
len--;
}
if(close < n && close < open){
str[len++] = ')';
printparenthesisRecur(n,open,close+1,str,len);
len--;
}
}

void printparenthesis(int n){
static char *str;
str = (char *)malloc(sizeof(char)*(2*n+1));
printparenthesisRecur(n,0,0,str,0);
}

int main(){
int n;
scanf("%d",&n);
printparenthesis(n);
return 0;
}

Merge 2 Sorted Arrays (without using extra array)

// INPUT : int A[5] = {1,2,5,7,10};
// int B[12] = {0,3,4,6,8,9,13};
// OUTPUT : {0,1,2,3,4,5,6,7,8,9,10,13}

#include<stdio.h>

void mergeArray(int *A,int *B,int m,int n){
//A has m elements, B has n-m elements
int i=m-1,j=n-m-1,k=n-1;
while(i>=0 && j>=0){
if(A[i] > B[j]){
B[k--] = A[i--];
} else {
B[k--] = B[j--];
}
}
if(j<0){
while(i>=0){
B[k--] = A[i--];
}
}
}

int main(){
int A[5] = {1,2,5,7,10};
int B[12] = {0,3,4,6,8,9,13};
int sizeA = sizeof(A)/sizeof(int);
int sizeB = sizeof(B)/sizeof(int);
int i;
mergeArray(A,B,sizeA,sizeB);
for(i=0;i<sizeB;i++){
printf("%d ",B[i]);
}
return 0;
}

Printing a N x N matrix using zigzag scanning algorithm

// Look here for zigzag scanning
// http://en.wikipedia.org/wiki/File:Zigzag_scanning.jpg
// INPUT : 4
// OUTPUT : 1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

#include<stdio.h>
#include<stdlib.h>

int populateMatrix(int *A,int n){
int i,j;
int k=1;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
*(A+i*n+j) = k++; 
}
}
}

void display(int *A,int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%d ",*(A+n*i+j));
}
}
}

void goRight(int *A,int *i,int *j,int n){
int x = *i;
int y = *j;
printf("%d ",*(A+n*x+y));
*j = *j + 1;
}

void goDown(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
printf("%d ",*(A+n*x+y));
*i = *i + 1;
}

void goSW(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
while((y!=0) && (x!=n-1)){
printf("%d ",*(A+n*x+y));
x++;
y--;
}
*i = x;
*j = y;
}

void goNE(int *A,int *i,int *j, int n){
int x = *i;
int y = *j;
while((x!=0) && (y!=n-1)){
printf("%d ",*(A+n*x+y));
x--;
y++;
}
*i = x;
*j = y;
}

void goRightorDown(int *A,int *i,int *j,int n,int *prevrd){
if(*prevrd == 0){
goRight(A,i,j,n);
} else {
goDown(A,i,j,n);
}
*prevrd = !(*prevrd);
}

void goSWorNE(int *A,int *i,int *j,int n,int *prevsn){
if(*prevsn == 1){
goSW(A,i,j,n);
} else {
goNE(A,i,j,n);
}
*prevsn = !(*prevsn);
}

void zigzag(int *A,int n){
int i=0,j=0;
int prevrd = 0;
int prevsn = 1;
int k = 1;
int done = -1;
while(1 && n>1){
k=1;
while(1){
goRightorDown(A,&i,&j,n,&prevrd);
k++;
if(k==n){
done += 1;
break;
}
goSWorNE(A,&i,&j,n,&prevsn);
}
if(done){
break;
}
goSWorNE(A,&i,&j,n,&prevsn);
prevrd = !prevrd;
}
printf("%d ",*(A+n*i+j));
}

int main(){
int n;
scanf("%d",&n);
int *A = (int *)malloc(sizeof(int)*n*n);
populateMatrix(A,n);
zigzag(A,n);
free(A);
return 0;
}