A Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. There are basically three operations that can be performed on stacks. They are:

1. inserting an item into a stack (push).
2. deleting an item from the stack (pop).
3. displaying the contents of the stack (peek or top). A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them. A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.

Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures.

Trie (also called **digital tree **or prefix tree) is a
tree-based data structure, which is used for efficient
retrieval

of a key in a large data-set of strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., the value of the key is distributed across the structure. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Each complete English word has an arbitrary integer value associated with it (see image).

A normal tree has no restrictions on the number of children each node can have. A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. There are three different types of binary trees: Full binary tree: Every node other than leaf nodes has 2 child nodes. Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible. Perfect binary tree: All nodes have two children and all leaves are at the same level.

Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize datahierarchically.

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data or key, and it may or may not have a child node. The first node of the tree is called the root. Leaves are the last nodes on a tree. They are nodes without children.

A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority.

A Heap is a special Tree-based data structure which is an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node. A common implementation of a heap is the binary heap, in which the tree is a binary tree.

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. Hash tables implement an associative array, which is indexed by arbitrary objects (keys). A hash table uses a hash function to compute an index, also called a hash value, into an array of buckets or slots, from which the desired value can be found.

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

A linked list is a linear data structure where each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference (pointer) to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted thathead is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A stack is a recursive data structure, so it's: a stack is either empty or it consists of a top and the rest which is a stack by itself;

Arrays are: Finite (fixed-size) - An array is finite because it contains only limited number of elements. Order -All the elements are stored one by one , in contiguous location of computer memory in a linear order and fashion Homogenous - All the elements of an array are of same data types only and hence it is termed as collection of homogenous

For traversing a (non-empty) binary tree in pre-order fashion, we must do these three things for every node N starting from root node of the tree: (N) Process N itself.

(L) Recursively traverse its

left subtree. When this step is finished we are back at N again.

(R) Recursively traverse its

right subtree. When this step is finished we are back at N again.

Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Implementation: Java

// Recursive function to perform pre-order traversal of the tree
public static void preorder(TreeNode root)
{
  // return if the current node is empty
  if (root == null) {
    return;
  }// Display the data part of the root (or current node)
System.out.print(root.data + " ");// Traverse the left subtree
preorder(root.left);// Traverse the right subtree
preorder(root.right);
}
PY
# Recursive function to perform pre-order traversal of the tree
def preorder(root):# return if the current node is empty
if root is None:

return# Display the data part of the root (or current node)

print(root.data, end=' ')# Traverse the left subtree
preorder(root.left)# Traverse the right subtree
preorder(root.right)

Because they help manage your data in more a particular way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants. Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections. More practically you should:

Use a queue when you want to get things out in the order that you put them in (FIFO) Use a stack when you want to get things out in the reverse order than you put them in (LIFO) Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

A singly linked list A doubly linked list is a list that has two references, one to the next node and another to previous node. A multiply linked list - each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set(e.g., by name, by department, by date of birth, etc.). A circular linked list - where last node of the list points back to the first node (or the head) of the list.

Few disadvantages of linked lists are : They use more memory than arrays because of the storage used by their pointers. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access. Random access has linear time. Nodes are stored incontiguously (no or poor cache locality), greatly increasing the time required to access individual elements within the list, especially with a CPU cache. If the link to list's node is accidentally destroyed then the chances of data loss after the destruction point is huge. Data recovery is not possible. Search is linear versus logarithmic for sorted arrays and binary search trees. Different amount of time is required to access each element.

Not easy to sort the elements stored in the linear linked list.

Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is

O(
n) .

Searching for a given value in the queue requires iterating until you find it. So search is

O(
n) .

Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is

