Swap every 2 nodes of a Linked List

// INPUT : a->b->c->d->e->f
// OUTPUT : b->a->d->c->f->e

void swapAdjacent(Node **headRef){
    Node *curr = *headRef;
    Node *prev = NULL;
    Node *currNext;
    if(curr == NULL){
        return;
    }
    while(curr->next != NULL){
        currNext = curr->next;
        curr->next = currNext->next;
        currNext->next = curr;
        if(*headRef == curr){
            *headRef = currNext;
        } else {
            prev->next = currNext;
        }
        if(curr->next != NULL){
            prev = curr;
            curr = curr->next;
        }
    }
}

Reverse a Linked List

#include<stdio.h>

typedef struct node{
int d;
struct node *next;
}Node;

Node* newNode(int data){
Node *n = (Node *)malloc(sizeof(Node));
n->d = data;
n->next = NULL;
return n;
}

void insert(struct node **headRef, int data){
Node *head = *headRef;
Node *temp;
if(head == NULL){
head = newNode(data);
} else {
temp = newNode(data);
temp->next = head;
head = temp;
}
*headRef = head;
}

void displayList(Node *head){
while(head != NULL){
printf("%d ",head->d);
head = head->next;
}
}

void reverseList(Node **headRef){
Node *head = *headRef;
Node *prev = NULL;
Node *temp;
if(head == NULL){
return;
}
while(head->next != NULL){
temp = head->next;
head->next = prev;
prev = head;
head = temp;
}
head->next = prev;
*headRef = head;
}

int main(){
Node *head = NULL;
int i;
for(i=10;i>0;i--){
insert(&head,i);
}
displayList(head);
reverseList(&head);
printf("\nafter reversing\n");
displayList(head);
return 0;
}

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;
}

Singleton design pattern in C++

#include<iostream>
using namespace std;

class Singleton{
private:
Singleton(){}
static Singleton* obj;
int x;
public:
static Singleton* getInstance(){
if(obj==NULL){
cout<<"constructing object"<<endl;
obj = new Singleton();
}
return obj;
}
void setdata(int);
void display();

};

void Singleton::setdata(int x){
this->x = x;
}

void Singleton::display(){
cout<<this->x<<endl;
}

Singleton* Singleton::obj = NULL;

int main(){
Singleton *s1 = Singleton::getInstance();
Singleton *s2 = Singleton::getInstance();
s1->setdata(5);
s1->display();
s2->display();
return 0;
}

Function Template in C++

#include<iostream>
using namespace std;

template<typename T>
T getmax(T a,T b){
return (a>b)?a:b;
}

int main(){
int a = 10;
int b = 20;
char x = 'c';
char y = 'x';
int c = getmax<int>(a,b);
cout<<c<<endl;
char temp = getmax<char>(x,y);
cout<<temp<<endl;
}

Implementing Stack in C++ using Class Template

#include<iostream>
using namespace std;

template<class T>
class stack{
T* arr;
static int top;
public:
stack(int);
void push(T);
T pop();
bool empty();
};

template<class T>
int stack<T>::top = -1;

template<class T>
stack<T>::stack(int x){
this->arr = new T(x);
}

template<class T>
void stack<T>::push(T a){
this->arr[++top] = a;
}

template<class T>
T stack<T>::pop(){
T a = this->arr[top--];
return a;
}

template<class T>
bool stack<T>::empty(){
return (top==-1);
}

int main(){
stack<int> s(10);
int i;
for(i=0;i<10;i++){
s.push(i);
}
while(!s.empty()){
cout<<s.pop()<<endl;
}
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;
}

Finding if two numbers are of same sign or opposite sign without using arithmetic operators

#include<stdio.h>

int ifopposite(int a,int b){
return ((a^b) < 0)?1:0;
}

int main(){
int a=-5;
int b=6;
if(ifopposite(a,b)){
printf("numbers are of opposite sign");
} else {
printf("numbers are of same sign");
}
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;
}

Convert Singly Linked List to height balanced BST

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

typedef struct node{
 int data;
 struct node *next;
 struct node *left;
}LNode;

