This post discusses a O(n) algorithm that construct a balanced binary search tree (BST) from a sorted list. For instance, consider that we are given a sorted list: [1,2,3,4,5,6,7]. We have to construct a balanced BST as follows.
1 3 5 7
To do so, we use the following definition of Tree, described in Scala By Example book.
One straight-forward approach would be to repeatedly perform binary search on the given list to find the median of the list, and then, to construct a balanced BST recursively. Complexity of such approach is O(nlogn), where n is the number of elements in the given list.
A better algorithm constructs balanced BST while iterating the list only once. It begins with the leaf nodes and construct the tree in a bottom-up manner. As such, it avoids repeated binary searches and achieves better runtime complexity (i.e., O(n), where n is the total number of elements in the given list). Following Scala code outlines this algorithm, which effectively converts a list ls to an IntSet, a balanced BST:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This is an interesting article by @DanCast that attempts to answer a long-standing question: What does “Senior” entail in the role of “Senior” Software Engineer? A must read for any aspiring (senior) software engineer.
I’ve been thinking a lot recently about the difference between the journeyman and master years of software engineering, how you move from one to the other, and how one might accelerate growth. As part of this process, a more fundamental question has come up – what does it even mean to be a “senior” software engineer (SSE)? Put aside titles for a second – there are plenty of “Senior Software Engineers” who aren’t worth the business cards their titles are written on, and we could quibble over whether we should be talking about “Senior” or “Principal” engineers. But really, what we’re trying to do is to describe what mastery looks like for a software engineer. This post is a stab at an answer.
An SSE knows her tools. She has a deep understanding of her OS, command line, utilities, and IDE, as well as the platform the software will…
"Functional Scala" is a set of tutorials on Scala programming language by Mario Gleichmann. Although a bit verbose, it introduces the key constructs of Scala, and outlines Scala’s primary features from the perspective of functional programming.
Welcome to the first part of a series of episodes about ‘Functional Scala’. While positioning itself as a so called object-functional language, most of the discussion and articles about Scala centered around its object oriented features so far. If you’re reading this, chances are you want to learn more about the functional side of Scala. Well, you’ve come to the right place.
The idea for the following episodes arose out of some talks i gave about ‘Functional Scala’. I decided to write and talk about it because I wanted to solidify my own knowledge about Functional Programming in general and about Scala in particular … and because I thought I could help some people new to Scala to learn its functional features from my perspective.
Not least, there were some critical discussions in the past whether Scala is rightfully characterized as a functional Language. For this to decide, we firstly have to be clear about the core ideas, you’ll regularly come across within widely accepted functional Languages, like Haskell. We’re going to see if and how they are offered in Scala and try to push them to its limits. So without any further ado, let’s enter the world of Functional Programming (FP) in Scala.