#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):
###The Challenge
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
A
into 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”.
###Intermediate difficulty
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.
###Hard Difficulty
- Adapt your function to insert a list of
n
numbers so that it runs inO(n log n)
time. Bear in mind that this is just the average case for a random sequence of numbers. If the listA
was sorted it would takeO(n^2)
.
- Adapt your function to check if the tree is balanced so that it runs in
O(n)
time.
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.
#####Find out more about hard challenges and Big O
###Winner
@tagrockstar79958 was the first to submit a complete working solution at the hard difficulty level: see it here.
###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