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

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.

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

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

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

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

Preorder traversal of a BST, iteratively using a Stack

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

#define MAX 100

typedef struct node{
 int data;
 struct node* left;
 struct node* right;
}Node;

Node* s[MAX];
int top = -1;

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

void insertNode(Node* root,int data){
 if(data < root->data){
  if(root->left == NULL){
   root->left = newNode(data);
  } else {
   insertNode(root->left,data);
  }
 } else {
  if(root->right == NULL){
   root->right = newNode(data);
  } else {
   insertNode(root->right,data);
  }
 }
}

Node* createBST(Node **rootRef){
 Node *root = newNode(4);
 insertNode(root,2);
 insertNode(root,1);
 insertNode(root,3);
 insertNode(root,6);
 insertNode(root,5);
 insertNode(root,7);
 *rootRef = root;
}

void push(Node* n){
s[++top] = n;
}

Node* pop(){
return s[top--];
}

int isempty(){
return (top==-1);
}

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

int main(){
 Node* root = NULL;
 createBST(&root);

 printf("\nPREORDER :\n");
 preorder(root);

 return 0;
}