Amazon interview Questions and Solutions

Amazon Interview Questions:

The following are the questions asked today (16/9/2017) in Amazon.

1- Find the number of repetitions of a given element in the sorted array in O(logn) ?

2- Print Diagonal Traversal of the binary tree ?

Can anyone optimize it further and provide comments?

Answer 1:  number of repetitions in sorted array

int findkRepeatCount(vector arr, int k)

{

int first = 0;

int last = arr.size() - 1;

int count = 0;

bool lastKElement = false;

bool startKElement = false;

bool midKElement = false;

int mid;

while (first <= last)

{

mid = (first + last) / 2;

if (arr[mid] == k && arr[mid - 1] < k && arr[mid + 1] >k)

{

return 1;

}

if (arr[mid] == k && arr[mid - 1] < k)

{

startKElement = true;

break;

}

if (arr[mid] == k && arr[mid - 1] > k)

{

lastKElement = true;

break;

}

if (arr[mid] == k)

{

midKElement = true;

break;

}

if (arr[mid] > k )

{

last = mid - 1;

}

if (arr[mid] < k)

{

first = mid + 1;

}

}

if (startKElement)

{

while (mid < arr.size() && arr[mid] == k)

{

++mid;

++count;

}

return count;

}

if (lastKElement)

{

while (mid >= 0 && arr[mid] == k)

{

--mid;

++count;

}

return count;

}

if (midKElement)

{

int temp = mid + 1;

while (mid >= 0 && arr[mid] == k )

{

--mid;

++count;

}

while (temp

{

++temp;

++count;

}

return count;

}

return 0;

}

Answer 2: Diagonal Traversal of the binary tree

struct treeNode

{

int value;

treeNode* left;

treeNode* right;

};

class tree

{

void printNodeDiag(treeNode* root, int diag, std::unordered_map>& mp);

public:

tree();

~tree();

treeNode* createNode(int);

void PrintNodes(treeNode*);

void printNodeDiag(treeNode*);

treeNode* root;

};

tree::tree()

{

root = nullptr;

}

treeNode* tree::createNode(int val)

{

treeNode * newNode = new treeNode;

newNode->value = val;

newNode->left = nullptr;

newNode->right = nullptr;

return newNode;

}

void tree::PrintNodes(treeNode* root)

{

if (root == nullptr) return;

PrintNodes(root->left);

cout << root->value << " ";

PrintNodes(root->right);

}

void tree::printNodeDiag(treeNode* root, int diag, std::unordered_map>& mp)

{

if (root == nullptr) return;

mp[diag].push_back(root->value);

printNodeDiag(root->left, diag + 1, mp);

printNodeDiag(root->right, diag, mp);

}

void tree::printNodeDiag(treeNode* root)

{

std::unordered_map> map;

printNodeDiag(root, 0, map);

for (auto it : map)

{

for (auto itt : it.second)

{

cout << itt << " ";

}

cout << endl;

}

}

tree::~tree()

{

}

Test Drive

int main()

{

vector myarr = { 1,1,2,3,4,8,8,8,8}; int repeatElemtentCount = findkRepeatCount(myarr, 8); tree mytree; mytree.root = mytree.createNode(1); mytree.root->right = mytree.createNode(3); mytree.root->right->right = mytree.createNode(6); mytree.root->right->left = mytree.createNode(5); mytree.root->right->left->right = mytree.createNode(8); mytree.root->right->left->left = mytree.createNode(7); mytree.root->left = mytree.createNode(2); mytree.root->left->left = mytree.createNode(4); cout << endl; cout << "print tree in-order\n"; mytree.PrintNodes(mytree.root); cout << "print tree in diegonal order\n"; mytree.printNodeDiag(mytree.root); cout << endl; return 0; }