Given an integer matrix, find the length of the longest increasing path

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Strategy: Dynamic Programming
This is a very classic DFS + memorialization problem. If we only use the DFS solution, it will end with many repeated calculations. Therefore, for each element in the matrix[i][j], we use a DP array dp[i][j] to denote the length of the maximum increasing path from this point. So along with the DFS, for a point in the matrix, if we've already found the longest increasing path, we don't have to repeatedly compute it again; we just need to return the length, which is dp[i][j].

One trick here is dp[i][j] stores the length of the longest increasing path. That is because the DFS from a point matrix[i][j] can guarantee the longest path from this point. Since we store this value in the dp[i][j], that can guarantee that dp[i][j] is the longest path from the point matrix[i][j].

http://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/
http://buttercola.blogspot.in/2016/06/leetcode-329-longest-increasing-path-in.html
http://adijo.github.io/2016/01/20/leetcode-longest-increasing-path-matrix/

Find paths from corner cell to middle cell in maze

Given a square maze containing positive numbers, find all paths from a corner cell (any of the extreme four corners) to the middle cell. We can move exactly n steps from a cell in 4 directions i.e. North, East, West and South where n is value of the cell,

We can move to mat[i+n][j], mat[i-n][j], mat[i][j+n], and mat[i][j-n] from a cell mat[i][j] where n is value of mat[i][j].

Example

Input:  9 x 9 maze
[ 3, 5, 4, 4, 7, 3, 4, 6, 3 ]
[ 6, 7, 5, 6, 6, 2, 6, 6, 2 ]
[ 3, 3, 4, 3, 2, 5, 4, 7, 2 ]
[ 6, 5, 5, 1, 2, 3, 6, 5, 6 ]
[ 3, 3, 4, 3, 0, 1, 4, 3, 4 ]
[ 3, 5, 4, 3, 2, 2, 3, 3, 5 ]
[ 3, 5, 4, 3, 2, 6, 4, 4, 3 ]
[ 3, 5, 1, 3, 7, 5, 3, 6, 4 ]
[ 6, 2, 4, 3, 4, 5, 4, 5, 1 ]

Output:
(0, 0) -> (0, 3) -> (0, 7) -> 
(6, 7) -> (6, 3) -> (3, 3) -> 
(3, 4) -> (5, 4) -> (5, 2) -> 
(1, 2) -> (1, 7) -> (7, 7) ->
(7, 1) -> (2, 1) -> (2, 4) -> 
(4, 4) -> MID

http://www.geeksforgeeks.org/find-paths-from-corner-cell-to-middle-cell-in-maze/

Concurrent Merge Sort in Shared Memory

Given a number ‘n’ and a n numbers, sort the numbers using Concurrent Merge Sort. (Hint: Try to use shmget, shmat system calls).
http://www.geeksforgeeks.org/concurrent-merge-sort-in-shared-memory/

Minimize Cash Flow among a given set of friends who have borrowed money from each other

Given a number of friends who have to give or take some amount of money from one another. Design an algorithm by which the total cash flow among all the friends is minimized.
http://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/

Backtracking — Search a Word In a Matrix

 Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and diagonally).

http://algorithms.tutorialhorizon.com/backtracking-search-a-word-in-a-matrix/

Backtracking — Knight’s Tour Problem

