00_algos.md

Algorithms

01_big_o.md

Big O Cheat Sheet

Definitions

Big O, also known as Big O notation, represents an algorithm's worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm.

Types

In Big O, there are six major types of complexities (time and space):

• Constant: O(1)
• Linear time: O(n)
• Logarithmic time: O(n log n)
• Quadratic time: O(n^2)
• Exponential time: O(2^n)
• Factorial time: O(n!)

Graph

Further reading

• FCC article

02_algo.md

Sort Algorithms

Types

1. In-place: modifies existing array while sorting its elements
2. External: when all to-be-sorted data cannot be placed in-memory (best for big size of data - doesn't fit in RAM so we use hard drive)
3. Stable: maintain the relative order of records with equal keys (i.e. values)

Algorithms

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. QuickSort
6. Heap Sort

Search Algorithms

Types

• Sequential: check all elements sequentially
• Interval: specifically designed for search in sorted data structures

Algorithms

1. Linear Search

   • start from the leftmost element
   • 1-1 compare with each element
   • if x matches element, return index
   • else, return -1

2. Binary Search

Comparison

Binary Search	Linear Search
sorted input	any form input
random data access	sequential access
O(log[n])	O(n)
ordering comparisons	equality comparisons

05_frogs.md

Frogs on lilypads

0. > > > _ < < <
1. > > > < _ < <
2. > > _ < > < <
3. > _ > < > < <
4. > < > _ > < <
5. > < > < > _ <
6. > < > < > < _
7. > < > < _ < >
8. > < _ < > < >
9. _ < > < > < >
10. < _ > < > < >
11. < < > _ > < >
12. < < > < > _ >
13. < < > < _ > >
14. < < _ < > > >
15. < < < _ > > >

Minimum number of moves = (leftFacingFrogs + 1)(rightFacingFrogs + 1) - 1 = (3+1)(3+1) -1 = 16 - 1 = 15