Algorithms

Question 1

What key algorithms does this course explore?

Answer 1

Search, Sort, String Manipulation

These algorithms up in software engineering interviews all the time!

Question 2

What distinguishes an average programmer from an outstanding software engineer?

Answer 2

Understanding how search, sort and string manipulation algorithms work and evolved distinguishes an average programmer from an outstanding software engineer!

Why?

Libraries and frameworks helps us sort data without knowing how sorting or searching algorithms work!

So…

That’s why sorting algorithms come up in interviews all the time!

Action:

How they work, Time & Space complexity, implementation

Question 3

What algorithms run in good Big-O?

Answer 3

algorithms that run in green or yellow!

Question 4

What are the seven essential sorting algorithms all software engineers must know?

Answer 4

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Counting Sort
7. Bucket Sort

Question 5

What must we be able to do with sorting algorithms?

Answer 5

Explain how each algorithm works

Know each algorithm’s time and space complexities

Implement each algorithm in given language of choice (Java)

Question 6

What is bubble sort?

Answer 6

sort in increasing order (ascending order)

scan array from left to right, if out of order, swap

if right is smaller than left, swap them

requires multiple passes (iterations)

next largest number moves to correct position

Question 7

What is the Big-O for bubble sort?

Answer 7

Best case = already sorted

worst case = reverse sorted

O(n) * O(n) = quadratic (worst case)

O(n) = linear (best case)

passes = each pass bubble one number into place

comparisions = bubbling into place

Question 8

How do we implement bubbleSort( ) in Java?

Answer 8

Question 9

How can we optimize our implementation of bubblesort( )?

Answer 9

reduce O(n) iterations if sorted!

compare only unsorted items by not comparing last items (bubbled up items)

Question 10

What is selection sort?

Answer 10

ascending order (smallest to largest)

Multiple passes over an array

In each pass we select the minimum value (from unsorted part) and swap this index with next index(in sorted part).

Question 11

What is the time complexity of the selection sort algorithm?

Answer 11

O(n) * O (n) : Quadratic

Fairly slow algorithm!

iterate array = O(n) operation!

iterate unsorted array = O(n) operation!

next min value - iterate unsorted part = O(n)

Question 12

How do we implement selectionSort ( ) using java?

Answer 12

Question 13

What is insertion sort?

Answer 13

each iteration pick one value from unsorted part, insert into sorted part (shift, make space)

Insert how?

We copy the values in the sorted part to the right to make space, then insert the value into the correct position.

Current (unsorted min value) is compared to all values in sorted part.

greater values are shifted to make space.

Question 14

What is the key difference about insertion sort vs. bubble sort and selection sort?

Answer 14

instead of swapping items, we shift items in our array to the right

Question 15

What is the Big-O for insertion sort?

Answer 15

O (n) * O (n) - quadratic

(worst case)
Same as bubbleSort( )!

Question 16

How do we implement insertionSort( ) in java?

Answer 16

Question 17

What is merge sort?

Answer 17

n (log n) time complexity!

Why?

It’s a type of algorithm called “divide and conquer algorithm.”

How?

it works by breaking the problem down into recursively smaller problems that are easy to solve.

Then it merges those solutions to get the final result.

Question 18

How does merge sort work?

Answer 18

dividing and conquering!

break array at middleIndex

divide again at middleIndex (left subarray)

divide again at middleIndex (right subarray)

keep breaking down the array into smaller subparts.

Until, cannot divide anymore

Then compare subparts and merge (sorted)

Question 19

What is the Big-O of the merge sort algorithm?

Answer 19

Time complexity:

O(n log n) operation!

O (log n) - dividing into subparts

O(n) - read each item, merge subparts

Faster than quadratic!

Space complexity:

O (n) space!

Don’t need to re-create arrays for merge, reuse

Question 20

How do we implement MergeSort algorithm in Java?

Answer 20

Question 21

How do we implement a base condition to stop recursion in merge sort?

Answer 21

if their is one item in the array only!

Question 22

What is partitioning?

Answer 22

How we move items around a pivot

How?

select last item as pivot

rearrange other elements around it

using two pointers

i = iterate over array (loop variable)

b = boundary (end of left partition)

if the item is smaller than the pivot…

increase boundary (left partition), we swap lower value into left partition

Question 23

What is the quickSort algorithm?

Answer 23

One of the most used sorting algorithms

built into many frameworks and languages

Why?

sorts an array in place without additional space.

O (log n) average time complexity!

How?

first, select a pivot

re-order the items around this pivot (partitioning)

items on right are larger than pivot

items on left are smaller than pivot

Pivot is now in place (doesn’t move)

select next item as pivot

partition again

Question 24

What is the Big-O of the quick sort algorithm?

Answer 24

Why?

O(n) - have to iterate all items and swap (partitioning)

# of times can partition - depends on pivot selection

