Coding Algorithms

Question 1

What is the sliding window algorithm and how does it work?

Answer 1

The sliding window algorithm is an algorithm that can be used to solve a problem that requires you identify a sub-pair or sub-list within the overall list. It works by forming a window over a portion of the array, performing the required calculations, and then sliding across to the next portion of the array.

Question 2

What conditions must a question meet that suggest the window sliding algorithm can be used to answer it?

Answer 2

Any questions that meet the following conditions:

• Ask to return a minimum/maximum value.
• Ask to return the longest/shortest values.
• Ask to return a k-sized value.
• Uses the word contiguous.
• The input is a data type, such as strings, arrays, linked lists, that must iterated over sequentially.

Question 3

What is the Breadth-First Search (BFS) Algorithm and how does it work?

Answer 3

The BFS is an algorithm that is useful when trying to find connected components in a tree data structure. It works by starting at the root of the tree, or at an arbitary node (known as the ‘search key’) and searching all the neighbouring nodes before moving on the next depth level.

Question 4

What is the Depth-First Search (DFS) Algorithm?

Answer 4

The DFS is an algorithm that is useful when trying to find connected components in a tree data structure. It works by starting at the root of the tree, or at an arbitary node (known as the ‘search key’) and searching all the nodes furthest away from it, before transvering across and searching the nodes in the next column of the tree.

Question 5

What are the similarities and differences between the Breadth-First Search and Depth-First Search?

Answer 5

Similarities:

• They both are useful for finding connected components in tree data structures.
• They both can start at the root node or at an arbitary node (‘search key’) before transversing the the next level/column of the tree.

Differences:

• The BFS algorithm searches the breadth (across) of the level it is currently on before moving to the next level of depth in the tree.
• The DFS algorithm search the depth (down) of the column it is currently on before moving across to the next column of nodes in the treee.

Question 6

What is the Slow and Fast Pointers Algorithm and how does it work?

Answer 6

The slow and fast pointers algorithm can be used to solve problems that deal with cyclic linked lists or arrays, and can be used to determine if the given data input is cyclical. It works by using two pointers, one that moves at a slow pace and the other moving at a faster pace. If they both meet at some point, then we can conclude the data structure was cyclical. However, if they never meet, and the faster pointer reaches the end of the data set first, then we know the structure is not cyclical.

Question 7

What is the Two Pointer Algorithm and how does it work?

Answer 7

The two pointer algorithm is useful for searching for pairs in a sorted array, string, or linked list. It works by using two pointers to point/track specific locations in the given data structure.

The directions at with the points can move can either be in opposite directions, or in the same direction.

• Opposite directions - the pointers start at the opposite ends of the list and move towards each other untill they meet.
• Same direction - the is where both pointers will start at the same position, however, one pointer will move across the data set faster than the other.

Question 8

Explain the concept behind time-space complexity when dealing with algorithms.

Answer 8

The concept describes that although there can be multiple algorithmic solutions to solve a problem, the algorithm that takes the least time and space is considered the most efficient. The space complexity of an algorithm refers to the total space used or needed by the algorithm to complete a task; whilst the time complexity refers to the number of operations needed for it to complete the task with respects to input size.

Question 9

What are the different notations that are used to represent the time complexity of an algorithm? What is the most commonly used notation?

Answer 9

There are three different notations used:

• Θ (theta) Notation - used to denotate the average time bound of an algorithm.
• Big O Notation - used to denote the upper time bound of an algorithm, representing the longest time it will take an algorithm to run. It the most commonly used notation to calculate time complexity.
• Ω (omega) Notation - used to denote the lower time bound of an algorithm, representing the fastest time the algorithm will return a result.