This is a straightforward and basic task to implement: given a string input to a function we want to return its reverse.
There’s a wide range of solutions to this problem and here we’ll go through 3 of them using C#:
the built-in Reverse extension function
the Aggregate LINQ operator
bare-bones solution based on a for-loop
Here are the three implementations:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class StringReverse
{
public string ReverseString(string input)
{
return ReverseStringWithReverse(input);
//return ReverseStringWithAggregate(input);
//return ReverseStringWithLoop(input);
}
private string ReverseStringWithReverse(string input)
{
var reverse = input.Reverse();
//return string.Join("", reverse);
return string.Concat(reverse);
//or in one line string.Concat(input.Reverse())
}
private string ReverseStringWithAggregate(string input)
{
return input.Aggregate("", (c1, c2) => c2 + c1);
}
private string ReverseStringWithLoop(string input)
{
string reversed = "";
for (int i = input.Length - 1; i >= 0; i--)
{
reversed += input[i];
}
return reversed;
}
}
}
In ReverseStringWithReverse we take the incoming string and apply the built-in Reverse() extension method on it. It returns a collection of chars, i.e. not the reversed string. To join those chars into a string we can call string.Join or string.Concat. Join takes a delimiter which is an empty string in this case as we don’t want to put any extra character in between the characters when they are joined. The Concat function is more straightforward to use, we can just pass in the array collection.
In ReverseStringWithLoop we iterate through the input string starting at the back. We build the reversed string character by character and return the result.
ReverseStringWithAggregate is a bit more “exotic” and uses the Aggregate LINQ operator. I only put it here in case you’d like to show your familiarity with this accumulator function in an interview. If you don’t know how this operator works then you can check out this post for an example. The empty string is a seed which is basically the starting point for building the reversed string.
This overload of the Aggregate function will operate on an IEnumerable<char> as the source string is dissected into its characters. We specified the seed as a string type so the overall result from this extension function will also be a string.
We start with an empty string and apply a function on the source string defined by
(c1, c2) => c2 + c1
This is the accumulator function and accepts two parameters: the first one, i.e. c1 will be of the same type as the seed, i.e. a string. The second one, i.e. c2 will be the same type as each element in the dissected string, i.e. a char. The accumulator function returns the same type as the seed, i.e. a string which is simply built up gradually as
c2 + c1
…i.e. take the character and add it to the growing string c1.
Let’s try to understand this function using the input string “hello”.
So we start with an empty string as c1 and take the first character from the source char collection, i.e. ‘h’. We get "" + 'h' = "h" as the resulting string which will be fed as the c1 string input into the next iteration. So next c1 will be “h” and c2 ‘e’ and we return ‘e’ + “h”, i.e. “eh”. “eh” is taken as c1 in the next round and ‘l’ as the character input, ‘l’ + “eh” will give “leh”. The function continues until we arrive at “olleh”. If we set the seed to “world” then that will be value of c1 in the very first iteration and the end result will be “ollehworld”.
It is probably overkill to use the Aggregate extension for a problem like this but it’s a good opportunity to demonstrate your familiarity with this relatively rarely used function in an interview setting.
Suppose you need a function that accepts a string and returns the character that occurs the most frequently in it. Examples:
Input
Result
mamaaaa
a
gaga
g
agag
a
12312312333456
3
Note that we’ll treat numeric values as strings. Also, with multiple values having the same max we’ll return the first one.
We’ll build a character map out of the input string, just like the one we saw in this post. Here’s a reminder:
What is a character map? It is a map where the key is of type char and the value if of type integer. We collect the unique characters of a string and count how many times each character occurs in the string. E.g.:
Char
Count
‘f’
2
‘g’
1
‘i’
2
‘d’
1
‘o’
1
We’ll reuse the same method as in the referenced post.
Then we sort the map by the values in descending order and return the key of the key-value pair on top:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MaxChar
{
public char GetMostFrequentChar(string input)
{
var charMap = input.Distinct().ToDictionary(c => c, c => input.Count(s => s == c));
return charMap.OrderByDescending(kvp => kvp.Value).First().Key;
}
}
}
Here comes a short set of unit tests:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms.Tests
{
[TestClass()]
public class MaxCharTests
{
[TestMethod()]
public void GetMostFrequentCharTests()
{
MaxChar mc = new MaxChar();
Assert.AreEqual('a', mc.GetMostFrequentChar("mamaaaa"));
Assert.AreEqual('g', mc.GetMostFrequentChar("gaga"));
Assert.AreEqual('a', mc.GetMostFrequentChar("agag"));
Assert.AreEqual('3', mc.GetMostFrequentChar("12312312333456"));
}
}
}
Two strings are anagrams if they are made up of the same set of characters. Examples:
“hello” and “loleh”
“123123” and “312312”
“qwerty” and “wretqy”
The degree of “anagram-ness” can vary:
ignore case?
ignore non-numeric characters?
ignore whitespace?
In this post we’ll only consider word-characters only and the comparison will be case-insensitive to make the problem more interesting.
We’ll write a function that accepts two integers and returns a boolean: true if the strings are anagrams, otherwise false.
We’ll look at two solutions out of many that exist out there:
using a character map
using string sort
What is a character map? It is a map where the key is of type char and the value if of type integer. We collect the unique characters of a string and count how many times each character occurs in the string. E.g.:
Char
Count
‘f’
2
‘g’
1
‘i’
2
‘d’
1
‘o’
1
We do that for both strings and compare the counts of each unique character.
Let’s start with a skeleton:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
namespace Algorithms
{
public class Anagram
{
public bool AreAnagrams(string first, string second)
{
if (first == null || second == null) return false;
return AreAnagramsWithCharMap(first, second);
//return AreAnagramsWithSortedStrings(first, second);
}
private bool AreAnagramsWithCharMap(string first, string second)
{
return false;
}
private bool AreAnagramsWithSortedStrings(string first, string second)
{
return false;
}
private Dictionary<char, int> MakeCharacterMap(string input)
{
string cleaned = CleanInput(input);
return cleaned.Distinct().ToDictionary(c => c, c => cleaned.Count(s => s == c));
}
private string CleanInput(string input)
{
return Regex.Replace(input, @"[_]+|[^\w]+|[\d-]+", "").ToLower();
}
}
}
We start by some null-checking and return false if either of the two inputs is null. The AreAnagramsWithCharMap function has been wired up but it’s not yet implemented. The function for the second solution AreAnagramsWithSortedStrings has also been prepared.
We have two private functions as well:
CleanInput
this one takes a string and strips all underscores, white space and non-word characters from it and returns the lower-case version of it
MakeCharacterMap
first we clean the incoming input string
second we use a couple of LINQ operators to build the character map
Distinct() to gather the unique characters from the string
ToDictionary() to build the map itself, the key will be the character itself and for the value we count the number of occurrences of that character in the string
Let’s look at the implementation of AreAnagramsWithCharMap:
We first create the two character maps. If they differ in size then we can immediately return false. It means that one of the strings has at least one more character than the other so it’s pointless to continue.
Otherwise we make use of the All LINQ operator which return true of all the elements of a collection fulfil a certain condition. The condition is based on two parameters:
whether the character map contains the character as the key in the first place
whether that character occurs with the same frequency as in the source map
If both conditions are fulfilled for all characters in the character maps then we return true.
Here’s a set of unit tests:
using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Algorithms.Tests
{
[TestClass]
public class AnagramTests
{
[TestMethod]
public void AreAnagramsTests()
{
Anagram a = new Anagram();
Assert.IsTrue(a.AreAnagrams("hello", "___ hllOe!! 456 ???"));
Assert.IsFalse(a.AreAnagrams("sdfs", null));
Assert.IsFalse(a.AreAnagrams(null, "sdfs"));
Assert.IsFalse(a.AreAnagrams(null, null));
Assert.IsFalse(a.AreAnagrams("qwerty", "yewr"));
Assert.IsFalse(a.AreAnagrams("qwerty", "qwertyuiop"));
Assert.IsTrue(a.AreAnagrams("? par**lIame%%nt !", "partIAL men"));
Assert.IsTrue(a.AreAnagrams("a gentleman", "elegant man"));
}
}
}
The will all pass.
The second solution takes the two cleaned strings, puts them in order and compares them. This solution is slightly less performant than the first one due to the string ordering though. The map comparison doesn’t involve any ordering so it’s somewhat quicker.
We again clean the input string and then call the OrderBy LINQ operator. It returns an ordered collection of characters from the string, i.e. not an ordered string. Hence we need to embed this bit of code in string.Concat so that we build the string again from the characters. Finally we simply compare the two strings.
Wire up this function from the main one and rerun the unit tests. They will still pass.
public bool AreAnagrams(string first, string second)
{
if (first == null || second == null) return false;
//return AreAnagramsWithCharMap(first, second);
return AreAnagramsWithSortedStrings(first, second);
}
I assume you know what a matrix is from your maths classes. They are two-dimensional containers of usually numeric values, but they can hold any type of data. They are widely used in various mathematical and other scientific fields such as machine learning.
Here’s an example of a 3×3 matrix:
3
23
44
65
32
43
87
6
7
Matrices have columns and rows and their enumeration starts at 0. The coordinates of the various cells are given as row-column pairs. The top left hand cell is in row 0 and column 0, (0, 0) in short but there are other notations as well, I’ve even seen R0C0 at some point. So that’s the number 3 in the above example. Then 23 is in row 0, column 1 and so on. Here’s the coordinate table of a 4×4 matrix:
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
In this post we’ll take a look at something simpler than machine learning though. Imagine that you’re tasked to build a circular matrix of integers. What do I mean by a circular matrix? The matrix starts with a certain integer in (0, 0), usually 0 or 1 and is then filled in an inward-spiraling pattern where the starting integer is incremented with every new cell. Here’s an example with a 4×4 spiraling matrix:
1
2
3
4
12
13
14
5
11
16
15
6
10
9
8
7
So we start with 1 then fill up the top row up to 4. Then we continue downwards to 7, followed by the bottom row and then back up again. We continue spiraling inwards until we reach the last cell at row 2, column 1 which has the value 16.
Matrices are relatively often used in technical interviews if the interviewer wants to see how comfortable you are with arrays. Matrices can be represented as 2-dimensional arrays which are not used that often in everyday programming and some candidates may feel uncomfortable using them.
The exact problem you are given can vary of course but building circular or spiraling matrices is one of the more complex ones in an interview. Knowing how to solve this particular matrix-related question will make you ready for other, similar types of question.
So how do we go about solving this? In questions where you need to work out some algorithm the key to success is often to find some kind of pattern in the data set. Can we see any patterns if we just look at the rows? Hmm, the top row is easy: 1, 2, 3, 4 but the second row is 12, 13, 14, 5, that doesn’t reveal anything to me. Looking at the columns is even less promising: 1, 12, 11, 10 and then 2, 13, 16, 9. Frankly, I don’t see anything that catches the eye, no symmetries, no patterns that can be modelled in a loop etc.
Therefore a more viable solution is to follow the index as it’s incremented and in the outer circle. We then do the same in the inner circle and continue inwards for any remaining circles.
So in the first iteration we want to fill the matrix as follows:
In the second iteration we follow the same route with the remaining, smaller inner matrix:
stop
This iteration will be an outer one in code. We’ll also need to iterate through the various sections:
top row rightwards
right column downwards
bottom row leftwards
left column upwards
We’ll write a function that accepts the dimension of the matrix. An incoming 4 means that we want to build a 4×4 matrix. Our implementation will return a list of integer lists where each list represents a row in the matrix. But wait, didn’t we say that matrices are best represented by a jagged array in code? Yes, we’ll use an array to build the matrix and then turn it into a list at the end of the function. This way you’ll be ready to build whichever data structure is required from you in the test. You’ll see why an array is better suited to hold the matrix data in just a bit.
Let’s start with some basic setup code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
//main algorithm to be implemented here
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
We set up the return list and the temporary jagged array and fill them with some empty containers. We make sure that the array contents are copied to the list and return it from the function.
We’ll need several counters. We need to know where we start and end each row and column in the main outer loop. Remember, the main outer loop serves to identify the dimensions of the array spirals:
1
1
1
1
1
2
2
1
1
2
2
1
1
1
1
1
In a 4×4 matrix we have 2 circles. They are denoted by purple 1’s and red 2’s in the above example. A 3×3 matrix will also have 2 circles but the inner circle has only one element, the one in the very middle of the matrix. A 2×2 matric has only a single circle.
The counter starts at 1 in row 0 and column 0, those are 3 variables that we can identify right there. Those are valid for the first circle. When we’re done with the first circle then the counter will have whatever value it has got up to in the iteration, whereas start row and start column will be 1. (1, 1) is the starting point for the inner circle of a 4×4 matrix – and for any other matrix of any size for that matter.
We also need to see how far out we’re allowed to go in each circular iteration. In the first iteration we’ll start at (0, 0) and the farthest we reach is at (3, 3), i.e. the bottom right hand cell of the matrix. In the second circle we start at (1, 1) and the max reach will be at (2, 2) otherwise we overwrite some of the values we have already calculated. It sounds like it’s not enough to know where we start, i.e. start column and start row, but where we end as well, i.e. the end column and end row.
If you refer back to the table with the arrows then we’ll need to set these row and column pointers as follows:
start row: 0
end row: n – 1, i.e. 3 in a 4×4 matrix to comply with the 0-based array indexing
start column: 0
end column: n – 1, same as for end row
We start filling up the top row, i.e. from start row to end column, (0, 0) to (0, 3) in a 4×4 matrix. When we’re done then we increment the start row to 1. At this point we’re filling up the right hand column from (1, 3) to (3, 3). Then we decrement the end column and continue filling up the bottom row from (3, 2) to (3, 0). Finally we move up, i.e. decrement the end row and fill in the cells from (2, 0) to (1, 0). Recall that we incremented the start row to 1 so we don’t return to (0, 0) when filling up the left hand column.
At this point start row and start column are 1, end row and end column are 2, we’re ready for the inner circle where the same steps are taken.
So we’ll need the following:
a main loop for each circle in the matrix
inner loops for each section of the circle
top row
right column
bottom row
left column
Also, the bottom row and left column are iterated backwards, i.e. we need a for-loop where the iterator integer decreases to make sure we’re moving in the right direction.
We break the main outer loop when we have reached the end column and the end row, i.e. the start row and the start columns have converged to the end equivalents.
This is a lot of talking that’s difficult to visualise so let’s see a partial implementation with only the counter values and the various loops:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Metadata.W3cXsd2001;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
int counter = 1;
int startColumn = 0;
int endColumn = n - 1;
int startRow = 0;
int endRow = n - 1;
while (startColumn <= endColumn && startRow <= endRow)
{
//top row
for (int i = startColumn; i <= endColumn; i++)
{
}
//done with the row, increase the row pointer, i.e. move down in the matrix
startRow++;
//right column
for (int i = startRow; i <= endRow; i++)
{
}
//done with the column, move to the left
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
}
//move up again on the right hand side of the matrix
endRow--;
for (int i = endRow; i >= startRow; i--)
{
}
//move to the right for the next loop
startColumn++;
}
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
Those loops pave the way for us to keep the index right, i.e. that we’re in the correct cell all the time. The while loop represents the circles in the matrix and is broken when the start and end indexes of the rows and columns have converged, i.e. we have reached the final cell in the matrix.
The 4 for-loops represent the 4 directions we’re taking, as outlined above. Also notice the decreasing direction of the second two loops that we also hinted at above.
Now that we have the correct pointers we can increase the counter variable within each for-loop, that’s simple:
for (int i = startColumn; i <= endColumn; i++)
{
counter++;
}
startRow++;
for (int i = startRow; i <= endRow; i++)
{
counter++;
}
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
counter++;
}
endRow--;
for (int i = endRow; i >= startRow; i--)
{
counter++;
}
startColumn++;
We have the pointers to the cell coordinates and the integer values we want to put in them. Now we need to use those to fill in the jagged array. This is where it’s absolutely necessary to use arrays and not lists because we fill the arrays the same way as we’re traversing the matrix. Each array within temporaryArray represents a row and when we’re done with the first for-loop we’ll have the following jagged array:
1
2
3
4
x
x
x
x
x
x
x
x
x
x
x
x
…where ‘x’ means “not yet properly filled in”.
The we move on and fill in the rightmost column:
1
2
3
4
x
x
x
5
x
x
x
6
x
x
x
7
So we need to access the last spots of arrays 2, 3, and 4 of the 2-dimensional array. We could not do the same with a list, there’s no equivalent accessor to a list where we can set the value at position n, we can only add new values to end of the list. So this is the main reason why it’s better to go for an array.
Next up we’ll fill up the bottom row:
1
2
3
4
x
x
x
5
x
x
x
6
10
9
8
7
…and finally the left hand column:
1
2
3
4
12
x
x
5
11
x
x
6
10
9
8
7
We then do the same in the “inner” matrix:
1
2
3
4
12
13
14
5
11
16
15
6
10
9
8
7
Now we need to select the correct indexes for the jagged array in the 4 for-loops.
In the first loop we move from left to right, i.e. from (0, 0) to (0, 3). So the row is constant, it will be equal to startRow. The column increases from 0 to endColumn. Hence we’ll use the following accessors:
temporaryArray[startRow][i]
In the second for loop we move from (1, 3) to (3, 3). The column is equal to end column and row moves up from startRow to and including endRow. Recall the we incremented startRow by 1 after the first loop. Therefore we won’t accidentally overwrite cell (0, 3). Here’s the accessor in the second loop:
temporaryArray[i][endColumn]
The in the third loop we move to the left from (3, 2) to (3, 0) and in the fourth loop upwards from (2, 0) to (1, 0).
Here’s the full solution:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Metadata.W3cXsd2001;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
int counter = 1;
int startColumn = 0;
int endColumn = n - 1;
int startRow = 0;
int endRow = n - 1;
while (startColumn <= endColumn && startRow <= endRow)
{
for (int i = startColumn; i <= endColumn; i++)
{
temporaryArray[startRow][i] = counter;
counter++;
}
startRow++;
for (int i = startRow; i <= endRow; i++)
{
temporaryArray[i][endColumn] = counter;
counter++;
}
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
temporaryArray[endRow][i] = counter;
counter++;
}
endRow--;
for (int i = endRow; i >= startRow; i--)
{
temporaryArray[i][startColumn] = counter;
counter++;
}
startColumn++;
}
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
I think that was quite a challenging problem. Make sure you study it before your next job interview so that you can quickly present your solution and move on to the next problem.
Say you need to write a function that accepts and integer and returns its reverse. Here come a couple of examples:
Input
Output
4
4
28
82
9876
6789
-4
-4
-456
-654
-1928
-8291
So we’re not talking about some mathematical function, but more of a string-reverse. However, note that the negative sign must stay in place, so there’s a little bit of maths in there.
If that doesn’t sound like a problem that you would normally solve in a real life project then you’re probably right. I’m not even sure if there’s a legitimate business use-case for such a function. However, job interview tests often don’t revolve around real-life problems, at least not the initial ones that are meant to filter out candidates that are not a good fit for the position. It’s good to go through the most common problems so that you can breeze through them and have time over for the more difficult ones.
The C# solution is very easy in fact, and I’m sure it’s equally simple in other popular languages. Without any further due here’s one of the many possible solutions out there:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class IntReverse
{
public int ReverseInteger(int start)
{
var reverse = string.Join("", Math.Abs(start).ToString().Reverse());
return int.Parse(reverse) * Math.Sign(start);
}
}
}
Let’s see how this works.
Math.Abs(start).ToString()
The above bit takes the incoming integer, takes its absolute value and turns it to a string. Why take the absolute value? We don’t want the ‘-‘ character to end up at the end of the string, so at this point we get rid of it. So at this point we have the following strings:
Input
Output
4
“4”
28
“28”
9876
“9876”
-4
“4”
-456
“456”
-1928
“1928”
Next we call the Reverse() extension on this string. It returns an IEnumerable<char>, i.e. not the reversed string, but the constituent characters in a reversed order like here:
Input
Output
4
[‘4’]
28
[‘8’, ‘2’]
9876
[‘6’, ‘7’, ‘8’, ‘9’]
-4
[‘4’]
-456
[‘6’, ‘5’, ‘4’]
-1928
[‘8’, ‘2’, ‘9’, ‘1’]
The string.Join function takes a delimiter and joins a collection into a string using that delimiter. Since the delimiter is an empty string it means that we don’t want anything in between the joined characters. This is the current state of things at this point:
Input
Output
4
“4”
28
“82”
9876
“6789”
-4
“4”
-456
“654”
-1928
“8291”
The values in the Output column are assigned to the reverse variable. It seems we have lost the negative sign on the way, but that’s OK, we can still read it from the incoming start parameter. The Math library has a function called Sign which returns -1 for negative numbers, 0 for 0’s and +1 for positive numbers. So we parse the reverse variable into an integer and multiply it with the correctly signed 1. Hence we have the reversed integer as specified and we can return it.
Here comes a set of unit tests:
using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Algorithms.Tests
{
[TestClass]
public class IntReverseTests
{
[TestMethod]
public void ReverseIntTests()
{
IntReverse intReverse = new IntReverse();
Assert.AreEqual(4, intReverse.ReverseInteger(4));
Assert.AreEqual(28, intReverse.ReverseInteger(82));
Assert.AreEqual(9876, intReverse.ReverseInteger(6789));
Assert.AreEqual(-4, intReverse.ReverseInteger(-4));
Assert.AreEqual(-456, intReverse.ReverseInteger(-654));
Assert.AreEqual(-1928, intReverse.ReverseInteger(-8291));
}
}
}
In this post we’ll look at an often recurring dev interview question: the Fibonacci series. The series is straightforward to build. The starting 0 and 1 are given and from then on each new number is calculated by adding the previous two numbers of the series. So the third element in the series will be 0 + 1 = 1, then 1 + 1 = 2 and so on. Here’s a short example:
0
1
1
2
3
5
8
13
21
34
The problem is most often presented as follows: write a function that returns the nth element of the Fibonacci series. The function will therefore accept an integer that denotes the position in the Fibonacci array. The index can be 0 or 1 based, this should be clarified with the interviewer. In this post will go for a 0-based solution, i.e. fib(2) must return the third element in the series, i.e. 1.
In this post we’ll go through 3 solutions:
build the series in a loop until the required index has been reached
recursion
enhanced recursion
If you get this question in an interview then what they are really after is the two recursive solutions. We’ll find out why in just a bit. Here we’ll start with the easy solution that most people would think of, i.e. the iterative approach.
Let’s prepare a skeleton with the iterative implementation as it’s simple and straightforward:
using System;
using System.CodeDom;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class Fibonacci
{
public int GetElementFromFibSeries(int index)
{
return BuildSeriesWithIteration(index + 1)[index]; //or .Last() LINQ
}
private int GetFibElementWithRecursion(int index)
{
return 0;
}
private int GetFibElementWithMemoizedRecursion(int index)
{
return 0;
}
private List<int> BuildSeriesWithIteration(int howMany)
{
if (howMany == 1) return new List<int>() { 0 };
if (howMany == 2) return new List<int>() { 0, 1 };
List<int> fib = new List<int>() { 0, 1 };
for (int i = 2; i < howMany; i++)
{
fib.Add(fib[i - 1] + fib[i - 2]);
}
return fib;
}
}
}
The BuildSeriesWithIteration function accepts an integer to indicate how many elements we want. As the leading 0 and 1 are given, we just return those lists without looking any further if the required size is 1 or 2. Otherwise we iterate from 2 until the required size and fill in the return list fib with the values calculated according to the formula presented above. Finally we return the list with the series.
We call this function from GetElementFromFibSeries. Recall that the index parameter is 0-based so we add 1 to it to get the correctly sized list of Fibonacci numbers. We only need the last value of that list which can be fetched using either the index parameter or the LINQ Last() operator.
Here comes a short test suite to see if everything works as intended:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms.Tests
{
[TestClass()]
public class FibonacciTests
{
[TestMethod()]
public void BuildFibSeriesTests()
{
Fibonacci fib = new Fibonacci();
Assert.AreEqual(0, fib.GetElementFromFibSeries(0));
Assert.AreEqual(1, fib.GetElementFromFibSeries(1));
Assert.AreEqual(3, fib.GetElementFromFibSeries(4));
Assert.AreEqual(8, fib.GetElementFromFibSeries(6));
Assert.AreEqual(34, fib.GetElementFromFibSeries(9));
Assert.AreEqual(832040, fib.GetElementFromFibSeries(30));
}
}
}
Run the tests, they should pass.
Let’s now turn our attention to the recursive solution:
What is this?! That’s something that you should memorise for your job interview and not really think too much about what’s happening. This solution is very short and you’ll find a couple of variations of it by a simple Google search. We’ll give it a try anyway to see if we understand what’s going on.
So this is a recursive function which calls itself in twice in the same expression. Mentally it’s not easy to follow how the function is called, what is returned , when it stops and why it works. The key to keep in mind is that the ultimate return value is in the if block, that’s where the recursion is broken. Recursion is broken if the index is less than 2. If the index is less than 2 then we return the index itself. This means that at the end of the day we ultimately only return 0 or 1 from this function. The 0’s and 1’s are then added in…
Run the test and you’ll get the following console output:
Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
As stated above the only real return value from this function is 1 and it is returned successively as the index parameter decreases with each iteration and reaches the value of 1. The 1’s are then added. Note how many times the recursive function was called with the argument of 1: 3 times, so we’ll end up with 1 + 1 + 1 = 3, which is the correct solution. Hmm, we’re onto something. Note that the function was called a total of 9 times for the incoming index 4.
Calling recursive function with 6
Calling recursive function with 5
Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Good grief, that’s 25 calls altogether and the function returned 1 exactly 8 times. So it looks like we found the essence of the function. Let’s just run the following unit test to make sure it’s not a coincidence:
I won’t paste the console output but the function was called 109 times in total, with index set to 1 exactly 34 times.
Now answer honestly: could you have come up with the recursive solution on your own without having seen it before in a stressful interview setting? For my part the answer is a resounding no. If you could do it then hats off to you, congratulations, you must be a genius. For everyone else just memorise it, it’s really not much. Also remember that we ultimately sum up a series of 1’s.
We’re not done yet. You see, this question leads to other areas in computing and algorithms that can be discussed, that’s why interviewers like it. We’ve already discussed recursion which is not exactly an overused language feature so some candidates might not even know that it exists. Another point to discuss is algorithm performance. Let’s summarise how many times the recursive function was called for each input:
Index
Number of calls
4
9
6
25
9
109
I also executed the last unit test with index 30 but Visual Studio truncated the console output. We can conclude that with index 30 the function was probably called A LOT of times.
At this point the interviewer will ask you how efficient this algorithm is. Here (s)he wants to know if you’re familiar with (run)time complexity and the Big O notation. We can conclude based on the tabular data above that with each increase in the input, i.e. an increase in the index parameter, we see a significant increase in runtime as the recursive function is called over and over again multiple times. The increase in runtime increases exponentially with every increase of the input parameter. We call that exponential runtime and it’s denoted as follows using the Big O notation:
O(2^n)
It’s pronounced “o to the 2 to the n”. Normally we want to avoid algorithms that show this kind of behaviour. Exponential runtime is so inefficient that it should only be used as a last resort, if there’s really nothing else we can do to solve a problem. The iterative solution in BuildSeriesWithIteration had a linear runtime, which is denoted as follows:
O(n)
It’s pronounced “o to the n”. Why is it linear? It’s because of the for-loop. For each increase in the index parameter we must go one more step in the loop to build the Fibonacci series.
Note that if the index is 0 or 1 then we don’t even enter the loop but return immediately. For those two cases the function has a constant runtime denoted like this:
O(1)
…, i.e. “o to the one”. This means that no matter what index is, the algorithm will show the exact same efficiency, there’s no increase in processing power. However, the iterative function overall is O(n) because if different sections of a function display different runtimes then the higher order runtime wins. In this case O(n) > O(1), so overall we land at O(n).
Similarly the recursive function is O(1) if index is 0 or 1 but that’s quickly outranked by the exponential runtime. Therefore its overall runtime complexity is exponential.
We’re still not done. The next step is whether we can improve the performance of the recursive function. When you’re asked this question then you must be ready to respond with a resounding yes, using a technique called
memoization.
Yes, memoization and not memoRization. It’s an optimisation technique the is based upon the idea that if we feed the same input value(s) to a function then it should return the same result over and over again. It’s similar to caching in a way. If you take a look at the various console outputs above you’ll see that the recursive function calls itself with the same input argument several times. Our goal with memoization is to make the function remember the return value for a set of parameters. This way we can avoid a lot of round trips in the recursive function as the results can be pulled from this “cache” instead of going through all those iterative function calls.
The function returns an integer and accepts an integer. That sounds like our in-memory cache can be represented by a Map data structure, i.e. a Dictionary in .NET, where the key and the value are both integers. The key will be the index and the value will represent the calculated value.
Here’s the enhanced recursive function:
using System;
using System.CodeDom;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class Fibonacci
{
private readonly Dictionary<int, int> memo;
public Fibonacci()
{
memo = new Dictionary<int, int>();
}
public int GetElementFromFibSeries(int index)
{
//return BuildSeriesWithIteration(index + 1)[index]; //or .Last() LINQ
//return GetFibElementWithRecursion(index);
return GetFibElementWithMemoizedRecursion(index);
}
private int GetFibElementWithMemoizedRecursion(int index)
{
if (memo.ContainsKey(index))
{
Console.WriteLine(string.Format("Pulling solution of index {0} from the memo", index));
return memo[index];
}
else
{
Console.WriteLine(string.Format("Index {0} not yet in memo", index));
int solution;
if (index < 2)
{
solution = index;
}
else
{
solution = GetFibElementWithMemoizedRecursion(index - 1) + GetFibElementWithMemoizedRecursion(index - 2);
}
memo[index] = solution;
return solution;
}
}
private int GetFibElementWithMemoizedRecursion(int index)
{
//truncated
}
private List<int> BuildSeriesWithIteration(int howMany)
{
//truncated
}
}
}
If memo contains the index key then we immediately return the value by that index. Otherwise we calculate the solution and put it into the map. I left a couple of console logging functions to check how many times we call the function.
Index 9 not yet in memo
Index 8 not yet in memo
Index 7 not yet in memo
Index 6 not yet in memo
Index 5 not yet in memo
Index 4 not yet in memo
Index 3 not yet in memo
Index 2 not yet in memo
Index 1 not yet in memo
Index 0 not yet in memo
Pulling solution of index 1 from the memo
Pulling solution of index 2 from the memo
Pulling solution of index 3 from the memo
Pulling solution of index 4 from the memo
Pulling solution of index 5 from the memo
Pulling solution of index 6 from the memo
Pulling solution of index 7 from the memo
That’s 17 calls instead of 109 for index 9. That’s quite an acceptable improvement.
Many technical interview questions you encounter don’t reflect real life problems that have some business value or use-case in commercial software. It’s very unlikely that you ever have to implement the Fibonacci series using recursion in your project. However, these interview questions are a great way to test your basic training and eliminate candidates that lack knowledge in data structures, algorithms and basic language features. See how many areas we can cover with just this single question?
collections
iteration
recursion
runtime complexity
memoization
big O notation
If you get this question in your next job interview then you can easily spend an hour just talking about these concepts in computing based on it. You will score high and you can start getting ready for the next round 🙂
Here comes another classic interview question: write a function that accepts a collection and an integer. The function must divide the incoming collection up into individual collections of the size specified by the integer parameter. These individual collections can be called batches, groups or chunks and probably other things as well.
Let’s take the following collection of integers as an example:
[43, 65, 23, 56, 76, 454, 76, 54, 987]
If the incoming size integer is 3 then we want to end up with the following chunks:
[[43, 65, 23], [56, 76, 454], [76, 54, 987]]
…, i.e. a list of list elements where each chunk will be of size 3. So the size parameter means that we want to have at most 3 elements in each chunk, not that we want to have 3 chunks altogether.
If the size parameter is 2 then we want to end up with the following chunks:
[[43, 65], [23, 56], [76, 454], [76, 54], [987]]
We’ve got 5 chunks: 4 * 2 and the last chunk of size 1 as the 5th element in the list. Since 9 is not divisible by 2 we end up with a smaller chunk as the last element in the resulting list. That will always be the case if the total size of the collection parameter is not divisible by the size parameter. We just add the remainder into the last array.
In this post we’ll go through 4 different solutions. As expected, there are probably many more, but these should be enough in an interview setting. These classic interview questions are usually not difficult and you can most likely figure them out yourself based on your basic programming 101 skills. However, if you have never seen them then you might spend too much time on them and won’t have enough time over for the harder problems. So it’s good to be prepared and once you see one of these problems then you can just breeze through it quickly.
The 4 solutions presented here are based on the following:
iterating through the collection and building the chunks using a temporary list
chunking up the collection into ranges
using LINQ operators
using LINQ operators and the yield keyword
So if your interviewer says please don’t use LINQ, only bare-bones language constructs to test your basic training then you still have a couple of options.
Let’s start with a skeleton:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class Chunk
{
public IEnumerable<IEnumerable<T>> BuildChunks<T>(List<T> fullList, int batchSize)
{
return BuildChunksWithIteration(fullList, batchSize);
}
private IEnumerable<IEnumerable<T>> BuildChunksWithLinq<T>(List<T> fullList, int batchSize)
{
return null;
}
private IEnumerable<IEnumerable<T>> BuildChunksWithLinqAndYield<T>(List<T> fullList, int batchSize)
{
return null;
}
private IEnumerable<IEnumerable<T>> BuildChunksWithIteration<T>(List<T> fullList, int batchSize)
{
return null;
}
private IEnumerable<IEnumerable<T>> BuildChunksWithRange<T>(List<T> fullList, int batchSize)
{
return null;
}
}
}
The private function names will give you a hint on which of the 4 solutions they represent.
We also add a couple of unit tests that are based on the same collection of 9 integers that we saw above:
Let’s start with the iterative solution, i.e. BuildChunksWithIteration:
private IEnumerable<IEnumerable<T>> BuildChunksWithIteration<T>(List<T> fullList, int batchSize)
{
var chunkedList = new List<List<T>>();
var temporary = new List<T>();
for (int i = 0; i < fullList.Count; i++)
{
var e = fullList[i];
if (temporary.Count < batchSize)
{
temporary.Add(e);
}
else
{
chunkedList.Add(temporary);
temporary = new List<T>() { e };
}
if (i == fullList.Count - 1)
{
chunkedList.Add(temporary);
}
}
return chunkedList;
}
We initialise the return list and a temporary list. We then start the iteration in a classic for-loop. In the first if-block we look at the current value in the iteration and see if the temporary array is smaller than the batch size. If that’s the case then we add element to the temporary list. Otherwise we add the temporary list to the return list and re-instantiate it to a new list. We also add the current element to the newly built temporary list so that it doesn’t get lost in the loop.
The last if-statement…
if (i == fullList.Count – 1)
…checks if we have reached the end of the source list. If that’s the case then we add the most recent temporary list to the return list. This will ensure that the very last batch is also added to the final collection before finishing the loop even if its size is smaller than the required size.
Run the unit tests, they should all pass.
Next up is the range-based solution:
private IEnumerable<IEnumerable<T>> BuildChunksWithRange<T>(List<T> fullList, int batchSize)
{
List<List<T>> chunkedList = new List<List<T>>();
int index = 0;
while (index < fullList.Count)
{
int rest = fullList.Count - index;
if (rest >= batchSize)
{
chunkedList.Add(fullList.GetRange(index, batchSize));
}
else
{
chunkedList.Add(fullList.GetRange(index, rest));
}
index += batchSize;
}
return chunkedList;
}
We iterate through the collection in a while loop using the index variable which was initialised to 0. First we calculate the rest, i.e. the portion of the incoming collection that we haven’t chunked up yet. In the first iteration it will be 9 in our example as the list size is 9 and index is 0. The if-condition checks if the rest is at least as large as the required batch size. If that’s the case then we add a list to the return list using the GetRange function that’s available on lists. It takes a start index and a count variable. In the first iteration we want to get the range starting from position 0 of the source array and take 3 elements from 0. That will be the first chunk in the return list.
Otherwise if the rest is smaller than the batch size, then we fetch the rest of the source collection and add it to the return list. Finally we increment the index by the batch size.
Therefore in the second iteration the rest variable will be 9 – 3, i.e. 6 and we want to get the range from and including index 3 – which will be 4th element in a 0-based index – plus the batch size 3. We keep iterating through the source collection like that until index is larger than or equal to the size of the source collection, i.e. we have covered the source collection in its entirety.
Hook up the function from the main function:
public IEnumerable<IEnumerable<T>> BuildChunks<T>(List<T> fullList, int batchSize)
{
return BuildChunksWithRange(fullList, batchSize);
//return BuildChunksWithIteration(fullList, batchSize);
}
Re-run the unit tests and they will still pass.
Let’s now look at the solution with a couple of LINQ operators:
If you’re not sure how they are used then get more info on them from the linked blog posts. They are often used together for paging purposes and are similar to the GetRange function. However, with Take we don’t need to worry about an index-out-of-range exception, it will just take the available amount of elements from the requested range:
private IEnumerable<IEnumerable<T>> BuildChunksWithLinq<T>(List<T> fullList, int batchSize)
{
int total = 0;
var chunkedList = new List<List<T>>();
while (total < fullList.Count)
{
var chunk = fullList.Skip(total).Take(batchSize);
chunkedList.Add(chunk.ToList());
total += batchSize;
}
return chunkedList;
}
You see that the loop is very similar to the GetRange-based solution, but we don’t need to calculate the rest, we can simply call Skip and Take and they are clever enough to figure out what we want.
Hook up the function list before:
public IEnumerable<IEnumerable<T>> BuildChunks<T>(List<T> fullList, int batchSize)
{
//return BuildChunksWithRange(fullList, batchSize);
//return BuildChunksWithIteration(fullList, batchSize);
return BuildChunksWithLinq(fullList, batchSize);
}
The unit tests will still pass.
Finally we have the same LINQ-based solution but together with the yieldkeyword. This one can be a bit difficult to wrap your head around. It is similar to a recursive solution and is best demonstrated by various examples:
private IEnumerable<IEnumerable<T>> BuildChunksWithLinqAndYield<T>(List<T> fullList, int batchSize)
{
int total = 0;
while (total < fullList.Count)
{
yield return fullList.Skip(total).Take(batchSize);
total += batchSize;
}
}
This is the short-hand form of BuildChunksWithLinq.
Call this function from the main function and the unit tests will still all pass.
In this post we’ll go through a classic interview question for developers: the FizzBuzz problem.
You are asked to write a function that accepts an integer. The function must implement a loop from 1 to the integer that was passed into the function. In the loop the function must print the following to the command window:
if the number is divisible by 3 then print “fizz”
if the number is divisible by 5 then print “buzz”
if the number is divisible by both 5 and 3 then print “fizzbuzz”
otherwise just print the number itself
We apply only one of these rules in the loop. E.g. 15 is divisible by both so we only print “fizzbuzz”, not “fizz”, then “buzz” and finally “fizzbuzz”.
The problem is simple to solve. However, if you have never encountered it before then it might turn into a tricky one in a stressful interview situation, especially with someone watching what you’re doing. So make sure you remember the below guidelines so that you’ll have more time over for the more complex tasks.
The solution is based on the relatively rarely used % operator, called the modulus. It returns the remainder of a division: e.g. 5 % 2 = 1 since we can fit 2 twice into 5 and we have a remainder of 1. Likewise 15 % 3 = 0 because we can fit 3 into 15 five times with nothing remaining.
We’ll have a couple of if-statements in the loop to check for the modulus. There are couple of details to watch out for:
check first if the integer is divisible by 3 and 5
use else-if-statements for the other conditions so that only one conditional block is carried out, i.e. the first one that meets the condition(s)
Why check for divisibility by 3 and 5 before anything else? Say that we get to 15 in the loop. If our first condition is to only check for divisibility by 3 then we’ll print “fizz” and that’s not what we want.
Why use else-if statements? If we have 3 “normal” if-statements then all of them will be evaluated and we don’t want that either. Again, taking 15 as an example, it is divisible by 3 which will print “fizz”, it is also divisible by 5 which will print “buzz” and then we also print “fizzbuzz” since 15 also fulfils the third condition.
Here’s the solution in C# code, but it can easily be ported to other popular OOP languages:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class FizzBuzz
{
public void RunFizzBuzz(int until)
{
for (int i = 1; i <= until; i++)
{
if (i % 3 == 0 && i % 5 == 0)
{
Console.WriteLine("fizzbuzz");
}
else if (i % 3 == 0)
{
Console.WriteLine("fizz");
}
else if (i % 5 == 0)
{
Console.WriteLine("buzz");
}
else
{
Console.WriteLine(i);
}
}
}
}
}
…and here’s a unit test to see if it works:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace Algorithms.Tests
{
[TestClass()]
public class FizzBuzzTests
{
[TestMethod()]
public void RunFizzBuzzTests()
{
FizzBuzz fb = new FizzBuzz();
StringWriter output = new StringWriter();
Console.SetOut(output);
fb.RunFizzBuzz(20);
string console = output.ToString();
Assert.AreEqual(string.Format("1{0}2{0}fizz{0}4{0}buzz{0}fizz{0}7{0}8{0}fizz{0}buzz{0}11{0}fizz{0}13{0}14{0}fizzbuzz{0}16{0}17{0}fizz{0}19{0}buzz{0}", Environment.NewLine), console);
}
}
}
Here comes another classic coding question that you might come across during an interview. Write a function that accepts a string and returns a boolean. The function must determine if the string is a palindrome. A string is a palindrome if it has the same value in both directions: forward and backward. Examples:
abba
qwertrewq
1234321
In this post we’ll look at two different solutions, but there are certainly others. Also, we’ll implement case-sensitive solutions, i.e. the following will return false:
aBba
qWertrewq
The first solution is based on looping through the characters of the string. In each iteration we compare the characters on two extremes from the midpoint. The midpoint is simply the string length divided by 2. Say we have the following string of length 8 chars:
q
w
e
r
r
e
w
q
The midpoint of this string is 4. We start by comparing the char at position 0 with the char at position length - 1, i.e. ‘q’ with ‘q’. Then we continue with position 1 and position length - 2, that is ‘w’ and ‘w’. We continue until we reach the midpoint, i.e. position 4 and compare ‘r’ with ‘r’. This is the end of the loop and the function returns true.
What if we have an odd number of characters in the string? The same algorithm will still work, here’s an example:
q
w
e
r
e
w
q
The midpoint is 3 in this case: 7 / 2 = 3.5 and .NET will turn it into 3 when boxing it into an integer. So we compare ‘q’ with ‘q’, then ‘w’ with ‘w’ and finally ‘e’ with ‘e’. We don’t need to worry about ‘r’, the char in the very middle is always symmetrical with itself.
Here’s all of that in code form:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class Palindrome
{
public bool IsPalindrome(string str)
{
return IsPalindromeWithLoop(str);
}
private bool IsPalindromeWithLoop(string str)
{
for (int i = 0; i < str.Length / 2; i++)
{
if (str[i] != str[str.Length - i - 1])
{
return false;
}
}
return true;
}
}
}
…and here come a couple of unit tests:
using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Algorithms.Tests
{
[TestClass]
public class PalindromeTests
{
[TestMethod]
public void IsPalindromeTest()
{
Palindrome palindrome = new Palindrome();
Assert.IsTrue(palindrome.IsPalindrome("abba"));
Assert.IsTrue(palindrome.IsPalindrome("qwewq"));
Assert.IsTrue(palindrome.IsPalindrome("12344321"));
Assert.IsFalse(palindrome.IsPalindrome(" hehe "));
Assert.IsFalse(palindrome.IsPalindrome("Hello olleh")); //case sensitive!!
Assert.IsTrue(palindrome.IsPalindrome(" abba "));
}
}
}
The second solution is based on a simple string comparison. We take the incoming string, reverse it and compare the original with the reversed string:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class Palindrome
{
public bool IsPalindrome(string str)
{
return IsPalindromeWithReverse(str);
//return IsPalindromeWithLoop(str);
}
private bool IsPalindromeWithReverse(string str)
{
if (str == null) return false;
var reverse = string.Join("", str.Reverse());
return str == reverse;
}
}
}
The Reverse() extension method creates an IEnumerable of chars, i.e. not a string. We take that char collection and join its elements into a string. The empty string in the string.Join function is the delimiter, meaning that we don’t want to put anything in between the chars when joining them. Finally we compare the two strings as the return value of the function.
The generic list (https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=netcore-3.1) is probably the most often used collection type in C#. It’s easy to use, it’s type safe, it offers a lot of manipulation methods and a myriad of LINQ functions for searching, sorting and much, much more. If you need a collection where you can add, remove, insert and set elements at an index then the List is your go-to collection type.
However, imagine that you’re sitting in a job interview and your interviewer tells you to build your own list-type collection without using any of the built-in collection types. Say you’re only allowed to use bare-bones language constructs from your C# 101 intro class. In this case what the interviewer really wants to know is how familiar you are with arrays.
Normally you wouldn’t do this in a real job assignment but quite many interviews revolve around data structures where they want to find out if you really know the ins and the outs of things like arrays, linked lists, queues, stacks etc.
Arrays and lists
What’s the difference between lists and arrays anyway? An array is a basic (primitive) data structure in .NET and many other computing languages to hold x number of contiguous data points such as here:
23
76
90
53
149
null
null
null
Array with capacity 8 and size 5
This is an integer array with a capacity of 8 and a size of 5. This distinction is important. The array was declared as int[8] where 8 is the fixed size of the array. We must provide the array capacity, we cannot just write arr = new int[], we’ll get a compilation error in Java and C#. It would work in JavaScript though, like let arr = [], but arrays in JS are more like lists with ready-made utility functions such as pop, push, unshift etc.. In this post we’ll stick to arrays as they are implemented in C#.
Also, this capacity cannot be changed later on, it’s constant. Therefore expanding and shrinking the array is not possible just like that, out of the box. At this stage the array is empty, i.e. its size is 0 because we haven’t set any of the values in the various slots. We can set the value of each slot using a 0-based index, like arr[4] = 149 which will set slot #4 to 149 just like in the example above. In an array we can set the slots in any order, we don’t need to go in any particular order, like arr[0] = 23, arr[1] = 76, arr[2]=90 etc. We can have an array such as this one:
23
76
null
53
null
null
376
null
A list on the other hand is a collection API that uses an array in the background for its work. It’s a utility or convenience class that makes working with arrays easier. It wraps an array to hide the implementation details from you so that you can conveniently call myList.Add(newItem), myList.Clear(), myList.RemoveAt(5) etc. without having to worry about stuff like copying and resizing an array. A List is also called a dynamic array which is a deceptive name, but there you go.
Implementation
The topic of this post is to come up with a possible implementation of a simple custom generic list using an array as its backup store. Let’s start with a skeleton. This skeleton also shows the implementation of the simplest methods:
using System;
using System.Collections.Generic;
using System.Data;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class RollYourOwnList<T>
{
private T[] data;
private int size = 0;
private int capacity;
public RollYourOwnList(int initialCapacity = 8)
{
if (initialCapacity < 1) initialCapacity = 1;
this.capacity = initialCapacity;
data = new T[initialCapacity];
}
public int Size { get { return size; } }
public bool IsEmpty { get { return size == 0; } }
public T GetAt(int index)
{
ThrowIfIndexOutOfRange(index);
return data[index];
}
public void SetAt(T newElement, int index)
{
ThrowIfIndexOutOfRange(index);
data[index] = newElement;
}
public void InsertAt(T newElement, int index)
{
ThrowIfIndexOutOfRange(index);
//to be implemented...
}
public void DeleteAt(int index)
{
ThrowIfIndexOutOfRange(index);
//to be implemented
}
public void Add(T newElement)
{
//to be implemented
}
public bool Contains(T value)
{
//to be implemented
return false;
}
public void Clear()
{
//to be implemented
}
private void Resize()
{
//to be implemented
}
private void ThrowIfIndexOutOfRange(int index)
{
if (index > size - 1 || index < 0)
{
throw new ArgumentOutOfRangeException(string.Format("The current size of the array is {0}", size));
}
}
}
}
The class is generic and has three backing fields:
data: the array that will hold the values of the list
size: the number of initialised slots in the array
capacity: the total number of available slots in the array
We can conclude that size is less than or equal to the array capacity. The list is full once size = capacity. The constructor lets us set an initial capacity which defaults to 8. Why default to 8? I don’t know really. I remember reading about it somewhere, that the actual .NET List implementation sets the initial capacity to 8 but don’t take my word for it, it could have been a dream or something. If you know more then feel free to write in the comment section.
So now we have a backing array with available slots set by the initial capacity. The size variable is of course 0 to begin with. The Size and IsEmpty properties should be fairly easy to read: they return the actual size and whether the array size is 0.
The ThrowIfIndexOutOfRange function is called from various places in the code. It throws an ArgumentOutOfRangeException if the user tries to access a slot in the array that has not been initialised. We basically want to avoid a data store where we have nulls or other default values somewhere in the middle.
The GetAt and SetAt functions do exactly what you think they do: they access the internal array using the 0-based index and square brackets to either return the current value or rewrite an existing one.
Next, let’s look at the InsertAt function. It accepts the element to be added and the position index. This is not the same as SetAt. Here we want to make room for a new item in the array without overwriting any existing values. What we need to do is shift the range of values in the array from and including the requested index so that the position at index becomes free. Then we can set the value of that new, empty slot. However, before the move can happen, we also need to check whether we have reached the max capacity, in which case we must extend the array.
Say that we have the following array:
54
34
25
77
…and we want to insert a new integer at position 2, i.e. that is currently occupied by the number 25.
So at first we check if we have room for one more. We clearly don’t so we need to resize the array. This is simply done by creating a new, bigger array and copying the existing values from the existing array into the same slots where they were before:
54
34
25
77
How much bigger should the new array be? A good rule of thumb is to double its current capacity, so in this example the new capacity is 8. You see that copying and shifting values is a relatively time-consuming operation so we want to economise on that.
The next step is to shift the values 25 and 77, i.e. everything from index 2 until the size of the array to the right:
54
34
25
77
Now we have an empty slot at position 2 without any data loss. We can now set position 2 of the array to the required integer, say 165:
54
34
165
25
77


