During an interview, I asked, in jest, whether I could use Whitespace to solve the problem. The interviewer chuckled and said that if I implemented the algorithm in Bash, I would receive an offer on the spot; jokingly. I did not solve the problem in Bash that day; however, I've been wondering why I haven't tried using Bash for algorithmic interviews. This post is an exploration on the subject.

We break this post into three sections. First, we review some Bash fundamental such as variable assignment, evaluating variables, integer arithmetic, control flow structures, and functions. Second, we show implementations of Fibonacci numbers and the in-place quicksort using Bash. Finally, we discuss the feasibility of using Bash during an algorithmic interview.

## Bash Review

As a brief review, we cover some simple mechanics in Bash such as variable assignment, evaluating variables, integer arithmetic, standard control flow structures, and functions. If you are already familiar with these concepts in Bash, you may skip this section.

### Variables and Values

We begin the review with binding values to variables and evaluating variables.
Suppose that we want to bind the string `"hello"`

to the variable `x`

and
printing out the value bound to the variable `x`

.

```
x=hello # binds "hello" to the variable x
echo $x # prints the value bound to the variable x
```

Binding values to variables and referencing the value in variables are two
common operations that we will use. There are two important syntactical nuances
to notice here. First, notice that there should be no spaces around the equals
sign `=`

for declaration. Second, notice that we prepend the variable `x`

with
a dollar sign `$x`

when we want to reference its value.

In Bash,

`$x`

is known asparameter expansionwhere the value bound to the variable is resolved during evaluation.

Now that we have some understanding of how variables and values interact, we may begin building functions.

### Integer Arithmetic

Operations on integers in addition to equality and inequality relationships
require a special syntax known as *arithmetic expansion*. To return the result
of an arithmetic expression, we wrap the expression between `$((`

and `))`

. The
results of this expression are assignable. For example, suppose we wanted express
the following assignment:

In Bash, we would express this using the arithmetic expansion syntax.

```
x=2 # binds the number 2 to the variable x
y=$(($x + 3)) # evaluates x + 3 and binds the result to y
```

There is also a special syntax for expressing integer boolean relationships. We
wrap boolean expressions between `((`

and `))`

. The succeess of the command is
determined by the result of the expression: the command succeeds if the
expression is true; the command fails otherwise. Suppose we wanted to print a
statement if a boolean expression evaluated to true.

```
(( 3 < 2 )) && echo "3 is less than 2"
```

Note that the `&&`

syntax means that the second command will run only if the
previous command succeeded.

### Control Flow Structures

Standard control flow structures include conditionals statements, case statements and loops. We presume that the reader is familiar with these structures and their semantics from other programming languages; hence, we proceed only with a presentation of the syntax.

Conditional statements change their behavior based on the success or failure of
an expression `expr`

. An example of an expression could be `(( 3 < 2 ))`

.

```
if expr; then
# statements
else
# statements
fi
```

Case statements also change their behavior based; however, the behavior is
based on pattern matching the results of an expression `expr`

. For example, an
expression may be input from a user in a variable `x`

and possible cases may
include `continue`

or `exit`

. A special case is `*`

which denotes the default
case.

```
case expr; then
a) # statements
;;
b) # statements
;;
*) # statements
;;
esac
```

Looping may be achieved through a `while`

statement that continues based on the
success or failure of an expression `expr`

. Although `for`

statements exist, we
do not cover it in this post.

```
while expr; do
# statements
done
```

### Functions

We begin with the syntactic structure of a function in Bash and show how to
take function arguments and return values. Suppose that we wanted to implement
an `increment`

function that takes a single number as an argument and returns
one plus the argument.

```
increment() {
local x=$1
return $(($x + 1))
}
```

This example demonstrates four concepts. We began by declaring a function
`increment`

. Then, we read the positional parameter `$1`

into a local variable
`x`

.

By default, variables have global scope. We must explicitly declare variables as

`local`

to guarantee that a variable has local scope within a function.

Next, before returning from the function, we add one to the value of `x`

using
arithmetic expansion `$(($x + 1))`

. Finally, we return the value of the
arithmetic expansion.

This function may called by providing a number to increment.

```
increment 3
echo $? # prints 4
```

