Week 1 Big O/ data structures

Question 1

What is a Datastructure?

Answer 1

a data organization, management and storage format that enable efficient access and modification through convenient operators .

Question 2

Arrays

Answer 2

a basic data structure with homogeneous data type referenced by index, contiguous locations.
Order: sequential
great for random access if you know the index, bad if you have to search throughout the array.
O(1) for accessing (time accessing
O(n) for searching, insertion, and deletion
O(log n) for binary searching

Question 3

Linked list

Answer 3

A sequence of data structures are called nodes in which one nodes reference points to the next. The first node is called the head, the last is
called the tail.
Single linked list - each node points to the next one
double linked list
circle linked list tail points back to the head. hence you get a circle.

O(n) accessing and searching elements
O(1) insertion and deletion

Question 4

stack

Answer 4

Container of objects that are inserted and removed according to LIFO.
Objects can be inserted into a stack at anytime, but only the most recent inserted object can be removed at any time.

Question 5

stack operations

Answer 5

push - inserting object to the top of the stack
Pop - removing the top element
peaking obtaining the value of the top but not removing it.

Question 6

queues

Answer 6

Container of objects that are inserted and removed according to FIFO.
Objects can be inserted into a stack at anytime but only the object that been in queue the longest ca be removed at anytime.

Question 7

Queue operations

Answer 7

Obtain and remove elements
poll() returns null if queue is empty.
remove() throws an exception if queue is empty

obtain but don’t remove the head.
peek() returns null if queue is empty
element() throws and exception if queue is empty.

Add an element - offer()
returns true if element was added
returns false if not added

Question 8

Tree

Answer 8

A very common heirarchical data structure, Much like an OS file system structure or an In memory representation of an HTML document.
Each element is represented by a node.
Root node is the first node
Parent nodes have references to child nodes.
Sibling nodes have the same parent
Leaf nodes are nodes that have no child
A branch is a complete line (path) from the leaf to the root

Question 9

graph

Answer 9

They are Less-restricted Tree ( or trees are a specific type of graph), and can be used to represent complex relationships between entities
much like neural networks.
Vertex - a node
Edge - a connection between two vertices
Weight - A value along an edge
Paths - routes through the graph
Cycles - is a non-empty trail in which the only repeated vertices are the first and last vertices.

Question 10

Heap

Answer 10

A specialized tree structures, Binary tree
Binary tree structure is each node has 2 children at most.
Max heap is where the root node is the max value.
Min heap is where the root node is the min value.
There is a HeapSort algorithm.

Question 11

Linear Data Structures

Answer 11

The data items are arranged in an orderly manner where the elements are attached adjacently. The data elements can be accessed in one
time (single run). Simpler to implement, Single level, memory inefficient. Linear structures include:
• Arrays
• Linked-List
• Stack
• Queues

Question 12

Hierarchical Data Structures:

Answer 12

Hierarchical Data Structures:
It arranges the data in a sorted order and there exists a relationship between the data elements. Traversing of data elements in one go is not
possible. Complex to implementation, Multiple levels, memory efficient. Hierarchical structures include:
•Trees
•Graphs
•Heaps

Question 13

What are the different types of Linked List?

Answer 13

• Simple Linked List - Each node only has one reference to the next (Goes from head to tail) the tail points to null.
• Doubly Linked List - Each node has a reference forward to the nest node and backwards to the previous node (except the head and tail) the
head and tail points to null.
• Circular Linked List - The tail has reference to the head node.

Question 14

How does Binary Search work?

Answer 14

Looks at the middle indice of the collection and then determine if the value you are looking for is greater than or less than that value, then
move to either half depending on that result. Can only be preformed on ordered data structures

Question 15

What is Big O notation?

Answer 15

It is essentially a measurement on an algorithm’s or a data structures efficiency
Can measure memory complexity of the algorithm and the data structure, and it can be used to measure the time complexity of the algorithm
and time complexity of the data structures ability to Access, Search, Insert, Delete its elements
Omega is for the best case, Theta is for the average case, and O is for the worst case.
We typically only care about the worst case scenario because we cannot rely on the best case always being true. We want to know how it
performs at its worst.
O(1) - Constant
O(log(n)) - Logarithmic
O(n) - Linear
O(nlog(n)) - Super Logarithmic
O(n^2) - polynomial
O(2^n) - Exponential
O(n!) = Factorial

Question 16

recursion vs iteration

Answer 16

recursion is when a statement in a function calls itself repeatedly
iteration is when a loop repeatedly executing until the controlling condition become false.
Recursion is a process always applied toa function. Iteration is applied to a set of instructions which want to get repeated execution/

Question 17

What is an algorithm

Answer 17

a process or set of steps to solving a problem

Question 18

Bubble Sort

Answer 18

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Question 19

Merge Sort

Answer 19

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.