Here’s the Resize() method:
private void Resize()
{
T[] resized = new T[capacity * 2];
for (int i = 0; i < capacity; i++)
{
resized[i] = data[i];
}
data = resized;
capacity = capacity * 2;
}
We create the larger array and make data point to it. We also make sure that capacity reflects the new, extended capacity.
Here’s the implemented InsertAt function:
public void InsertAt(T newElement, int index)
{
ThrowIfIndexOutOfRange(index);
if (size == capacity)
{
Resize();
}
for (int i = size; i > index; i--)
{
data[i] = data[i - 1];
}
data[index] = newElement;
size++;
}
As stated above: check if we need to resize the array, then shift the necessary range to the right and insert the new element. We also increase the size by 1 of course. Note that the shifting loop starts from the right, i.e. from size and moves each element one slot to the right. In our example we move 77 and then 25. If we started the shifting from the left, i.e. from index then we would overwrite the value in the position i + 1. In our example we would move 25 to the position of 77 and 77 would disappear, that’s clearly not what we want.
The DeleteAt function is also based on shifting values, but we don’t need to create any empty slot for a new element. It’s enough to shift the values by one from right to left. Here’s our starting array:
54
34
165
25
77


Say we want to delete 34, i.e. the element at position 1. Then we first move 165 to the left, then 25 and 77. If we implement this loop up to this point only then our array will in fact look like this:
54
165
25
77
77