The return value is bound to a special parameter `$?`

which is printed by the
`echo`

command.

## Bash Algorithms

Now that we have a fundamental understanding of Bash syntax and semantics, we may proceed implementing some common algorithms. We will not explain the details of the algorithms; only the implementation follows.

### Fibonacci Numbers

Let us begin with a simple problem: Find the $n^\text{th}$ Fibonacci number for any $n > 0$. Recall that Fibonacci numbers follow the sequence

This is a simple exercise of constructing a recursive function.

```
fib() {
local n=$1
case $n in
1) return 1 ;;
2) return 1 ;;
esac
fib $(($n - 1))
local fib1=$?
fib $(($n - 2))
local fib2=$?
return $(($fib1 + $fib2))
}
```

This implementation is straightforward though non-optimal. However, we begin to see that the language has the capacity to express familiar algorithms intuitively. We leave the optimal implementation as an exercise to the reader. Note that the implementation may require knowledge of associative arrays.

Let's try something more complex.

### In-place Quicksort

In this algorithm, we are interested in sorting an array of integers. For this particular problem, we require some supplementary material which is a representation of arrays in Bash.

#### Bash Arrays

An array literal may be represented as a sequence of space-delimited tokens
within parentheses. The following defines an array bound to a variable
`a`

:

```
a=(4 1 3 2)
```

Some standard operations include getting the length of the array and accessing an element at a particular index.

```
${#a[@]} # the length of the array a
${a[2]} # the element of the array a at index 2
```

#### Algorithm Implementation

Describing the algorithm is outside of the scope of this post. Instead, we refer you to Wikipedia's Quicksort article for the details of the algorithm.

Suppose that we have an array

```
a=(4 1 3 2)
```

We implement the sorting algorithm `quicksort`

that sorts the array `a`

in-place.

```
swap() {
a[$1]=$4
a[$3]=$2
}
quicksort() {
local length=${#a[@]}
quicksort_recursive 0 $(($length - 1))
}
quicksort_recursive() {
local start=$1
local end=$2
if (($start >= $end)); then
return
fi
local pivot=${a[$start]}
local p q pvalue qvalue
p=$(($start + 1))
q=$end
while (($p <= $q)); do
qvalue=${a[$q]}
if (($qvalue < $pivot)); then
pvalue=${a[$p]}
swap $p $pvalue $q $qvalue
p=$(($p + 1))
else
q=$(($q - 1))
fi
done
swap $start $pivot $q $qvalue
quicksort_recursive $start $(($q - 1))
quicksort_recursive $(($q + 1)) $end
}
```

Glancing at this algorithm, the logic is clear. We are able to express logic using control flows, integer arithmetic, and functions on an array data structures. Many algorithms can be decomposed into similar components.

### Other Classes of Algorithms

Although we have covered two popular algorithms, there may be some concerns that the language would not be able to express other classes of algorithms. These classes may include graph algorithms, numerical algorithms, etc.

A few moments of thought will quickly dismiss many of these concerns. Graphs
can be represented densely as matrices which can be simulated by arrays.
Alternatively, graphs can be represented sparsely with maps for which Bash has
associative arrays. Regarding numerical algorithms, all computations can be
piped to the calculator tool `bc`

.

## Bash for Algorithm Interviews

It is clear at this point that Bash is capable of expressing most if not all algorithms commonly given an interview scenario. There are a few soft tradeoffs that we may further outline.

We begin by framing these tradeoffs in a concrete example. Suppose that you
are an in an algorithm interview for a company where you are allowed to choose
a programming language to interview in. You are the *interviewee* and the
person evaluating you is the *interviewer*. Suppose now that you wanted to use
Bash.

Some advantages include

- Amusing to implement
- Novel implementation that the interviewer has unlikely seen
- It is improbable for the interviewee to cheat

Some disadvantages include

- Interviewer may not be able to help the interviewee debug
- Code may not be as concise as other programming languages
- Interviewee may not know Bash as well as other languages
- Language is not representative of application code

We have discussed the feasibility of using Bash for algorithmic interviews including many of the soft tradeoffs. Although I do not claim that Bash should be used for all interviews, I would personally be willing to try Bash if I had sufficient confidence in my solution for the problem given. Why not?