Data Structures & Algorithms

Question 1

Swift collection protocols

Answer 1

“Tier 1, Sequence: A sequence type provides sequential access to its elements. This axiom comes with a caveat: Using the sequential access may destructively consume the elements.

Tier 2, Collection: A collection type is a sequence type that provides additional guarantees. A collection type is finite and allows for repeated nondestructive sequential access.

Tier 3, BidirectionalColllection: A collection type can be a bidirectional collection type if it, as the name suggests, can allow for bidirectional travel up and down the sequence. This isn’t possible for the linked list, since you can only go from the head to the tail, but not the other way around.

Tier 4, RandomAccessCollection: A bidirectional collection type can be a random access collection type if it can guarantee that accessing an element at a particular index will take just as long as access an element at any other index. This is not possible for the linked list, since accessing a node near the front of the list is substantially quicker than one that is further down the list.

Question 2

Performance analysis of linked list

Answer 2

Question 3

Explain linked list

Answer 3

It has head

It has tail

Unidirectional

Methods:

push: Adds a value at the front of the list.
append: Adds a value at the end of the list.

insert(after:): Adds a value after a particular node of the list.

After adopting Sequence and Collection gets:

push

append

insert(after:)

pop

removeLast

remove(after:)

Has copy-on-write value semantic (COW) that use isKnownUniquelyReferenced

Question 4

Linked-list queue strengths and weaknesses and Complexity table

Answer 4

Despite O(1) performance, it suffers from high overhead. Each element has to have extra storage for the forward and back reference. Moreover, every time you create a new element, it requires a relatively expensive dynamic allocation. By contrast, QueueArray does bulk allocation, which is faster.

Question 5

In-order traversal

Answer 5

Question 6

Pre-order traversal

Answer 6

Question 7

Explain Binary Search Tree

Answer 7

two rules on the binary tree:

The value of a left child must be less than the value of its parent.

Consequently, the value of a right child must be greater than or equal to the value of its parent.

Lookup, insertion and removal is O(log n) if tree is balanced

The binary search tree is a powerful data structure for holding sorted data.

Elements of the binary search tree must be comparable. This can be achieved using a generic constraint or by supplying closures to compare with.

The time complexity for insert, remove and contains methods in a BST is O(log n).

The performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, so you’ll learn about a self-balancing binary search tree called the AVL tree

Question 8

Graph analysis matrix vs list

Answer 8

Question 9

Types of time complexity

Answer 9

Constant time, O(1)
logarithmic time, O(log n)
linear time, O(n)
quasi-linear time O(n log n)
quadratic time O(n2)

Question 10

If you try to add new elements to an array that is already at maximum capacity

Answer 10

Array must restructure itself to make more room for more elements. This is done by copying all the current elements of the array in a new and bigger container in memory. However, this comes at a cost; Each element of the array has to be visited and copied.

Question 11

Explain queues

Answer 11

“Array-based
Linked list
Ring buffer
Stack based”
Deque

Question 12

Common operations for queue:

Answer 12

enqueue: Insert an element at the back of the queue. Returns true if the operation was successful.
dequeue: Remove the element at the front of the queue and return it.

isEmpty: Check if the queue is empty.

peek: Return the element at the front of the queue without removing it.

Question 13

Array-based queue strengths and weaknesses and Complexity table

Answer 13

Can be inefficient for very large queues

Question 14

Ring buffer implementation

Answer 14

if read & write is at the same index -> it means that queue if full or empty

fixed size

Question 15

Double-stack implementation

Answer 15

Dynamic
dequeue is amortised O(1)
Array elementts are next to each other in memory blocks -> loaded in a cache.
Array require O(n) for copy, but it’s very fast O(n)

Question 16

Compared to other data structures, leveraging two stacks improves

Answer 16

the dequeue(_:) time complexity to amortized O(1) operation.

Question 17

double-stack implementation beats out Linked-list in terms

Answer 17

of spacial locality.

Question 18

Space complexity: Array vs linked list queues

Answer 18

Elements in an array are laid out in contiguous memory blocks, whereas elements in a linked list are more scattered with potential for cache misses.

Question 19

Post-order traversal

Answer 19

Question 20

Explain Adjacency matrix graph

Answer 20

uses a square matrix to represent a graph

good for dense graphs, when your graph has lots of edges

Question 21

Objects of graph

Answer 21

Vertex
Edge

Question 22

Time complexity

Answer 22

“is a measure on the time required to run an algorithm as the input size increases.”

Question 23

Space complexity

Answer 23

is a measure of the resources required for the algorithm to run.

Question 24

Big O notation is used to represent

Answer 24

the general form of time and space complexity.

Question 25

Time and space complexity are

Answer 25

high-level measures of scalability; they do not measure the actual speed of the algorithm itself.

Question 26

For small data sets, time complexity is usually

Answer 26

irrelevant. A quasilinear algorithm can be slower than a linear algorithm.

Question 27

Types of Data Structures & Algorithms complexities

Answer 27

Time complexity
Space complexity

Question 28

How much memory an array takes?

Answer 28

Underneath the hood, Swift arrays are allocated with a predetermined amount of space for its elements.

Question 29

Array vs Dictionary operations and time cost

Answer 29

Question 30

If you find yourself needing to use insert(at:) frequently with indices near the beginning of the array

Answer 30

you may want to consider a different data structure such as the linked list.”

Question 31

Copy-on-write behavior

Question 32

head first complexity insertion for array and list

Answer 32

Linked lists have a O(1) time complexity for head first insertions. Arrays have O(n) time complexity for head-first insertions

Question 33

runner’s technique

Answer 33

One is running x2 and when he reaches the end of the list, the slower runner will be in the middle

Finding the middle of list

Question 34

What to think about when you create new algorithm?

Answer 34

Space complexity -> if you need allocate more objc
Time complexity -> how many objc you need iterate

Question 35

What ordering queues use?

Answer 35

FIFO first in first out

Question 36

How blocks of memory placed in linked list vs stack/array

Answer 36

Question 37

Enqueue vs Dequeue

Answer 37

Enqueue inserts an element to the back of the queue.
Dequeue removes the element at the front of the queue.

Question 38

Ring-buffer-queue based implementation is good

Answer 38

for queues with a fixed size.

Question 39

Tree vs linked-list

Answer 39

linked-list nodes may only link to one successor node,

a tree node can link to many child nodes.

Question 40

Type of traversals

Answer 40

depth-first and level-order

Question 41

Explain Binary Tree

Answer 41

binary trees that impose restrictions on the insertion/deletion behaviors

Question 42

AVL Trees explain

Answer 42

It looks like Search Treen, but it balanced itself

Type of balance:
Perfect Balance
Good Balance
Unbalanced

A self-balancing tree avoids performance degradation by performing a balancing procedure whenever you add or remove elements in the tree.

Question 43

how to measuring balance in AVL tree?

Answer 43

Find height of node and see if left&right child are differ

Question 44

How AVL balanced itself?

Answer 44

Balance is achieved by four types of tree rotations on node insertion and removal.

Question 45

How AVL preserve balance?

Answer 45

AVL trees preserve balance by readjusting parts of the tree when the tree is no longer balanced.

Question 46

Explain Adjacency list graph

Answer 46

stores a list of outgoing edges for every vertex

good for sparse graphs, when your graph has the least amount of edges