I had a coding interview yesterday, for the first time in a long time, I let my nerves get the better of me, and when presented with an opportunity to code a solution, I wiffed on a simple problem, and frankly, couldn’t leave it alone, so when I got home, I had to solve it.
The request is simple, find the longest sequence of ascending numbers from an array, and return that sequence. It’s essentially a test to see if you understand iteration, arrays, and can write logic that constructs and compares sequences. Here’s the solution, I had come up with, (without the corrections outlined below):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public string GetLongestAscendingSequence(int[] values) { var lastInt = 0; IList<int[]> collection = new List<int[]>(); var cList = new List<int>(); for (var i = 0; i < values.Length; i++) { var curInt = values[i]; if (i == 0) { // for the first value, we just start the first collection. lastInt = curInt; cList.Add(curInt); } else { // all subsequent values we check if they are less than the previous if (curInt < lastInt) { //if the value is lower, add the current list of values to our collection collection.Add(cList.ToArray()); cList.Clear(); cList.Add(curInt); } else { cList.Add(curInt); } lastInt = curInt; } if (i == values.Length - 1) collection.Add(cList.ToArray()); } var c1 = collection.OrderByDescending(c => c.Length).FirstOrDefault(); return string.Join(",", c1); } |
Essentially, the code reads the array from left to right, building a new list every time it encounters a value that is less than the previous. Then, looking at the entire collection of arrays, it’s easy to sort the collection, and grab the first longest sequence.
The Corrections
The gotcha is that the operator is wrong, and the difference in functionality could be easily overlooked.
Consider this sequence: 1,4,6,2,4,0,1,1,9,7
In this case, when using the less than operator, the sequence returned will be 0,1,1,9 as its the longest consecutive sequence of non-decreasing numbers. Therefore, if we only want the longest consecutive sequence of ascending integers, line 18 is incorrect, and should actually be:
|
18 |
if (curInt <= lastInt) |
I’ll also note that my return statement could throw an exception because c1 could be null because I’m using FirstOrDefault(), so a simple null check can prevent that error:
|
35 36 |
//if null, return an empty string. return c1 != null ? string.Join(",", c1) : string.Empty; |
Additional reading..
Finally, I did a little more research (google) on the challenge, and there’s a number of articles and publications that outline the problem, including a free ebook “Fundamentals of Computer Programming with C#” by Svetlin Nakov and Veselin Kolev. see exercise # 5 on page 257 if your interested..