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