Coding Interview #1 – Code Performance

Coding Interview #1 – Code Performance

Ok, let’s talk academics!

Here is an interview question I was recently asked –

Given a list of unsorted numbers, print each number and the number of occurrences in the list.
Example: 1, 1, 2, 3, 5, 5, 2, 2.
Should print like following.
1 – 2
2 – 3
3 – 1
5 – 2

Ok, so what the interviewer is really trying to look for is an efficient way to write code for answering the question above. Efficiency means code with good performance -i.e. the least possible steps in code to get the required output.

Code performance is measured through a process called the Big O Notation. The Big O Notation is a reflection of the running time of an algorithm and measures performance by counting the number of times the input elements are visited in the algorithm to create the output. So, if an input of n elements are visited once in the algorithm to create the output, the algorithm is said to have running time of O(n).

The same Big O notation is used for measuring memory used. The memory bandwidth for an n element list is O(n).

So, our goal here is make sure the unsorted list of numbers are visited the least number of times to create the required output.

Given below are two approaches to provide the required output:

 


//Objective-C based methods

//Total runtime = O(n^2) for bubble sort and O(n) to print the occurrences of the values
- (void) SortAndDisplay1: (int[]) arr1
{
int temp = 0;

//bubble sort - O(n^2) runtime
for(int i = 0; i < [arr1 count] - 1;i++)
{
for(int j = i + 1; j < [arr1 count];j++)
{
if(arr1[j] < arr1[i])
{
temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
}
}
}

//print the output - O(n) operation
temp = arr1[0];
int count = 1;
for(int i = 1; i < [arr1 count];i++)
{
if(arr1[i] == temp)
{
count++;
}
else
{
Console.WriteLine(temp + " - " + count);
count = 1;
}
}

}

//Total runtime = O(n) for dumping into a HashMap and O(n) to print the occurrences of the values.
//The difference to SortAndDisplay2 is additional memory taken for a HashMap.
- (void) SortAndDisplay2(int[]) arr1
{

NSMutableDictionary *occurrences = [NSMutableDictionary dictionary];

//bubble sort - O(n) runtime

[occurrences setObject: 1 forKey: arr1[0]];

int count = 1;
for (int i = 1; i < [arr1 count] - 1; i++)
{
if([occurrences objectForKey: arr1[i]] != nil)
{

int val = [occurrences objectForKey: arr1[i]];

val  = val + 1;
[occurrences removeObjectForKey:arr1[i]];

[occurrences setObject:val forKey:arr1[i]];
}
else
{
[occurrences setObject:1 forKey:arr1[i]];
}
}

//print the output - O(n) operation
NSArray *keys = [occurrences allKeys];

for (int j = 0;j < [keys count];j++)
{
NSLog("%@ - %@", [NSString stringWithFormat:@"%i", keys[j]], [NSString stringWithFormat:@"%i", [occurrences objectForKey:keys[j]]]);
}

}


//C# based methods

//Total runtime = O(n^2) for bubble sort and O(n) to print the occurrences of the //values
static void SortAndDisplay1(int[] arr1)
{
int temp = 0;

//bubble sort - O(n^2) runtime
for(int i = 0; i < arr1.Length - 1;i++)
{
for(int j = i + 1; j < arr1.Length;j++)
{
if(arr1[j] < arr1[i])
{
temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
}
}
}

//print the output - O(n) operation
temp = arr1[0];
int count = 1;
for(int i = 1; i < arr1.Length;i++)
{
if(arr1[i] == temp)
{
count++;
}
else
{
Console.WriteLine(temp + " - " + count);
count = 1;
}
}

}

//Total runtime = O(n) for dumping into a HashMap and O(n) to print the occurrences of the values.
//The difference to SortAndDisplay2 is additional memory taken for a HashMap.
static void SortAndDisplay2(int[] arr1)
{
Dictionary<int, int> occurrences = new Dictionary<int, int>();

//bubble sort - O(n) runtime
occurrences.Add(arr1[0], 1);
int count = 1;
for (int i = 1; i < arr1.Length - 1; i++)
{
if(occurrences.ContainsKey(arr1[i]))
{
occurrences[arr1[i]] = occurrences[arr1[i]] + 1;
}
else
{
occurrences.Add(arr1[i], 1);
}
}

//print the output - O(n) operation
int temp = arr1[0];
count = 1;
foreach (KeyValuePair<int,int> pair in occurrences)
{
Console.WriteLine(pair.Key.ToString() + " - " + pair.Value.ToString());
}

}

 

So, in terms of pure code performance and execution time, the method SortAndDisplay2 will complete faster than method SortAndDisplay1 but consequently uses more memory to accommodate the HashMap data structure. There is always a trade off between execution time and memory usage when trying to achieve maximum code performance for an algorithm.

– Subramanian Ramachandran

Leave a Reply

Your email address will not be published. Required fields are marked *