DSA Interview Q&A: Stacks, Queue, Linked Listsand Tree

Title: Mastering Data Structures and Algorithms: Interview Questions and Answers

Introduction: In this blog post, we will explore essential interview questions related to three fundamental data structures: stacks, queues, and linked lists, as well as binary trees. Each data structure will be accompanied by five well-detailed questions and their answers. Furthermore, we will provide code examples in three popular programming languages: Java, C++, and JavaScript. So, let's dive in!

Table of Contents:

1. Stacks 1.1 Stack Basics 1.2 Interview Questions and Answers

2. Queues 2.1 Queue Basics 2.2 Interview Questions and Answers

3. Linked Lists 3.1 Linked List Basics 3.2 Interview Questions and Answers

4. Binary Trees 4.1 Binary Tree Basics 4.2 Interview Questions and Answers

5. Stacks: 1.1 Stack Basics: A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. It can be implemented using an array or a linked list.

1.2 Interview Questions and Answers: Q1. Implement a stack using an array in Java. A1. Here's the Java code for implementing a stack using an array:

javaCopy code
public class Stack {
    private int maxSize;
    private int top;
    private int[] stackArray;

    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int value) {
        if (top == maxSize - 1) {
            System.out.println("Stack Overflow");
        } else {
            stackArray[++top] = value;
        }
    }

    public int pop() {
        if (top == -1) {
            System.out.println("Stack Underflow");
            return -1;
        } else {
            return stackArray[top--];
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }
}

Q2. Explain the time complexity of various stack operations. A2. The time complexity of stack operations is as follows:

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• isEmpty: O(1)

Q3. How can you implement a stack using a linked list in C++? A3. Here's the C++ code for implementing a stack using a linked list:

cppCopy code
class Node {
public:
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = nullptr;
    }

    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            cout << "Stack Underflow" << endl;
            return -1;
        } else {
            int value = top->data;
            Node* temp = top;
            top = top->next;
            delete temp;
            return value;
        }
    }

    bool isEmpty() {
        return (top == nullptr);
    }
};

Q4. What is the space complexity of a stack implemented using a linked list in JavaScript? A4. The space complexity of a stack implemented using a linked list in JavaScript is O(n), where n is the number of elements in the stack.

Q5. Explain the concept of stack unwinding. A5. Stack unwinding refers to the process of deallocating resources and reversing the effects of function calls when an exception occurs. It involves popping the stack frames of the called functions until an exception handler is found or the program terminates. This ensures proper cleanup and prevents memory leaks.

2. Queues: 2.1 Queue Basics: A queue is a linear data structure that follows the FIFO (First In, First Out) principle. It can be implemented using an array or a linked list.

2.2 Interview Questions and Answers: Q1. Implement a queue using an array in Java. A1. Here's the Java code for implementing a queue using an array:

javaCopy code
public class Queue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] queueArray;

    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
    }

    public void enqueue(int value) {
        if (rear == maxSize - 1) {
            System.out.println("Queue Overflow");
        } else {
            queueArray[++rear] = value;
        }
    }

    public int dequeue() {
        if (front > rear) {
            System.out.println("Queue Underflow");
            return -1;
        } else {
            return queueArray[front++];
        }
    }

    public boolean isEmpty() {
        return (front > rear);
    }
}

Q2. Explain the time complexity of various queue operations. A2. The time complexity of queue operations is as follows:

• Enqueue: O(1)
• Dequeue: O(1)
• Peek: O(1)
• isEmpty: O(1)

Q3. How can you implement a queue using a linked list in C++? A3. Here's the C++ code for implementing a queue using a linked list:

cppCopy code
class Node {
public:
    int data;
    Node* next;
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = nullptr;

        if (rear == nullptr) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    int dequeue() {
        if (front == nullptr) {
            cout << "Queue Underflow" << endl;
            return -1;
        } else {
            int value = front->data;
            Node* temp = front;
            front = front->next;

            if (front == nullptr)
                rear = nullptr;

            delete temp;
            return value;
        }
    }

    bool isEmpty() {
        return (front == nullptr);
    }
};

