Tips and tricks

Sorted array

• Binary search
• 2 sorted arrays - "merge" operation from the merge sort (e.g. to find closest elements with minimal absolute difference).

Singly-linked list

• Slow and Fast pointers
• Finding the middle element
• Detecting a cycle
• In-place transformations
• Inversion (using cur, next, and next_next)
• Duplication by inserting duplicates after every original item (for fancy linked lists)

Tree

• BFS - queue
• Useful if processing a long sequence, and at each step you can take either of two(or many) steps. E.g. see http://www.geeksforgeeks.org/find-all-possible-interpretations/
• A binary tree can be presented as an array with [0] being the root, and [2*i+1] and [2*i+2] being children of a node i.
• Catalan number - a number of structurally different binary trees of n nodes = (2n)! / (n!*(n+1)!)
  It also represents a number of expressions with n parantheses.
  http://en.wikipedia.org/wiki/Catalan_number
  http://www.careercup.com/question?id=22049663
• A binary tree can be restored from in-order and either post- or pre-order traversals. One of the latter give us the roots, and the in-order is needed to decide between the left and right paths.

Limited number of math operators

• Consider several passes over a collection (most likely an array) in different directions (1 -> N and then N -> 1, or vice versa) to accumulate partial results

Prime numbers

• No divisors other than 1 and itself. Therefore can identify duplicates by accumulating a product of all numbers in a collection - if a number is a divisor for the product, then it's already been examined.

Math

• Two's compliment of x = ~x + 1. For negative x this is equivalent to -1 * x.
• A range of integers is given: 0..(N-1)
• consider using a bitset data structure (e.g. for sorting, provided no duplicates present)
• Can probably modify the original array where the numbers are stored (e.g. to count them).
• Use counting sort, replacing +1 with +N at arr[arr[i]%N].
• If most values are encountered twice (e.g. in a list), we can eliminate them using XOR over all the elements. The result of XOR will contain only those elements that aren't doubled.

String

• Anagrams - use hashing to detect anagrams. E.g. hash = product of prime numbers associated with every character (a..z map to 2..101) - avoids collisions, but can overflow. Or deal with the collisions later when printing the result.
  http://www.careercup.com/question?id=5743007936544768