Coding Interview

A class implementation of Binary Search Tree in C++

9/18/2015

/******************************************************************************************
*******************************************************************************************
Chapter 4 Trees and Graphs

This is a class implementation of Binary Search Tree (BST), containing:

   inser(): insert a value in a BST
   isBalanced(): check if a BST is balanced, a BST is balanced if the difference of left and right subtrees height is atmost one!
   getHeight(): returns the height of a BST
   deleteBST(): deletes a BST      
   inOrder():      prints a BST i in-order fashion
   preOrder(): prints a BST i pre-order fashion
   postOrder(): prints a BST i post-order fashion

By: Hamed Kiani (Sep. 18, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

// tree node, including left and right pointers, data 
struct Node{
        Node(int value): data(value), left(NULL), right(NULL) {}
        int data;
        Node *left;
        Node *right;
};

/////////////////////////////////////////////////////////////////////////////////////////
// BST class
class BST{
private:
        Node *_root;
        void insert(Node *treeNode, int data);
        bool isBalanced(Node *treeNode);
        int  getHeight(Node *treeNode);
        void deleteBST(Node *treeNode);
        void inOrder(Node * treeNode);
        void preOrder(Node * treeNode);
        void postOrder(Node * treeNode);
public:

        BST();  // constructor     
        ~BST();     // destractor

        void insert(int data){ insert(_root, data);}       

        int getHeight(){return getHeight(_root);}
        Node * getMaxNode();
        Node * getMinNode();

        void deleteBST() {deleteBST(_root);}

        bool isBalanced(){return isBalanced(_root);        }

        void inOrder() {inOrder(_root);}
        void preOrder(){preOrder(_root);}
        void postOrder(){postOrder(_root);}
};

/////////////////////////////////////////////////////////////////////////////////////////
BST::BST()
{
        _root = NULL;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::insert(Node *treeNode, int data)
{
        if (!treeNode)
        {
                treeNode = new Node(data);           
                _root = treeNode;           
        }
        else
        {
                if (data < treeNode->data)
                {
                        if (!treeNode->left)
                        {
                                Node *treeTemp = new Node(data);
                                treeNode->left = treeTemp;
                        }
                        else
                                insert(treeNode->left, data);
                }
                else
                {
                        if (!treeNode->right)
                        {
                                Node *treeTemp = new Node(data);                         
                                treeNode->right = treeTemp;
                        }
                        else
                                insert(treeNode->right, data);
                }
        }
}

/////////////////////////////////////////////////////////////////////////////////////////
int BST::getHeight(Node *treeNode)
{
        if (!treeNode)
                return 0;
        return 1 + max(getHeight(treeNode->left) , getHeight(treeNode->right));
}

/////////////////////////////////////////////////////////////////////////////////////////
bool BST::isBalanced(Node *treeNode)
{
        if (!treeNode)
                return false;
        int leftHeight = getHeight(treeNode->left);
        int rightHeight = getHeight(treeNode->right);

        if (abs(leftHeight - rightHeight) > 1)
                return false;
        return true;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMaxNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->right)
                treeNode = treeNode ->right;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMinNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->left)
                treeNode = treeNode ->left;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::deleteBST(Node *treeNode) 
{
        if (!treeNode)
                return;

        Node * curTreeNode = treeNode;
        Node * leftTreeNode = treeNode->left;
        Node * rightTreeNode = treeNode->right;
        delete(curTreeNode);
        deleteBST(leftTreeNode);
        deleteBST(rightTreeNode);
}

/////////////////////////////////////////////////////////////////////////////////////////
BST::~BST()
{
        deleteBST();
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::inOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        inOrder(treeNode->left);
        cout << treeNode->data << " " ;
        inOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::preOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        cout << treeNode->data << " ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::postOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout << treeNode->data << " ";
}

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
        BST myBST;
        myBST.insert(5);
        myBST.insert(10);
        myBST.insert(3);

        myBST.insert(51);
        myBST.insert(110);
        myBST.insert(13);
        
        int h = myBST.getHeight();
        cout << "the height of this BSt is : " << h << endl;

        Node * mx = myBST.getMaxNode();
        cout << "max value: " << mx->data << endl;

        Node * mi = myBST.getMinNode();
        cout << "min value: " << mi->data << endl;

        bool isbal = myBST.isBalanced();
        if (isbal)
                cout << "BST is balanced! " << endl;
        else
                cout << "BST is not balanced! " << endl;

        cout << " in-order traverse is : " << endl;
        myBST.inOrder();cout << endl;
        cout << " pre-order traverse is : " << endl;
        myBST.preOrder();cout << endl;
        cout << " post-order traverse is : " << endl;
        myBST.postOrder();cout << endl;
}

10 Comments

Write a program to sort a stack in ascending order. c++

9/15/2015

0 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Write a program to sort a stack in ascending order.
You should not make any assumptions about how the stack is implemented.
The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

peek: return the top value of stack without removing it.

We use two stacks for ordering the elements. The main stack contains the elements in a sorted fashion. 
The auxulary stack is used to sort the elements of the main stack if required. 
memory  O(n)
time       O(n^2)

Questions:

how can we write this function with the memory of O(1)?
how about a time of O(n)? is that possible?


By: Hamed Kiani (Sep. 14, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class sortedStack{

private:
        int *_mainStack;     // main ordered stack
        int *_auxStack;              // auxulary stack for ordering
        int _size;                       // the max size of stack for overflow checking
        int _top;                        // index of the top element of main stack
        int _aux_top;            // index of the top element of aux stack

public:
        sortedStack(int n);      // constructor
        ~sortedStack();             // destructor
        bool isEmpty();           // is the stack empty?
        bool isFull();            // is the stack full?
        void push(int data);       // ordered push
//         void ordered_push(int data);
        void pop();                       // normal pop operation
        int peek();                       // peek function   
        void print();             // print the main stack
};

////////////////////////////////////////////////////////////
sortedStack::sortedStack(int n)
{
        _size = n;
        _top = -1;
        _aux_top = -1;
        // initializaing the main and aux stacks
        _mainStack = (int*) malloc(sizeof(int) * _size);
        _auxStack  = (int*) malloc(sizeof(int) * _size);
}

////////////////////////////////////////////////////////////
sortedStack::~sortedStack()
{
        free(_mainStack);
        free(_auxStack);        
}

////////////////////////////////////////////////////////////
bool sortedStack::isEmpty()
{
        return (_top == -1);
}

////////////////////////////////////////////////////////////
bool sortedStack::isFull()
{
        return (_top == _size-1);
}

////////////////////////////////////////////////////////////
void sortedStack::push(int data)
{
        // is full, not possible to push a new element
        if (isFull())
        {
                cout << " stack overflow!" << endl;
                return;
        }
        // if the stack is empty or the new element is smaller 
        //  than the top value just do simple push
        int top_data = peek();
        if ((data >= top_data) | (isEmpty()))
        {
                _mainStack[++_top] = data;
                return;
        }

        // otherwise, use aux-stack to push the new element in the right place
        while(~isEmpty() & (top_data > data ))
        {
                _auxStack[++_aux_top] = top_data;
                pop();
                top_data = peek();
        }
        _mainStack[++_top] = data;
        // re-push the lements in aux-stack back to the main stack
        while(_aux_top >= 0)
        {
                _mainStack[++_top] = _auxStack[_aux_top--];         
        }
        return;
}

////////////////////////////////////////////////////////////
void sortedStack::pop()
{
        if (isEmpty())
        {
                cout << " stack unerflow!" << endl;
                return;
        }
        _top--;
}

////////////////////////////////////////////////////////////
int sortedStack::peek()
{
        if (isEmpty())
        {
                cout << " stack is empty!" << endl;
                return INT_MAX;
        }
        return _mainStack[_top];
}

void sortedStack::print()
{
        if (isEmpty())
        {
                cout << " stack is empty!" << endl;
                return;
        }
        cout << " the elemets of stack " << endl;
        for (int i=0; i<=_top; i++)
                cout << _mainStack[i] << " " ;
        cout << endl; 
}

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        sortedStack myStack(10);
        myStack.push(1);
        myStack.push(15);
        myStack.push(32);
        myStack.push(4);
        myStack.push(1);
        myStack.print();        
        myStack.pop();
        myStack.pop();
        myStack.push(77);
        myStack.push(10);
        myStack.pop();
        myStack.push(-15);   
        myStack.print();        
        return 0;
}

0 Comments

Implement a MyQueue class which implements a queue using two stacks : c++

9/7/2015

0 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Implement a MyQueue class which implements a queue using two stacks.
We use two stacks, s1 and s2 for enqueue and dequeue. 
 
By: Hamed Kiani (Sep. 7, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

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

class MyQueue{
private:
        Node *_s1_head;     // enQueue is done using s1
        Node *_s2_head;     // s2 is used for dequeue
        int _s1_size;    // the size of s1 stack    
        int _s2_size;    // the size of s2 stack
        
public:
        MyQueue();
        ~MyQueue();
        void enQueue(int data);    // enqueue data value using s1
        Node* deQueue();             // dequeue using s1 and s2
        void print_s1();          // print elements of s1 stack
        void print_s2();          // print elements of s2 stack
        bool isEmpty(Node *); // check if s1 or s2 are empty
        int get_s1_size(){return _s1_size;}        // return size of s1
        int get_s2_size(){return _s2_size;}        // return size of s2
};

////////////////////////////////////////////////////////////////////
MyQueue::MyQueue()
{
        _s1_head = NULL;
        _s2_head = NULL; 
        _s1_size = 0;
        _s2_size = 0;
        cout << "the stack and queue are initialized! " << endl;
}

////////////////////////////////////////////////////////////////////
MyQueue::~MyQueue()
{
        Node *temp;
        
        while(_s1_head != NULL)
        {
                temp = _s1_head;
                _s1_head = _s1_head->next;
                delete temp;
        }

        while(_s2_head != NULL)
        {
                temp = _s2_head;            
                _s2_head = _s2_head->next;
                delete temp;
        }
        cout << "the stack and queue are deleted! " << endl;
}

////////////////////////////////////////////////////////////////////
// enQueue data at begin of s1 (push s1 stack)
void MyQueue::enQueue(int data)
{
        Node *temp = new Node;
        temp->data = data;
        temp->next = _s1_head;
        _s1_head = temp;
        _s1_size++;  
        cout << " the enQueue value is: " << data << endl;
}

////////////////////////////////////////////////////////////////////
// For deQueue, 
// we copy all from s1 to ss except the last node of s1 O(n)
// re-copy s2 to s1 in reverse order O(n)
// update the s1_size and s2_size
Node* MyQueue::deQueue()
{
        // the queue is empty and dequeue is not possible
        if ((_s1_size == 0) )
        {
                cout<< "dequeue is not possible !" << endl;
                return NULL;                 
        }

        // there is just one element in queue
        if ((_s1_size == 1) )
        {
                Node * temp = _s1_head;
                _s1_head = NULL;
                _s1_size--;
                cout << " the dequeue value is: " << temp->data << endl;
                return temp;
        }

        // there are more than one element in the queue
        _s2_head = _s1_head;
        _s1_head = NULL;
        Node * temp;
        temp = _s2_head;
        _s1_size--;
        while(temp->next->next != NULL)
        {
                temp = temp->next;
        }
        Node * temp2;
        temp2 = temp->next;
        temp->next = NULL;       
        _s1_head = _s2_head;
        _s2_head = NULL;
        cout << " the dequeue value is: " << temp2->data << endl;
        return temp2;
}

////////////////////////////////////////////////////////////////////
void MyQueue::print_s1()
{
        if (_s1_head == NULL)
        {
                cout << " stack s1 is empty" << endl;
                return;
        }
        Node* temp;
        temp = _s1_head;
        while(temp)
        {
                cout << temp->data << " " ;
                temp = temp->next;
        }
        cout << endl;
}

//////////////////////////////////////////////////////////
void MyQueue::print_s2()
{
        if (_s2_head == NULL)
        {
                cout << " stack s2 is empty" << endl;
                return;
        }
        Node* temp;
        temp = _s2_head;
        while(temp)
        {
                cout << temp->data << " " ;
                temp = temp->next;
        }
        cout << endl;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        MyQueue queue;
        queue.enQueue(1);        
        cout << queue.get_s1_size() << endl;
        cout << queue.get_s2_size() << endl;
        queue.print_s1();
        queue.print_s2();
        Node * temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        temp = queue.deQueue();
        queue.print_s1();
        queue.print_s2();
        queue.enQueue(3);
        queue.enQueue(4);
        queue.print_s1();
        queue.print_s2();
        return 0;
}

0 Comments

Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this.Implement

9/7/2015

1 Comment

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Imagine a (literal) stack of plates.
If the stack gets too high, it might topple.
Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. 
Implement a data structure SetOfStacks that mimics this.
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
 
By: Hamed Kiani (Sep. 7, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class SetOfStacks{
private:
        int _numOfStk;   // number of stacks
        int _thOfStk;    // threshold of stacks
        int _curStk;     // index of current stack
        int **_stacks;       // two-dim array to keep stacks elements
        int *_elmts; // number of elements in each stack

public:
        SetOfStacks(int n, int t);
        ~SetOfStacks();
        void push(int n);  // push the element n on the stack
        int pop();                        // pop operation
        int pop(int k);            // pop operation from stack k
        bool isFull(int k);        // is stack k full?
        bool isFull();            // is the stack full?
        bool isEmpty(int k);//        is the stack k empty?
        bool isEmpty();           // is the stack empty?
        void printAll();  // print all elements
        void printK(int k);        // print elemets of stack k
};

////////////////////////////////////////////////////////////       
SetOfStacks::SetOfStacks(int n, int t)
{
        _numOfStk = n;
        _thOfStk  = t;
        _curStk   = 0;

        // _elmts = new int[_numOfStk];
        _elmts = (int*) malloc(_numOfStk * sizeof(int));
        for(int i = 0; i < _numOfStk; i++)
                _elmts[i] = -1;  // all are empty


        _stacks = (int **) malloc(_numOfStk * sizeof(int *));
        for (int i = 0; i<_numOfStk; i++)
                _stacks[i] = (int *) malloc(_thOfStk * sizeof(int));
        cout << n << " stacks are created, windex 0,..., " << n-1 << endl;
        cout << " the threshold for each stack is " << t << " elements " << endl;
}

////////////////////////////////////////////////////////////
SetOfStacks::~SetOfStacks()
{
        free(_elmts);
        free(_stacks);
        cout << " stacks are deleted!" << endl;
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull(int k)
{
        return (_elmts[k] == _thOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isFull()
{
        return isFull(_numOfStk-1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty(int k)
{
        return (_elmts[k] == -1);
}

////////////////////////////////////////////////////////////
bool SetOfStacks::isEmpty()
{
        return isEmpty(0);
}

////////////////////////////////////////////////////////////
void SetOfStacks::push(int n)
{
        if (isFull())
        {
                cout << "stack overflow! cann't push " << n << " value! " << endl;
                return;
        }       
        if (_elmts[_curStk] == _thOfStk - 1)
                _curStk++;
        cout << "value " << n << " pushed on stack " << _curStk <<  endl;
        _elmts[_curStk]++;
        _stacks[_curStk][_elmts[_curStk]] = n;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop()
{
        if (isEmpty())
        {
                cout << "stack under flow! " << endl;
                return INT_MAX;
        }
        int i = _stacks[_curStk][_elmts[_curStk]];
        cout << "value " << i << " is popped from stack " << _curStk << endl;
        _elmts[_curStk]--;  
        if ((_elmts[_curStk] == -1) & (_curStk > 0))
                _curStk--;
        
        return i;
}

////////////////////////////////////////////////////////////
int SetOfStacks::pop(int k)
{
        if (isEmpty(k))
        {
                cout << "stack under flow!" << endl;
                return INT_MAX;
        }

        if ((k > _numOfStk-1) | (k < 0))
        {
                cout << " stack index is out of range! " << endl;
                return INT_MAX;
        }

        
        int i = _stacks[k][_elmts[k]];
        cout << "value " << i << " is popped from stack " << k << endl;
        _elmts[k]--;
        if ((_elmts[k] == -1) & (k > 0) & (k == _curStk))
                _curStk--;
        return i;
}

////////////////////////////////////////////////////////////

void SetOfStacks::printAll()
{
        cout << "print all the stacks:" << endl;
        for (int i = 0; i < _numOfStk; i++)
        {
                if (isEmpty(i))
                        cout << "stack " << i <<  " is empty " << endl;
                else
                {
                        for (int j = 0; j <= _elmts[i]  ; j++)
                                cout << _stacks[i][j] << " " ;
                        cout << endl;
                }
        }
}

////////////////////////////////////////////////////////////
void SetOfStacks::printK(int k)
{
        if (k > _numOfStk-1)
        {
                cout << "index is more than the stack size!" << endl;
                return;
        }

        if (k < 0)
        {
                cout << "index is less than the stack size!" << endl;
                return;
        }

        if (isEmpty(k))
                        {
                                cout << "stack " << k <<  " is empty " << endl;
                                return;
        }
                else
                {
                        for (int j = 0; j <= _elmts[k]  ; j++)
                                cout << _stacks[k][j] << " " ;
                        cout << endl;
                }
}

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        int n = 2;
        int t = 3;
        SetOfStacks stacks(n,t);
        
        stacks.push(1);
        stacks.push(2);
         stacks.push(3);
        
        stacks.push(10);
        stacks.push(20);
        stacks.push(30);

        stacks.push(100);
        stacks.push(200);
        stacks.push(300);

        stacks.push(1000);
        stacks.push(2000);
        stacks.push(3000);
        stacks.push(3001);
        stacks.push(3002);       

        stacks.printK(0);
        stacks.printK(1);
        stacks.printK(2);
        stacks.printK(3);
        stacks.printK(4);

        stacks.printAll();

        stacks.pop();
        stacks.pop();
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(0);
        stacks.pop(2);
        stacks.printAll();
        return 0;
}

1 Comment

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.We design this class using array instead of linkedlist

9/2/2015

1 Comment

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? 
Push, pop and min should all operate in O(1) time.
We design this class using array instead of linkedlist
 
By: Hamed Kiani (Sep. 2, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class minStack{

private:
        int* _main_stk;      // main stack
        int* _aux_stk;       // aux. stack to keep elements in sorted
        int _cap;        // the maximum capacity of stack
        int _top;        // size of stack

public:
        minStack(int n);
        ~minStack();
        void push(int data);
        int pop();
        bool is_empty();
        bool is_full();
        void print_stk();
        void print_aux_stk();
        int getMin();
};

minStack::minStack(int n)
{
        _cap = n;
        _main_stk = new int[_cap];
        _aux_stk  = new int[_cap];
        _top = -1;       
        cout << " an object of minStack is created!" << endl;
}

minStack::~minStack()
{       
        delete[] _main_stk;
        delete[] _aux_stk;
        cout << " an object of minStack is deleted!" << endl;
}

bool minStack::is_empty()
{
        return (_top == -1);
}

bool minStack::is_full()
{
        return (_top == _cap-1);
}

void minStack::push(int data)
{
        if (is_full())
        {
                cout << "stack overflow!" << endl;
                return;
        }
        cout << " The element " << data << " is pushed on the stack!" << endl;
        // if the stack is empty or data is less than all elements in the aux. stack, just push it
        if ((_top == -1) || (data <= _aux_stk[_top]))
        {
                _top++;             
                _main_stk[_top] = data;
                _aux_stk[_top]  = data;             
                return;
        }

        // otherwise, push data on the main stack and duplicate the current min in the new position
        int temp = _aux_stk[_top];
        _top++;             
        _main_stk[_top] = data;     
        _aux_stk[_top] = temp;      
}

// pop operation: simply just _top--!
int minStack::pop()
{
        if (is_empty())
        {
                cout << "underflow!" << endl;
                return INT_MAX;
        }       
        _top--;
        cout << " The element " << _main_stk[_top+1] << " is popped from the stack!" << endl;
}

// return min value
int minStack::getMin()
{
        return _aux_stk[_top];
}

// print the main stack
void minStack::print_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _main_stk[j] << " " ;
        cout << endl;
}

// print the main stack
void minStack::print_aux_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _aux_stk[j] << " " ;
        cout << endl;
}

////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        minStack stack(10);

        stack.push(12);
        stack.push(3);
        stack.push(4);   
        stack.push(11);

        stack.push(12);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(11);
        stack.push(41);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(12);
        stack.push(1);
        stack.push(3);
        
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();

        cout << "the min value is : " << stack.getMin() << endl;
        stack.pop();
        stack.pop();
        stack.pop();
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();
        return 0;
}

1 Comment

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

9/2/2015

2 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? 
Push, pop and min should all operate in O(1) time.
We design this class using array instead of linkedlist
 
By: Hamed Kiani (Sep. 2, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class minStack{

private:
        int* _main_stk;      // main stack
        int* _aux_stk;       // aux. stack to keep elements in sorted
        int _cap;        // the maximum capacity of stack
        int _top;        // size of stack

public:
        minStack(int n);
        ~minStack();
        void push(int data);
        int pop();
        bool is_empty();
        bool is_full();
        void print_stk();
        void print_aux_stk();
        int getMin();
};

minStack::minStack(int n)
{
        _cap = n;
        _main_stk = new int[_cap];
        _aux_stk  = new int[_cap];
        _top = -1;       
        cout << " an object of minStack is created!" << endl;
}

minStack::~minStack()
{       
        delete[] _main_stk;
        delete[] _aux_stk;
        cout << " an object of minStack is deleted!" << endl;
}

bool minStack::is_empty()
{
        return (_top == -1);
}

bool minStack::is_full()
{
        return (_top == _cap-1);
}

void minStack::push(int data)
{
        if (is_full())
        {
                cout << "stack overflow!" << endl;
                return;
        }
        cout << " The element " << data << " is pushed on the stack!" << endl;
        // if the stack is empty or data is less than all elements in the aux. stack, just push it
        if ((_top == -1) || (data <= _aux_stk[_top]))
        {
                _top++;             
                _main_stk[_top] = data;
                _aux_stk[_top]  = data;             
                return;
        }

        // otherwise, push data on the main stack and duplicate the current min in the new position
        int temp = _aux_stk[_top];
        _top++;             
        _main_stk[_top] = data;     
        _aux_stk[_top] = temp;      
}

// pop operation: simply just _top--!
int minStack::pop()
{
        if (is_empty())
        {
                cout << "underflow!" << endl;
                return INT_MAX;
        }       
        _top--;
        cout << " The element " << _main_stk[_top+1] << " is popped from the stack!" << endl;
}

// return min value
int minStack::getMin()
{
        return _aux_stk[_top];
}

// print the main stack
void minStack::print_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _main_stk[j] << " " ;
        cout << endl;
}

// print the main stack
void minStack::print_aux_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _aux_stk[j] << " " ;
        cout << endl;
}

////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        minStack stack(10);

        stack.push(12);
        stack.push(3);
        stack.push(4);   
        stack.push(11);

        stack.push(12);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(11);
        stack.push(41);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(12);
        stack.push(1);
        stack.push(3);
        
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();

        cout << "the min value is : " << stack.getMin() << endl;
        stack.pop();
        stack.pop();
        stack.pop();
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();
        return 0;
}

2 Comments

A class of K Stacks in a single array! Efficient memory and run time.: c++

9/2/2015

3 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

A class of K Stacks in a single array! Efficient memory and run time. 
 
By: Hamed Kiani (Sep. 2, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class kStacks{

private:
        int *arr;    // an array of size n to save the values in stacks
        int *top;    // an array of size k to keep the index of top values of k stacks
        int *next;   // an array of size n to keep the next entry in stacks
        int n,k; // n: size of array, k: number of stacks
        int next_slot;   // the next free slot in the array 

public:
        kStacks(int k1, int n1);
        ~kStacks();         
        bool is_full() { return (next_slot == -1);}
        bool is_empty(int sn) { return(top[sn] == -1);}
        void push(int sn, int data);
        int pop(int sn);
        void print_sn(int sn);
};

// constructor
kStacks::kStacks(int k1, int n1)
{
        k = k1; n = n1; 
        arr  = new int[n];    // to keep the values in the stacks
        top  = new int[k];    // to keep the last index of stacks
        next = new int[n];    // to handle the next and previous index of stacks

        // initial to -1, all k stacks are empty
        for (int i = 0; i < k; i++)
                top[i] = -1;

        // the next slot of each entry is the next index
        for (int i = 0; i < n-1; i++)
                next[i] = i+1;

        // for the last entry there is no free slot
        next[n-1] = -1;
        // the initial free slot is arr[0]
        next_slot = 0;
}

// destructor
kStacks::~kStacks()
{
        k = 0; n = 0;
        delete[] arr;
        delete[] next; 
        delete[] top;
}
 
// push operator
void kStacks::push(int sn, int data)
{
        // wrong stack number
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return;
        }

        // first check if the stack sn is overflow
        if (is_full())
        {
                cout << "stack overflow! cann't push!" << endl;
                return;
        }
        // keep the next free slot in i, we will use this to push data in arr
        int i = next_slot;
        // update the next free slot using next[i]. next free slot will be used for next push operation
        next_slot = next[i];
        // now we use next in a different role, to keep the second top value in stack, 
        next[i] = top[sn];
        // update the top by i
        top[sn] = i;
        // push the data in arr[i]
        arr[i] = data;
}

// pop operator
int kStacks::pop(int sn)
{
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return INT_MAX;
        }
        if (is_empty(sn))
        {
                cout << "stack underflow! cann't pup!" << endl;
                return INT_MAX;
        }
        // keep the current index of stack sn
        int i = top[sn];
        // keep the previous index of stack sn in top
        top[sn] = next[i];
        // initialize the next[i] by next free slot
        next[i] = next_slot;
        // next free slot is current i
        next_slot = i;
        // return current value
        return arr[i];
}

// print the stack sn
void kStacks::print_sn(int sn)
{
        if (sn > k-1)
        {
                cout << "sn must be in [0...k-1]" << endl;
                return;
        }
        if (is_empty(sn))
        {
                cout << "no value to print" << endl;
                return;
        }

        int i = top[sn];
        
        while(next[i] != -1)
        {
                cout << arr[i] << " ";
                i =  next[i];
        }
        // for the last stack value with next[i] = -1;
        cout << arr[i] << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
        kStacks stack(3, 10);
        stack.push(0, 1);
        stack.push(0, 2);
        stack.push(0, 3);

        stack.push(1, 10);
        stack.push(1, 20);

        stack.push(2, 100);
        stack.push(2, 200);

        stack.print_sn(0);

        stack.pop(0);
        stack.pop(0);
        stack.print_sn(0);
        
        stack.print_sn(1);
        stack.print_sn(2);
        return 0;
}

3 Comments

Stack class: c++ code: we assume that there is not stack overflow error!

9/1/2015

2 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

A simple class of Stack!
 
By: Hamed Kiani (Sep. 1, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;


struct Node{
        int _data;
        Node* _next;
};

class myStack{
private:
        Node* _head;
        int _size;

public:
        myStack();
        ~myStack(); 
        void push(int data);
        void pop();
        Node* return_top();
        int get_size();
        bool is_empty();
        void clear();
        void print_stack();
};

// constructor
myStack::myStack()
{
        _head = NULL;
        _size = 0;
}
myStack::~myStack()
{
        clear();
}

// is empty function
bool myStack::is_empty()
{
        return (_size == 0);
}

// retrun the stack size
int myStack::get_size()
{
        return _size;
}

// puch on the top
void myStack::push(int data)
{
        Node* temp = new Node;
        temp->_data = data;
        temp->_next = _head;
        _head = temp;
        _size++;
}

// pop the top data
void myStack::pop()
{
        if (is_empty())
        {
                cout << " the stack is empty, poping faild" << endl;
                return;
        }

        Node* temp  = _head;
        _head = _head->_next;
        delete temp;
        _size--;
}

// return the pointer of the top value
Node* myStack::return_top()
{
        if (is_empty())
                return NULL;
        Node* temp = _head;
        return temp;
}

// empty the stack
void myStack::clear()
{
        while(_size)
                pop();
        cout << " stack is deleted" << endl;
}

// print the stack values
void myStack::print_stack()
{
        Node* temp = _head;
        while(temp != NULL){
                cout << temp->_data << " " ;
                temp = temp->_next;
        }
        cout << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
        myStack stack;  
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.print_stack();
        cout << stack.get_size() << endl;
        stack.pop();
        stack.print_stack();

        Node* temp = stack.return_top();
        cout << temp->_data << endl;

        return 0;
}

2 Comments

Linked list class in c++

7/26/2015

2 Comments

A brief tutorial for linked list from the Stanford University.

Linked list at Youtube:

Tutorial: https://www.youtube.com/watch?v=U-MfAoL6qjM

Reverse a linked list

Detect a loop in a linked list

Find the junction node of two lists

Find the mid point of a list by just one scanning

/******************************************************************************************
*******************************************************************************************
Chapter 2 Linked List: a class and three interview questions

By: Hamed Kiani (July 25, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
#include <cstring>
using namespace std;

// a struct of linked list node, 
// contains two elements, _data: the value of node, _next: a pointer to the next node/NULL
struct Node{
        int _data;
        Node* _next;
};


// LinkedList class, 
// private: 
//         _head: keeps the head address (first node)
//         _tail: keeps the tail address (last node)
//         _size: the number of nodes in a linked list

// public:
//         LinkedList(): constructor
//         ~LinkedList(): destructor
//         size(): return the _size of the list
//         addFront(data): add a node at begining/head of the list with _data = data 
//         addTail(data):  add a node at end/tail of the list with _data = data
//         deleteFront():  delete the first node of the list
//         deleteTail():   delete the tail node
//         getHead():              return the address of list's head
//         getTail():              return the address of list's tail
//         insertAfter(position, data):    instert a node with data value after the position address
//         deleteThisNode(position):               delete the node at the position address
//         searchInList(data):                             find data in the list
//         reverseList():                                  reverse the linked list
//         addWithList(listTemp):                  sum the list with the listTemp
//         appendTheList(listTemp):                append the listTemp to the end of the list
//         printList():                                    print the list
//         printListRecursion(temp):               recursion version of print list
//         remove_deuplicate_fun_1():              remove duplicate values in the list
//         nth_to_end_node(n):                             return the address of the n-th to end of the list


// class declaration

class LinkedList{

private:
        Node* _head;
        Node* _tail;
        int _size;

public:
        LinkedList();
        ~LinkedList();

        int size();

        void addFront(int data);
        void addTail(int data);

        void deleteFront();
        void deleteTail();

        Node* getHead();
        Node* getTail();

        void insertAfter(Node* position, int data);
        void deleteThisNode(Node* position);
        int searchInList(int data);

        void reverseList();

        void addWithList(const LinkedList *listTemp);
        void appendTheList(const LinkedList *listTemp);

        void printList();
        void printListRecursion(Node* temp);

        void remove_deuplicate_fun_1();
        Node* nth_to_end_node(int n);
};

LinkedList::LinkedList()
{
        _head = NULL;
        _tail = NULL;
        _size = 0;
}

LinkedList::~LinkedList()
{
        cout << "**********DESTRUCTOR***********" << endl;
        cout << "**********DESTRUCTOR***********" << endl;
        cout << "**********DESTRUCTOR***********" << endl;


        cout << "the destructor is called! deleting the linked list by calling deleteFront() function!" << endl;
        while (_size>0)
                deleteFront();
}

int LinkedList::size()
{
        return _size;
}

void LinkedList::addFront(int data)
{
        
        Node* nodeTemp = new Node;
        if (_head == NULL)
        {
                nodeTemp->_data = data;
                _head = nodeTemp;
                _tail = nodeTemp;
                nodeTemp->_next = NULL;
                _size = 1;
        }
        else
        {
                nodeTemp->_data = data;
                nodeTemp->_next = _head;
                _head = nodeTemp;
                _size++;
        }
        cout << "the value: " << data << " is added to the front of list! " <<
                "current size is: " << _size << endl;
}

void LinkedList::addTail(int data)
{
        Node* nodeTemp = new Node;
        nodeTemp->_data = data;
        nodeTemp->_next = NULL;

        if (_tail != NULL)
        {
                _tail->_next = nodeTemp;
                _tail = nodeTemp;
                _size++;
                cout << "the value: " << data << " is added to the tail of list! " <<
                        "current size is: " << _size << endl;
        }
        else
                addFront(data);
}

void LinkedList::printList()
{
        cout << "***********************************" << endl;
        cout << "The list containts: " << endl;
        int i = _size;
        Node* temp = _head;
        while (i>0)
        {
                cout << temp->_data << " " ;
                temp = temp->_next;
                i--;
        }
        cout << endl;
        cout << "***********************************" << endl;
}

void LinkedList::deleteFront()
{
        if (_head == NULL)
                return;
        int data = _head->_data;
        Node* temp;
        temp = _head;
        if (_head->_next == NULL)
        {
                _head = NULL;
                _tail = NULL;
        }
        else
                _head = _head->_next;
        _size--;
        delete temp;
        cout << "the value: " << data << " is deleted from the front of list! " <<
                "current size is: " << _size << endl;
}

void LinkedList::deleteTail()
{
        if (_tail == NULL)
                return;
        int data = _tail->_data;
        Node* temp = _head;
        while (temp->_next != _tail)
                temp = temp->_next;
        _tail = temp;
        temp = temp->_next;
        _tail->_next = NULL;
        delete temp;
        _size--;
        cout << "the value: " << data << " is deleted from the tail of list! " <<
                "current size is: " << _size << endl;
}


Node* LinkedList::getHead()
{
        return _head;
}

Node* LinkedList::getTail()
{
        return _tail;
}

void LinkedList::insertAfter(Node* position, int data)
{
        if (position == NULL)
        {
                addFront(data);
                return;
        }
        if (position->_next == NULL)
        {
                addTail(data);
                return;
        }

        Node* temp = new Node;
        temp->_data = data;
        temp->_next = position->_next;
        position->_next = temp;
        _size++;
}

void LinkedList::deleteThisNode(Node* position)
{
        if (position == NULL)
                return;
        if (position == _head)
        {
                deleteFront();
                return;
        }
        if (position->_next == NULL)
        {
                deleteTail();
                return;
        }
        Node * temp = _head;
        while (temp->_next != position)
                temp = temp->_next;
        temp->_next = position->_next;
        delete position;
        _size--;
}


int LinkedList::searchInList(int data)
{
        Node* temp = _head;
        int i = 1;
        while (temp != NULL)
        {
                if (temp->_data == data) return i;
                temp = temp->_next;
                i++;
        }
        return -1;
}

void LinkedList::reverseList()
{
        // keep the next node to add to reverse list. 
        Node* next;
        // keep the head of the reversed list so far.
        // at the first, the reversed list is empty - null
        Node* prev = NULL;
        // a loop to traverse the list
        while (_head)
        {
                next = _head->_next;
                _head->_next = prev;
                prev = _head;
                _head = next;
        }
        // at the end, the head of reversed list is pointed by prev
        _head = prev;

        // we need to update the tail too
        next = _head;
        while (next->_next != NULL)
                next = next->_next;
        _tail = next;
}


void LinkedList::addWithList(const LinkedList *listTemp)
{
        int s = listTemp->_size;
        if (s != _size)
                return;
        Node* t1 = listTemp->_head;
        Node* t2 = _head;

        while (t1 != NULL)
        {
                t2->_data += t1->_data;
                t1 = t1->_next;
                t2 = t2->_next;
        }
}

void LinkedList::appendTheList(const LinkedList *listTemp)
{
        Node* temp = listTemp->_head;
        while (temp != NULL)
        {
                Node* newNode = new Node;
                newNode->_data = temp->_data;
                newNode->_next = NULL;
                _tail->_next = newNode;
                _tail = _tail->_next;
                temp = temp->_next;
                _size++;
        }
}

void LinkedList::printListRecursion(Node* temp)
{
        if (temp == NULL)
                return;
        printListRecursion(temp->_next);
        cout << temp->_data << endl;
}


// inplace removing, O(n^2) time and O(1) additional space
void LinkedList::remove_deuplicate_fun_1()
{
        Node *head;
        Node *end;
        head = _head;
        int l = 0;
        if (!head)
                return;
        end = head->_next;
        Node *c;
        head = head->_next;
        while (head != NULL)
        {
                c = _head;
                while (c != end){
                        if (c->_data == head->_data)
                                break;
                        else
                                c = c->_next;
                }
                if (c == end)
                {
                        end->_data = head->_data;
                        end = end->_next;
                }
                head = head->_next;
        }
        head = _head;
        while (head->_next != end)
        {
                l++;
                head = head->_next;
                _tail = head;
        }
        _size = ++l;
        head->_next = NULL;
        _tail->_next = NULL;
}


Node* LinkedList::nth_to_end_node(int n)
{
        Node *p, *q;
        p = _head;
        q = _head;
        int i = 0;
        while (i < n & q != NULL)
        {
                q = q->_next;
                i++;
        }
        if (q == NULL)
                return NULL;
        while (q->_next != NULL)
        {
                q = q->_next;
                p = p->_next;
        }
        return p;
}


//         some useful functions and linked list questions
int pow(int a, int b)
{
        if (b == 0)
                return 1;
        return a*pow(a, b - 1);
}

// time: O(N), additional space:O(N)
void add_two_lists(LinkedList* l1, LinkedList* l2, LinkedList* l3)
{
        if (!l1 & !l2)
                return;
        if (!l1)
                l3 = l2;
        if (!l2)
                l3 = l1;

        // convert the linked list to a decimal digit
        int d1 = 0;
        int d2 = 0;
        int i  = 0;

        Node* temp1 = l1->getHead();
        Node* temp2 = l2->getHead();
        while (temp1 != NULL)
        {
                d1 += temp1->_data * pow(10, i);
                temp1 = temp1->_next;
                i++;
        }
        cout << "the digit of first link: " << d1 << endl;
        i = 0;
        while (temp2 != NULL)
        {
                d2 += temp2->_data * pow(10, i);
                temp2 = temp2->_next;
                i++;
        }
        cout << "the digit of 2nd link: " << d2 << endl;

        int add = d1 + d2;
        while ((add) > 0)
        {
                l3->addFront(add % 10);
                add /= 10;
        }
}

// without converting to decimal and re-digiting into the third linked list
void add_two_lists_2(LinkedList* l1, LinkedList* l2, LinkedList* l3)
{
        if (!l1 & !l2)
                return;
        if (!l1)
                l3 = l2;
        if (!l2)
                l3 = l1;
        int carry = 0;
        Node* temp1 = l1->getHead();
        Node* temp2 = l2->getHead();
        while (temp1 || temp2)
        {
                int t1 = (!temp1) ? 0 : temp1->_data;
                int t2 = (!temp2) ? 0 : temp2->_data;
                l3->addFront((t1 + t2 + carry) % 10);
                carry = (t1 + t2 + carry) / 10;
                if (temp1 != NULL)
                        temp1 = temp1->_next;
                if (temp2 != NULL)
                        temp2 = temp2->_next;
        }
        if (carry > 0)
                l3->addFront(1);
}

//         find the joint node of two linked list: time O(N), memory: O(N)
Node* find_joint_node_of_two_links(Node* h1, Node* h2)
{
        if (!h1 | !h2)
                return NULL;
        int l1, l2;
        l1 = 0;
        l2 = 0;
        Node *temp = h1;
        while (temp != NULL)
        {
                l1++;
                temp = temp->_next;
        }
        temp = h2;
        while (temp != NULL)
        {
                l2++;
                temp = temp->_next;
        }
        int diff = (l1 - l2>0) ? (l1 - l2) : (l2 - l1);
        for (int i = 0; i < diff; i++)
        {
                if (l1 > l2)
                        h1 = h1->_next;
                else
                        h2 = h2->_next;
        }

        while (h1 != NULL & h2 != NULL){
                if (h1 == h2)
                        return h1;
                h1 = h1->_next;
                h2 = h2->_next;
        }
        return NULL;
}

// check if there is a loop in the linked list
Node* is_loop_in_linkedlist(Node* head)
{
        Node* slow = head;      // moves one node
        Node* fast = head;      // moves two nodes

        if (!head)
                return NULL;

        while (fast != NULL & fast->_next != NULL & slow != NULL)
        {
                slow = slow->_next;
                fast = fast->_next->_next;
                if (fast == slow)
                        return slow;
        }
        return NULL;
}

// check the video and description in the post for more details
Node* find_the_first_node_of_loop(Node* head)
{
        Node* meetPoint = is_loop_in_linkedlist(head);
        if (meetPoint == NULL)
                return NULL;

        Node* temp;
        temp = head;
        while (temp != meetPoint)
        {
                temp = temp->_next;
                meetPoint = meetPoint->_next;
        }
        return temp;
}
void main() {
        // test the basics functions
        // a linked list object with five nodes
        LinkedList myList;
        myList.addFront(5);
        myList.addFront(4);
        myList.addFront(3);
        myList.addFront(2);
        myList.addFront(1);

        // print the list
        myList.printList();
        // myList.printListRecursion(myList.getHead());

        // add to the tail
        myList.addTail(1);
        myList.addTail(3);
        myList.addTail(3);

        // print the list
        myList.printList();

        cout << "delete from front" << endl;
        myList.deleteFront();
        myList.deleteTail();
        myList.printList();

        // print the head and tail values
        Node* tail = myList.getTail();
        Node* head = myList.getHead();

        cout << "the value in the first node is: " << head->_data << endl;
        cout << "the value in the last node is: "  << tail->_data << endl;

        // insert a node in the list
        cout << "insert a new value of " << 200 << " in the third place: " << endl;
        Node* position = myList.getHead();
        myList.insertAfter(position->_next, 200);
        myList.printList();
        
        // delete a node from the list
        cout << "delete the third node: " << endl;
        position = myList.getHead();
        myList.deleteThisNode(position->_next->_next);
        myList.printList();

        // search a value in the linked list
        int pos = myList.searchInList(10);
        (pos < 0) ? (cout << "the value 10 is no found" << endl) : (cout << "the value 10 is found at node : " << pos << endl);

        // reverse the list
        myList.reverseList();
        myList.printList();

        // a new linked list object
        LinkedList myList_2;
        myList_2.addFront(7);
        myList_2.addFront(6);
        myList_2.addFront(5);
        myList_2.addFront(4);
        myList_2.addFront(4);
        myList_2.addFront(4);

        // adding the myList_2 to myList
        myList.addWithList(&myList_2);
        myList.printList();

        // appending two lists
        myList.appendTheList(&myList_2);
        myList.printList();

        // remove duplicates form myList
        myList.remove_deuplicate_fun_1();
        myList.printList();

        // return the n-th node to the end
        int n = 4;
        position = myList.nth_to_end_node(n);
        if (position)
                cout << " the " << n << " to end element is :" << position->_data << endl;
        else
                cout << "is longer the length of the list ! " << endl;

        // Problem1: adding the values of two linked lists
        LinkedList myList_3;

        add_two_lists(&myList, &myList_2, &myList_3);
        // add_two_lists_2(&myList, &myList_2, &myList_3);
        myList_3.printList();

        // Problem 2: find the junction of two lists

        Node n1, n2, n3, n4, n5, n6;
        n1._data = 1;
        n2._data = 2;
        n3._data = 3;
        n4._data = 4;
        n5._data = 5;
        n6._data = 6;
        n1._next = &n2;
        n2._next = &n3;
        n3._next = &n4;
        n4._next = &n5;
        n5._next = NULL;
        n6._next = &n4;
        Node* conj = find_joint_node_of_two_links(&n1, &n6);
        if (!conj)
                cout << "there is no conjuction  " << endl;
        else
                cout << "the conjuction node contains the value of : " << conj->_data << endl;
        
        // Problem 3: is there a cycle in the linked list
        n1._next = &n2;
        n2._next = &n3;
        n3._next = &n4;
        n4._next = &n5;
        n5._next = &n2;
        conj = is_loop_in_linkedlist(&n1);
        if (conj)
                cout << "there is a loop" << endl;
        else
                cout << "there is not loop" << endl;

        // Problem 4: if there is a cycle in the linked list, return the start node of the loop
        
        conj = find_the_first_node_of_loop(&n1);
        if (conj)
                cout << "the value of the start-loop node is : " << conj->_data << endl;
        else
                cout << "there is not loop" << endl;               
}

2 Comments

A method isSubstring which checks if one word is a substring of another, use this method to check if two strings are rotated.

7/20/2015

3 Comments

/******************************************************************************************
*******************************************************************************************
Chapter 1 Arrays and Strings

 * Assume you have a method isSubstring which checks if one word is a substring of another.
 * Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
 * only one call to isSubstring (i.e., "waterbottle" is a rotation of "erbottlewat")
 
By: Hamed Kiani (July 20, 2015)
******************************************************************************************
******************************************************************************************/

