Data-Structures-and-Algorithms.md

Data Structures and Algorithms

How do we measure algorithms ?

Solution

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

Why should developers care about data structures and algorithms ?

Solution

There are numerous data structures that can be choosen 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.

Which sorting alogorithm uses a pivot and partitioning ?

Solution

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

What are the properties of a doubly linked node ?

Solution

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

Name three built-in data structures in Swift ?

Solution

Arrays, Set and Dictionary.

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

Solution

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.

What is the runtime of contains on an array ?

Solution

O(n)

What's the runtime of contains on a set ?

Solution

O(1)

What's the requirements of a recursive function ?

Solution

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

Name a few sorting algorithms and their runtimes ?

Solution

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

What is divide and conquer and give an algorithm example ?

Solution

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.