Overview

Question 1

What is a data structure

Answer 1

Data structures are a way to store data in an efficient manner inside the Random Access Memory, called “RAM”

Question 2

What is an array

Answer 2

An array is a collection of ordered, contiguous (next to each other in memory) group of elements

Question 3

What is a byte

Answer 3

8 bits

Question 4

What is RAM measured in

Answer 4

Bytes

Question 5

What is a bit

Answer 5

A position that can store a 0 or 1

Question 6

Integer size

Answer 6

4 bytes

Question 7

What are the two components of RAM that are stored

Answer 7

Value and Address

Question 8

Char size

Answer 8

1 byte (typically if they are ASCII characters)

Question 9

Array sizing

Answer 9

Since arrays are contiguous and of fixed size and we don’t know if spots in RAM are open or not, we can’t always just add to the initial array. And we can’t have one array be split amongst the RAM. Order of the values matters as well. Biggest limitation of static arrays. Python and stuff have dynamic arrays as default.

Question 10

Dynamic array sizing

Answer 10

A new array will get created (typically twice the size of the first) for more space

Question 11

What can be used to implement a stack?

Answer 11

A dynamic array
Python: myArr = [] # default dynamic array
C++: vector<int> myArr</int>

Question 12

What’s a good way to think about a stack?

Answer 12

Instead of horizontal, think of it as vertical. So when we say we’re pushing on to the top of the stack it means we are throwing a value to the “top” or “end” and it will land at the next available spot. We don’t have to worry about the space since it’s dynamic array. When we pop we can only do it from the “end” or “top” of the array.

Question 13

What is the difference between linked lists and arrays in memory?

Answer 13

Arrays are stored contiguously in memory. Linked lists have no order to them in memory, but the addresses are “linked” together. They can be in some random order but connected via pointers.

Question 14

What are Queues?

Answer 14

FIFO, first in first out
For example, print jobs. If multiple people are trying to print documents, it will be handled on a first come first serve basis.

It is an abstract interface, similar to a stack and can be implemented by multiple data structures, provided that they fulfill the contract of implementing enqueue and dequeue operations.

Question 15

What is the most common implementation of a queue?

Answer 15

Using a linked list

Question 16

What are the operations of a queue?

Answer 16

Enqueue and dequeue:
Enqueue adds elements to the tail (end) of the queue, which runs in O(1) time.

Dequeue removes elements from the head (front) of the queue, which can be O(1) (or O(n) if implemented using an array)

Question 17

What is a deque (pronounced “deck”)

Answer 17

Double-ended queue. Allows you to add and remove elements from both the head and the tail.

Question 18

What is one of the more important use cases of queues?

Answer 18

Performing breadth-first search for trees and graphs

Question 19

What is the best way to represent recursion?

Answer 19

Using a decision tree (one-branch or more)