LNode* newNode(int data){
 LNode *n = (LNode*)malloc(sizeof(LNode));
 n->data = data;
 n->next = NULL;
 n->left = NULL;
 return n;
}

void buildList(LNode **headRef){
 int i;
 for(i=7;i>0;i--){
  LNode *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(LNode *head){
    LNode *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(LNode *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}


LNode* buildBST(LNode* head){
        if(head == NULL || head->next == NULL) return head;
        LNode *root = NULL;
        LNode *slow = head;
        LNode *fast = head;
        LNode *prev = NULL;
        while(fast != NULL && fast->next != NULL){
                prev = slow;
                slow = slow->next;
                fast = fast->next->next;
        }

        root = slow;
        prev->next = NULL;
        root->left = buildBST(head);
        root->next = buildBST(slow->next);
        return root;
}

void preorder(LNode* root){
 if(root != NULL){
  printf("%d ",root->data);
  preorder(root->left);
  preorder(root->next);
 }
}

void inorder(LNode* root){
 if(root != NULL){
  inorder(root->left);
  printf("%d ",root->data);
  inorder(root->next);
 }
}

void postorder(LNode* root){
 if(root != NULL){
  postorder(root->left);
  postorder(root->next);
  printf("%d ",root->data);
 }
}

int main(){
 LNode *head = NULL;
 LNode *root = NULL;
 buildList(&head);
 display(head);
 root = buildBST(head);
 preorder(root);
 printf("\n");
 inorder(root);
 printf("\n");
 postorder(root);
// freeMem(head);
 return 0;
}

Inorder Traversal without using recursion

void inorder(Node* root){
if(root == NULL) return;
Node *temp = root;
push(temp);
while(!isempty()){
temp = temp->left;
while(temp != NULL){
push(temp);
temp = temp->left;
}
temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
temp = temp->right;
push(temp);
}
}
}

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;
}

Inserting into Trie and Checking if an element is present in the Trie

// INPUT : char *str[] = { "one$", "two$", "three$", "four$", 
//                         "thre$" };
//         char *test[] = { "one$", "too$", "three$", "fore$" };
// OUTPUT : one$ is present, too$ is not present, three$ is 
//          present, fore$ is not present



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

#define ASIZE 255

typedef struct node {
    struct node *a[ASIZE];
} Node;

Node *newNode()
{
    Node *n = (Node *) malloc(sizeof(Node));
    int i;
    for (i = 0; i < ASIZE; i++) {
n->a[i] = NULL;
    }
    return n;
}

void insertTrie(Node ** rootRef, char *str)
{
    int len = strlen(str);
    int i;
    Node *root = *rootRef;
    if (root == NULL) {
root = newNode();
*rootRef = root;
    }
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   root->a[p] = newNode();
}
root = root->a[p];
    }
}

int isPresent(Node * root, char *str)
{
    int len = strlen(str);
    int i;
    int isPresent = 1;
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   isPresent = 0;
   break;
} else {
   root = root->a[p];
}
    }
    return isPresent;
}

printAllWordsRecur(Node *root,char *out,int len){
int i;
int done = 1;
for(i=0;i<ASIZE;i++){
if(root->a[i] == NULL){
continue;
} else{
done = 0;
out[len++] = i;
printAllWordsRecur(root->a[i],out,len);
len--;
}
}
if(done){
out[len] = '\0';
printf("%s\n",out);
}
}

printAllWords(Node *root){
static char out[50];
printAllWordsRecur(root,out,0);
}

int main()
{
    char *str[] = { "one$", "two$", "three$", "four$", "thre$" };
    char *test[] = { "one$", "too$", "three$", "fore$" };
    Node *root = NULL;
    int i;
    for (i = 0; i < 5; i++) {
insertTrie(&root, str[i]);
    }
    for (i = 0; i < 4; i++) {
if (isPresent(root, test[i])) {
   printf("%s is present\n", test[i]);
} else {
   printf("%s is not present\n", test[i]);
}
    }
    printAllWords(root);
    return 0;
}