Data Structure -- 2. Linked List

Linked List is a sequence data structure like Array. It doesn't have index for fast query, but more flexible for insertion/deletion than Array. Single linked list is asked often as double linked list is more expensive even easier to do some manipulation.
Basic Linked List operations are find/insert/remove/shift/reverse/rotate.
Dummy Node is very useful for Java to retain the head.
remove remove N from end Rotate Reverse(whole, subchain, everyK etc.) IsPalindrome Swap More advanced operations are
find insertion of two linked list Detect Cycle Copy linked list with random pointers inside

Data Structure -- 3. HashMap

Unlike other sequential data structure(List, Array, String), Hash is not sequential(no order) without direct index access. But it provides map access, which is O(1). And its mapping is very flexible and key can be many things.

HashMap does two important usecases

• translate original set to a different value set
• The value normally has certain designed pattern for comparison
• partition a large set into subgroup. each subgroup shared the same key/signature.
• The value/subgroup can be a set for storage, comparison, output

Sometimes, bi-directional HashMap(two) can solve binding problems.
The HashMap translate usages are duplicates in a set/string/array, Palindrome, StringIsAnagram
The HashMap subgroup usages are below HashMap can also run multiple scans or bi-directional to handle complex logic

Data Structure -- 4.2 Binary Search Tree

Binary Search Tree is a special binary tree, where

• left child contains only nodes with value less than the parent node
• right child only contains nodes with values greater than or equal to parent

It's good for searching

This page has many basic insertion/deletion algorithms http://blog.jobbole.com/79305/
IsValidBST is fundamental Lowest Common Ancester is interesting.

Data Structure -- 4. Binary Tree

Binary Tree is a tree with each node has UP TO TWO leaves

• Full/Strict, every node except leaf nodes have two children
• Complete, every level except the last(left justified) is completely filled
• Perfect, every node except the leaf nodes have two children and all level are completely filled

Binary Tree is common data structure and base for many advanced ones. 

DFS and BFS are two broad traversal algorithms.

• DFS is divided into pre-order, inorder, postorder.They can be implemented as recursive(very simple) and non-recursive.
• BFS is non-recursive using queue

The basic DFS with and without recursion is here
PATHSUM from rootToleaf or anyPath illustrates the DFS variations The basic BFS without and with recursion is here. Some similar level order problem can be solved with BFS
Bottomup Zigzag Rightview Right next pointer Some Binary Tree basic tools are useful like MaxDepth, MinDepth, Height, SameTree, isSymmetric isBalanced can be speeded up with the help of

Algorithm -- Two Pointers

Two pointers is an useful algorithm to deal with Array and String and Linked-List

• Actually, most linked list problem can be solved by this algorithm
• Two pointers is one basic algorithm and used widely. One typical origination is quickSort. 

A few subtypes

• two pointers move from left to right, slide window 
• two pointers move from left, right to middle 
• two pointers control two array or list, typically merging

Merge Two Sorted Array
Replicate Duplicates from Single Sorted Array
Reverse Words in a String
Rotate Array

Algorithm -- Binary Search

Binary search is one essential algorithm type. It operates on

• array
• sorted

Basic Binary Search has recursion and non recursion implementation. Normally, non recursion is simpler to control and vary for many derived problems

Here is the basic form


Search Insert Position
\ Search in Rotated Sorted Array
Find Square root of an integer
Search in a 2D matrix
Search for a range

[Leetcode] LRU Cache (Design)

[Problem]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[Algorithm]

hashmap + linkedlist(for fast LRU update)

[Code]

Python