Searching a 2D Sorted Matrix Part I

Source

Problem

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1]
Table[i][j] ≤ Table[i + 1][j]

Implement strstr() to Find a Substring in a String

Source

Problem

Write C code to implement the strstr (Search for a substring) function. Do not use any system library such as strlen.

Queue that Support Push_rear, Pop_front, and GetMin in Constant Time

Source

Problem

Design a queue that supports push_rear, pop_front, and get_min in O(1). Would that be elegantly possible too?

Solution

Maintain an extra queue lets call it secondary queue.

push_rear

-> push the element in the primary queue

-> start from the front of the queue. Remove all elements which are smaller then the element. If element is greater then all it will take the last position.

pop_front

--> remove the element from primary queue

--> if the element is present at head of secondary queue remove it.

get_minimum

-->return head of the secondary queue

Stack that Support Push, Pop, and GetMin in Constant Time

Source

Problem

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

Solution

Use extra stack. Lets call it secondary stack.

push

-> if number is less then top of the stack element in secondary queue. Push it in secondary queue

-> push it in primary queue

pop

-> if top of the secondary queue == top of primary queue. Pop from secondary queue

-> pop from primary queue

-> pop from primary queue

get_minimum

-> return top of secondary queue

Largest Binary Search Tree (BST) in a Binary Tree

Source

Problem

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

My Attempt

Every node in the BST will be an BST (Recursive definition of BST)

Go top down. In-order traversal. traversal. If you find a node which does not hav both children which does not follow BST property save them (Add them to linked list) we wil treat them as root of new possible BST,

lbst(node *root, int &count, node* queue) {

ChkPtrAssert(queue);

if (!root) { return; }

// visit the element if atleast one chil has BST property. Include the node in current BST tree

if (root->left && root->left->data <>data) || (root->right && root->right->data >= no)

count++;

//visit left child

if (root->left)

if(root->left->data <>data)

lbst(root->left, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

//visit tight child

if (root->right)

if(root->right->data <>data)

lbst(root->right, count, queue);

else

{

// skip the element and add it to queue. We will visit latter

queue->addQueue(root->left);

}

}

main() {

Queue *queue = new Queue();

Node* lbstRoot = root;

int maxCount = 0;

ChkMem(queue);

queue->addQueue(root);

node* currentNode = root;

while (CurrentNode)

{

lbst(currentNode, count, queue);

if (count > maxCount) {

maxCount = count;

lbstRoot = currentNode;

}

queue->popQueue(&currentNode);

}

Coins in a Line

Source

Here is an interview question you would expect from a typical Google interview, which is an interesting problem itself. Different solutions from multiple perspectives are provided in this post.

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

U.S. coins in various denominations in a line. Two players take turn to pick a coin from one of the ends until no more coins are left. Whoever with the larger amount of money wins.

My Attempt

1. sum all even positions and odd positions. Whichever is greater players takes those positions.

2.

int optimalSequenceValue (int arr[ ] , int left, int right, bool player, int P[ ] [ ])

{

if (left == right) // last element

return 0;

if (player == PLAYER1) // pick one left or right and select max of the output

p[left] [right] = max (arr[left] + optimalSequenceValue (arr, left + 1, right, P) ,

arr[righjt] + optimalSequenceValue (arr, left, right -1 , P)

return p[left][right];

if(player == PLAYER2) // value doesnt count just skip

return max (optimalSequenceValue (arr, left + 1, right, P) ,

optimalSequenceValue (arr, left, right -1 , P)

}

with values in P[][] we could back track the pattern.

Print All Combinations of a Number as a Sum of Candidate Numbers

Source

Problem

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3

My Attempt

void Sum(int arr[], int reminder, int index, int visited[]) {

if (index LessThen 0) { return }

if (difference == 0) { printSum(arr, visited) , return; }

if (reminder - arr[index] LessThen 0) { return }

visited[index]++;

Sum(arr, reminder - arr[index] , index, visited) // duplicate number

Sum(arr, reminder - arr[index], index - 1, visited) // next number

visted[index]--;

Sum(arr, reminder, index - 1, visited) // skip

}

Find all possible combination of numbers using a pre-defined candidate set.
Each number from the candidate set may be used only once in the combination.

For example,

Candidate Set = {10, 1, 2, 7, 6, 1, 5}
Target Number = 8

One possible output could be:
1+1+6
1+2+5
1+7
2+6

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3e.g. target is 7, candidate is 2,3,6,7

output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3e.g. target is 7, candidate is 2,3,6,7

output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3

// repeat the current index for possible duplicates

}

Source

Problem

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)

My Attempt

Sum(int arr[], int remainder, int index, int visited[])

{

if (index LessThen 0 ) { return; }

if (difference == 0) {

// bingo!

printAddition(arr, visited); // print all visited numbers

return;

}

if (difference - arr[index] > = 0 ) {

visited[index]++;

Sum(arr[], difference - arr[index], index, visited[]); // repeat the number dont move index

Sum(arr[], difference - arr[index], index - 1, visited[]);

visited[index]--;

}

Modified Problem

Let’s change the question a little bit.

Find all possible combination of numbers using a pre-defined candidate set.
Each number from the candidate set may be used only once in the combination.

For example,

Candidate Set = {10, 1, 2, 7, 6, 1, 5}
Target Number = 8

One possible output could be:
1+1+6
1+2+5
1+7
2+6