w/ the right pivot selection on average can run in

O(log n) time

Question 25

How do we implement the **quickSort algorithm**?

Answer 25

Question 26

**What** are **comparision** based **sorting algorithms**?

Answer 26

They **sort data** based **on comparision**

Question 27

**What** are **non comparision** **sorting algorithms**?

Answer 27

**They** use **basic math to sort**

Question 28

What is **count sort?**

Answer 28

**non comparision sorting algorithm** we count occurrences and use that to sort data **How?** allocates a separate **counts array** **iterates input array**, **updating counts** array **iterates counts arra**y, **sorting input** array

Question 29

**When** should we use **count sort**?

Answer 29

**values must be positive** to **use as index** in **counts array** if **input range** has **gaps**, will **end up** with **many 0s in counts array**

Question 30

**What** is the **Big - O** of **counting sort algorithm**?

Answer 30

**O(n) time complexity!** **faster than O(n log n)** **Why?** **Space - O(k)** where **k = max range** of **input array** **Populate counts array** - iterate input array **O(n) operation**! iterate counts array, refil input array = **O(n + k)** **Cost?** **time-memory tradeoff!** **allocating extra memory!**

Question 31

**How** do we implement the **counting sort** **algorithm**?

Answer 31

**O (n) time complexity** ## Footnote **O(k) space complexity!**

Question 32

**What** is the **bucket sort algorithm**?

Answer 32

**iterate input array**, **dividing items into buckets** **iterate buckets**, **sort each bucket using sorting algorithm** **merge buckets** can **sort buckets** in **parallel** **each item** in the bucket is a **linked-list**

Question 33

What is **Big-O** of **bucket sort algorithm**?

Answer 33

**Range: O(n)** to **O(n^2)** **single bucket (worst case) - O(n^2) using insertionSort on buckets** **many buckets** each a **single item (best case) - O(n) time complexity but at a memory cost**

Question 34

**How** can we **refactor** **bucketSort** to **make it cleaner**?

Answer 34

Question 35

**What** are the **five** essential **searching algorithms** all **software engineers** must know?

Answer 35

**These** come up in **coding interviews!** **Understand** how **it works**! Understand its **Big-O**! **There** are **more searching algorithms** but these five **come up in coding algorithms!** **Five algorithms:** 1. **Linear Search - O (n)** 2. **Binary Search - O (n)** 3. **Ternary Search - O (n)** 4. **Jump Search - O (n)** 5. **Exponential Search - O (n)**

Question 36

What is **Linear Search**?

Answer 36

Simplest **search algorithm.** relatively slow **O(n) operation**! works well with a **small list**! **How it works:** Iterate over a list **inspect items**, if **value matches search**, **return it** otherwise return -1

Question 37

**What** is the **time complexity** of **linear search**?

Answer 37

**O(1) best case** - item is **first in list** **O(n) worst case** - item is **last in list**

Question 38

**How** do we implement **linear search** in Java?

Answer 38

Question 39

**What** is **binary search**?

Answer 39

**Divide and conquer algorithm** **O (log n) operation!** **In each step,** **we cut the number of items** to **inspect by half!** **First,** calculate **middle index** **Next,** item is either on left or right side of **partition** **Repeat,** calculate middle index Stop, index = value

Question 40

**What type** of **lists** does **binary search only work on**?

Answer 40

**sorted lists**! **if our list** is **unsorted**, we either **must sort it first** or **use linear search!** **Why?** **Divide and conquer algorithm!** **When?** **if we have multiple items to lookup, pays off to sort then use binary search!**

Question 41

**What** is **Big-O** for **binary search**?

Answer 41

**O(log n) time** - divide and conquer algorithm **O(log n) space** - recursive calls on stack **O (1) space** - iteration implementation

Question 42

**How** do we **implement** **binary search** using **recursion**?

Answer 42

Question 43

**How** do we **implement binary** search **using iteration**?

Answer 43

Question 44

**What** is **ternary search**?

Answer 44

**divide** list into **three parts** **(partitions) recursively** **partitionSize** = (right - left) / 3 **midPointOne** = left + partitionSize **midPointTwo** = right - partitionSize **compare** these **index values** to our **search value** if not a **midPoint**, could be in **partition, recursive part** **eventually**, the **method will return the index** of **search value!**

Question 45

**What** does the **logarithm** function **tell us**?

Answer 45

To **which power** to **raise a number** to **get another number** ## Footnote **Ex.** **Log base 2 of 8** **tells us what power to raise two to get eight!** **To which power should we raise 2 to get 8?** **Answer 3.**

Question 46

What is the **Big-O** of **ternary search**?

Answer 46

As we **divide our list** into **more parts**, **search algorithm** gets **slower!** **Binary search** is **faster** than **ternary search**! Why? **Worst case scenario** a **list of 10 items** has **10 partitions**, O(n) have to **compare value to every item in list**

