What is a data structure?

  • Used for organization and modification of data.

What are the two types of data structures?

  1. Linear: Elements result in a sequence or linear list. Examples: arrays, linked lists, stacks, etc.
  2. Non-linear: Traversal of nodes is not done in a sequential manner. Examples: trees, graphs, etc.

What is an array?

  • A collection of the same data type that are stored at contiguous memory locations (memory locations are adjacent to each other in memory).
  • Insertion takes O(n) time since you would need to shift elements down.
  • Deletion takes O(n) time since you would need to shift elements up.
  • Arrays use random access–can access certain elements directly by referring to their indeces. Thus, readings will take O(1) time.

What is a multidimensional array?

  • An array that spans across more than one dimension.

What is a linked list?

  • Sequence of nodes where every node is connected to the next node by a reference pointer.
  • A collection of elements can be of different data types.
    • Each element will hold the address of the next element in the list (reference dependent) and other data that is relevant.
    • It uses sequential access–can only read elements one at a time starting from the first node. Thus, it takes O(n) time.
    • Can view it as a treasure hunt–address will basically say, Oh, the next item will be stored in this specific location!"
  • Elements are not stored in adjacent memory locations–they are NOT contiguous.
  • EVERY linked-list has a head and tail node
    • Head = start of the linked-list
    • Tail = end of the linked-list

How are linked lists more efficient than arrays?

  • Insertion and deletion
  • Dynamic data structure
  • No wastage of memory

Scenarios when you can use linked lists and arrays?

  • Linked list over array
    • When you do not know the exact number of elements beforehand.
  • Array over linked list
    • Know the exact number of elements beforehand.

What is a doubly-linked list?

  • Linked list where nodes have two references.
    • Reference to next node in sequence
    • Reference to previous node in sequence.

What is a stack?

  • LIFO (Last In First Out)
  • Push, pop, peek are basic operations

What is a queue?

  • FIFO (First In First Out)
  • Enqueue, dequeue, get front, get rear are basic operations.

How is a stack different from a queue?

  • In a stack, the item that is most recently added is removed first whereas in a queue, the item least recently added is removed first.

How to implement a queue using stacks?

  • Using 2 stacks.

How to implement a stack using queues?

  • Using 2 queues.

What is a hashmap?

  • Implementation of a hash table data structure allows basic operations in constant time O(1).

Can we store a duplicate key in a hashmap?

  • no.

Which data structures are used for implementing cache?

  1. Queue: Using doubly-linked list. Maximum size of queue is determined by cache size. Least recently used will be at the front of queue.
  2. Hashmap: Stores the page number as the key along with address of corresponding queue node as value.

What is a priority queue?

  • Queue but with priority assigned to elements.
  • Elements with higher priority are processed first.

What is a tree?

  • Recursive, non-linear data structure consisting of the set of one or more elements where one node is designated as the root and the remaining nodes are called children of the root.
  • Tree organizes data into a hierarchical manner.

What is a binary tree?

  • Tree where each node can have AT MOST two children.

What is the maximum number of nodes in a binary tree of height k?

  • (2^k+1) - 1, where k >= 1.

What are tree traversals?

  • Process of visiting all nodes of a tree.
  • Inorder, preorder, postorder

What is a binary search tree (BST)?

  • Variant of binary tree where the values of nodes in the left sub-tree are less than the root and values of nodes in the right sub-tree are greater than the root.

What is an AVL tree?

  • Height balancing BST.
  • Checks the height of left and right sub-trees and assures that the difference is NOT more than 1.

What is a graph?

  • Non-linear data structure that consists of vertices and edges.
  • Edges connecting nodes may be directed or undirected.

How do you represent a graph?

  1. Adjacency matrix: Used for sequential data representation.
  2. Adjacency list: Used to represent linked data.

What is the difference between a tree and a graph?

  • Trees must be connected and can NEVER have loops; graphs have no restrictions.
  • Trees are hierarchical and graphs follow a network model.