Merge Sort vs Quick Sort

94 4/24/2017 12:53:10 AM

Merge Sort Quick Sort Implementation void MeargeSort(int[] arr) { int[] helper = new int[arr.Length]; MergeSort(arr, helper, 0, arr.Length); } void MergeSort(int[] arr, int[] helper, int low, int high) { if (low < high) { int middle = (low + high) / 2; MergeSort(arr, helper, low, middle); MergeSort(arr, helper, low, middle); Merge(arr, helper, low, middle, high); } } void Merge(int[] arr, int[] helper, int low, int middle, int high) { //Copy both halves into a helper array for (int i=low; i<=high; i++) { helper[i] = arr[i]; } int helperLeft = low; int helperRight = middle + 1; int curren...

BFS vs DFS (Breadth First Search vs Depth First Search)

124 4/21/2017 6:55:34 AM

Breadth First Search (BFS) Depth First Search (DFS) Data Structure Used Queue Stack Traversal Level order Traversal Inorder Traversal (Left-Root-Right) Preorder Traversal (Root-Left-Right) Postorder Traversal (Left-Right-Root) Starts visiting nodes from root or leaves Root Leaves When to use If our problem is to search something that is more likely to closer to root. If the target node is close to a leaf, we would prefer DFS Approach Iterative Reccursive Shortes Path Problem BFS is more efficient than DFS. DFS is not recommendedas it will start traversing from a leaf node. Implementation //Sea...

Algorithms - Interview Questions With Answers

64 4/21/2017 6:38:15 AM

Algorithms - Interview Questions With Answers...

Time Complexity of Algorithms

79 4/12/2017 12:54:46 AM

S.No Term Called As Definition 1 O(1) Constant Time Time taken for an operation, fixed number of steps E.g. Push and Pop operations for the stack. Enqueue and Deque operations for Queue. 2 O(log n) Logarithmic Time Time was taken will double with each additional element in the input data set E.g. Binary Search Insert and Find operations in a Binary Search tree. Insert and Remove operations for a heap 3 O(n) Linear Time A number of steps proportional to the size of the tasks. (If the size of the task increases then no of steps increases) E.g. Finding Max/Min element in a list. Sequential search...

Tree vs Graph Data structure

171 3/17/2017 3:47:33 AM

Tree Graph Type Tree is type of graph Root Node Tree has root node Graph may or may not have root node Cycles Tree does not contain cycles Graph contains cycles Direction Trees have parent/child relationships Graph may or may not have parent/child relationships e.g. ...

How relational and non-relational database works?

178 3/15/2017 9:17:59 PM

Relational Database (e.g. SQL) Non-Relational Database (e.g. DynamoDB) Performance Databases are optimized for storage. Performance generally depends on the disk subsystem. Developers must know databaseimplementation details. Developers and database administrators must optimize queries, indexes, and table structures in order to achieve peak performance. DynamoDB is optimized for computing. Performance mainly depends on underlying hardware and network latency. As a managed service, DynamoDB insulates you and your applications from these implementation details. Developerscan focus on designing a...

Spell Checker Using Ternary Search Tree

219 2/13/2017 6:56:42 AM

Ternary Search Tree Advantages More efficientthanTrie. Disadvantages Ternary Search Tree requires a lot of extra space thanTrie. ...

Spell Checker Using Trie

209 2/13/2017 6:55:39 AM

Trie Advantages Can find all words beginning with a prefix. Disadvantages Tries is they require a lot of extra space. Complexity Search time: O(M) where M is the length of the string. ...

Spell Checker Using ​Binary Search Tree

182 2/13/2017 6:54:56 AM

Binary Search Tree Complexity A well-balanced BST will need time proportional to M * log N, M is maximum string length and N is a number of keys in the tree. ...


Spell Checker Using Hashing

211 2/13/2017 6:52:40 AM

Hashing Dictionary Will be stored in Hash Table Spell Checker Matching will be done by exact match. Disadvantage Does not support prefix search,where a user types a prefix and your dictionary shows all words starting with that prefix. Doesn’t support efficient printing of all words in the dictionary in alphabetical order and nearest neighbor search. Complexity Seach - O(n) ...

Ternary Search Tree

195 2/12/2017 9:20:28 AM

Ternary search tree is a type of trie (sometimes called a prefix tree), unlike trie(standard) data structure where each node contains max 26 pointers for its children, each node in a ternary search tree contains only 3 pointers. Pointers in Ternary Tree: The left pointer points to the node whose value is less than the value of the current node. The equal pointer points to the node whose value is equal to/close to the value of the current node. The right pointer points to the node whose value is greater than the value of the current node. ref:http://d1hyf4ir1gqw6c.cloudfront.net//wp-content/upl...

Design Spell Checker

240 2/12/2017 7:28:33 AM

Let's see various data structures (e.g. Hashing, Binary Search Tree, Trie, Ternary Search Tree, BK- Tree) which can be used to design data structure and their features and usage: ...

Design Tic-Tac-Toe

264 2/11/2017 10:57:16 PM

Object Oriented Tic-Tac-Toe Tic-tac-toe - Java Game Programming Case Study Object-Oriented Design - Ohio State Computer Science and Engineering TicTacToe - Game Design design Tic Tac Toe ...

Basic Terminology of Graphs

186 2/7/2017 6:15:55 AM

Define a Graph: G = (V, E)by defining a pair of sets: V = a set ofvertices E = a set ofedges Edges: Each edge is defined by a pair of vertices An edgeconnectsthe vertices that define it In some cases, the vertices can be the same Vertices: Vertices also callednodes Denote vertices with labels Representation: Represent vertices with circles, perhaps containing a label Represent edges with lines between circles Example: V = {A,B,C,D} E = {(A,B),(A,C),(A,D),(B,D),(C,D)} Path: sequence of vertices in which each pair of successive vertices is connected by an edge Cycle: a path that starts and ends ...

Height Balance Tree (aka AVL trees)

192 2/7/2017 6:09:13 AM

Balanced tree -A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced. Height Balanced Tree aka AVL Tree(InventorsG.M. Adel’son-Vel’skii and E.M. Landis), are self-balancing binary search trees. An AVL tree is one that requires heights of left and right children of every node to differ by at most ±1. AVL Tree (Height Balanced Tree) - A tree whose subtrees differ in height by no more than one and the subtrees are height-...

Threaded Binary Tree

181 2/7/2017 6:06:58 AM

What is Threaded Binary Tree? It is a binary tree where leaf node is threaded towardsboththe in-order pre­de­ces­soror suc­ces­sor (leftorright) means all right null point­ers will point to inorder suc­ces­sororall left null point­ers will point to inorder predecessor. A binary tree isthreadedby making all right child pointers that would normally be null point to the inorder successor of the node (ifit exists), and all left child pointers that would normally be null point to the inorder predecessor of the node Why do we need Threaded Binary Tree? Binary tree...

Application of Tree Data Structure

429 2/7/2017 6:05:47 AM

Decision Making Next Move in games Computer chess games build a huge tree (training) which they prune at runtime using heuristics to reach an optimal move. Networking Router algorithms -Network Routing, where the next path/route of the packet is determined Social networking is the current buzzword in CS research. It goes without saying that connections/relations are very naturally modeled using graphs. Often, trees are used to represent/identify more interesting phenomena. Representation Chemical formulas representation XML/Markup parsers use trees Producers/consumers often use a balanced tree...

Basic Terminology Of Trees

168 2/7/2017 4:19:03 AM

Trees are hierarchical data structures, itsabstract data type, made up of nodes or vertices and edges without having any cycle. Tree Terminologies: Root The node at the top of the tree is called root. Parent Any node that has one edge upward to a node Child The node below a given node connected by its edge downward Leaf The node which does not have any child node Level The level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. Height Height is consideredas is the maximum number of nod...

Factorial Function

187 2/7/2017 4:04:04 AM

Factorial Function: Theproduct of the integers 1 through given number. Represented using '!' factorial of 3 will represented as 3!. For example, 3! equals1*2*3(i.e 6) function factorial(n) { if (n<=1) return 1; else return n * factorial(n-1); } How factorial/recursion works: e.g. 3! = 3*2! = 3*2*1! (base case reached) = 3*2*1 (recursion is terminated) ...

Recursion

174 2/7/2017 4:02:34 AM

Recursion is the repeated application of a procedure or function or definition, with one base case/termination case. Examples of Recursion: Application Factorial function Check if word is palindrome Computing powers of a number The Sierpinksi gasket Counting employees under The 8-Queens problem Hierarchies A tree traversal algorithm Networks Google Map Graphs Business’s organization chart A minesweeper game Algorithm Euclid's algorithm (GreteGreateston divisor) Towers of Hanoi ...

Priority Queue

232 2/7/2017 3:53:34 AM

A priority queue can be implemented using many of the data structures that we've already studied (an array, a linked list, or a binary search tree (BST)). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we'll use a new data structure called a heap. Implementing priority queues using heaps A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue supports inserting new priorities and removing/returning the highest priority. When a priority...

Operations On Queues

194 2/7/2017 3:53:01 AM

Queueprimitive operationsare to be supported: enqueue(o): Insert o at rear of queue – Input: Object; Output: None dequeue(): Remove object at front; error if empty – Input: None; Output: Object removed Queuesupport operationsare to be supported: size(): Return number of objects in queue – Input: None; Output: Integer isEmpty(): Return a boolean indicating queue empty – Input: None; Output: Boolean first(): Return object at front without removing; error if empty – Input: None; Output: Object ...

Implementation of queues as an array and linked list

122 2/7/2017 3:51:37 AM

Queue - Array Implementation - Types Queue - Linked-List Implementation - Types ...

Circular Queue

160 2/7/2017 3:50:15 AM

A circular queue follows the basic rules of a queue data structure. It has the first in first out mechanism, but its size is restricted. We just need to keep track of two terms to understand, implement, and use a circular queue; they are: Front position (from where you can dequeue) Rear position (the last element's position in the queue) ...

Queues stored as a linked list

111 2/7/2017 3:49:44 AM

Queue - Linked-List Implementation - Types ...

Queues as an ADT

117 2/7/2017 3:48:19 AM

Collection: Elements of some proper type T Operations: void push (T t) void pop () T front () bool empty () unsigned int size () (plus constructor and destructor) Axioms: (for any Queue Q) Q.size(), Q.empty(), Q.push(t) are always defined Q.pop() and Q.front() are defined iff Q.empty() is false Q.empty(), Q.size(), Q.front() do not change Q Q.empty() is true iff 0 = Q.size() Suppose n = Q.size() and the next element pushed onto Q is t; then, after n elements have been popped from Q, t = Q.front() Q.push(t) increases Q.size() by 1 Q.pop() decreases Q.size() by 1 If t = Q.front() then Q.pop() re...

Converting an expression from infix to postfix

166 2/7/2017 1:06:19 AM

Infix, Prefix and Postfix Expressions: Examples: Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * + (A + B) * C * + A B C A B + C * A + B * C + D + + A * B C D A B C * + D + (A + B) * (C + D) * + A B + C D A B + C D + * A * B + C * D + * A B * C D A B * C D * + A + B + C + D + + + A B C D A B + C + D + Algorithm for converting an expression from infix to postfix: Create an empty stack called myStack for keeping operators. Create an empty list for output. Convert the input infix string to a list by using the string method split. Scan the token ...

Evaluating Postfix expressions

196 2/7/2017 1:05:41 AM

Infix, Prefix and Postfix Expressions: Examples: Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * + (A + B) * C * + A B C A B + C * A + B * C + D + + A * B C D A B C * + D + (A + B) * (C + D) * + A B + C D A B + C D + * A * B + C * D + * A B * C D A B * C D * + A + B + C + D + + + A B C D A B + C + D + Algorithm for evaluating postfix expression: Create an empty stack called myStack. Convert the string to a list by using the string method split. Scan the token list from left to right. If the token is an operand, convert it from a string to an ...

Arithmetic expressions

186 2/7/2017 1:04:50 AM

Anarithmetic expressionis an expression using additions+, subtractions-, multiplications*, divisions/, and exponentials** Anarithmetic expressionis anexpressionthat results in a numeric value. Types of numeric values Integers(whole numbers), and Realorfloating pointnumbers (numbers containing a decimal point). Anarithmetic expressionis a syntactically correct combination of numbers, operators, parenthesis, and variables. Examples: 1 + 3is4 1.23 - 0.45is0.78 3 * 8is24 6.5/1.25is5.2 8.4/4.2is2.0rather than2, since the result must be of Realtype. -5**2is-25 12/4is3 13/4is3rather than3.25. Since13...

stacks stored as a linked list

132 2/7/2017 1:04:04 AM

Implementation of stacks as a linked list ...