Question 47

How do we **implemen**t **ternary search** using **recursion**?

Answer 47

Question 48

**What** is **jump search**?

Answer 48

**Divide list into blocks (blockSize = squrt(n))** **jump to that** block where **value may exist** **How?** **Compare last item** in block with **target value** if **value is greater**, jump to **next block** **When?** value is **less than** last **item in block** do **linear search** in **that block**

Question 49

**What** is the **Big-O** of **jump search**?

Answer 49

**O**( **squareroot(n)** ) An **improvement** to **linear search**! **Not as fast** as **binary search**!

Question 50

**How** do we **implement** **jumpSearch** in **Java**?

Answer 50

Question 51

**How** do we **refactor this code** in **jumpSearch**?

Answer 51

Add the **conditional statement** to the **while loop**

Question 52

**What** is **exponential search**?

Answer 52

Start w/ **small range** **check** if target is **w/in range** if **it's** **not, double the range**. **check if target is in this range.** **if target is potentially w/in range** **do a binary search w/in range (after upper bound of previous range)**

Question 53

What is **Big-O** of **exponential search**?

Answer 53

**O ( log i )** **i** = **# items** in **range**

Question 54

**How** do you **implement exponentialSearch** in **Java**?

Answer 54

Question 55

What are the **string manipulation** algorithms?

Answer 55

1. Find the **number of vowels** in a string 2. **Reverse a string** 3. **Reverse the order of words** in a sentence 4. Check if a **string is a rotation** of another string 5. **Remove duplicate characters** in a string 6. Find the **most repeated character** in a string 7. **Capitalize the first letter** of each word in a sentence 8. **Detect if two strings are anagrams** (contains exact same letters in any order) 9. **Check if a string is a palindrome.** (If we read palindrome string left to right get same letters).

Question 56

**What** are some **useful Java classes/methods** for **solving string manipulation excercises**?

Answer 56

Question 57

**How** do we **implement countVowels ( )**?

Answer 57

Question 58

**How** do we **implement** **reverse ( )** to **reverse a string**?

Answer 58

Question 59

**How** can we **reduce the time complexity** of **reverse ( )** from **O(n^2) to O(n)**?

Answer 59

**Use** the java class **StringBuilder** to create **mutable strings** **eliminates O(n)** for creating a **new string everytime** we **add a letter**!

Question 60

**What's** another **implementation** of **reverseWords ( )** using built in **Java functions**?

Answer 60

Question 61

**How** do we **implement reverseWords ( )**?

Answer 61

Question 62

**How** do we **implement areRotations ( )**?

Answer 62

If **this string** is **one million characters** the **space complexit**y is **very large** therefore we **need to implement** this **method** using a **for loop** to **compare values**!

Question 63

**What** is a **different way** of **implementing** **areRotations ( )**?

Answer 63

Question 64

**How** do we **implement** **removeDuplicates ( )**?

Answer 64

Question 65

**How** do we **implement getMaxOccuringChar ( )** w/o using a **HashMap \<\> ( )**?

Answer 65

**Can** use an **array** Store **each character** at **ASCII value** as **index** **increment value** at **ASCII index**

Question 66

**How** do we **implement maxOccurringChar ( )**?

Answer 66

Question 67

**How** do we **implement capitalize ( )**?

Answer 67

**Popular Interview Question**! **Edge cases:** **whitespace front / back** - . trim **whitespace between words** - .replaceAll w/ single space **pass empty space** - .isEmpty, return empty string

Question 68

**How** do we **implement** **isAnagram ( )** using sorting?

Answer 68

**Very popular Interview Question!** ask if solution must be case insensitive **Edge cases**: pass empty string pass white space pass null - check

Question 69

**What** does **adding optimizations** do to the **readability and maintainability of our code**?

Answer 69

It makes it **less readable** and **less maintainable** don't do t**oo much pre optimizations** (early stage optimizations) if **affects code readability** and **maintainability** **Take context in count** **Ask questions about execution, size of inputs, etc.** **Ask about size of input**

Question 70

SM **How** do we **implement isPalindrome ( )**?

Question 71

**What** is a **code monkey**?

Answer 71

**Writes code** without **understanding the problem** **Writes code** without understanding **what they're doing**

Question 72

**What** is a **software engineer**?

Answer 72

A **software engineer** is **one who developers** properly **engineered solutions** to **today's problems**, **not tomorrows problems** that **may never happen**! Be a **software engineer,** not a **code monke**y who **doesn't really understand** the **problem** / what **solution is doing**

Question 73

**What** is **mosh's advice**?

Answer 73

Study **other resources as well**! **Especially to pass interviews** at **Google**, **Microsoft** and **Amazon**! **Check out:** **leetcode.com** **interviewcake.com** **online communities** for **popular interview questions**!