A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is one knight’s move from the begin­ning square (so that it could tour the board again imme­di­ately, fol­low­ing the same path), the tour is closed, oth­er­wise it is open. (Source : http://en.wikipedia.org/wiki/Knight%27s_tour)

http://algorithms.tutorialhorizon.com/backtracking-knights-tour-problem/

Backtracking — N Queens Problem

Backtracking — N Queens Problem

In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks how to place 8 queens on an ordi­nary chess board so that none of them can hit any other in one move.(Source: http://www.math.utah.edu/~alfeld/queens/queens.html)

Here we are solv­ing it for N queens in NxN chess board.

http://algorithms.tutorialhorizon.com/backtracking-n-queens-problem/

Backtracking — SUDOKU Solver

The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) con­tains all of the dig­its from 1 to 9. The puz­zle set­ter pro­vides a par­tially com­pleted grid, which for a well-posed puz­zle has a unique solu­tion. (Source: Wiki — http://en.wikipedia.org/wiki/Sudoku)

http://algorithms.tutorialhorizon.com/backtracking-sudoku-solver/

Highway Billboard Problem

Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by num­bers x1 < x2 < · · · < xn, each in the inter­val [0, M], spec­i­fy­ing their posi­tion in miles mea­sured from the west­ern end of the road. If you place a bill­board at posi­tion xi , you receive a rev­enue of ri > 0.

Reg­u­la­tions imposed by the High­way Depart­ment require that no two bill­boards be within five miles or less of each other. You’d like to place bill­boards at a sub­set of the sites so as to max­i­mize your total rev­enue, sub­ject to this restriction.

http://algorithms.tutorialhorizon.com/dynamic-programming-highway-billboard-problem/

Rod Cutting Problem

Given a rod of length n inches and a table of prices p_i, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue r_n obtain­able by cut­ting up the rod and sell­ing the pieces.
http://algorithms.tutorialhorizon.com/dynamic-programming-rod-cutting-problem/
http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

http://www.programcreek.com/2014/03/leetcode-house-robber-java/
http://www.programcreek.com/2014/05/leetcode-house-robber-ii-java/
http://www.programcreek.com/2015/03/leetcode-house-robber-iii-java/
http://shirleyisnotageek.blogspot.in/2016/06/house-robber-i-ii-and-iii.html

Find maximum stack possible with given slabs

You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.Generalize this for n dimensions.

Algorithms Learning / Interview Questions

The following Links are very useful for learning and preparing for interviews regarding Algos.

Learning---------
http://www.cs.berkeley.edu/~vazirani/algorithms.html

Interviews Specific-----------
Algo Geeks

Rat in a maze algorithm

A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

http://algorithms.tutorialhorizon.com/backtracking-rat-in-a-maze-puzzle/
http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

Code:BackTracking

#include<stdio.h>
#include<stdlib.h>

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

int main()
{
    int maze[N][N] =
    {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}

Maximum sum path in a triangle

You have been given a triangle of numbers (as shown). You are supposed to start at the apex (top) and go to the base of the triangle by taking a path which gives the maximum sum. You have to print this maximum sum at the end. A path is formed by moving down 1 row at each step (to either of the immediately diagonal elements)

Maximise the value of Expression

Suppose you are given an expression E= x1 y1 x2 y2....yn-1 xn.
Where Xi belongs to natural number and Yi belongs to { +,*}

you need to parenthesize such that it maximize the value of E ?
Let's change Yi to { +,-,*,/}, then how to maximize E?
Now add % operator in that set..then how to maximize E?

The Word Break Problem

Given an string and a dic­tio­nary of words, find out if the input string can be bro­ken into a space-separated sequence of one or more dic­tio­nary words.

http://algorithms.tutorialhorizon.com/the-word-break-problem/

http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

Maximum possible sum of Non-consecutive elements

There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.

Example: If given array is (6, 4, 2, 8, 1), the answer will be 14 (8+6). This is the maximum sum we can obtain without taking two consecutive elements.

Method 1:

To solve these type of question, first thing is to find a recurring relation. In this case our recurring relation will tell the max sum till a given length. It means that we will get the max sum for running length of the array. If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }

S(-1) = 0;
if i=0, S(i) = T(0);

Note: while developing this relationship, I assume array index is starting from 0.

sum2 = 0;
sum = sum1 = array[0];
for(i=1; i<len; i++)
{
   sum = MAX(sum2 + array[i], sum1);
   sum2 = sum1;
   sum1 = sum;}
Method 2:Dynamic Programming

This is a problem of Dynamic Programing and similar to longest increasing sub-sequence with the restriction that the sub-sequence cannot contain adjacent elements. The only difference is that in that problem, for an index j all the indices i, such that i < j were considered. But here we will consider i, such that i < j-1
The problem (and the longest sub-sequence as well) can be solved by modeling the array as a graph with an edge between (i,j) if j>i where j and i are the indices of the numbers but not when i = j-1 i.e. the two numbers are adjacent.

Pseudo Code:

  Create an array L[N]
for j = 1 to N:
    L(j) = a(j) + max{L(i) : (i; j) belongs to E}
return max L(j)

the base case will be when j=1 
max{ L(i): (i,j) belongs to E}= 0

The solution has O(N2) time complexity and O(N) space complexity.

Interval Tree & Overlapping Intervals

Discuss the use and implementation for Interval trees. 

You have N pairs of intervals, say integers. You're required to identify all intervals that overlap with each other in O(N logN) time. For example, if you have

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.

Knapsack Problem

Given a set of items, each with a weight (w_i) and a value (v_i), determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Alternatively,
US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.
Items          Nutrition Value per Gram         Available
Noodle      10                                                           100 gm
Soyabean  30                                                             15 gm
Macroni     5                                                            100 gm
Fruits         40                                                             10 gm


Strategy:
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i.

We can define m[i,w] recursively as follows:

• m[0,w] = 0
• m[i,0]=0
• m[i,w] = m[i-1,w] if w_i > w (the new item is more than the current weight limit so this element cannot be accepted because it’s weight is larger than w )
• m[i,w] = max(m[i-1,w] ,m[i-1,w-w_i ] + vi) if w_i < = w.


The solution can then be found by calculating m[n,W]. To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW)space. 

Solution to alternate problem:
     All we need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on.

I am sure you get the idea. For the given example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).