### Description

I am not well trained into solving algorithms but from time to time this topic raises my interest and I find my self drawn into wanting to understand the underlying logic. I recently found a problem that I found to interresting to solve, it’s a Microsoft engineer interviewing question and I followed along the question and the solution and I might say the following:

- I am a bit disappointing that the interviewer was only focused on having the problem solved in his own way
- The solution is not the best

The problem to solve was:

Given a list of integers L and a number K, write a function to partition L into elements that are <K, =K, >K. There is no need for the partions to be sorted, so a sorting algorithm is out of question because it’s not efficient in this case.

E.G.

Given a list 4 5 3 2 1 0 and K = 3 we need to rearrange the list L to beÂ 2 1 0 3 4 5 (more or less. Important is that 3 is in the middle, smaller values on the left, higher values on the right).

### Classic Solution

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 |
static void PartitionKBasedMicrosoftSolving(int[] array, int k) { void Swap(ref int[] arr, int index1, int index2) { int swap = arr[index2]; arr[index2] = arr[index1]; arr[index1] = swap; } int mid = 0; int s = 0; int l = array.Length - 1; while (mid < l) { if (array[mid] < k) { Swap(ref array, s, mid); s++; mid++; } else if (array[mid] >= k) { Swap(ref array, l, mid); l--; } else { mid++; } } } |

### My Simplified approach

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 |
static void PartitionKBasedCustom(int[] array, int k) { void Swap(ref int[] arr, int index1, int index2) { int swap = arr[index2]; arr[index2] = arr[index1]; arr[index1] = swap; } //4 5 3 2 1 2 = 1 //2 5 3 2 1 4 = 2 //2 1 3 2 5 4 = 3 //2 1 2 3 5 4 = 4 int mid = array.Length / 2; for (int i = 0, j = array.Length - 1; i < array.Length - mid && j >= mid; i++, j--) { if (array[i] > array[j]) { Swap(ref array, i, j); } } }; |

To understand the microsoft interview solution you can follow the link: https://www.youtube.com/watch?v=UaI3WeesCoE&list=RDCMUCNc-Wa_ZNBAGzFkYbAHw9eg&start_radio=1&t=2433

What I did is to write in code what my brain did when solving this in my head:

- iterate the list from left to mid, and from right to mid
- when an element on the left is greater then an element from the right, swap them

### Performance

This might not be a stellar test but i ran a couple of arrays against the 2 methods and the results show that my simple approach is about 4 times faster:

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 |
int count = 1000000; int seed = 0; //a list of random arrays List<int[]> randomArrays = Enumerable.Range(0, count).Select(x => Enumerable .Range(0, new Random(seed++).Next(0, 1000)) .Select(x => x) .ToArray()).ToList(); //timing my method Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (int i = 0; i < 1000000; i++) { PartitionKBasedCustom(randomArrays[i], 3); } stopwatch.Stop(); Console.WriteLine(stopwatch.ElapsedMilliseconds); //timing the classical method stopwatch.Restart(); for (int i = 0; i < 1000000; i++) { PartitionKBasedMicrosoftSolving(randomArrays[i], 3); } stopwatch.Stop(); Console.WriteLine(stopwatch.ElapsedMilliseconds); |

## Leave a Comment