Chain Matrix Multiplication

Suppose that we want to multiply four matrices, A x B x C x D, of dimensions 50 x 20, 20 x 1, 1 x 10, and 10 x 100, respectively. This will involve iteratively multiplying two matrices at a time. Matrix multiplication is not commutative but it is associative. Thus we can compute our product of four matrices in many different ways, depending on how we parenthesize it. Are some of these better than others?

Multiplying an m x n matrix by an n x p matrix takes m*n*p multiplications, to a good enough approximation. Using this formula, let's compare several different ways of evaluating A x B x C x D:

You can see, the order of multiplications makes a big difference in the final running time!

Dynamic Programming Solution:

If we want to compute A1 x A2 x ... x An, where the Ai's are matrices with dimensions M0 x M1, M1 x M2, ... ,Mn-1 x Mn respectively. The first thing to notice is that a particular parenthesization can be represented by a binary tree in which the individual matrices correspond to the leaves, the root is the final product, and interior nodes are intermediate products.

The binary trees in the above figure are suggestive: for a tree to be optimal, its sub-trees must also be optimal. What are the sub-problems corresponding to the sub-trees? They are products of the form Ai x Ai+1 x ... x Aj. Let's see if this works: for 1 <= i <= j <= n, define

The size of this sub-problem is the number of matrix multiplications, |j - i|. The smallest sub-problem is when i = j, in which case there's nothing to multiply, so C(i, i) = 0. For j > i, consider the optimal sub-tree for C(i, j). The first branch in this subtree, the one at the top, will split the product in two pieces, of the form Ai x ... x Ak and Ak+1 x ... x Aj , for some k between i and j. The cost of the subtree is then the cost of these two partial products, plus the cost of combining them: C(i, k) + C(k + 1, j) + Mi-1 * Mk * Mj and we just need to find the splitting point k for which following is the smallest:

Implementation:

int ChainMatrixMultiplication(int dims[], int size)

{

int** C = new int* [size];

for(int i = 0; i <= size; ++i)

{

C[i] = new int[size];

C[i][i] = 0;

}

for(int s = 1; s < size; ++s)

{

for(int i = 1; i < size - s; ++i)

{

int j = i + s;

C[i][j] = INT_MAX;

for(int k = i; k < j; ++k)

{

int count = C[i][k] + C[k + 1][j] + dims[i - 1] * dims[k] * dims[j];

if(count < C[i][j])

C[i][j] = count;

}

}

}

return C[1][size - 1];

}

Time Complexity: O(n³)

Amazon Question: Run Length Encoding

Problem: Convert a string into it's Run Length Encoded String. For example run length encoded string of AABBBCCCCD is A2B3C4D1.

Solution: 

void RLE(char* str)
{
if(!str)
return;
int len = std::strlen(str);
if(len == 0 || len == 1)
return;

int count = 1;
int spaces = 0;
char currChar = str[0];
int j = 0;
for(int i = 1; i < len; ++i)
{
if(str[i] == currChar)
{
++count;
}
else
{
str[j++] = currChar;
if(count > 1)
{
char *countStr = intToStr(count);
int lenCountStr = strlen(countStr);

for(int k = 0; k < lenCountStr; ++k)
str[j++] = countStr[k];
delete [] countStr;
countStr = 0;
count = 1;
}
else
++spaces;
currChar = str[i];
}
}
str[j++] = currChar;
if(count > 1)
{
char *countStr = intToStr(count);
int lenCountStr = strlen(countStr);
for(int k = 0; k < lenCountStr; ++k)
str[j++] = countStr[k];
delete [] countStr;
countStr = 0;
}
else
++spaces;
if(j + spaces <= len)
{
str[j + spaces] = '\0';
bool getInt = false;
for(int i = j - 1, k = j + spaces - 1; i >= 0; --i)
{
if(str[i] < '0' || str[i] > '9')
{
if(!getInt)
{
str[k--] = '1';
}
str[k--] = str[i];
getInt = false;
}
else
{
str[k--] = str[i];
getInt = true;
}
}
}
else
str[j] = '\0';
}

Complexity: O(n)

Longest Palindromic Subsequence

Problem: Given a sequence, find the length of the longest palindromic sub-sequence in it.

Solution: 

Longest Common Sub-sequence can be used to solve this problem. The steps are as follows:
1. Reverse the given sequence and store the reverse in another array say reverse[0..n-1]
2) LCS of the given sequence and reverse[] will be the longest palindromic sequence

Implementation:

int LPS(std::string S)
{
std::string T = S;
std::reverse(T.begin(), T.end());
return LCS(S, T);
}

Please find the implementation of LCS at the following URL:
http://algods-cracker.blogspot.in/2015/03/longest-common-sub-sequencelcs.html

Complexity: O(n²)

Longest Common Sub-sequence(LCS)

Given two strings: string S of length n, and string T of length m. The longest common sub-sequence is the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

Dynamic Programming Solution:

LCS[i,j] is the length of the LCS of S[1..i] with T[1..j]. 

If S[i] != T[j] then, LCS[i,j] = max(LCS[i−1,j],LCS[i,j−1])

If S[i] = T[j] then, LCS[i,j] = 1 + LCS[i−1,j−1]

Example:

Implementation:

int LCS(std::string S, std::string T)

