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