Adobe Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

Code for hard coded heap, getting its inorder traversal and then restoring heap back from in-order traversal. Hint is how you get the in-order traversal, then just reverse the assignment in in-order traversal to get the heap back.

void HeapTest()
{
	const int kHeapSize = 10;
	int heap[kHeapSize] = { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };
	cout << "Heap is : " << endl;
	PrintArray(heap, kHeapSize);

	int inOrderTraversal[kHeapSize];
	FillInOrderTraversal(heap, inOrderTraversal, kHeapSize);
	cout << "In Order Traversal is : " << endl;
	PrintArray(inOrderTraversal, kHeapSize);

	int outputHeap[kHeapSize];
	ReconstructHeap(inOrderTraversal, outputHeap, kHeapSize);
	cout << "Reconstructed heap is : " << endl;
	PrintArray(outputHeap, kHeapSize);
}

void PrintArray(const int* data, int size)
{
	for (int index = 0; index < size; index++) {
		cout << data[index] << "    ";
	}
	cout  << endl;
}

void FillInOrderTraversal(const int* data, int* output, int size)
{
	int temp = 0;
	InOrderTraversal(data, 1, size, output, temp);
}

bool InOrderTraversal(const int* data, int currentNode, int size,
					  int* outData, int& dataPoint)
{
	if (currentNode > size) {
		return false;
	}
	InOrderTraversal(data, currentNode * 2, size, outData, dataPoint);
	outData[dataPoint] = data[currentNode - 1];
	dataPoint++;
	InOrderTraversal(data, (currentNode * 2) + 1, size, outData, dataPoint);
	return true;
}

void ReconstructHeap(const int* inorderTraversal, int* outputHeap, int size)
{
	int temp = 0;

	InOrderContruct(inorderTraversal, 1, size, outputHeap, temp);
}

bool InOrderContruct(const int* inOrderTraversal, int currentNode,
					 int size, int* outData, int& dataPoint)
{
	if (currentNode > size) {
		return false;
	}
	InOrderContruct(inOrderTraversal, currentNode * 2, size, outData, dataPoint);
	outData[currentNode - 1] = inOrderTraversal[dataPoint];
	dataPoint++;
	InOrderContruct(inOrderTraversal, (currentNode * 2) + 1, size, outData, dataPoint);
	return true;
}

- Anonymous July 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what should be time complexity
if it is o(nlogn) then its simple
just use traditional method

- PreP July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) First find the maximum element, that will be the root of the heap.
2) This element divides the array in two half. Recursively, keep finding the largest element and making it root.

Time Complexity: O(n^2)

- Ankuj July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you post the solution i think it will nlogn isnt it ??
please post code

- David July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@PreP you wont get the same heap back

- Ankuj July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If it is a min heap, isn't the solution trivial ? why do we have to find the max ?

- JeanGrey July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

k i thought that convert tree such that each node is bigger than its childrens

- PreP July 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store Inorder Traversal in to array & then convert from it heap will take O(nlogn)

Shshank

- WgpShashank July 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is how to reconstruct it back from inorder traversal

- Anonymous July 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So Why I used Array :)

- WgpShashank July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

But using array is not the solution constructing the same heap from which that inorder traversal came is the real question. For eg given a heap 16,14,10,8,7,9,3,2,4,1. Its inorder traversal is 2,8,4,14,1,7,16,9,10,3. Construct same heap from this.

- Anonymous July 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can do it in n time
start from the first element. Keep track of the maximum element seen till now.
At each point, maximum element at that point will be one of roots and the elements seen before that will be part of its left subtree. (it could also be a leaf element)
elements after this max element and before any other element found in the list which is greater than this max element will be in its right subtree.

so you have to go through the list. Keep forming left subtrees. Once you reach to any right subtree. form it separately and attach it to main tree.

in this example
- 2
- 8
/
2
- 8 4
/
2

-
14
/
8
/ \
2 4


and so on

- Anonymous July 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) If just binary tree. => It would take O(n lgN).
2) If bs tree. => O(N)

- max July 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the question was not, what order...
it is how do you do it...

- chakradarraju July 16, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More