1. What is the difference between a stack and a queue? How are they implemented using arrays or linked

lists?

A stack is a linear data structure that follows the LIFO (Last In First Out) principle, meaning that the last

element inserted is the first one to be removed. A queue is also a linear data structure that follows the FIFO

(First In First Out) principle, meaning that the first element inserted is the first one to be removed. Both

stacks and queues can be implemented using arrays or linked lists. For arrays, a stack can use either the

beginning or the end of the array as the top, and a queue can use either the beginning or the end of the array

as the front. For linked lists, a stack can use either the head or the tail as the top, and a queue can use the

head as the front and the tail as the rear.

2. What is a binary search tree? What are its properties and applications?

A binary search tree (BST) is a binary tree data structure that satisfies the following properties: for any node

in the tree, all the nodes in its left subtree have values less than or equal to its value, and all the nodes in its

right subtree have values greater than or equal to its value. A BST supports efficient search, insertion,

deletion, and traversal operations. Some applications of BSTs are: sorting, searching, indexing, priority

queues, symbol tables, etc.

3. What is a hash table? How does it work and what are its advantages and disadvantages?

A hash table is a data structure that maps keys to values using a hash function. A hash function takes a key

as input and returns an integer value called a hash code, which is used to index an array of buckets or slots

where the values are stored. A hash table works by applying the hash function to the key and accessing the

corresponding bucket or slot in the array. If there is more than one value stored in the same bucket or slot,

then a collision occurs and a resolution technique is needed to handle it. Some common collision resolution

techniques are: chaining, linear probing, quadratic probing, double hashing, etc. The advantages of hash

tables are: fast access, insertion, and deletion operations; dynamic resizing; flexible keys; etc. The

disadvantages of hash tables are: possible collisions; wasted space; unpredictable order; etc.

4. What is an algorithm? What are some criteria to measure its efficiency and quality?

An algorithm is a finite sequence of well-defined steps or instructions that solves a problem or performs a

task. Some criteria to measure its efficiency and quality are: correctness, completeness, optimality, time

complexity, space complexity, simplicity, readability, modularity, robustness, etc.

5. What are some common sorting algorithms? How do they work and what are their time and space

complexities?

Some common sorting algorithms are: selection sort, insertion sort, bubble sort, merge sort, quick sort, heap

sort, radix sort, etc. They work by comparing and rearranging elements in an array or list until they are in a

desired order (ascending or descending). Their time and space complexities vary depending on the algorithm

design and implementation. For example:

- Selection sort works by finding the smallest (or largest) element in each iteration and placing it at its