Amazon Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
class BinarySearch {
public static void main(String args[]) {
int x[]= {0,1,2,3,4,5,6,7,8};
for(int i=0;i<=13;i++) {
System.out.println("Position of "+i+" : "+BS(x,0,x.length-1,i)+".");
}
}
public static int BS(int x[],int low,int high,int key) {
if(high<low) {
return -1;
}
else {
int mid = low + (high-low)/2;
if(x[mid]==key) {
return mid;
}
else if(key>x[mid]) {
return BS(x,mid+1,high,key);
}
else {
return BS(x,low,mid-1,key);
}
}
}
}
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child, a pointer to right
child and a pointer to random node*/
struct Node
{
int key;
struct Node* left, *right, *random;
};
/* Helper function that allocates a new Node with the
given data and NULL left, right and random pointers. */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->random = temp->right = temp->left = NULL;
return (temp);
}
/* Given a binary tree, print its Nodes in inorder*/
void printInorder(Node* node)
{
if (node == NULL)
return;
/* First recur on left sutree */
printInorder(node->left);
/* then print data of Node and its random */
cout << "[" << node->key << " ";
if (node->random == NULL)
cout << "NULL], ";
else
cout << node->random->key << "], ";
/* now recur on right subtree */
printInorder(node->right);
}
/* Driver program to test above functions*/
int main()
{
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->left = newNode(4);
tree->left->right = newNode(5);
tree->random = tree->left->right;
tree->left->left->random = tree;
tree->left->right->random = tree->right;
cout << "Inorder traversal of original binary tree is: \n";
printInorder(tree);
return 0;
}
public static void inorder(Node root) {
inorderHelper(null,root);
}
private static void inoderHelper(Node randomIter, Node iter) {
if(iter == null)
return;
inorderHelper(randomIter,iter.left);
if(randomIter == null)
randomIter = iter;
else {
randomIter.random = iter;
randomIter = iter;
}
inorderHelper(randomIter,iter.right);
}
please let me know the if it will work for non empty tree.
inorderPath(root, root->left);
/*for non empty tree, has at least one node*/
tree* inorderPath(tree *root, tree* next){
if (root == NULL || next == NULL) return root;
next->random = inorderPath(root->left, next->left);
inorderPath(root->right, root);
return root;
}
c# implementation, NO recursion, keep a reference of the previous in order node to set up its Random property.
public class RandomTreeNode
{
public int Value;
public RandomTreeNode Left;
public RandomTreeNode Right;
public RandomTreeNode Random;
}
public RandomTreeNode SetInorderTraversal(RandomTreeNode root)
{
if (root == null)
return null;
var prev = new RandomTreeNode();
var first = prev;
var stack = new Stack<RandomTreeNode>();
var node = root;
while (node != null && stack.Count > 0)
{
if (node == null)
{
node = stack.Pop();
prev.Random = node;
prev = node;
node = node.Right;
break;
}
stack.Push(node);
node = node.Left;
}
return first.Random;
}
#include <iostream>
#include <conio.h>
using namespace std;
struct Tree
{
int data;
Tree* left, *right, *random;
Tree(int d)
{
data = d;
left = right = random = NULL;
}
};
void inorder(Tree* root)
{
if(!root)
return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
void inorderWithRandom(Tree* root)
{
if(!root)
return;
Tree* curr, *pre;
curr = root;
while(curr)
{
if(curr->left == NULL)
{
cout<<curr->data<<" ";
curr = curr->right ? curr->right : curr->random;
}
else
{
pre = curr->left;
while(pre->right && !pre->random)
{
pre = pre->right;
}
if(!pre->right && !pre->random)
{
pre->random = curr;
curr = curr->left;
}
else
{
cout<<curr->data<<" ";
curr = curr->right ? curr->right : curr->random;
}
}
}
}
void main()
{
Tree* root = new Tree(6);
root->left = new Tree(3);
root->right = new Tree(10);
root->left->left = new Tree(1);
root->left->right = new Tree(5);
root->right->left = new Tree(7);
root->left->left->right = new Tree(2);
root->left->right->left = new Tree(4);
root->right->left->right = new Tree(8);
root->right->left->right->right = new Tree(9);
//inorder(root);
inorderWithRandom(root);
getch();
}
- dklol February 20, 2016