Q. What's the difference between a LinkedList and an ArrayList (or between a linked list and an array/vector)?

An ArrayList is a List implementation backed by a Java array. With a LinkedList, the List implementation is backed by a 
doubly linked list data structure.

Q. How can you detect a cycle in a linked list?

Turtle and Rabbit: The idea is to have two references to the list and move them at different speeds. Move one forward by 1  
node and the other by 2 nodes. If the linked list has a loop they will meet. If there is no loop either of the references 
will become null when it reaches the end of the list. O(n)

Q. What is a weighted round robin load balancing algorithm?

Round robin distribution is used by DNS servers, peer-to-peer networks, and many other multiple-node clusters/networks.  
In a weighted round-robin algorithm, each destination (in this case, server) is assigned a value that signifies, relative 
to the other servers in the list, how that server performs. This "weight" determines how many more (or fewer) requests are 
sent that server's way; compared to the other servers on the list.

Q. Breadth first search

root, children (enqueue/add), children of children (dequeue/remove first and enqueue), etc... Use a fifo queue

Q. Depth first search

root, children (push) to leaf nodes, left, then up (pop) and right... Use a stack
    +
  3   4
preorder/prefix (Polish notation, e.g. + 3 4), postorder/postfix (reverse Polish notation, e.g. 3 4 +), 
inorder/infix (e.g. 3 + 4) - expression tree

Q. Name some self balancing binary trees

Red/black tree, splay tree, AVL tree

Q. What is Big-O Notation?

Defines best, average and typically worst case performance of an algorithm.  
Given n we might have, n, n log n, n^2 performance, for example.

Q. Quick sort

Divide/pivot point, less vs. greater, recurse

Q. Merge sort

Split in 2, recurse left, recurse right, merge sorted halves

Q. Implement a hashtable (dictionary)

An array of linked lists, indexed by a hash, where hash collisions are placed in buckets in the linked list.

Q. Binary search trees

left subtree nodes < parent node <= right subtree nodes.  Efficient for sorting, searching in-order.

Q. Heap (priority queue)

Complete binary tree (i.e. only bottom level might not be complete, left to right), 
heap ordered (i.e. parent values > children values)

Q. Graphs

trees with interconnecting nodes

Q. Graph algorithms, such as Dijkstra and A*

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen 
according to a specified rule.  A* uses a best-first search and finds the least-cost path from a given initial
node to one goal node (out of one or more possible goals).  It uses a distance-plus-cost heuristic  function 
(usually denoted f(x)) to determine the order in which the search visits nodes in the tree.
  
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959,[1]  is a graph search 
algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, 
producing a shortest path tree. This algorithm is often used in routing.

Q. NP-complete problems, such as traveling salesman and the knapsack problem

Traveling Salesman problem: Given a list of cities and their pairwise distances, the task is to find a shortest 
possible tour that visits each city exactly once.

Knapsack problem: Given a set of items, each with a weight and a value, determine the number of each item to 
include in a collection so that the total weight is less than a given limit and the total value is as large as 
possible.

Data Structures And Algorithm Notes

Data Structures

Algorithms

Big-O Notation

Questions and Topics