{

int m = S.size();

int n = T.size();

if(m == 0 || n == 0)

return 0;

int **LCS = new int*[m + 1];

for(int i = 0; i <= m; ++i)

{

LCS[i] = new int[n + 1];

LCS[i][0] = 0;

}

for(int j = 0; j <= n; ++j)

LCS[0][j] = 0;

for(int i = 1; i <= m; ++i)

{

for(int j = 1; j <= n; ++j)

{

if(S[i-1] != T[j-1])

LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

else

LCS[i][j] = 1 + LCS[i-1][j-1];

}

}

return LCS[m][n];

}

Time Complexity: O(mn)

Adobe Question: Calculate square of a number without using arithmetic operators and inbuilt methods

Question: Calculate square of a number without using arithmetic operators like *, /, +, -. Obviously inbuilt methods like pow() can't be used.

Solution:

1: If the given number 'num' is even then:
    num = 2 * n
    so square(num) = square (2 * n) = 4 * square(n)

2: If num is odd then:
    num =  2 * n + 1
    so square(num) = square(2 * n +  1) = 4 * square(n) + 4 * n + 1

Implementation:

int square(int num)
{
if(num == 0 || abs(num) == 1)
return abs(num);

if(num < 0)
num = -num;

int half = num>>1;

if(num & 1)
return ((square(half)<<2) + (half<<2) + 1);
else
return (square(half)<<2);
}

Complexity: O(log(n))

[LLD] Design Chess Game

class Point {
    private:
        int x, y;
    public:
        Point(int i, int j); // x = i; y = j;
        int GetX();
        int GetY();
        void SetX(int i);
        void SetY(int j);
        void SetPoint(int i, int j); x = i; y = j;
}

class History {
    private:
        Board *board;
        Point from; // the point a piece was moved from
        Point to; // the point a piece was moved to
        Piece killed_piece; // remembers which piece was killed
        History *next;
        History *prev;
    public:
        History(Point f, Point t, Board* b, History *p);
        SetNext(History *n);
        void UndoLastMove();
        void RedoUndoneMove();
}

class Board {
    private:
        Piece* the_board[width][height];
        Color turn;
        History* first_history;
        History* last_history;
        Point en_passant:
    public:
        Board(); // creates board with pieces in initial configuration;  white's turn
        Piece* PieceAt(Point p); // return the piece at location p
        Piece* PieceAt(int x, int y);        // return the piece at location (x,y)
        PlacePieceAt(Piece* p, Point* pt);    // place piece p at location pt
        void Move(Point p1, Point p2);    // move piece at p1 to p2
        void Move(Point p1, Point p2, Point ep); // move piece at p1 to p2
        void TryToMove(Point p1, Point p2);
        Point GetEnPassant();
}

enum MoveType {
ILLEGAL,
NORMAL,
CASTLE,
DOUBLESTEP,
ENPASSANT
}

class Piece {
    private:
        Board* board;
        Color color;
        Point location;
    protected:
        virtual MoveType CanMove(Point p);
    public:
        Piece(Point p, Color c, Board* b);
        Point GetLocation();
        Color GetColor();
        void SetLocation(Point p);
        void SetLocation(int x, int y);
        virtual void TryToMove(Point p);
}

class Pawn : Piece {
    private:
        int direction;  // 1 for up, -1 for down
    protected:
        bool CanMove(Point p);
    public:
        Pawn(Point p, Color c, Board * b, int d);
        void TryToMove(Point p);
}

class Bishop : Piece {
    protected:
        MoveType CanMove(Point p);
}

Rook, Knight etc. we can easily think of it.

[LLD] Design Elevator

enum LiftDirection
{
      UP = 0,
      DOWN,
      STOP
}

enum LiftState
{
      ON = 0,
      OFF
}

enum DoorState
{
      OPEN = 0,
      CLOSE
}

class Task
{
      int floor;
      LiftDirection direction;
}

class ElevatorState
{
      int floor;
      LiftDirection direction;
      LiftState state;
}

class OutsideButtonListener
{
      listen();
}

class OutsideButton
{
      OutsideButtonListener listener;
      int floor;
      bool direction;
      void createTask();
      bool sendTask();
      void listenForUserInput();
}

class ControllerListener
{
      queue<Task*> tasks;
      void listen();
}

class CentralController
{
private:
      ControllerListener m_listener;
      vector<Elevator> m_elevators;
      int totalFloors;
      void AssignTask(Task* task);
      void TaskDone(Task* task);
      set<Task*> AssignedTaks;
      void MonitorAssignedTasks();

public:
      void ListenForTasks();
}

class Instantiator
{
      InitController();
      CentralController *controller
}

class ElevatorTask
{
      int floor;
      CentralController* controller
      friend bool operator < (ElevatorTask t1, ElevatorTask t2)
      {
        return t1.floor < t2.floor;
      }
}

class ElevatorDoor
{
      DoorState state;
      bool open();
      bool close();
      bool isClosed();
      DoorState getState();
}

class Button
{
      Action action;
      void setAction(Action ac);
      Action getAction();  
}

class KeyPad
{
      vector<Button> buttons;
      getAction(int index);
}

class KeyPadListner
{
      queue<int>q_indices;
      void listen();
}

class KeyPadController
{
      KeyPadListner listner;
      void waitForInput();
      bool doAction(int index);
      KeyPad pad;
}

class Elevator
{
private:
      int floor;
      ElevatorDoor door;
      Direction direction;
      KeyPadController keyPadController;
      ElevatorState state;
      set<ElevatorTask> assignedTasks;
      void ProcessTasks();

public:
      bool AssignTask(Task* task, CentralController* controller);
      ElevatorState getState();
}