avinash
BAN USER
- 4
0of 2 votes
AnswersDifference between a crash and exception.
- avinash in India for GTSC
Difference between macros and inline functions.
Mfc: message maps and virtual functions.
Different calling convention.
Late n early binding...
Garbage collector algorithm. When gc will fail to clean the memory.
How to know heap size, crash dump analysis, What is a stack n how to know stack memory size.
Commands in windbg.
Questions on Critical section, mutex, semaphores. Can we use mutex in single process and how?
Working of MSIL and JIT COMPILER.
Can a C# code, use c++ code and call kernel functions like createfile.
Areas: dot net, oops, operating systems, thread synchronization.
Difference in execution steps of c++ and c# code| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Assembly C++ Data Structures Debugging Object Oriented Design Operating System Threads - 11
1of 1 vote
AnswersOne of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
- avinash in India
Eg -
{-1, 0, 0, 1, 1} would represent a tree with -
* 0 as root
* 1 and 2 as children of 0
* 3 and 4 as children of 1
Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.
Eg -
For the above given tree, level order traversal would be -
0
1 2
3 4
And hence, the reverse level order traversal is -
3 4
1 2
0
Please note -
* An element with parent = -1 is the root element.
* An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
* When printing a level of tree you need to maintain left to right order.
Input Format -
First line of the input contains number of nodes in the tree (N)
Next line contains N (space seperated) numbers that denote where i-th number will denote the parent node of i-th node.
Output Format -
Print reverse level order traversal of the corresponding tree, with every new level starting in a different line.
Notes/Limits -
* 1 <= N <= 50
* There will be only one root element in any given test case
* Given numbers will always form a valid undivided tree
* Output should be in the exact format as specified (including whitespaces)
Sample Test Cases -
Input -
5
-1 0 0 2 1
Output -
4 3
1 2
0
Input -
9
8 7 0 5 5 8 7 0 -1
Output -
1 6
2 7 3 4
0 5
8
Input -
45
24 42 4 30 29 43 22 15 26 36 26 16 3 22 21 41 18 16 34 41 12 29 32 30 43 15 4 38 36 -1 24 42 18 6 21 38 6 17 32 17 3
34 12 14 14
Output -
1 31
20 42 9 28
12 40 33 36
3 23 37 39 6 13 27 35
0 30 11 17 22 38 7 25
5 24 16 32 15 19
8 10 43 44 18 41
2 26 14 34
4 21
29
Input -
33
17 25 0 14 7 2 5 25 18 8 16 27 10 9 19 7 31 31 19 0 8 14 9 17 18 2 30 16 30 10 5 -1 27
Output -
13 22
26 28 4 15 9 20
6 30 1 7 3 21 8 24
5 25 14 18
12 29 11 32 2 19
10 27 0 23
16 17
31| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Trees and Graphs - 20
1of 1 vote
AnswersGiven an integer array find all pythogorean triplets. a^2 + b^2 = c^2 print the a,b,c and their indexes
- avinash in India for Global Payment Services| Report Duplicate | Flag | PURGE
Amazon SDE-2
I did answered along the same line that most of you have answered. However, interviewer gave following remark to my answer.
1. If input array has negative numbers? in which case, squaring it could result in printing invalid Pythagorean triplets.
2. If we have sort, then we will loose the index numbers which we have retrieve to print the Triplets.
3. Interviewer seems to be in agreement with time complexity. i.e O(n^2)*log(n).
[O(n^2) to pick two numbers] * [O(log n) for binary search]. But for binary search, i would have to sort and it is erroneous. Here i was caught!
- avinash February 19, 2014#include <cstdlib> #include <iostream> #include <map> using namespace std; struct Node{ int data; Node* left; Node* right; }; Node* NewNode(int data) { Node* newNode = new Node(); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } int FindRoot(std::map<int,int> mapChildParent) { for (int i=0; i< mapChildParent.size(); i++) if(mapChildParent[i] == -1) return i; return -1; } void FindChild(int iChildArray[], std::map<int, int> myMap, int iParentIndex) { int iCount = 0; for (int i=0; i< myMap.size(); i++) { if(myMap[i] == iParentIndex) { iChildArray[iCount] = i; iCount++; } } } void prepareSubTree (Node* parentNode, map<int, int> myMap) { int iChildArray[2] = {-1, -1}; FindChild(iChildArray, myMap, parentNode->data); if (iChildArray[0] != -1) { Node* temp = NewNode(iChildArray[0]); parentNode->left = temp; prepareSubTree(temp, myMap); } if (iChildArray[1] != -1) { Node* temp = NewNode(iChildArray[1]); parentNode->right = temp; prepareSubTree(temp, myMap); } } int height( Node* node) { if (node==NULL) return 0; else { /* compute the height of each subtree */ int lheight = height(node->left); int rheight = height(node->right); /* use the larger one */ if (lheight > rheight) return (lheight+1); else return (rheight+1); } } void printGivenLevel(struct Node* root, int level) { if(root == NULL) return; if(level == 1) { cout << root->data; cout << ' ' ; } else if (level > 1) { printGivenLevel(root->left, level-1); printGivenLevel(root->right, level-1); } } void printReverseLevelOrder(Node* root) { // print reverse level order order int iHeight = height(root); int i; for(i=iHeight; i>=1; i--) { printGivenLevel(root, i); cout << endl; } } int main(int argc, char *argv[]) { int iNum ; cin >> iNum; int* arr = new int[iNum]; for (int i=0; i < iNum; i++) cin >> *(arr+i); std::map<int, int> myMap; // store child-parent relationship in a map data structure for(int i=0; i<iNum; i++) myMap[i] = arr[i]; int iRootIndex = FindRoot(myMap); Node* root = NewNode(iRootIndex); prepareSubTree(root, myMap); printReverseLevelOrder(root); return 0; }