O(
1) .

Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `

O(
1) .

Queue can be classified into following types: Simple Queue - is a linear data structure in which removal of elements is done in the same order they were inserted i.e., the element will be removed first which is inserted first. Circular Queue - is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called Ring Buffer. Circular queue avoids the wastage of space in a regular queue implementation using arrays. Priority Queue - is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value In case of max-priority queue, the element will be deleted first which has the largest priority value In case of min-priority queue the element will be deleted first which has the minimum priority value. De-queue (Double ended queue) - allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end.

Input restricted deque - In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends. Output restricted deque - In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.

The easiest solution that comes to mind here is iteration:

function fib(n){
  let arr = [0, 1];
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1])
  }
return arr[n]
}

And output:

fib(4)
=> 3

Notice that two first numbers can not really be effectively generated by a for loop, because our loop will involve adding two numbers together, so instead of creating an empty array we assign our arr variable to [0, 1] that we know for a fact will always be there. After that we create a loop that starts iterating from i = 2 and adds numbers to the array until the length of the array is equal to n + 1 . Finally, we return the number at n index of array. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) An algorithm in our iterative solution takes linear time to complete the task. Basically we iterate through the loop n-2 times, so Big O (notation used to describe our worst case scenario) would be simply equal to O (n) in this case. The space complexity is O(n) . Implementation: JS

function fib(n){
  let arr = [0, 1]
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1])
  }
return arr[n]
}
Java
double fibbonaci(int n){
  double prev=0d, next=1d, result=0d;
  for (int i = 0; i < n; i++) {
    result=prev+next;
    prev=next;
    next=result;
  }
return result;
}
PY
def fib_iterative(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1

return a

Recursive solution looks pretty simple (see code). Let’s look at the diagram that will help you understand what’s going on here with the rest of our code. Function fib is called with argument 5: Basically our fib function will continue to recursively call itself creating more and more branches of the tree until it hits the base case, from which it will start summing up each branch’s return values bottom up, until it finally sums them all up and returns an integer equal to 5. Complexity Analysis:

Time Complexity: O(2^n)

In case of recursion the solution take exponential time, that can be explained by the fact that the size of the tree exponentially grows when n increases. So for every additional element in the Fibonacci sequence we get an increase in function calls. Big O in this case is equal to

O(
2n) . Exponential Time complexity denotes an algorithm

whose growth doubles with each addition to the input data set. Implementation: JS

function fib(n) {
  if (n < 2){

return n

}
return fib(n - 1) + fib (n - 2)
}
Java
public int fibonacci(int n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

PY
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)

A dynamic array is an array with a big improvement: automatic resizing. One limitation of arrays is that they're fixed size, meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

Binary search tree is a data structure that quickly allows to maintain a sorted list of numbers. It is called a binary tree because each tree node has maximum of two children. It is called a search tree because it can be used to search for the presence of a number in O(log n) time. The properties that separates a binary search tree from a regular binary tree are: All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs i.e. they have the above two properties

The space complexity of a datastructure indicates how much space it occupies in relation to the amount of elements it holds. For example a space complexity of O(1) would mean that the datastructure alway consumes constant space no matter how many elements you put in there. O(n) would mean that the space consumption grows linearly with the amount of elements in it. A hashtable typically has a space complexity of O(n) .

A Binary Heap is a Binary Tree with following properties:

It’s a complete tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap. 10 10 / \ /
20 100 15 30 / / \ /
30 40 50 100 40

That is a basic (generic) tree structure that can be used for String or any other object: Implementation: Java

public class Tree<T> {
  private Node<T> root;
  public Tree(T rootData) {
    root = new Node<T>();
    root.data = rootData;
    root.children = new ArrayList<Node<T>>();
  }
public static class Node<T> {
  private T data;
  private Node<T> parent;
  private List<Node<T>> children;
}
}
PY
Generic Tree:
class Tree(object):
"Generic tree node."
def __init__(self, name='root', children=None):
self.name = name
self.children = []
if children is not None:
for child in children:
self.add_child(child)
def __repr__(self):

return self.name def add_child(self, node):

assert isinstance(node, Tree)
self.children.append(node)

# *
# /|\
# 1 2 +
# / \
# 3 4
t = Tree('*', [Tree('1'),
Tree('2'),
Tree('+', [Tree('3'),
Tree('4')])])
Binary tree:
class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None

Graph: Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph) Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices Could be directed or undirected (which would apply to all edges in the graph) Tree: A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG)) Vertices are more commonly called "nodes" Edges are directed and represent an "is child of" (or "is parent of") relationship Each node (except the root node) has exactly one parent (and zero or more children) Has exactly one "root" node (if the tree has at least one node), which is a node without a parent Has to be connected Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself" Trees aren't a recursive data structure

Char arrays: Static-sized Fast access Few built-in methods to manipulate strings A char array doesn’t define a data type Strings: Slower access Define a data type Dynamic allocation More built-in functions to support string manipulations

Linked lists are very useful when you need : to do a lot of insertions and removals, but not too much searching, on a list of arbitrary (unknown at compile- time) length. splitting and joining (bidirectionally-linked) lists is very efficient. You can also combine linked lists - e.g. tree structures can be implemented as "vertical" linked lists (parent/child relationships) connecting together horizontal linked lists (siblings). Using an array based list for these purposes has severe limitations: Adding a new item means the array must be reallocated (or you must allocate more space than you need to allow for future growth and reduce the number of reallocations)

Removing items leaves wasted space or requires a reallocation inserting items anywhere except the end involves (possibly reallocating and) copying lots of the data up one position

To convert a singly linked list to a circular linked list, we will set the next pointer of the tail node to the head pointer. Create a copy of the head pointer, let's say temp . Using a loop, traverse linked list till tail node (last node) using temp pointer. Now set the next pointer of the tail node to head node. temp->next = head Implementation: PY def convertTocircular(head):

# declare a node variable
# start and assign head
# node into start node.
start = head# check that
while head.next
# not equal to null then head
# points to next node.
while(head.next is not None):
head = head.next#
if head.next points to null
# then start assign to the
# head.next node.
head.next = start

return start

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array. In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i , its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one). The HeapSort steps are: Create a max heap from the unsorted list Swap the max element, located at the root, with the last element Re- heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place. Repeat Steps 2–3 until complete (when the list size is 1)

Visualisation: Complexity: Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n) Best:

O(
n log n)
Average:
O(
n log n)
Worst:
O(
n log n)
Implementation:
JS
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];
function swap(a, i, j) {
  var tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
function max_heapify(a, i, length) {
  while (true) {
    var left = i*2 + 1;

    var right = i*2 + 2;
    var largest = i;
    if (left < length && a[left] > a[largest]) {
      largest = left;
    }
  if (right < length && a[right] > a[largest]) {
    largest = right;
  }
if (i == largest) {
  break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
  for (var i = Math.floor(length/2); i >= 0; i--) {
    max_heapify(a, i, length);
  }
}
function heapsort(a) {
  heapify(a, a.length);
  for (var i = a.length - 1; i > 0; i--) {
    swap(a, i, 0);
    max_heapify(a, 0, i-1);
  }
}
heapsort(a);
PY
def heapsort(lst):
"""

Sorts list in-place with a heap. """

last_element = len(lst) - 1
lst = heapify(lst)
while last_element >= 0:
# swap the max element with the last element
# like popping off the max
swap(lst, 0, last_element)
# rebalance the remaining heap, from index 0 to last_element exclusive
balance(lst, 0, last_element)
last_element -= 1

return lst def heapify(lst): """ Turns list into a max heap in-place, in linear time. Begins process at 1 depth before leaves. """# initiliazes cur at halfway point based on length of list

if len(lst) % 2 == 0:
cur = len(lst) / 2 - 2
else:
cur = len(lst) / 2 - 1

# rebalance until reached beginning of list
while cur >= 0:
balance(lst, cur)
cur -= 1

return lst def swap(lst, i, last_element): """ Swaps two elments of a list - the current and last in this case. """ lst[i], lst[last_element] = lst[last_element], lst[i] def balance(lst, cur, last_element=None): """ Rebalances heap. Keyword arg for last_element allows for re-use in both heapify and heapsort. """ if last_element is None:

last_element = len(lst)
while cur < last_element:
left_child = 2*cur + 1
right_child = 2*cur + 2
# check to see if we're out of bounds for the children
# this is necessary for even length heaps
if left_child >= last_element:

return

if right_child >= last_element:
# since left child is in bounds, check for swap
if lst[cur] < lst[left_child]:
swap(lst, cur, left_child)

return

if we're in bounds for both children, find the max

max_child = find_max_child(lst, left_child, right_child)

check to see if swap needed

if lst[cur] < lst[max_child]:
swap(lst, cur, max_child)
cur = max_child

Let's look at the merge principle: Given two separate lists A and B ordered from least to greatest, construct a list C by: repeatedly comparing the least value of A to the least value of B, removing (or moving a pointer) the lesser value, and appending it onto C. when one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list.

Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) This problem will have O(n) complexity at best. Implementation: JS

function merge(a, b) {
  var result = [];
  var ai = 0;
  var bi = 0;
  while (true) {
    if ( ai < a.length && bi < b.length) {
      if (a[ai] < b[bi]) {
        result.push(a[ai]);
        ai++;
      } else if (a[ai] > b[bi]) {
        result.push(b[bi]);
        bi++;
      } else {
        result.push(a[ai]);
        result.push(b[bi]);
        ai++;
        bi++;
      }
  } else if (ai < a.length) {
    result.push.apply(result, a.slice(ai, a.length));
    break;
  } else if (bi < b.length) {
    result.push.apply(result, b.slice(bi, b.length));
    break;
  } else {
    break;
  }

}
return result;
}
Java
public static int[] merge(int[] a, int[] b) {
  int[] answer = new int[a.length + b.length];
  int i = 0, j = 0, k = 0;
  while (i < a.length && j < b.length)
  answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
  while (i < a.length)
  answer[k++] = a[i++];
  while (j < b.length)
  answer[k++] = b[j++];
  return answer;
}
PY
def merge(left, right):
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
if left[i] <= right[j]:
print('Appending {} to the result'.format(left[i]))
result.append(left[i])
print('result now is {}'.format(result))
i += 1
print('i now is {}'.format(i))
else:
print('Appending {} to the result'.format(right[j]))
result.append(right[j])
print('result now is {}'.format(result))
j += 1
print('j now is {}'.format(j))
print('One of the list is exhausted. Adding the rest of one of the lists.')
result += left[i:]
result += right[j:]
print('result now is {}'.format(result))

return result

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array. In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i , its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one). The HeapSort steps are: Create a max heap from the unsorted list Swap the max element, located at the root, with the last element Re- heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place. Repeat Steps 2–3 until complete (when the list size is 1)

Visualisation: Complexity: Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n) Best:

O(
n log n)
Average:
O(
n log n)
Worst:
O(
n log n)
Implementation:
JS
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];
function swap(a, i, j) {
  var tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
function max_heapify(a, i, length) {
  while (true) {
    var left = i*2 + 1;

    var right = i*2 + 2;
    var largest = i;
    if (left < length && a[left] > a[largest]) {
      largest = left;
    }
  if (right < length && a[right] > a[largest]) {
    largest = right;
  }
if (i == largest) {
  break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
  for (var i = Math.floor(length/2); i >= 0; i--) {
    max_heapify(a, i, length);
  }
}
function heapsort(a) {
  heapify(a, a.length);
  for (var i = a.length - 1; i > 0; i--) {
    swap(a, i, 0);
    max_heapify(a, 0, i-1);
  }
}
heapsort(a);
PY
def heapsort(lst):
"""

Sorts list in-place with a heap. """

last_element = len(lst) - 1
lst = heapify(lst)
while last_element >= 0:
# swap the max element with the last element
# like popping off the max
swap(lst, 0, last_element)
# rebalance the remaining heap, from index 0 to last_element exclusive
balance(lst, 0, last_element)
last_element -= 1

return lst def heapify(lst): """ Turns list into a max heap in-place, in linear time. Begins process at 1 depth before leaves. """# initiliazes cur at halfway point based on length of list

if len(lst) % 2 == 0:
cur = len(lst) / 2 - 2
else:
cur = len(lst) / 2 - 1

# rebalance until reached beginning of list
while cur >= 0:
balance(lst, cur)
cur -= 1

return lst def swap(lst, i, last_element): """ Swaps two elments of a list - the current and last in this case. """ lst[i], lst[last_element] = lst[last_element], lst[i] def balance(lst, cur, last_element=None): """ Rebalances heap. Keyword arg for last_element allows for re-use in both heapify and heapsort. """ if last_element is None:

last_element = len(lst)
while cur < last_element:
left_child = 2*cur + 1
right_child = 2*cur + 2
# check to see if we're out of bounds for the children
# this is necessary for even length heaps
if left_child >= last_element:

return

if right_child >= last_element:
# since left child is in bounds, check for swap
if lst[cur] < lst[left_child]:
swap(lst, cur, left_child)

return

if we're in bounds for both children, find the max

max_child = find_max_child(lst, left_child, right_child)

check to see if swap needed

if lst[cur] < lst[max_child]:
swap(lst, cur, max_child)
cur = max_child

Let's look at the merge principle: Given two separate lists A and B ordered from least to greatest, construct a list C by: repeatedly comparing the least value of A to the least value of B, removing (or moving a pointer) the lesser value, and appending it onto C. when one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list.

Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) This problem will have O(n) complexity at best. Implementation: JS

function merge(a, b) {
  var result = [];
  var ai = 0;
  var bi = 0;
  while (true) {
    if ( ai < a.length && bi < b.length) {
      if (a[ai] < b[bi]) {
        result.push(a[ai]);
        ai++;
      } else if (a[ai] > b[bi]) {
        result.push(b[bi]);
        bi++;
      } else {
        result.push(a[ai]);
        result.push(b[bi]);
        ai++;
        bi++;
      }
  } else if (ai < a.length) {
    result.push.apply(result, a.slice(ai, a.length));
    break;
  } else if (bi < b.length) {
    result.push.apply(result, b.slice(bi, b.length));
    break;
  } else {
    break;
  }

}
return result;
}
Java
public static int[] merge(int[] a, int[] b) {
  int[] answer = new int[a.length + b.length];
  int i = 0, j = 0, k = 0;
  while (i < a.length && j < b.length)
  answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
  while (i < a.length)
  answer[k++] = a[i++];
  while (j < b.length)
  answer[k++] = b[j++];
  return answer;
}
PY
def merge(left, right):
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
if left[i] <= right[j]:
print('Appending {} to the result'.format(left[i]))
result.append(left[i])
print('result now is {}'.format(result))
i += 1
print('i now is {}'.format(i))
else:
print('Appending {} to the result'.format(right[j]))
result.append(right[j])
print('result now is {}'.format(result))
j += 1
print('j now is {}'.format(j))
print('One of the list is exhausted. Adding the rest of one of the lists.')
result += left[i:]
result += right[j:]
print('result now is {}'.format(result))

return result

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation:

ABC

// original string (3)

ABC ACB BAC BCA CBA CAB

// permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion: Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call. The base case is when the input is an empty string the only permutation is the empty string. In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case. Complexity Analysis: Time Complexity: O(n!) Space Complexity: O(n!) For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) . Implementation: JS

// using backtracking
let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position, e.q. backtrack to prev state of the string
      str = swap(str, left, i);
    }
}
}//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];

  return arr.join('');
}
Java
public static void permutation(String str) {
  permutation("", str);
}
private static void permutation(String prefix, String str) {
  int n = str.length();
  if (n == 0) System.out.println(prefix);
  else {
    for (int i = 0; i < n; i++)
    // take new prefix from string[i], put it as a first element and construct the rest of the
    string
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
  }
}
PY
# using backtracking
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
# backtrack
# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1. In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.

A weight is a numerical value attached to each individual edge. If edges in our graph have weights then your graph is said to be a weighted graph if the edges do not have weights, the graph is said to be unweighted A cyclic graph is a directed graph which contains a path from at least one node back to itself. In simple terms cyclic graphs contain a cycle. An acyclic graph is a directed graph which contains absolutely no cycle, that is no node can be traversed back to itself. Dense graph is a graph in which the number of edges is close to the

maximal (max) number of edges.

Sparse graph is a graph in which the number of edges is close to the

minimal (min) number of edges.

Sparse graph can be a disconnected graph. A graph is connected if any two vertices of the graph are connected by a path. A graph is disconnected if at least two vertices of the graph are not connected by a path. In a multigraph, there can be more than one edge from vertex 1 to vertex 2. In a simple graph there is at most one.

Hash tables are O(1) average and amortized time complexity case complexity, however it suffers from O(n) worst case time complexity (when you have only one bucket in the hash table, then the search complexity is O(n) ). A hashtable typically has a space complexity of O(n) . Hash tables suffer from O(n) worst time complexity due to two reasons:

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time (for linked

lists)

2. Once a hash table has passed its load balance - it has to rehash (create a new bigger table, and re-insert each element to the table). However, it is said to be O(1) average and amortized case because:
3. It is very rare that many items will be hashed to the same key if you chose a good hash function and you don't have too big load balance.
4. The rehash operation, which is O(n) , can at most happen after n/2 ops, which are all assumed O(1) : Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node.

In an in-order traversal, first the left sub-tree is traversed, then the root is visited, and finally the right sub-tree is traversed. One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list in-place i.e. we should not create new nodes for the doubly linked list. This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified. Start with the root node and solve left and right sub-trees recursively At each step, once left and right sub-trees have been processed: fuse output of left subtree with root to make the intermediate result fuse intermediate result (built in the previous step) with output from the right sub-tree to make the final result of the current recursive call Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n)

Recursive solution has

O(
h) memory complexity as it will consume memory on the stack up to the height of

binary tree h . It will be

O(
log n) for balanced tree and in worst case can be
O(
n) .
Implementation:
Java
public static void BinaryTreeToDLL(Node root) {
  if (root == null)
  return;
  BinaryTreeToDLL(root.left);
  if (prev == null) {
    // first node in list
    head = root;
  } else {
    prev.right = root;
    root.left = prev;
  }
prev = root;
BinaryTreeToDLL(root.right);
if (prev.right == null) {
  // last node in list
  head.left = prev;
  prev.right = head;
}
}
PY
def BinaryTreeToDLL(self, node):
#Checks whether node is None
if(node == None):
return;#Convert left subtree to doubly linked list
self.BinaryTreeToDLL(node.left);#If list is empty, add node as head of the list
if(self.head == None):

#Both head and tail will point to node

self.head = self.tail = node;

#Otherwise, add node to the end of the list else: #node will be added after tail such that tail's right will point to node

self.tail.right = node;
#node's left will point to tail
node.left = self.tail;
#node will become new tail
self.tail = node;#Convert right subtree to doubly linked list
self.BinaryTreeToDLL(node.right);

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation:

ABC

// original string (3)

ABC ACB BAC BCA CBA CAB

// permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion: Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call. The base case is when the input is an empty string the only permutation is the empty string. In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case. Complexity Analysis: Time Complexity: O(n!) Space Complexity: O(n!) For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) . Implementation: JS

// using backtracking
let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position, e.q. backtrack to prev state of the string
      str = swap(str, left, i);
    }
}
}//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];

  return arr.join('');
}
Java
public static void permutation(String str) {
  permutation("", str);
}
private static void permutation(String prefix, String str) {
  int n = str.length();
  if (n == 0) System.out.println(prefix);
  else {
    for (int i = 0; i < n; i++)
    // take new prefix from string[i], put it as a first element and construct the rest of the
    string
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
  }
}
PY
# using backtracking
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
# backtrack
# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

Some applications of trie data structure include: dictionary lookup prefix searches auto complete feature in text editors command completion in IDE etc phone number/contacts searching IP lookups mapping URLs to operations on a web server matching sentences (if a trie based on a sequence of words, like Gmail autocompletion) index a complete text (as the Ukkonen suffix tree algorithm alternative)

AVL trees are height balancing binary search tree. It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. This allows us to search for an element in the AVL tree in O(log n) , where n is the number of elements in the tree. The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N))
// BalanceFactor(N) belongs to the
set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations: Left Rotation, Right Rotation, Left Right Rotation, Right Left Rotation.

A tree is said to be balanced only when all three conditions satisfy: The left and right subtrees height differ by at most one The left subtree is balanced The right subtree is balanced Height-balancing requirement: A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1. A tree is height-balanced if all of its nodes are height-balanced.

In a balanced BST, the height of the tree is log n where n is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto n which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time O(n) that shall be avoided. Balanced BST maintains h = O(log n) so all operations run in O(log n) time.

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists: In Array:

insert() operation can be implemented by adding an item at end of array in O(1) time.
getMax() operation can be implemented by linearly searching the highest priority item in array. This
operation takes O(n) time.
deleteMax() operation can be implemented by first linearly searching an item, then removing the item by

moving all subsequent items one position back. In a Binary Heap:

getMax() can be implemented in O(1) time,
insert() can be implemented in O(log n) time and
deleteMax() can also be implemented in O(log n) time.

A sparse array is an array of data in which many elements have a value of zero. This is in contrast to a dense array, where most of the elements have non-zero values or are “full” of numbers.

0 3 5 0 0 0 0 9 0 0 For example consider representing a very large 2D matrix of values, where most of the values are 0. The most straightforward representation would be a very large two dimensional array of integers. This straightforward approach has a few limitations however. If the matrix we are reperesenting is very large, it requires a large quantity of memory to store, even if the number of non-zero elements is small. A better way of representing a sparse martrix would be to only store the values that are non-zero, in such a way that iterating through the rows or columns of non-empty elements is relatively fast.

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of [key, value] pairs, such that each possible key appears at most once in the collection. Associative array can be implemented as: Hash table Self-balancing binary search tree Unbalanced binary search tree Association list

A hash table can look up individual strings very quickly. It's like a thoroughbred racehorse. That's all it can do. A trie, on the other hand, is a workhorse that can do a lot of things. It'll never be as fast at lookups as a hash table, but it can do lots of things that the hash table can't do. For example, finding all the words in a hash table that start with "pre" will take O(n) time because you have to search all of the words. With a trie, it takes three probes to find the subtree that contains all of those words, and then all you have to do is traverse that subtree. Sure, the worst case is O(n) , but that's only if all the words in your trie start with "pre".

Think about B-Tree as a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set ), but is most commonly used to implement a map (ditto for java.util.Map ). If you think about a linguistic dictionary, it's ordered by "word", and associated with each word is a definition. You look up a word, and get a definition. The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query. A typical use of B-Trees is to implement DB indexes. A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store. A typical use in a modern filesystem is to implement directories ("folders" if you're more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.

1. To find the length of loop apply Tortoise and Hare algorithm: Pointer A advances one (1) node a time. Pointer B advanced two (2) node a time. Start from head, they advanced at the same time until B hit null (no loop) or A and B point to the same node.
2. Now, has A advances only, A would meet B again. From that you can find the length of the loop say L.
3. Start from head again, this time have a pointer C advances L nodes first, followed by pointer D behind it, each advances one node at a time.
4. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop.

Implementation: Java package com.farenda.tutorials.algorithms.lists;

public class FloydCycleDetector {
  private int position;
  private int length;
  private boolean cycle;
  private Node head, tortoise, hare;
  public void detect(Node head) {
    this.head = head;
    this.tortoise = this.hare = head;
    this.cycle = detectCycle();
    if (cycle) {
      System.out.println("Found cycle.");
      this.position = findPosition();
      this.length = cycleLength();
    } else {
      System.out.println("No cycle.");
      this.position = -1;
      this.length = 0;
    }
}
public boolean hasCycle() {
  return cycle;
}
public int length() {
  return length;
}
public int position() {
  return position;
}
private boolean detectCycle() {
  if (tortoise == null || tortoise.next == null) {
    return false;
  }
while (hare != null && hare.next != null) {
  System.out.printf("(%d, %d),", tortoise.data, hare.data);
  tortoise = tortoise.next;
  hare = hare.next.next;
  if (tortoise == hare) {
    System.out.printf("turtle(%d) == hare(%d)%n",
    tortoise.data, hare.data);
    return true;
  }
}
return false;
}
private int findPosition() {
  int i = 1;
  tortoise = head;
  System.out.printf("(%d, %d),", tortoise.data, hare.data);
  while (tortoise != hare) {
    tortoise = tortoise.next;
    hare = hare.next;
    ++i;
  }
return i;
}
private int cycleLength() {
  int i = 0;
  do {

    hare = hare.next;
    ++i;
  } while (tortoise != hare);
return i;
}
}
PY
nodes = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2)]
def next(parent):
def find(nodes, parent):
current = nodes[0]
rest = nodes[1:]
if current and current[0] == parent:
return current[1]
else:
return find(rest, parent)
return find(nodes, parent)
def next_next(x):
return next(next(x))
def meet(slow, fast, p1, p2, steps):
p1 = slow(p1)
p2 = fast(p2)
steps = steps + 1
if p1 == p2:
return (p1, steps)
else:
return meet(slow, fast, p1, p2, steps)
def meet_result(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[0]
def meet_count(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[1]
def find_cycle(init):
cycle_meet = meet_result(next, next_next, init, init)
cycle_root = meet_result(next, next, cycle_meet, init)
cycle_length = meet_count(lambda x: x, next, cycle_root, cycle_root)
return (cycle_meet, cycle_root, cycle_length)

1. To find the length of loop apply Tortoise and Hare algorithm:

Pointer A advances one (1) node a time. Pointer B advanced two (2) node a time. Start from head, they advanced at the same time until B hit null (no loop) or A and B point to the same node. 2. Now, has A advances only, A would meet B again. From that you can find the length of the loop say L. 3. Start from head again, this time have a pointer C advances L nodes first, followed by pointer D behind it, each advances one node at a time. 4. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop. Implementation: Java package com.farenda.tutorials.algorithms.lists;

public class FloydCycleDetector {
  private int position;
  private int length;
  private boolean cycle;
  private Node head, tortoise, hare;
  public void detect(Node head) {
    this.head = head;
    this.tortoise = this.hare = head;
    this.cycle = detectCycle();
    if (cycle) {
      System.out.println("Found cycle.");
      this.position = findPosition();
      this.length = cycleLength();
    } else {
      System.out.println("No cycle.");
      this.position = -1;
      this.length = 0;
    }
}
public boolean hasCycle() {
  return cycle;
}
public int length() {
  return length;
}
public int position() {
  return position;
}
private boolean detectCycle() {
  if (tortoise == null || tortoise.next == null) {
    return false;
  }
while (hare != null && hare.next != null) {
  System.out.printf("(%d, %d),", tortoise.data, hare.data);
  tortoise = tortoise.next;
  hare = hare.next.next;
  if (tortoise == hare) {
    System.out.printf("turtle(%d) == hare(%d)%n",
    tortoise.data, hare.data);
    return true;
  }
}
return false;
}

private int findPosition() {
  int i = 1;
  tortoise = head;
  System.out.printf("(%d, %d),", tortoise.data, hare.data);
  while (tortoise != hare) {
    tortoise = tortoise.next;
    hare = hare.next;
    ++i;
  }
return i;
}
private int cycleLength() {
  int i = 0;
  do {
    hare = hare.next;
    ++i;
  } while (tortoise != hare);
return i;
}
}
PY
nodes = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2)]
def next(parent):
def find(nodes, parent):
current = nodes[0]
rest = nodes[1:]
if current and current[0] == parent:
return current[1]
else:
return find(rest, parent)
return find(nodes, parent)
def next_next(x):
return next(next(x))
def meet(slow, fast, p1, p2, steps):
p1 = slow(p1)
p2 = fast(p2)
steps = steps + 1
if p1 == p2:
return (p1, steps)
else:
return meet(slow, fast, p1, p2, steps)
def meet_result(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[0]
def meet_count(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[1]
def find_cycle(init):
cycle_meet = meet_result(next, next_next, init, init)
cycle_root = meet_result(next, next, cycle_meet, init)
cycle_length = meet_count(lambda x: x, next, cycle_root, cycle_root)
return (cycle_meet, cycle_root, cycle_length)

There is actually a simple mathematical formula called Binet's formula for computing the nth Fibonacci number, which does not require the calculation of the preceding numbers: It features the Golden Ratio (φ):

φ = (1+sqrt(5))/2

or The iterative approach scales linearly, while the formula approach is basically constant time. Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n) Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the n th Fibonacci number in O(log n) time ( O(log n) because of the exponentiation in the formula). Implementation: CS

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
const double inverseSqrt5 = 0.44721359549995793928183473374626
const double phi = 1.6180339887498948482045868343656
*/
static int Fibonacci(int n) {
  return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
JS
const sqrt = Math.sqrt;
const pow = Math.pow;

const fibCalc = n => Math.round(
(1 / sqrt(5)) *
(
pow(((1 + sqrt(5)) / 2), n) -
pow(((1 - sqrt(5)) / 2), n)
)
);
Java
private static long fibonacci(int n) {
  double pha = pow(1 + sqrt(5), n);
  double phb = pow(1 - sqrt(5), n);
  double div = pow(2, n) * sqrt(5);
  return (long)((pha - phb) / div);
}
PY
def fib_formula(n):
golden_ratio = (1 + math.sqrt(5)) / 2
val = (golden_ratio**n - (1 - golden_ratio)**n) / math.sqrt(5)
return int(round(val))

Traversal more efficient than

O(
n) is not possible, since "traversal" requires accessing

each node in turn. It is possible to make random access faster than

O(
n) though, by maintaining a second linked list that retains
links to intermediate nodes; insertion, deletion, and appending cost will go up though, due to the increased

complexity of maintenance of the second list.

Short answer: Delete a node in a Single Linked List:

O(
n)

You don't know which is the preceeding node so you have to traverse the list until you find it:

deleteNode(Node node){
  prevNode = tmpNode;
  tmpNode = prevNode.next;
  while (tmpNode != null) {
    if (tmpNode == node) {
      prevNode.next = tmpNode.next;
    }
  prevNode = tmpNode;
  tmpNode = prevNode.next;

}
}

Delete a node in a Double Linked List:

O(
1)

You can simply update the links like this:

deleteNode(Node node){
  node.prev.next = node.next;
  node.next.prev = node.prev;
}
Long Answer:

Insertion is clearly less work in a singly-linked list, as long as you are content to always insert at the head or after some known element. (That is, you cannot insert before a known element, but see below.) Deletion, on the other hand, is trickier because you need to know the element before the element to be deleted. One way of doing this is to make the delete API work with the predecessor of the element to be deleted. This mirrors the insert API, which takes the element which will be the predecessor of the new element, but it's not very convenient and it's hard to document. It's usually possible, though. Generally speaking, you arrive at an element in a list by traversing the list. Of course, you could just search the list from the beginning to find the element to be deleted, so that you know what its predecessor was. That assumes that the delete API includes the head of the list, which is also inconvenient. Also, the search is stupidly slow. The way that hardly anyone uses, but which is actually pretty effective, is to define a singly-linked list iterator to be the pointer to the element preceding the current target of the iterator. This is simple, only one indirection slower than using a pointer directly to the element, and makes both insertion and deletion fast. The downside is that deleting an element may invalidate other iterators to list elements, which is annoying. (It doesn't invalidate the iterator to the element being deleted, which is nice for traversals which delete some elements, but that's not

much compensation.)

If deletion is not important, perhaps because the data structures are immutable, singly-linked lists offer another really useful property: they allow structure-sharing. A singly-linked list can happily be the tail of multiple heads, something which is impossible for a doubly-linked list. For this reason, singly-linked lists have traditionally been the simple data structure of choice for functional languages.

Fibonacci search is a search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in

O(
log n) time complexity.

Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two unequal parts that have sizes that are consecutive Fibonacci numbers. Some facts to note: Fibonacci search has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication,

operations that were less common at the time Fibonacci search was first published Binary search works by dividing the seek area in equal parts 1:1 . Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations. On average, Fibonacci search requires 4% more comparisons than binary search Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful. Thus Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a non-uniform access memory storage. Let the length of given array be length and the element to be searched be key . Steps of Fibonacci Search:

1. Find the smallest Fibonacci number F(n) that F(n) - 1 >= length

2. F(n) = F(n-1) + F(n-2) => F(n) - 1 = [ F(n-1) - 1 ] + (1) + [ F(n-2) - 1 ] , where (1) here is for the
middle item (the m in below figure).
// |<--------- p: F(n) - 1 --------->|
// |<--- q: F(n-1) - 1 --->| |<-- r: F(n-2) - 1 -->|
// +----+---+--------------------+---+---+---+---+
// | | k | | m | | k | |
// +----+---+--------------------+---+---+---+---+
// ^
3. If key < m , then search key in q = F(n-1) - 1 :
// |<--- p: F(n-1) - 1 --->|
// |<----- q ----->| |<-- r -->|
// +----+---+------+---+---------+
// | | k | | m | |
// +----+---+------+---+---------+
for that set p = F(n-1) - 1, q = F(n-2) - 1, r = F(n-3) - 1 and repeat the process. Here Fibonacci numbers
go

backward once. These indicate elimination of approximately one-third of the remaining array. 4. If key > m , then repeat then search key in r = F(n-2) - 1 :

// |<-- p: F(n-2) - 1 -->|
// |<--- q --->| |<- r ->|
// +---+---+---+
// | | k | | m
// +---+---+---+
// ^
For that, set p = F(n-2) - 1, q = F(n-3) - 1, r = F(n-4) - 1 and repeat the process. Here Fibonacci
numbers go

backward twice, indicating elimination of approximately two-third of the remaining array. Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n) Fibonacci search has an average- and worst-case complexity of

O(
log n) . The worst case will occur when we
have our target in the larger (2/3) fraction of the array, as we proceed to find it. In other words, we are
eliminating the smaller (1/3) fraction of the array every time. We call once for n, then for (2/3) n, then for (4/9) n

and henceforth.

Implementation: CS #include #include #include "search.h" typedef struct FibonacciValues

{
  // Fibonacci number: F(n) = F(n-1) + F(n-2)
  int Fn_2; // F(n-2)
  int Fn_1; // F(n-1)
  int Fn; // F(n)
  FibonacciValues(int fn_2, int fn_1, int fn)
  : Fn_2(fn_2)
  , Fn_1(fn_1)
  , Fn(fn)
  {
    assert(Fn == Fn_1 + Fn_2);
  }
~FibonacciValues()
{
}
void forward()
{
  Fn_2 = Fn_1;
  Fn_1 = Fn;
  Fn = Fn_1 + Fn_2;
  assert(Fn == Fn_1 + Fn_2);
}
void backward()
{
  Fn = Fn_1;
  Fn_1 = Fn_2;
  Fn_2 = Fn - Fn_1;
  assert(Fn == Fn_1 + Fn_2);
}
} FibonacciValues;
// Returns the smallest Fibonacci number that is greater than or equal to k.
FibonacciValues GetFibonacci(int k)
{
  FibonacciValues fib(0, 1, 1);
  while (fib.Fn < k) {
    fib.forward();
  }
return fib;
}
// Notice that the current middle might exceed the array!
int fibonacciSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);

  int left = 0, right = length - 1, middle;
  // Find a fibonacci number F(n) that F(n) - 1 >= length
  FibonacciValues fib = GetFibonacci(length + 1);
  while (left <= right) {
    // Avoid the middle is over the array.
    middle = std::min(left + (fib.Fn_1 - 1), right);
    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      fib.backward();
    } else { // list[middle] < key
    left = middle + 1;
    fib.backward(); fib.backward();
  }
}
return NOT_FOUND;
}
JS
function fib(n) {
  if (n <= 0)
  return 0;
  if (n <= 2)
  return 1;
  return fib(n-1) + fib(n-2);
}
function smallest_greater_eq_fib(n) {
  let f = fib(0),
  cu = 0;
  while (f < n)
  f = fib(++cu);
  return cu;
}
async function fibonacciSearch(a, k, l, r, display) {
  let f = smallest_greater_eq_fib(r-l+1);
  while (f >= 0) {
    i = Math.min(l+fib(f-1), r-1);
    i = Math.max(0, i);
    refresh(glob_comp, a[i]);
    display(a, i, l, r);
    await sleep(glob_sleep_time);
    if (a[i]==k) {
      glob_comp++;
      refresh(glob_comp, a[i]);
      return new Promise(resolve => resolve(i));
    } else if (k < a[l+fib(f-1)]) {
      glob_comp+=2;
      refresh(glob_comp, a[i]);
      r = i;
      f-=1;
    } else {
      glob_comp+=2;
      refresh(glob_comp, a[i]);
      l = i;
      f-=2;
    }

}
return new Promise(resolve => resolve(-1));
}
Java
public class Fibonacci_Search
{
  static int kk = -1, nn = -1;
  static int fib[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
    377, 610, 98, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
    75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
    3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
    102334155, 165580141 };
  static int fibsearch(int a[], int n, long x)
  {
    int inf = 0, pos, k;
    if (nn != n)
    {
      k = 0;
      while (fib[k] < n)
      k++;
      kk = k;
      nn = n;
    }
  else
  k = kk;
  while (k > 0)
  {
    pos = inf + fib[--k];
    if ((pos >= n) || (x < a[pos]))
    ;
    else if (x > a[pos])
    {
      inf = pos + 1;
      k--;
    }
  else
  return pos;
}
return -1;
}
}
PY
def FibonacciSearch(lys, val):
fibM_minus_2 = 0
fibM_minus_1 = 1
fibM = fibM_minus_1 + fibM_minus_2
while (fibM < len(lys)):
fibM_minus_2 = fibM_minus_1
fibM_minus_1 = fibM
fibM = fibM_minus_1 + fibM_minus_2
index = -1;
while (fibM > 1):
i = min(index + fibM_minus_2, (len(lys)-1))
if (lys[i] < val):
fibM = fibM_minus_1
fibM_minus_1 = fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1
index = i
elif (lys[i] > val):
fibM = fibM_minus_2

fibM_minus_1 = fibM_minus_1 - fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1
else :

return i

if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
return index+1;

return -1

A graph is bipartite when the graph vertices are parted into two disjoint sets; no two adjacent vertices would reside in the same set. A bipartite graph must not contain odd cycle (a cycle with an odd number of vertices). BFS (Breadth First Search) can be used in detecting a bipartite graph. Another method of checking a bipartite graph is to check the occurrence of an odd cycle in the graph.

A Rope data structure is a tree data structure which is used to store or manipulate large strings in a more efficient manner. It allows for operations like insertion, deletion, search and random access to be executed faster and much more efficiently in comparison to a traditional String. More specifically a rope is a binary tree (that is, each node can have maximum of 2 children) where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. Nodes that are not leaf nodes do not hold an array of characters.

Pascal strings were made popular by one specific, but huge influential Pascal implementation, named UCSD. So UCSD Strings is a better term. In general it is not one specific type, but the basic principle of having the size prefixed to the character data. This makes getting the length a constant time operation O(1) instead of scanning the character data for a nul character. Pascal strings excel in... everything. NUL terminated strings save one to three bytes on short strings, which may have been useful in 1970 but isn't even worth mentioning today in virtually all circumstances. Aside from not being able to store a zero byte (which isn't too bad for text but rules out any kind of binary data), you can't determine string length efficiently. This affects a a good portion of string algorithms negatively. One example, in the comment you link to, is string comparison: If you have the length, you can instantly return false when comparing strings of different length.

The following are the main advantages of tries over hash tables: Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless. Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above. Performing such a "closest fit" find can, depending on implementation, be as quick as an exact find. Tries tend to be faster on average at insertion than hash tables because hash tables must rebuild their index when it becomes full - a very expensive operation. Tries therefore have much better bounded worst case time costs, which is important for latency sensitive programs. By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers.

Tries and hash tables are used for different things: If all you want is the ability to lookup a word, then a hash table will be faster. A well constructed hash table (i.e. a good hash function and a reasonable load factor) has O(1) lookup time. If you want to find common prefixes, ordered retrieval, or do similar things, then you want a trie. Lookup time in a trie is O(m) : it depends on the length of the string you're looking up. And memory wise: A hash table's overhead is typically a constant multiple of the number of words it contains. That is, in addition to the memory required to store the strings, there is per-string overhead to store the mapping between hash code and string. Memory for a trie is a little more involved. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That's a million nodes of overhead.

B-tree is a self-balancing tree data structure that maintains sorted data. B-tree stores data such that each node contains keys in ascending order. Unlike a binary tree, each node in a B-Tree can have more than 2 children. Each node can have up to m children, where m is called the tree’s “order”. Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data. It is most commonly used in database and file systems. By maximizing the number of keys within each internal node, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. B-trees may waste some space, since nodes are not entirely full.

A red-black tree is a binary search tree in which each node has a color (red or black) associated with it (in addition to its key and left and right children). This can be saved in memory as a single bit (e.g. 'red' = 1, 'black' = 0). the following 3 properties hold: (root property) The root of the red-black tree is black (red property) The children of a red node are black.

(black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same. This is sometimes known as the black-depth. The height of the red-black tree is at most 2*log(n + 1) Red-black trees maintain a slightly looser height invariant than AVL trees. Because the height of the red-black tree is slightly larger, lookup will be slower in a red-black tree. However, the looser height invariant makes insertion and deletion faster. Also, red-black trees are popular due to the relative ease of implementation.

Quick Sort is a divide and conquer, comparison, in-place algorithm. Efficient implementations of Quicksort are not a stable sort. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Quicksort determines something called a pivot, which is a somewhat arbitrary element in the collection. Using the pivot point, quicksort partitions (or divides) the larger unsorted collection into two, smaller lists. It moves all the elements smaller than the pivot to the left (before) the pivot element, and moves all the elements larger than the pivot to the right (after) the pivot element. Even though the list isn’t completely sorted yet, we know that the items are in the correct order in relation to the pivot. This means that we never have to compare elements on the left side of the partition to elements on the right side of the partition. We already know they are in their correct spots in relation to the pivot. The sub-lists are then sorted recursively. Ideally, partitioning would use the median of the given values (in the array), but the median can only be found by scanning the whole array and this would slow the algorithm down. In that case the two partitions would be of equal size; In the simplest versions of quick sort an arbitrary element, typically the

last (rightmost) element is
used as an estimate (guess) of the median.
Complexity Analysis:
Time Complexity: O(n log n) Space Complexity: O(n log n)

Overall time complexity of Quick Sort is

O(
n log n) . In the worst case, it makes
O(
n2) comparisons (all elements
are same or array is already sorted).
The partition step used in quicksort ideally is an in-place operation (without creating any additional arrays). But
since quicksort calls itself on the order of log(n) times (in the average case), worst case number of calls is

O(
n) , at each recursive call a new stack frame of constant size must be allocated. Hence the
O(
log n) space
complexity.
Implementation:
JS
With additional memory (naive):
function quickSort (arr) {
  if(arr.length <= 1) return arr;// find middle point of array (effectively random pivot)
  var swapPosition = Math.floor((arr.length -1) / 2);
  var pivot = arr.splice(swapPosition, 1);
  var left = [];
  var right = [];
  for(var i = 0; i < arr.length; i++) {
    if(arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i])
    }
}
return quickSort(left).concat(pivot, quickSort(right));
}

In-place:

var quickSort = function(array, left, right) {
  var leftIndex = partition(array, left, right);
  if (left < leftIndex - 1) {
    quickSort(array, left, leftIndex - 1);
  }
if (right > leftIndex) {
  quickSort(array, leftIndex, right);
}
return array;
}
var swap = function(array, left, right) {
  var temp;
  temp = array[leftIndex];
  array[leftIndex] = array[rightIndex];
  array[rightIndex] = temp;
}
var partition = function(array, left, right) {
  var pivotIndex = Math.floor((left + right) / 2);
  var pivot = array[pivotIndex];
  leftIndex = left;
  rightIndex = right;
  while (leftIndex <= rightIndex) {
    while (array[leftIndex] < pivot) {
      leftIndex++;
    }
  while (array[rightIndex] > pivot) {
    rightIndex--;

  }
if (leftIndex <= rightIndex) {
  swap(array, left, right);
  leftIndex++;
  rightIndex--;
}
}
return leftIndex;
}
PY
With additional memory (naive):
def quick_sort(collection):
length = len(collection)
if length <= 1:

return collection else:

Use the last element as the first pivot

pivot = collection.pop()
# Put elements greater than pivot in greater list
# Put elements lesser than pivot in lesser list
greater, lesser = [], []
for element in collection:
if element > pivot:
greater.append(element)
else:
lesser.append(element)
return quick_sort(lesser) + [pivot] + quick_sort(greater)
Quick sort without additional memory (in place):
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]

return pivot def quicksort(array, begin=0, end=None): if end is None:

end = len(array) - 1
def _quicksort(array, begin, end):
if begin >= end:

return

pivot = partition(array, begin, end)
_quicksort(array, begin, pivot-1)
_quicksort(array, pivot+1, end)
return _quicksort(array, begin, end)