## Search Insert Position in Sorted Array

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Assume that there are NO duplicates in the array. This should be done in O(log n) time.

## Merge Sorted Array

Given two sorted integer arrays `A`

and `B`

, merge `B`

into `A`

as one sorted array. Array `A`

has `m`

number of elements, and array `B`

has `n`

number of elements. You may assume that `A`

has enough space to hold additional elements from `B`

; that is, `A`

has length of `m`

but has capacity of `m + n`

.

## Compare Strings

Compare two strings `A`

and `B`

, determine whether `A`

contains all of the characters in `B`

. The characters in string `A`

and `B`

are all upper case letters. The characters of `B`

in `A`

are not necessary continuous or ordered.

## Median

Given a unsorted array with integers, find the median of it. A median is the middle number of the array after it is sorted. If there are even numbers in the array, return the N/2-th number after sorted.

## Binary Tree Pre-Order Traversal

Given a binary tree, traverse the tree and output the node values using pre-order traversal. In pre-order traversal, the values of the tree is output in this order:

## Binary Tree Post-Order Traversal

Given a binary tree, traverse the tree and output the node values using post-order traversal. In post-order traversal, the values of the tree is output in this order:

## Binary Tree In-Order Traversal

Given a binary tree, traverse the tree and output the node values using in-order traversal. In in-order traversal, the values of the tree is output in this order:

## Single Number

Given `2 * n + 1`

numbers, every numbers occurs twice except one. Find the single number. Can you do it in O(n) time and O(1) space?

## Partition Linked List

Given a linked list and a value `x`

, partition it such that all nodes less than `x`

come before nodes greater than or equal to `x`

. You should preserve the original relative order of the nodes in each of the two partitions.

## Binary Search Tree Insertion

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree. Assume there is no duplicates in the tree.