Maximum value in a Sliding Window

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 ...

Read More

Container With Most Water

http://n00tc0d3r.blogspot.in/2013/02/container-with-most-water.ht...

Read More

Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them. Problem Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram. (Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.) Consider...

Read More

Arrays Index

Rotated array How to rotate an array? Rotated sorted array Find the minimum element in the rotated sorted array. Find the rotation count in rotated sorted array Find Nth largest element in the rotated sorted array Search an element in the sorted rotated array  Sorted Infinite Arrays Searching the element in sorted infinite array of integers Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .  Binary or only few integer arrays Find the point of transition from 0 to 1 in an infinite...

Read More

Maximum weight independent set (WIS) graph problem using DP

Input - A path graph G = (V,E) with non - negative weights on vertices eg.Consider the graph with vertex weights - 1,4,5,4 Desired output - subset of non-adjacent vertices - an independent set of maximum total weights. Solutions Brute force polynomial time, so lets do better. greedy approach Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex ...

Read More

Sequence Alignment using Dynamic Programming

Problem : Input : 2 strings or sequence of characters i.e. X = x1x2...xm, Y = y1y2...yn Goal - To define the similarity matrix between the 2 sequences with best alignment. This is based on penalty score, called Needleman/Wunsch score. Eg. consider the sequence - AGGGCT and AGGCA , best alignment here is: AGGGCT  |  |  |      | AGG - CA Penalty Penalty = penalty of match+penalty of difference + penalty of...

Read More

Application of clustering

Informal goal - given n points [web pages images, genome fragments, etc] classify into "coherent groups" People in machine learning must have heard of unsupervised learning. Assumption 1) As input, given a (dis) similarity measure 2 symmetric examples - euclidean distance, genome similarity goal - same clusters => nearby So, coherent group has smaller distance. Objective function to do clustering - there are many objective functions, but we are reading max-spacing k-clusterings.  Max spacing  k-clustering Assume we know...

Read More

Minimum Spanning tree MST

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim's algo [1957, also djikstra' 1959] or Jarnic found it in 25 years earlier. Kruskal's algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: O( m log n) time m = edges, n=vertices OR better O (|E| log |V|) Problem definition Input - undirected graph...

Read More

Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here. Example So consider the tree:       1    /    \   2      3  /   \   /    \ 4   5  6   7 The BFS or level order traversal here is : 1 2 3 4 5 6 7 Last time we used BFS,...

Read More

Binary Tree Post-Order Traversal - Recursive and Iterative Solution

Consider the tree: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root. Therefore, the Postorder traversal of the above tree will...

Read More

Binary Tree In-Order Traversal - Recursive and Iterative Solution

Consider the tree Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree. To traverse a binary tree in Inorder, following operations are carried-out : Traverse the left most subtree starting at the left external node,  Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will...

Read More

Find the rank w.r.t K - Number of nodes with value less than K

If the rank of the BST is k, it implies how many nodes/keys are less than k. So, it boils down to 3 easy recursive calls In the simplest case if K==node value, then whole of the let is rank of the node if K < node.value then we know that rank depends on the size of left sub tree and its less than sub tree's length If K > node.value then we know that we have to count full left subtree w.r.t with that node, and some nodes in right public int rank(int K, node x) { if(x==null) return 0; if(K < x.data) return rank(K,x.left); ...

Read More

Iterators - Allowing iteration over data structures (in java)

Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves. Here's where java gives us the power called iterators which allows us to iterate over data structure. Design Challenge Consider the stack data structure and we want to support iteration over it on client side. Step 1 - Make your stack ADT implement Iterable interface. What is Iterable? has a method that returns an Iterator. public...

Read More

Generic data structures in java

Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this. Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again. Attempt 2 - Implement a stack using Object class. Example Downside - Discover type mismatch errors at run time Casting has to be done at client side Code looks ugly because of so many castings Attempt 3 - Java generic...

Read More

Evaluating postfix expression using stack

We have seen the conversion of infix to postfix expression here. Now lets  see how to evaluate it. Algorithm Scan input expression from left to right If scanned input is an operand, push it into the stack If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack. Repeat above two steps till all the characters are scanned. After all characters are scanned, there will be only one element in the stack, and this is the result of given expression. Note...

Read More

Converting an Infix Expression to Postfix expression using a stack

Pre-requisite - What is infix, postfix and prefix? Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions.  Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation. Infix - Operators are written in-between their operands. eg.  A+B Postfix -  Operators are written after their operands.      eg.  AB+...

Read More