CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

IBM Interview Question for Software Engineer / Developers






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

Just do any traversal on the binary tree and store the contents in an array. Sort the array. Then do an in-order traversal of the binary tree and assign values from array to the nodes. Complexity: O(n log n) Space complexity: O(n).

- vinod August 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you want to sort the array?

- IBMer August 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you want to sort the array?

- IBMer August 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the challenge here is to do it in O(1) space

- Anonymous August 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you cannot do it in o(1) space

- Vinay August 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually we can do it in O(1) space. Basic idea is, given a root node, recursively build BST on its left sub-tree, then build BST on its right sub-tree. After building each sub-tree, convert sub-BST to Doubly-Linked List, then merge the two Lists to form the ultimate BST. This is done in O(1) space since the merge directly uses the nodes in the lists.

- papaya August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how would you form the ultimate BST of a specific shape, from the doubly linked list constructed from the sub-BST?

- syrus August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you show tht with an example.... i huess its not possible in o(1)

- srinivas August 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

in-order traversal
sort
map

- syrus August 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Anyone can write a C/C++ code for this question? Thx

- Anonymous August 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check this out - stackoverflow.com/questions/3531606/convert-binary-tree-bst-maintaining-original-tree-shape

- shrikar August 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Calculate the # of nodes in the tree(say a), the left subtree(b) and right subtree(c), then a = b + c + 1;
sort the nodes in this tree and find the node in the b+1 th position, use this as the root for BST

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

Calculate the # of nodes in the tree(say a), the left subtree(b) and right subtree(c), then a = b + c + 1;
sort the nodes in this tree and find the node in the b+1 th position, use this as the root for BST

- qianduixue July 21, 2011 | Flag Reply


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