#Code Challenge #5: May 10, 2017
Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.
This week’s challenge was reportedly asked in interviews at Google (and even in some other contexts that you may not expect):
You are given a list of numbers stored in a list,
A. Your challenge is to build a [Binary Search Tree] (Binary search tree - Wikipedia) to store these numbers. You will need to:
- Represent each node of the tree (including its data, left child and right child).
- Print the tree out in an understandable form.
- Make a function to insert a list of numbers (
A) into the tree.
Check if you can insert all the numbers in
Ainto your tree, and that it prints out as expected.
Use the language of your choice to solve this challenge, but only submissions in languages taught by Codecademy are eligible to “win”.
Write a function to check if the Binary Search Tree that you’ve created is balanced.
A tree is considered balanced when the difference between the
min depth and
max depth does not exceed 1, i.e. if the list had
n elements in it the height of the tree would be
log(n) (base 2).
#####Find out more about intermediate challenges.
- Adapt your function to insert a list of
nnumbers so that it runs in
O(n log n)time. Bear in mind that this is just the average case for a random sequence of numbers. If the list
Awas sorted it would take
- Adapt your function to check if the tree is balanced so that it runs in
If your BST is balanced then the insert function would have only taken
O(n log n) time, see if you can figure out why.
###How to Participate
If you want to add your own submission to this challenge, you are more than welcome to do so – it will help you to practice and help everyone else to learn! Simply scroll down and
reply to this thread with your code to participate! Don’t just submit your code, remember to
explain your solution, too! If you want your entry to be considered under our “best code” assessment, you must include a link to your code running on repl.it and abide by our other simple rules.
The fine print:
Click the links to find out more about:
- the rules & how to participate in challenges
- how challenges are used as job interview questions
- why Codecademy runs challenges (and why they are formatted this way)
- more details about the challenges and why we think they are useful.
- find previous challenges (and see the past winners) in our Challenge Index