# Algorithmic Toolbox

# Nail Your Next Job Interview - Graph

# Sorting Algorithms

# Summary

Sort type | Time Complexity | Space complexity | stable? | |
---|---|---|---|---|

bubble sort | $O(n^2)$ | $O(1)$ | Yes (do not swap on equal val) | |

selection sort | $O(n^2)$ | $O(1)$ | Yes (do not update max idx on equal value) | |

insertion Sort | $O(n^2)$ | $O(1)$ | Yes (stop insert on equal val | |

radix/bucket sort | $O(nd)$ d is number of digit for max val | $o(n)$ | Yes | |

heap Sort | $O(nlogn)$ | $O(n)$ | No? | |

merge sort | $O(nlogn)$ | $O(n)$ | Yes | |

quick sort | $O(nlogn)$ | $O(logn)$ call stack w/ tail recursion | No |

# All You Can Eat - Java

# Permutation and Combination of a Given String

# Basic Datastructure Toolbox

# Regex Cheatsheet

# Leet269 - Alien Dictionary

## Description

There is a new alien language which uses the latin alphabet. However, the **order** among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

**Example 1**:

Given the following words in dictionary,

1 | [ |

The correct order is: `"wertf"`

.

**Example 2:**

Given the following words in dictionary,

1 | [ |

The correct order is: `"zx"`

.

**Example 3:**

Given the following words in dictionary,

1 | [ |

The order is invalid, so return `""`

.

**Note**:

- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.

# [LeetCode & LintCode] Lowest Common Ancestor Series

## Overview

- LeetCode 236. Lowest Common Ancestor of a Binary Tree
- Followup1: LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
- Followup2: LintCode 474. Lowest Common Ancestor II
- Followup3: LintCode 578. Lowest Common Ancestor III

## 236. Lowest Common Ancestor of a Binary Tree

### Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes `p`

and `q`

as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: `root = [3,5,1,6,2,0,8,null,null,7,4]`

**Example 1:**

1 | Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 |

**Example 2:**

1 | Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 |

**Note**:

- All of the nodes’ values will be unique.
- p and q are different and both values will exist in the binary tree.