Q4. What is the space complexity of a queue implemented using a linked list in JavaScript? A4. The space complexity of a queue implemented using a linked list in JavaScript is O(n), where n is the number of elements in the queue.

Q5. What is a priority queue, and how does it differ from a regular queue? A5. A priority queue is an abstract data type that stores elements along with their associated priorities. Unlike a regular queue, where elements are processed in the order of their arrival, a priority queue retrieves elements based on their priority. Elements with higher priority are dequeued first. It can be implemented using heaps or self-balancing binary search trees.

3. Linked Lists: 3.1 Linked List Basics: A linked list is a linear data structure that consists of nodes linked together via pointers. Each node contains data and a reference to the next node.

3.2 Interview Questions and Answers: Q1. Implement a singly linked list in Java. A1. Here's the Java code for implementing a singly linked list:

javaCopy code
class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = null;
    }
}

class LinkedList {
    Node head;

    void insert(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

Q2. Explain the time complexity of various linked list operations. A2. The time complexity of linked list operations is as follows:

• Insertion at the end: O(n)
• Deletion at the end: O(n)
• Searching for an element: O(n)
• Insertion at the beginning: O(1)
• Deletion at the beginning: O(1)

Q3. How can you implement a doubly linked list in C++? A3. Here's the C++ code for implementing a doubly linked list:

cppCopy code
class Node {
public:
    int data;
    Node* prev;
    Node* next;

    Node(int value) {
        data = value;
        prev = nullptr;
        next = nullptr;
    }
};

class DoublyLinkedList {
private:
    Node* head;

public:
    DoublyLinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node(value);

        if (head == nullptr) {
            head = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

Q4. What is the space complexity of a doubly linked list implemented in JavaScript? A4. The space complexity of a doubly linked list implemented in JavaScript is O(n), where n is the number of elements in the linked list.

Q5. What are the advantages and disadvantages of using linked lists? A5. Advantages of linked lists include dynamic size, efficient insertion and deletion at the beginning, and better memory utilization. Disadvantages include higher memory overhead compared to arrays, slower access to elements, and the need for additional memory for storing pointers.

4. Binary Trees: 4.1 Binary Tree Basics: A binary tree is a hierarchical data structure consisting of nodes where each node has at most two children: left and right.

4.2 Interview Questions and Answers: Q1. Implement a binary tree in Java. A1. Here's the Java code for implementing a binary tree:

javaCopy code
class Node {
    int data;
    Node left;
    Node right;

    Node(int value) {
        data = value;
        left = null;
        right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    void insert(int value) {
        root = insertRec(root, value);
    }

    Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }

        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }
}

Q2. Explain the time complexity of various binary tree operations. A2. The time complexity of binary tree operations is as follows:

• Insertion: O(log n) on average (for balanced trees), but O(n) in the worst case (for skewed trees)
• Deletion: O(log n) on average (for balanced trees), but O(n) in the worst case (for skewed trees)
• Searching: O(log n) on average (for balanced trees), but O(n) in the worst case (for skewed trees)
• Traversals (in-order, pre-order, post-order): O(n)

Q3. How can you implement a binary search tree (BST) in C++? A3. Here's the C++ code for implementing a binary search tree:

cppCopy code
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

class BinarySearchTree {
private:
    Node* root;

public:
    BinarySearchTree() {
        root = nullptr;
    }

    void insert(int value) {
        root = insertRec(root, value);
    }

    Node* insertRec(Node* root, int value) {
        if (root == nullptr) {
            root = new Node(value);
            return root;
        }

        if (value < root->data) {
            root->left = insertRec(root->left, value);
        } else if (value > root->data) {
            root->right = insertRec(root->right, value);
        }

        return root;
    }
};

Q4. What is the space complexity of a binary tree implemented in JavaScript? A4. The space complexity of a binary tree implemented in JavaScript is O(n), where n is the number of nodes in the tree.

Q5. Explain the difference between a binary tree and a binary search tree. A5. A binary tree is a general tree structure where each node can have at most two children. In contrast, a binary search tree (BST) is a binary tree where the left child of a node contains a value less than the node's value, and the right child contains a value greater than the node's value. This property allows for efficient searching, insertion, and deletion operations in logarithmic time complexity.