#include<iostream>
#include<cstring>

using namespace std;

bool is_sub_string(const char* s1, const char* s2)
{
        // check if two strings are not null
        if (!s1 || !s2)
                return false;
        // find the first char of s2, s2[0] in the s1, if found then check the rest of s2 over s1
        int i,j ;
        j = 0;
        for (i = 0; s1[i] != '\0'; i++)
        {
                if (s1[i] == s2[0]) {
                        for(j = 1; s2[j] != '\0'; j++)                    
                                // we are already sure that s1[i] == s2[0]
                                if (s2[j] != s1[i+j])
                                        break;
                }
                // if (s2[j] == '\0') means that we have similar chars till the end of s2
                if (s2[j] == '\0')
                        return true;
        }
        // is not s sub string
        return false;
}

// O(n) time, O(1) additional space.
bool is_rotation_fun1(const char* s1, const char* s2)
{
        if (!s1 || !s2)
                return false;
        if (strlen(s1) != strlen(s2))
                return false;

        while(*s2 != '\0')
                s2++;
        s2--;
        while(*s1 != '\0')
        {
                if (*s1 != *s2)
                        return false;
                s1++; s2--;
        }       
        return true;
}

// O(n) time, O(n) additional space.
// using is_rotation function
// the trick is that we append the inverse of s1 to s1 and then check:
// if is_sub_string(s1+inv(s1[1:length(s1)-1]), s2).
// name + man = nameman
// is is_sub_string(nameman, eman)
bool is_rotation_fun2(  char* s1,   char* s2)
{
        int l1;
        l1 = strlen(s1);            
        char* temp = (char *) malloc( sizeof(char) * l1 * 2);
        char *t1 = s1;   
        int i = 0;
        while(*t1 != '\0')
        {
                temp[i] = *t1;
                t1++; i++;
        }
        // move t1 pointin to end of s1 to next to last char. 
        // accordingly, we change l1 = l1 -2, since we ignore the last char of s1 
        //and consider length counter as [0...strlen(s1)-1]
        t1 -= 2; l1 -= 2;
        while(l1>=0)
        {
                temp[i] = s1[l1];
                l1--; i++;
        }       
        bool check = is_sub_string(temp, s2);
        free(temp);
        return check;
}

void main() {
        char str1[] = "check this string";
        char str2[] = "this";
        bool check ;
        check = is_sub_string(str1,str2);
        cout << check << endl;

        char str3[] = "siht";
        check = is_rotation_fun1(str3, str2);
        cout << check << endl;

        check = is_rotation_fun2(str3, str2);
        cout << check << endl;
}

3 Comments

<<Previous

A class implementation of Binary Search Tree in C++

Write a program to sort a stack in ascending order. c++

Implement a MyQueue class which implements a queue using two stacks : c++

Imagine a (literal) stack of plates.If the stack gets too high, it might topple.Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this.Implement

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.We design this class using array instead of linkedlist

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

A class of K Stacks in a single array! Efficient memory and run time.: c++

Stack class: c++ code: we assume that there is not stack overflow error!

Linked list class in c++

A method isSubstring which checks if one word is a substring of another, use this method to check if two strings are rotated.

Author

Categories

Archives