Tuesday, July 21, 2015

Insertion Sort

The idea behind the insertion sort is to loop over positions in the array, starting with index 1. Each element at the given index needs to be inserted  into the correct place in the array.

Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

Implementation:

void insertionSort(int *arr, int len)
{
if(arr == NULL || len <= 1)
return;

for(int i = 1; i < len; ++i)
{
int key = arr[i];
int j = i  - 1;
for(; j >= 0 && arr[j] > key; --j)
arr[j+1] = arr[j];

arr[j + 1] = key;
}
}

Complexity: O(n2)

Monday, July 13, 2015

Size of binary tree

Problem: Write a method which returns the number of nodes present in the given binary tree.

Solution: Do any traversal and instead of printing the node, count the number of nodes. I am using post order traversal here.

Implementation:

//Public Interface
int BSTree::size()
{
if(!root)
return 0;
return size(root);
}

//Actual Implementation
int BSTree::size(BSTree::Node *node)
{
if(!node)
return 0;
int ls = size(node->left);
int rs = size(node->right);

return ls + rs + 1;

Complexity: O(n)

Thursday, July 9, 2015

Longest Increasing Subsequence

A sequence of numbers a1, a2,..., an, a sub-sequence is ai1, ai2, ... , aik where 1 <= i1 < i2 < ... < ik <= n and an increasing sub-sequence is one in which the numbers are getting strictly larger. The task is to find the increasing sub-sequence of greatest length.

Example: The longest increasing sub-sequence of 5, 2, 8, 6, 3, 6, 9, 7 is 2, 3, 6, 9:


Solution: Create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for ai and aj to be consecutive elements in an increasing sub-sequence,that is, whenever i < j and ai < aj.


Note that this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and there is a one-to-one correspondence between increasing sub-sequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag. Here is the algorithm:


Implementation:

int LIS(int arr[], int len)
{
int *L = new int[len];

for(int i = 0; i < len; ++i)
L[i] = 1;

for(int j = 1; j < len; ++j)
{
for(int i = 0; i < j; ++i)
{
if((arr[j] > arr[i]) && (L[j] < L[i] + 1))
L[j] = L[i] + 1;
}
}

int max = 0;
for(int i = 0; i < len; ++i)
{
if(max < L[i])
max = L[i];
}

delete [] L;
return max;
}

Complexity: O(n2)

Monday, July 6, 2015

OLA Question: Modify Boolean matrix

Problem: Given a Boolean matrix , modify it such that if a matrix cell mat[i][j] is true then make all the cells of ith row and jth column as true.

Solution: Following are the steps -
  1. Traverse the first row and set a variable firstRowFlag to indicate whether all the cells in first row should be set to true or not.
  2. Similarly traverse the first column and set a variable firstColFlag to indicate whether all the cells in first column should be set to true or not.
  3. Now set all the cells in first row and column as false.
  4. Traverse the input matrix and see if mat[i][j] is true, then set mat[0][j] and mat[i][0] as true.
  5. Traverse the input matrix and for each entry mat[i][j], check if either mat[0][j] or mat[i][0] is true, then set mat[i][j] to true.
  6. Now, using firstRowFlag and firstColFlag, update first row and first column if needed.

Implementation:

void modifyBoolMatrix(bool **mat, int M, int N)
{
bool firstRowFlag = false, firstColFlag = false;
for(int i = 0; i < N; ++i)
{
if(mat[0][i])
{
mat[0][i] = false;
firstRowFlag = true;
}
}

for(int i = 0; i < M; ++i)
{
if(mat[i][0])
{
mat[i][0] = false;
firstColFlag = true;
}
}

for(int i = 1; i < M; ++i)
{
for(int j = 1; j < N; ++j)
{
if(mat[i][j])
{
mat[0][j] = true;
mat[i][0] = true;
}
}
}

for(int i = 1; i < M; ++i)
{
for(int j = 1; j < N; ++j)
{
if(mat[0][j] || mat[i][0])
mat[i][j] = true;
}
}

if(firstRowFlag)
{
for(int i = 0; i < N; ++i)
mat[0][i] = true;
}

if(firstColFlag)
{
for(int i = 0; i < M; ++i)
mat[i][0] = true;
}
}

Complexity: O(M * N)

Amazon Question: Add two numbers represented by linked lists

Problem: Given two numbers represented by two linked lists, write a method that returns linked list representing the addition of two input numbers.

Solution: No need to explain. Can be easily understood by the implementation.

Implementation:

//All of these methods are friends to List class

void addAtFront(List::ListNode*& head, int num)
{
List::ListNode* newNode = new List::ListNode(num, head);
head = newNode;
}

void addCarry(List::ListNode* node1, List::ListNode* node2, int& carry, List::ListNode *&result)
{
if(node1 != node2)
{
addCarry(node1->next, node2, carry, result);
int sum = node1->data + carry;
carry = sum/10;
sum = sum % 10;
addAtFront(result, sum);
}
}

List::ListNode* addSameLenNum(List::ListNode* node1, List::ListNode* node2, int& carry)
{
if(!node1)
return NULL;
List::ListNode *node = new List::ListNode();
node->next = addSameLenNum(node1->next, node2->next, carry);
int sum = node1->data + node2->data + carry;
carry = sum / 10;
node->data = sum % 10;
return node;
}

List* addNum(List l1, List l2)
{
if(!l1.head)
{
return new List(l2);
}
if(!l2.head)
{
return new List(l1);
}
 List* result = new List()
List::ListNode *head1 = l1.head, *head2 = l2.head;
int len1 = l1.len, len2 = l2.len;
int carry = 0;
if(len1 == len2)
result->head = addSameLenNum(l1.head, l2.head, carry);
else
{
if(len1 < len2)
{
head1 = l2.head;
head2 = l1.head;
}
int diff = std::abs(len1 - len2);
List::ListNode* curr = head1;
for(int i = 0; i < diff; ++i, curr=curr->next);
result->head = addSameLenNum(curr, head2, carry);
addCarry(head1, curr, carry, result->head);
}

if(carry)
addAtFront(result->head, carry);

return result;
}

Complexity: O(n)

Thursday, July 2, 2015

Width of a binary tree

Problem: Given a binary tree, write a method to get the width of the given binary tree. Width of a tree is maximum of widths of all levels in the tree.

Solution: Use level order traversal.

Implementation:

int BSTree::getWidth()
{
int maxW = -1;
if(!root)
return maxW;
std::queue<Node*> q[2];
bool turn = 0;
q[turn].push(root);
while(!q[turn].empty())
{
int currW = q[turn].size();
if(maxW < currW)
maxW = currW;
while(!q[turn].empty())
{
Node *temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
}

turn = !turn;
}

return maxW;
}

Complexity: O(n)

Kth min in BSTree

Problem: Write a method which returns the kth minimum element in a given Binary Search Tree.

Solution: Use inorder traversal.

Implementation:

//Public interface
int BSTree::kthMin(int k)
{
if(!root || k <= 0)
return -1;
return kthMin(root, k);
}

//Actual Implementation
int BSTree::kthMin(BSTree::Node *node, int& k)
{
static int result = -1;
if(node)
{
kthMin(node->left, k);
if(--k == 0)
result = node->data;
if(k > 0)
return kthMin(node->right, k);
}
else if(k > 0)
result = -1;
return result;
}

Complexity: O(n)

Kth max in BSTree

Problem: Write a method which returns the kth maximum element in a given Binary Search Tree.

Solution: Use reverse inorder traversal.

Implementation:

//Public interface
int BSTree::kthMax(int k)
{
if(!root || k <= 0)
return -1;
return kthMax(root, k);
}

//Actual implementation
int BSTree::kthMax(BSTree::Node *node, int& k)
{
static int result = -1;
if(node)
{
kthMax(node->right, k);
if(--k == 0)
result = node->data;
if(k > 0)
return kthMax(node->left, k);
}
else if(k > 0)
result = -1;
return result;
}

Complexity: O(n)