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.

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);

}