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