2017. november 2., csütörtök

Codility simple C programming task 2 - solution

As part of my job interview process a few years ago in the UK, I was given a Codility task to solve online. I can't remember which company I applied for, neither the names of the interviewer(s). I could not solve the task back then (no wonder why, as you'll see soon), but I saved the task for the future. The time has come and I re-visited the task. After I did the code review, to my surprise, it turned out that the PROBLEM WAS NOT WITH ME but with the IT WAS TO DO WITH THE INTERVIEWER. I solved the task on my own at home and my solution is shorter, better. I publish it for public benefit and to see that it's not always the candidate unskilled but the interviewer was completely at a loss and was an incompetent bungler. The original task was simply wrong, it contained buggy code and it is not even close to being right. He should have devoted more time to prepare a good task for the candidate assessment.

The task can be seen in the attached picture below.


The task is to solve the C code by modifying "at most two lines of code". This is not possible. If something is BROKEN, you can't fix it by applying cosmetic fixes. YOU HAVE TO THROW IT AWAY. If you examine the bad code below, you can see it contains nonsense. It simply does not work. It's not even close to being a good code. I assume it's just there to derail the candidate. For e.g. if you look at the assumptions, you can see that the wrong code contains checks it should not check for, since we assume something, we should not check for it. We assume it and that's it.

BAD CODE:

int solution(int A[], int N, int K) {
   int i;
   for (i = 0; i < N - 1; i++) {
if (A[i] + 1 < A[i + 1])
          return 0;
   }
   if (A[0] != 1 && A[N - 1] != K) 
          return 0;
     else
          return 1;
}

Look at my fixed code below in its clear beauty.

GOOD CODE:

int solution(int A[], int N, int K) {
   int i;
   for (i=0; i<=N-1; i++) {
      if (A[i]==K) return 1;
   }
   return 0;
}

The correct algorithm goes like this. When you find the element of A array equals to K, we return with 1 (true). We find what we want and do not have to worry about the rest. When the check is over and no value is found that matches the key we're looking for, we will return with false (0). This is how you write simple and good code that solves the problem without the extra hassle. What can be easier than that?

I also wrote a wrapper main program to actually test the above function with different values. See below. 

task-2.h:

/* 
   This is task-2.h. It declares the function to be used in the main program. 
 */

int solution(int[], int, int);

task-2.c:

#include
#include "task-2.h"

int main() {

int noofelements=3; 
int key=2;
short rc=0;
int array[noofelements];

array[0]=1;
array[1]=1;
array[2]=3;

printf("elements in the array are:\n");
for (int i=0; i
   printf("%d\n", array[i]);
}

rc=solution(array,noofelements,key);
printf("is key %d found in array?\n", key);
if (rc==0)
   printf("false.\n");
else
   printf("true.\n");

return 0; // return true to satisfy shell

}

Put the solution() function , the good code into into a separate file task-2-fixed.c and compile and link them together with gcc and try it. IT WILL WORK. Below is the Makefile for reference:

# Makefile for task-2
#
task-2-fixed.o: task-2-fixed.c
gcc -c $<

task-2.o: task-2.c task-2.h

gcc -c $<

task-2: task-2.o task-2-fixed.o

gcc -o $@ task-2.o task-2-fixed.o

all: task-2


I feel much better as I solved the problem and proved that I am competent enough. Also, I proved that the interviewer was not good. I am happy that I was not hired by that company at the time! Problem solved. If you need help with the code, it's been tested by me and works successfully.

;-)

qmi
2 Nov 2017

UPDATE:
A friend of mine, Zoltan Hanko pointed out to me that although my solution may be correct finding the key K in the array A but that task was not exactly that in the first place. He was right. The task is to check whether array A contains number 1,2.......K and no other numbers. I am sorry, I overlooked it. My solution above only finds the key K and returns with true if found. I fixed my code so that it checks for stray numbers that are greater than K and also checks if there is no 0 (zero) among the array elements. Since the original task description says that 'assume that the array elements are sorted in non-decreasing order', I do not check if they are out of order. See the fixed code below:

int solution(int A[], int N, int K) {
   short found=0;
   int i;
   for (i=0; i<=N-1; i++) {
      if ((A[i]==0) || (A[i]>K)) return 0;
      if (A[i]==K) found=1;
   }
   if (found==1) 
return 1; // true
   else
return 0; // false
}

It is tested and works. For e.g., with array values 1,1,2,3 taken as input the function returns false, because even though key K=2 is found but the last index value is 3, which is a stray number larger than K. Therefore returns with false. However, even with the above code and now finally the original task requirement is fully met, the above working code is NOT EVEN CLOSE TO THE ORIGINAL BROKEN ONE. The interviewer who prepared this task was obviously incompetent.

Take away: I suggest every interviewer to come up with value-added and well written tasks to AVOID WASTING TIME of the unsuspecting candidate.

qmi

7 Nov 2017