Bloomberg LP Interview Question for Financial Software Developers


Country: United States
Interview Type: In-Person




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

1. I would ask the interviewer if they meant a binary search tree, and not a basic binary tree. A simple binary tree isn't used for searching it is simply a way to store data with left and right nodes, so really has no comparison with the other two types of trees.

I'll assume they clarified after my question that it is in fact a binary search tree to compare against.

Binary Search trees do not need to be balanced, so depending on the order of insertions the tree can become unbalanced quickly and search times could potentially vary a lot. This is the most basic search tree, and inserts and deletes have very simple logic.

AVL trees are always at the optimal balance point, but can slow down inserts and deletes because they never allow that tree height to be outside the -1 to 1 range. But you will have the fastest look times.

Red black trees are also self balancing but can become slightly imbalanced to improve insert and delete times, with a small potential hit to search times.

So if a system updates the tree often I would lean toward using a red black tree, and if the tree is updated very rarely then a AVL tree would be the better direction.

If the data will come in a "controlled manner" that we will not likely have a large imbalance than a BST could be an option but it would still be good to look at one of the self balancing tree structures.

- Kyle April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

B-tree is not binary tree

- alex June 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

A Binary Tree is a tree in which each node can have maximum of 2 children.
Uses could be like a folder structure or the organizational hierarchy. It is used when there are no specific rules as to which node should be where, unlike in the case of a BST or a balanced tree which follow a set f rules.
An AVL tree is a balanced BST,it basically assures that the height of your tree is k*log n where k is a constant and n is the number of nodes in the tree. This in turn reduces the time complexity of an add, delete or a search operation to O(log n) which would normally be O(n) in a binary tree and O(h) in a BST.
I guess this answers the question for which is most efficient.
I do not know much about RB trees, but it too is a balanced BST like AVL trees and I believe that the implementation of operations in an RB tree are a lot more complex than that of an AVL tree but RB trees are apparently more secure and are used by several java libraries.
Please correct me if I'm wrong.

- teli.vaibhav February 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Most of what you said isn't right.

You wouldn't want to use a binary tree for a folder structure, because a folder can have many sub-folders, not just 2.

An AVL tree's leaf nodes differ in height by at most one.

RB trees have nothing to do with security. They are often used instead of AVL trees because their insertion and deletion times have a lower constant factor.

- eugene.yarovoi February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

All that you said makes a lot of sense, thanks for correcting me.
Could you please also give a scenario where a Binary Tree would be more useful compared to an AVL tree? It would be very helpful.

- Anonymous February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

An AVL tree is a type of binary search tree, which is a type of binary tree. I don't know what it means to compare an AVL tree to a binary tree because an AVL tree is a type of binary tree.

- eugene.yarovoi February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the scenario boils down to when one would use a BT over a BST..

- teli.vaibhav February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A binary search tree is a type of binary tree. Asking to compare the two is like asking to compare dogs to animals.

- eugene.yarovoi February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks eugene it makes sense. Also that's why most libraries (like stl:map) prefer rb tree rather than avl when they need a balanced BST

- Paddy February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

avl treee we have to avoid sked tree from bst. practically b tree are used for file system storage

- Raj February 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ni thatha ra yadav oka muka kuda ardhamiyi chadateledu...........
bavakuffff

- Anonymous January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

B-Tree is used for large data, like file system or where we used external storage.It is used with multiple keys in the node w.r.t to degree of the tree and height of the tree will be lower than AVL and RB-Tree .
AVL and RB-Tree use for smaller date and could be computed on internal memory and each node can have max one key only.

- zafar ziya February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.


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