Why 77 twice? We don’t really move the values of the array, we rather copy them to a different position. In this loop the final operation will be to copy 77 to position 3 from 4, but the value in position 4 is still available, its value is not overwritten by anything. So what can we do?
We can overwrite its value by the default of the T data type: null, 0, false etc. Also, we must make sure that size is decremented by one so that loops traversing the array disregard that default value. So we’ll end up with this array:
54
165
25
77
0

…since the default value of integers is 0. C# has a neat shorthand to get the default value of a type which we’ll use in the implementation:
public void DeleteAt(int index)
{
ThrowIfIndexOutOfRange(index);
for (int i = index; i < size - 1; i++)
{
data[i] = data[i + 1];
}
data[size - 1] = default(T);
size--;
}
The Add function adds a new element to the end (tail) of the array, i.e. at the size position. Remember that array positions are 0 based and sizes start with one. This is a lovely source of off-by-one and out-of-range errors that every normal developer has experienced a couple of times. Again, we need to resize the array before trying to add a new element to end of the array:
public void Add(T newElement)
{
if (size == capacity)
{
Resize();
}
data[size] = newElement;
size++;
}
The Contains and Clear functions are straightforward. In the former we iterate through the array and if we find a value that’s equal to the search term then we return true. In the latter we simply recreate the backing array and set the size to 0:
public bool Contains(T value)
{
for (int i = 0; i < size; i++)
{
T currentValue = data[i];
if (currentValue.Equals(value))
{
return true;
}
}
return false;
}
public void Clear()
{
data = new T[capacity];
size = 0;
}
That’s it really. We could of course implement a lot of other functions on our custom list, such as AddRange but the ones above are probably the most commonly used besides LINQ functions. Also, if you think of the above assignment in an interview setting you probably won’t have time to implement anything else – unless it’s a day-long hackathon 🙂
Finally let me give you a set of unit tests that test the main functions of our own beautiful dynamic array:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms.Tests
{
[TestClass()]
public class RollYourOwnListTests
{
[TestMethod()]
public void RollYourOwnListSetupTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>();
Assert.AreEqual(0, intList.Size);
Assert.IsTrue(intList.IsEmpty);
intList = new RollYourOwnList<int>(16);
Assert.AreEqual(0, intList.Size);
Assert.IsTrue(intList.IsEmpty);
}
[TestMethod()]
public void RollYourOwnListAddTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
Assert.AreEqual(1, intList.Size);
Assert.IsFalse(intList.IsEmpty);
intList.Add(35);
Assert.AreEqual(2, intList.Size);
Assert.IsFalse(intList.IsEmpty);
intList.Add(29);
Assert.AreEqual(3, intList.Size);
intList.Add(16);
Assert.AreEqual(4, intList.Size);
intList.Add(48);
Assert.AreEqual(5, intList.Size);
intList.Add(90);
Assert.AreEqual(6, intList.Size);
Assert.AreEqual(13, intList.GetAt(0));
Assert.AreEqual(35, intList.GetAt(1));
Assert.AreEqual(29, intList.GetAt(2));
Assert.AreEqual(16, intList.GetAt(3));
Assert.AreEqual(48, intList.GetAt(4));
Assert.AreEqual(90, intList.GetAt(5));
intList.SetAt(1000, 2);
Assert.AreEqual(1000, intList.GetAt(2));
intList.SetAt(1001, 0);
Assert.AreEqual(1001, intList.GetAt(0));
intList.SetAt(1002, 5);
Assert.AreEqual(1002, intList.GetAt(5));
}
[TestMethod()]
public void RollYourOwnListInsertTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.InsertAt(24, 0);
intList.InsertAt(48, 1);
Assert.AreEqual(3, intList.Size);
intList.InsertAt(87, 2);
Assert.AreEqual(4, intList.Size);
Assert.AreEqual(24, intList.GetAt(0));
Assert.AreEqual(48, intList.GetAt(1));
Assert.AreEqual(87, intList.GetAt(2));
Assert.AreEqual(13, intList.GetAt(3));
}
[TestMethod()]
public void RollYourOwnListDeleteTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.DeleteAt(0);
Assert.AreEqual(0, intList.Size);
Assert.IsTrue(intList.IsEmpty);
intList.Add(85);
intList.Add(43);
intList.Add(8643);
intList.Add(90);
intList.Add(1000);
intList.Add(1200);
Assert.AreEqual(6, intList.Size);
intList.DeleteAt(5);
Assert.AreEqual(5, intList.Size);
intList.DeleteAt(0);
Assert.AreEqual(4, intList.Size);
intList.DeleteAt(2);
Assert.AreEqual(3, intList.Size);
Assert.AreEqual(43, intList.GetAt(0));
Assert.AreEqual(8643, intList.GetAt(1));
Assert.AreEqual(1000, intList.GetAt(2));
}
[TestMethod()]
public void RollYourOwnListClearTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(65);
intList.Add(73);
intList.Add(5678);
intList.Add(987);
intList.Clear();
Assert.AreEqual(0, intList.Size);
Assert.IsTrue(intList.IsEmpty);
}
[TestMethod()]
public void RollYourOwnListContainsTests()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(65);
intList.Add(73);
intList.Add(5678);
Assert.IsTrue(intList.Contains(73));
Assert.IsTrue(intList.Contains(65));
Assert.IsTrue(intList.Contains(13));
Assert.IsTrue(intList.Contains(5678));
Assert.IsFalse(intList.Contains(1001));
}
[TestMethod()]
[ExpectedException(typeof(ArgumentOutOfRangeException))]
public void ThrowExceptionIfGettingAtInvalidIndex()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(35);
intList.Add(29);
intList.GetAt(3);
}
[TestMethod()]
[ExpectedException(typeof(ArgumentOutOfRangeException))]
public void ThrowExceptionIfSettingAtInvalidIndex()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(35);
intList.Add(29);
intList.SetAt(45, 3);
}
[TestMethod()]
[ExpectedException(typeof(ArgumentOutOfRangeException))]
public void ThrowExceptionIfInsertingAtInvalidIndex()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(35);
intList.Add(29);
intList.InsertAt(45, 3);
}
[TestMethod()]
[ExpectedException(typeof(ArgumentOutOfRangeException))]
public void ThrowExceptionIfDeletinggAtInvalidIndex()
{
RollYourOwnList<int> intList = new RollYourOwnList<int>(2);
intList.Add(13);
intList.Add(35);
intList.Add(29);
intList.DeleteAt(3);
}
}
}
Exercises in .NET with Andras Nemes 