Data Structures and Algorithms

Sorting:
No comparison sort can have better worst-case performance than O(nlog(n))
You can make any sorting algorithm stable by assigning a sequence number to each element and using the sequence number as the 
tie-breaker in the multikey sort

Selection Sort:
O(n^2) in all cases. It requires only O(n) swaps, however, it is suitable for data sets where copying is very expensive.

Insertion Sort:
Efficient when dealing with mostly sorted data sets, where it can have O(n) performance, but average and worst cases are O(n^2). 
Selection sort is an in-place algorithm. Typical inmplementations are not stable.
In situations in which moving data elements is more expensive than comparing them, selection sort may perform better than other 
algorithms. 

Quick Sort:
O(nlog(n)) in the best and average cases and O(n^2) in the worst case.

Merge Sort:
O(nlog(n)) in all cases. It is especially useful for sorting data sets that cannot fit into memory. Requires O(n) additional memory. 
Typical merge sort implementation are stable but not in-place.


Heaps:
Find max/min/root in constant time: O(1)
Insertion/Deletion: O(log(n))
Lookup/Printing nodes in order: O(n)

Binary Search Tree:
Lookup in a balanced BST: O(log(n))
Worst case: O(n) (When a tree is created by adding data already in sorted order)
Insertion/Deletion: O(log(n))

Trie:
Inseart and Search: O(key length)
Memory: O(Alphabet Size * key length * number of keys)
Common Uses:
1.Autocomplete
2.Spell Checker
3.IP routing (Longest Prefix Matching)

Trie Vs Hashtable
HT not efficient for finding all keys with a common prefix
Enumerating a dataset of strings in lexicographical order
hash table increases in size, there are lots of hash collisions and the search time 
complexity could deteriorate to O(n), where n is the number of keys inserted. Trie could 
use less space compared to Hash Table when storing many keys with the same prefix. In 
this case using trie has only O(m) time complexity, where m is the key length. 
Searching for a key in a balanced tree costs O(mlogn) time complexity.

Insert:
Time complexity : O(m), where m is the key length.
In each iteration of the algorithm, we either examine or create a node in the trie till 
we reach the end of the key. This takes only m operations.

Space complexity : O(m).
In the worst case newly inserted key doesn't share a prefix with the the keys already 
inserted in the trie. We have to add m new nodes, which takes us O(m) space.

Search:
Time complexity : O(m) In each step of the algorithm we search for the next key character. 
In the worst case the algorithm performs mm operations.

Space complexity : O(1)





Common Searches (searching a tree without the benefit ordering)
Find a node: O(n)

BFS:
A BFS uses additional memory because it is necesssary to track the child nodes for all nodes on a given level while searching that level
Good for searching in upper levels

BFS is sufficient for finding the shortest path when the edges have no(or equal) weights. Dijkstra's Algorithm is used when each edge is 
assigned a weight.

DFS:
DFS has much lower memory requirements than BFS because it is not necessary to store all the child pointers at each level.
Good for searching in lower levels

Traversals (three most common types of depth-first traversals for binary trees:
(These classes of traversals can also apply to nonbinary trees as long as you have a way to classify whether a child is "less than" 
(on the left of) or "reater than" (on the right of) its parent node)

Preorder: a node is always visited before any of its children
Inorder: the left subtree is visited first, then the node itself, and then the node's right subtree
Postorder: a node is always visited after all its children


Topological Sort:
Applications:
Build Systems
Adavanced packaging tools (apt-get)
task scheduling
pre-requisite problems

Modified DFS: O(V+E)

OOP:
Abstraction
Interface
Polymorphism
Inheritence
Encapsulation

Abstraction: The process of picking out (abstracting) common features of objects and procedures.
Class: A category of objects. The class defines all the common properties of the different objects that belong to it.
Encapsulation: The process of combining elements to create a new entity. A procedure is a type of encapsulation because it combines a series of computer instructions.
Information hiding: The process of hiding details of an object or function. Information hiding is a powerful programming technique because it reduces complexity.
Inheritance: a feature that represents the "is a" relationship between different classes.
Interface: the languages and codes that the applications use to communicate with each other and with the hardware.
Messaging: Message passing is a form of communication used in parallel programming and object-oriented programming.
Object: a self-contained entity that consists of both data and procedures to manipulate the data.
Polymorphism: A programming language's ability to process objects differently depending on their data type or class.
Procedure: a section of a program that performs a specific task.

One of the principal advantages of object-oriented programming techniques over procedural programming techniques is that they enable programmers to create modules that do not need to be changed when a new type of object is added. A programmer can simply create a new object that inherits many of its features from existing objects. This makes object-oriented programs easier to modify.

Encapsulation:
encapsulation is one of the four fundamentals of OOP (object-oriented programming). Encapsulation refers to the bundling of data with the methods that operate on that data.[7] Encapsulation is used to hide the values or state of a structured data object inside a class, preventing unauthorized parties' direct access to them. Publicly accessible methods are generally provided in the class (so-called getters and setters) to access the values, and other client classes call these methods to retrieve and modify the values within the object.