If you’re studying computer science, at some point you’re going to be exposed to the Quicksort algorithm. Even if you’re not a computer science student, chances are this particular algorithm will come up at some point in time as part of an interview. I’ve been asked about it plenty of times in interview processes and never once used it again.
Whether or not you’ll ever use the Quicksort algorithm, it is important to know and that is what we’re going to review in this back to the basics tutorial.
In this tutorial we’re going to sort a vector of integer values using the Quicksort algorithm. We’re going to use a vector because it is a commonly used data structure in C++.Read More
Previously you saw an implementation of Quicksort, one of the better sorting algorithms. This time we’re going to look at a much inferior sorting algorithm which generally makes its appearance in introduction to computer science type courses. I’m talking about the Bubble Sort algorithm.
Bubble Sort via Wikipedia:
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
The Bubble Sort algorithm is sub-par because of the outrageous time-complexity that it has for all sorting calls and we’re going to see why.Read More
Circling back to data structures and algorithms, we’re now going to take a look at the efficient sorting algorithm known as Quicksort.
Quicksort via Wikipedia:
Sometimes called partition-exchange sort, is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.
The idea behind Quicksort is to take a large array of values and divide it into two smaller arrays, doing this recursively, and swapping elements.
This is one of the fundamental algorithms you’ll learn in any computer science course. It is also a very good question that could be asked in a job interview for an engineering type position. I’m going to help you through it using Java.Read More
If you’ve been keeping up with my blog, I’ve made a topic regarding Binary Search Trees, but another very important topic in computer science and software engineering is in regards to Graphs.
Graphs via Wikipedia:
A graph data structure consists of a finite (and possibly mutable) set of nodes or vertices, together with a set of ordered pairs of these nodes (or, in some cases, a set of unordered pairs). These pairs are known as edges or arcs.
When interviewing for a new programming or software engineering position, it is incredibly likely that you are asked a question on this topic. Because of this, I figured it would be a good idea to go over a few of the Graph search algorithms.Read More
Reverse Polish Notation via Wikipedia:
A mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed.
In this phase two article, we’re going to look at how to solve a mathematical expression that has been parsed into Reverse Polish Notation (RPN).Read More
Anyone who knows how to program can probably solve a mathematical equation such as
5 + 3 * 6 - ( 5 / 3 ) + 7, but how might you get a computer to understand the appropriate order of operations? The equation I listed is in a format known as Infix Notation.
Infix Notation via Wikipedia:
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands.
This format is not the most ideal to work with when attempting to solve.
Instead it is more appropriate to use format such as
5 3 6 * + 5 3 / - 7 + which is more commonly known as Postfix Notation or Reverse Polish Notation (RPN). This conversion can be accomplished by what is known as the Shunting Yard algorithm.
Back on the topic of possible programming interview questions, you may at some time in your career be asked to reverse words in a string. This is a much simpler problem and may be more likely to appear on a technical phone screening.
In it’s simplest form, you would assume all space separated string collections to be words. To clarify, it doesn’t matter if you’re looking at a true word or just some jumbled text separated by a space character.Read More