Data Structures Algorithms

Question 1

How do we measure algorithms ?

Answer 1

In computer science and programming the efficiency of an algorithm is measured using Big O notation.

Question 2

Why should developers care about data structures and algorithms ?

Answer 2

There are numerous data structures that can be chosen for a given problem, example should one use an array to store phone numbers or use a dictionary to map the names to phone numbers and so on. The more data structures one is exposed to the better the decision making process can be in choosing the right structure. As per algorithms, those are the steps in solving a given problem, some pre-defined algorithms exist such as binary search and shortest path, but everyday developers solve software development challenges and have to come up with steps and test cases for their given solution, so as with data structures, exposure and knowing how to measure efficiency of algorithms using Big O is vital to the success of a software engineer.

Question 3

Which sorting algorithm uses a pivot and partitioning ?

Answer 3

Quick sort uses partitioning to return a pivot as it continues to sort a collection using divide and conquer.

Question 4

What are the properties of a doubly linked node ?

Answer 4

A value (the data type of the Node), a next pointer and a previous pointer property.

Question 5

Name three built-in data structures in Swift ?

Answer 5

Arrays, Set and Dictionary.

Question 6

Name the types of depth-first traversals and explain how each works ?

Answer 6

In order, pre order and post order traversal.

In-order traversal visits the left nodes then the root node then the right nodes.

Pre-order traversal visits the root node first, then the left sub tree, then the right subtree.

Post-order traversal visits the left subtree, then the right, then visits the root node.

Question 7

What is the runtime of contains on an array ?

Answer 7

O(n)

Question 8

What’s the runtime of contains on a set ?

Answer 8

O(1)

Question 9

What’s the requirements of a recursive function ?

Answer 9

Any recursion function must have a base case and the recursive call.

Question 10

Name a few sorting algorithms and their runtimes ?

Answer 10

Bubble sort, O(n ^ 2)
Insertion sort, O(n ^ 2)
Merge sort, O(n log n)
Quick sort, O(n log n)

Question 11

What is divide and conquer and give an algorithm example ?

Answer 11

Divide and conquer is the process of taking a larger problem and breaking it down into smaller parts and solving sub parts until a solution is met. Examples of divide and conquer algorithms are merge sort, quick sort and binary search.