Saturday, November 2, 2013

how to implement two stacks in one array

My friend came up with a new question  that he is asked in his interview,

Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The code is implemented in C++.



/* 
 * File:   main.cpp
 * Author: bekoC
 */

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

#define N 10 

struct Stacks {
    char charArray[N];
    int top1, top2;
    void olustur();
    bool Insert(int stackNumber, char veri);
    char deleteFromStack(int stackNumber);
    bool isEmpty(int stackNumber);
    void printStack(int stackNumber);
};

bool Stacks::Insert(int stackNumber, char newChar) {
    if (top1 == top2)
    {
        return false;
    }
    if (stackNumber == 1)
        charArray[top1++] = newChar;
    else
        charArray[top2--] = newChar;
    return true;
}

char Stacks::deleteFromStack(int stackNumber) {
    if (stackNumber == 1)
        return charArray[--top1];
    else
        return charArray[++top2];
}

bool Stacks::isEmpty(int stackNumber) {
    if (stackNumber == 1)
        return (top1 == 0);
    else
        return (top2 == N - 1);
}

void Stacks::create() {
    top1 = 0; 
    top2 = N - 1; 
}

void Stacks::printStack(int stackNumber) {

    if (stackNumber == 1 && !isEmpty(stackNumber)) {
        {
            for (int i = 0; i <= top1; ++i) {
                printf("%c", charArray[i]);

            }
        }
    } else if (isEmpty(stackNumber)) {
        printf("Stack 1 is empty");
    }
    if (stackNumber == 2 && !isEmpty(stackNumber)) {
        for (int i = N - 1; i >= top2; i--) {
            printf("%c", charArray[i]);
        }
    } else if (isEmpty(stackNumber)) {
        printf("Stack 2 is empty");
    }
}

int main() {
    Stacks myStack;
    myStack.create();
    myStack.Insert(1, 'A');
    myStack.Insert(1, 'B');
    myStack.Insert(1, 'C');
    myStack.Insert(1, 'D');
    myStack.Insert(1, 'E');
    myStack.Insert(1, 'F');

    myStack.Insert(2, 'W');
    myStack.Insert(2, 'X');
    myStack.Insert(2, 'Y');
    myStack.Insert(2, 'Z');
    myStack.printStack(1);
    myStack.printStack(2);
    if (!myStack.isEmpty(1))
        myStack.deleteFromStack(1);
    if (!myStack.isEmpty(2))
        myStack.deleteFromStack(2);
    return 0;
}

Linked List Interview Question

Recently, my friend asked me to write a basic program in C to add a indicator (e.g. any number or char) between the two nodes of the given linked list. He is asked this question in one of the job interviews.
The output of the program with the indicator of  99 is shown as below.



The code
/* 
 * File:   main.cpp
 * Author: bekoC
 */

//Some notes about my compilation errors:
//There are many ways to get a segfault, 
//at least in the lower-level languages such as C(++). 
//A common way to get a segfault is to dereference a null pointer:
//int *p = NULL;
//*p = 1;


#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};

struct Node* insert(struct Node *head, int data) {
    struct Node *temp = (struct Node*) malloc(sizeof (struct Node)); // for the new node address is taken by malloc in heap
    temp->data = data;
    temp->next = NULL;
    if (head == NULL) {
        head = temp; // first node give the head temp's address
    } else {
        Node *temp1 = head;
        while (temp1->next != NULL) {
            temp1 = temp1->next;
        }
        temp1->next = temp;
    }
    return head;
}

struct Node* addIndicator(struct Node *head, int indicator) {
    struct Node *newNode, *scan;
    struct Node *temp1 = head;
    while (temp1 != NULL && temp1->next != NULL) {
        newNode = (struct Node*) malloc(sizeof (struct Node));
        newNode->data = indicator;
        newNode->next = temp1->next;
        temp1->next = newNode;
        temp1 = newNode->next;
    }
    return head;
}

void printList(struct Node *head) {
    //using recursion
    if (head == NULL) {
        return;
    }
    printf("%d  ", head->data);
    printList(head->next);
}

int main(int argc, char** argv) {
    struct Node *head = NULL; // head point to no address
    head = insert(head, 2);
    head = insert(head, 4);
    head = insert(head, 6);
    head = insert(head, 8);
    printList(head);
    printf("\n");
    //Adding a indicator which is 99
    int indicator = 99;
    head = addIndicator(head, indicator);
    printList(head);
    return 0;
}