Amazon Question: Find the first occurrence of an integer in an array.

Given an array of integers in which the difference between  two adjacent integers is less than or equal to 1. Find the first occurrence of an given integer. Do better than linear search.


int firstOccurence(vector < int > A, int n)
{
    int i = 0;
    int size = A.size();
    while(i < size)
    {
if(A[i] == n)
return i;

i += abs(n - A[i]);
    }
    return -1;
}

Microsoft Question: Find balanced binary sub-tree of size N within a binary tree

void BinaryTree::findBalancedTree(Node* node, int& height, int& size, int N, Node*& out)
{
if(!node)
{
size =0;
height = 0;
return;
}
int lheight = 0, rheight = 0, lsize = 0, rsize = 0;
findBalancedTree(node->left, lheight, lsize, N, out);
findBalancedTree(node->right, rheight, rsize, N, out);

if(abs(lheight - rheight) <= 1 && lsize + rsize + 1 == N)
{
out = node;
}

height = max(lheight, rheight) + 1;
size = lsize + rsize + 1;
}

Check if a binary tree is BST or not

bool BinaryTree::isBST(Node* node)

{
static Node* prev = 0;
if(node)
{
if(!isBST(node->left))
return false;
if(prev && node->data <= prev->data)
return false;
prev = node;
return isBST(node->right);
}
return true;
}

Populate Inorder Successor for all nodes.

Problem: Given a Binary Tree where each node has following structure, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to in-order successor.


struct Node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
};

Solution:  1. In constructor, made all node's next pointer NULL. 2. Traverse the given tree in reverse inorder traversal and keep track of previously visited node.  3. When a node is being visited, assign previously visited node as next. Implementation: //Public Interface void BTree::populateInOrderSuccessor() {     populateInOrderSuccessor(root);  } //Actual Working void BTree::populateInOrderSuccessor(Node* node) {          Node *tempNext = NULL;     if (node)     {         populateInOrderSuccessor(node->right);         node->next = tempNext;         tempNext = node;         populateInOrderSuccessor(node->left);     } }