Basics

Question 1

What are the two types of data structure? Give examples.

Answer 1

linear structures and hierarchical structures. Arrays, linked lists, stacks, and queues are linear structures, while trees, graphs, heaps etc. are hierarchical structures.

Question 2

What is a heap?

Answer 2

Heap is a binary tree that stores a collection of keys by satisfying heap property. Max heap and min heap are two flavors of heap data structure. The heap property for max heap is: each node should be greater than or equal to each of its children. While, for min heap it is: each node should be smaller than or equal to each of its children. Heap data structure is usually used to implement priority queues.

Question 3

What is a hash table?

Answer 3

Hash Table is again a data structure that stores data in form of key-element pairs. A key is a non-null value which is mapped to an element. And, the element is accessed on the basis of the key associated with it. Hash table is a useful data structure for implementing dictionary.

Question 4

What are linked lists and what are they good / bad at?

Answer 4

Stores data with nodes that point to other nodes.
Nodes, at its most basic it has one datum and one reference (another node). Designed to optimize insertion and deletion, slow at indexing and searching.

Question 5

Big O of Linked Lists

Answer 5

Indexing: Linked Lists: O(n)
Search: Linked Lists: O(n)
Optimized Search: Linked Lists: O(n)
Insertion: Linked Lists: O(1)

Question 6

Big O of Arrays

Answer 6

Indexing: Linear array: O(1), Dynamic array: O(1)
Search: Linear array: O(n), Dynamic array: O(n)
Optimized Search: Linear array: O(log n), Dynamic array: O(log n)
Insertion: Linear array: n/a Dynamic array: O(n)

Question 7

What is the hash used for?

Answer 7

Designed to optimize searching, insertion, and deletion.

Indexing: Hash Tables: O(1)
Search: Hash Tables: O(1)
Insertion: Hash Tables: O(1)

Question 8

What are hash collisions?

Answer 8

Hash collisions are when a hash function returns the same output for two distinct outputs.

Question 9

What is a degenerate tree?

Answer 9

An unbalanced tree, which if entirely one-sided is a essentially a linked list.

Question 10

What are binary trees and what are they good at?

Answer 10

Designed to optimize searching and sorting.
Indexing: Binary Search Tree: O(log n)
Search: Binary Search Tree: O(log n)
Insertion: Binary Search Tree: O(log n)
Is a tree like data structure where every node has at most two children. left and right nodes.

Question 11

What is Breadth First Search?

Answer 11

An algorithm that searches a tree (or graph) by searching levels of the tree first, starting at the root.
It finds every node on the same level, most often moving left to right.
While doing this it tracks the children nodes of the nodes on the current level.
When finished examining a level it moves to the left most node on the next level.

Question 12

What data structure is used when performing a BFS?

Answer 12

Queue

Question 13

What is Depth First Search?

Answer 13

An algorithm that searches a tree (or graph) by searching depth of the tree first, starting at the root.
It traverses left down a tree until it cannot go further.
Once it reaches the end of a branch it traverses back up trying the right child of nodes on that branch, and if possible left from the right children.
When finished examining a branch it moves to the node right of the root then tries to go left on all it’s children until it reaches the bottom.

Question 14

What data structure is used when performing a DFS?

Answer 14

Stack

Question 15

BFS vs DFS

Answer 15

For wide, shallow trees use Breadth First Search

For deep, narrow trees use Depth First Search

Question 16

What is the merge sort?

Answer 16

A comparison based sorting algorithm

• Divides entire dataset into groups of at most two.
• Compares each number one at a time, moving the smallest number to left of the pair.
• Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
• repeat process till one set

Question 17

What is merge sort efficiency?

Answer 17

Best Case Sort: Merge Sort: O(n)
Average Case Sort: Merge Sort: O(n log n)
Worst Case Sort: Merge Sort: O(n log n)

Question 18

What is the quick sort?

Answer 18

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

Pick an element, called a pivot, from the array.
Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Question 19

What is the quick sort efficiency?

Answer 19

Best Case Sort: Merge Sort: O(n)
Average Case Sort: Merge Sort: O(n log n)
Worst Case Sort: Merge Sort: O(n^2)

Question 20

What is the Bubble sort?

Answer 20

A comparison based sorting algorithm
It iterates left to right comparing every couplet, moving the smaller element to the left.
It repeats this process until it no longer moves and element to the left.

Question 21

What is the bubble sort complexity?

Answer 21

Best Case Sort: Merge Sort: O(n)
Average Case Sort: Merge Sort: O(n^2)
Worst Case Sort: Merge Sort: O(n^2)

Question 22

What is the selection sort?

Answer 22

Scan through the array each time selecting the index of the smallest value. swap smallest index with currently unsorted index. repeat till through list. O(n^2)

Question 23

What is the insertion sort?

Answer 23

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Best O(N), Average O(N^2), Worst O(N^2)

Question 24

What is the heap sort?

Answer 24

Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum
Best O(N), Average O(NlogN), Worst O(NLogN)