Job Interview: Codility Practical

funkey_monkey

Hi,

I've got a job interview next week part of the interview will involve me taking a Codility test to check my programming skills.

Does anyone have any useful hints and tips for me as I've not done one of these before?

Thanks.

funkey_monkey

https://codility.com/programmers/task/perm_missing_elem/

I've been looking at the above link. my method for this (not done proper programming in years) would be to bubble sort the array initially. as the values are 1 .. n+1 then return 0 if the first element of the sorted array does not contain 0 otherwise return rhs value if comparison of each subsequent two elements (rhs-lhs = 1) is false (can be optimised but id need to see it to do so).

In terms of timing it is not very elegant as there are two big loop structures.

There use of the term element confuses me. I always considered the element to be the bit inside [] but they seem to be referring to the contents if I have read it correctly.

Talisman

Get thee to the Codility website.

Talisman

funkey_monkey wrote: »

https://codility.com/programmers/task/perm_missing_elem/

I've been looking at the above link. my method for this (not done proper programming in years) would be to bubble sort the array initially. as the values are 1 .. n+1 then return 0 if the first element of the sorted array does not contain 0 otherwise return rhs value if comparison of each subsequent two elements (rhs-lhs = 1) is false (can be optimised but id need to see it to do so).

In terms of timing it is not very elegant as there are two big loop structures.

There use of the term element confuses me. I always considered the element to be the bit inside [] but they seem to be referring to the contents if I have read it correctly.

You're not thinking about the problem and instead are brute forcing a solution.

There are three simple rules:
N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

The fastest it way to solve the problem is simple maths.

[1,2,3,5] -> 1 + 2 + 3 + 5 = 11

[1,2,3,4,5] -> 1 + 2 + 3 + 4 + 5 = 15

(5 * 6) / 2 = 15 (It's not a coincidence!)

=> (n * (n+1)) / 2 = 1 + .. + n

15 - 11 = 4

c_man

Do lots of practice. There's lots of example questions online (try stackoverflow and general google searches). I've found them quite... mathsy and not very clear tbh, so get used to the format.

Also when doing it make sure you have your IDE/dev environment of choice at hand! Not point wafing about with gcc and gdb if you're bread and butter is some VS. Good luck.

funkey_monkey

Bollox - I never noticed that. In fairness, the coding I´ve done has been pretty limited in terms of its maths.

Anyhow, I tried the demo:

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

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

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Here is my code. Is it a reasonable effort, or is it laughable?

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

#include <stdio.h>
int solution(int A[], int N) {
    // write your code in C99
    
    // Walk through array    
    for(int p = 0; p < N; p = p + 1)
    {
       // Determine lower side of the equilibrium point        
       int left = 0;
       for(int i = 0; i < p; i = i + 1)
       {
          left = left + A[i];
       }
    
       // Determine upper side of the equilibrium point
       int right = 0;
       for(int i = p + 1; i < N; i = i + 1)
       {
          right = right + A[i];
       }
    
       // Return Statement
       if (left == right)
       {
          return p;  // Value found
       }   
  
    }
    return -1;  // All indexes assessed.  No value found
}

Results stated:

The following issues have been detected: wrong answers, timeout errors.

For example, for the input [0, -2147483648, -2147483648] the solution returned a wrong answer (got 0, but it is not equilibrium point, left sum (empty set)=0, sum[1..2]=-4294967296).

On the results, it passed everything other than extreme numbers and overflow and failed 3 of the performance tests.


How is this for my first C program? Not that it matters. Unfortunately, I have to take my test over the weekend, so this was basically it. Next time is for real.

Any advice as to where you can see I´ve gone fundamentally wrong?

I know that it doesn´t consider numerous equilibrium points, but I didn´t know how to return multiple values - I´ve only ever considered returning a single value in my previous work. I did consider an array, but didn´t know how to implement it.

funkey_monkey

Off to read through their solutions now...

Am I missing something, or will this solution only return the first equilibrium point it encounters? The example array contained 3 such points.

int equi(int arr[], int n) {
    if (n==0) return -1; 
    long long sum = 0;
    int i; 
    for(i=0;i<n;i++) sum+=(long long) arr[i]; 

    long long sum_left = 0;    
    for(i=0;i<n;i++) {
        long long sum_right = sum - sum_left - (long long) arr[i];
        if (sum_left == sum_right) return i;
        sum_left += (long long) arr[i];
    } 
    return -1; 
}

The language I´ve previously used would exit upon encountering a return statement. Is that not the case here too?

Talisman

given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

Returns any means return the first solution you find.

If you can recognise the maths problem then it will be easier to provide a simple solution. Think the problem through before writing any code, work out a solution using pencil and paper if necessary.

Loops within loops should not be necessary to solve such problems.

In the second problem posted it's obvious you need to sum the elements of the array so do that.

sum = 0;
for (i=0; i < N; i++) { sum += A[i]; }

You now have the sum of all the elements. Because you have the final total you can work your way through the array again and work out the equilibrium points.

Addition is commutative:
A[1] + A[2] + A[3] = sum
=> A[1] = sum - (A[2] + A[3])
or
left + right = sum
=> left = sum - right

left = 0; right = sum;
for (i = 0; i < N; i++) {
  right = sum - left - A[i];
  if (right == left) {
    // equilibrium found
    return i;
  }
  left += A[i]; // move element to the left
}
// no equilibrium has been found
return -1;

N=0 is a special case which you have to allow for.

Talisman

funkey_monkey wrote: »

Bollox - I never noticed that. In fairness, the coding I´ve done has been pretty limited in terms of its maths.

Don't think in terms of code, try to visualise the problem for yourself and then solve it as simply as possible.

Consider my example array for your first problem: [1,2,3,4,5]

1 = #
2 = ##
3 = ###
4 = ####
5 = #####

That's almost a triangle. The formula for calculating the area of a triangle is : half the base by the perpendicular height.

In this case : (5 * 5) / 2 = 25 / 2 = 12.5

But there are 15 '#' characters. The answer is off by 0.5 times the number of rows. The reason for this is that the triangle does not have a jagged edge, it has smooth edges so the area calculation is chopping the right most '#' on each line in half and this needs to be accounted for in the calculation.

(base * height) / 2 becomes (base * height) / 2 + (base * 1) / 2

The base and height are equal so:

((n * n) + (n * 1)) / 2
=> ((n * n) + n) / 2
=> (n * (n + 1)) / 2

That simple calculation solves the problem quickly.

funkey_monkey

Exam Done.

Disappointed. Got stuck on comparison of two array elements, one was a pointer. I could see the value, but I couldn´t get the comparison to work.

funkey_monkey

Returns any means return the first solution you find.

To me, returns any does not equate to return the first encountered. The program is unable to return any subsequent indices - therefore, to me it is not capable of returning 'any' only the 'first'.

Talisman

funkey_monkey wrote: »

To me, returns any does not equate to return the first encountered. The program is unable to return any subsequent indices - therefore, to me it is not capable of returning 'any' only the 'first'.

You want your function to be fast (time efficient) so that is why you want to return the first result you find. The problem isn't asking you to identify subsequent solutions.

rock22

Talisman wrote: »

Don't think in terms of code, .....
The base and height are equal so:

((n * n) + (n * 1)) / 2
=> ((n * n) + n) / 2
=> (n * (n + 1)) /
That simple calculation solves the problem quickly.

Nice, elegant solution.
A general question though. are such questions really testing the candidates coding ability or their geometry and algebra.
My background is science and i only ever coded in a very amateur way - often there was no of the shelf software available. And basic maths was often useful.

Is such basic maths still important?

Idleater

rock22 wrote: »

A general question though. are such questions really testing the candidates coding ability or their geometry and algebra.

Yes and no. I think their primary objective is to determine the candidates' thought processes.

A maths brain might get to a calculation result quickly, an artistic brain might draw a nicer presented value. These are purely stereotypical examples, but the thought process in tackling the problem is of interest.

beauf

rock22 wrote: »

Nice, elegant solution.
A general question though. are such questions really testing the candidates coding ability or their geometry and algebra.
My background is science and i only ever coded in a very amateur way - often there was no of the shelf software available. And basic maths was often useful.

Is such basic maths still important?

I've used very little maths in any programming I've done. The only time I've used it was when I did some graphics processing and another time for some pharmaceutical work.Perhaps if you did work in specialized area it might be essential. I wouldn't consider myself a programmer though. I just dabble in it. Most of the time I would be trying to solve problems of logic and sequencing.

Talisman

rock22 wrote: »

Nice, elegant solution.
A general question though. are such questions really testing the candidates coding ability or their geometry and algebra.
My background is science and i only ever coded in a very amateur way - often there was no of the shelf software available. And basic maths was often useful.

Is such basic maths still important?

The purpose of the questions is to give an insight into the thinking process and problem solving approach of a candidate. Some candidates will dive straight into the coding process and if they find themselves in a rut will more than likely provide a brute force solution. A more experienced candidate will tease out a solution before writing the code. They might take a bit longer to provide a solution but it will be more efficient.

I wouldn't say knowledge of maths is a requirement but the thought process of programming and mathematics are very similar. In my experience spotting the connections between concepts has been of great assistance when tackling programming projects.

For example, writing SQL queries is like doing Set Theory maths, people struggle with SQL and JOIN queries in particular but would have little problem with visualising the problem if it was a Venn Diagram.

funkey_monkey

Good news - I've got a job working with Java.

My start date is a while away yet so I want to undertake some online training. Any recommendations? I don't mind if it has a fee as it can contribute to my professional development record.

Long term I would be considering SCJP - is this worthwhile? I'm not sure how much of the libraries I'd be using in this job but I'm just happy to get back into work.

Any recommendations would be gratefully appreciated.


Thanks!

funkey_monkey

Well, I'm about one month into my job now as the start date was delayed.
I am struggling massively with it. The java I can mostly understand. Their architecture, I cannot.

There is a lot of cutting and pasting of code involved, moreso than I expected and I'm making many mistakes. I'm probably the slowest of my intake group.

It is getting me very stressed out and going into work is torture. Unfortunately, I've got very few options at the minute, so u have to stick with it, unless I get sacked first.

How long does it usually take to be proficient in these environments. I'm honestly shocked at how badly in performing - simple mistakes.

I'm getting totally disheartened and losing interest in it already. But I need to get over this, as in reality the only other choice is to go abroad.

L.Jenkins

Before you begin to sink, speak to senior team members and management in order to see what training is available. Also, it would be advised to voice your concerns now and let them know you're struggling, as opposed to going under and getting the sack. Shows initiative and the desire to learn.

AlmightyCushion

funkey_monkey wrote: »

Well, I'm about one month into my job now as the start date was delayed.
I am struggling massively with it. The java I can mostly understand. Their architecture, I cannot.

There is a lot of cutting and pasting of code involved, moreso than I expected and I'm making many mistakes. I'm probably the slowest of my intake group.

It is getting me very stressed out and going into work is torture. Unfortunately, I've got very few options at the minute, so u have to stick with it, unless I get sacked first.

How long does it usually take to be proficient in these environments. I'm honestly shocked at how badly in performing - simple mistakes.

I'm getting totally disheartened and losing interest in it already. But I need to get over this, as in reality the only other choice is to go abroad.

What do you mean by simple mistakes? Can you give us a few examples? Also, I wouldn't copy and paste code. Even if you are going to copy it word for word, type it out. I find doing that really helps with learning the language, its syntax structure etc.

Senna

I definitely know what you mean by the architecture being the problem, Im not lucky enough to be working as a developer, I'm in a platform team for about a month now and the code is no problem, it's how it integrates to all the other systems that is hugely confusing.

As said above, voice this now, don't let it get on top of you. It takes a lot longer than a month for a new developer to get up to speed so mgt will expect you to need help, you just have to ask for it.

funkey_monkey

I'm training now. This is the training exercise in doing. We are being asked to copy, paste and modify code as that is how they work. There is also some new code to be written.

I'm making mistakes like bringing in the wrong chide to start with, missing steps in the process and last night I had to do something that I should have copied from one place that was marked and mine was different. I genuinely don't know where I got it from or how it ended up being wrong.

I'll be working remotely, so I'm fretting about what happens when this happens. Hence why I'm wide awake at 3am.

I'll speak with the guy tomorrow, but I am totally shocked at how bad I am, I was a leading member in my previous job, but I'm so far behind the others in my intake, many of whom have less experience than me of this type of software that it has rattled me, compounded by my simple mistakes that I am making, it feels like a losing battle.

Buford T Justice

AlmightyCushion wrote: »

What do you mean by simple mistakes? Can you give us a few examples? Also, I wouldn't copy and paste code. Even if you are going to copy it word for word, type it out. I find doing that really helps with learning the language, its syntax structure etc.

This. You'll learn nothing with copy and paste. I'm doing a course in android at the minute, and its architecture in itself can be tough to get my head around. Nevertheless I torture myself with typing out the code I'm given rather than copy paste. Its helping

What sort of things are you struggling with?

Buford T Justice

funkey_monkey wrote: »

... I'm so far behind the others in my intake, many of whom have less experience than me of this type of software that it has rattled me....

Don't necessarily be so sure about that

Talisman

funkey_monkey wrote: »

I'll be working remotely, so I'm fretting about what happens when this happens. Hence why I'm wide awake at 3am.

You're stressing yourself, if you don't get proper sleep you are going to be tired the following day. Tiredness will lead to little mistakes which will frustrate you further which will lead to more stress and less sleep. That's a cycle which will erode your confidence in yourself and your ability.

Get some proper sleep and begin to break the cycle.

funkey_monkey

Buford T Justice wrote: »

AlmightyCushion wrote: »

What do you mean by simple mistakes? Can you give us a few examples? Also, I wouldn't copy and paste code. Even if you are going to copy it word for word, type it out. I find doing that really helps with learning the language, its syntax structure etc.

This. You'll learn nothing with copy and paste.

What sort of things are you struggling with?

We are being told to copy and paste by the supervisor. As in use this code here and that code there.

I'm struggling as they seem to have no defined ways to do repetitive tasks. I thought part of the point of oo was to create interfaces for standard tasks and I just pass on my object and the interface or superclass would do the needful. Maybe these tasks are at a low level that they just do them themselves?
So getting a standard to replicate is a hassle too.

Buford T Justice

funkey_monkey wrote: »

So getting a standard to replicate is a hassle too.

It'll also lead to problems down the line when something changes.

Perhaps they don't know any better or they don't implement best practices?

14ned

funkey_monkey wrote: »

Well, I'm about one month into my job now as the start date was delayed.
I am struggling massively with it. The java I can mostly understand. Their architecture, I cannot.

There is a lot of cutting and pasting of code involved, moreso than I expected and I'm making many mistakes. I'm probably the slowest of my intake group.

It is getting me very stressed out and going into work is torture. Unfortunately, I've got very few options at the minute, so u have to stick with it, unless I get sacked first.

How long does it usually take to be proficient in these environments. I'm honestly shocked at how badly in performing - simple mistakes.

I'm getting totally disheartened and losing interest in it already. But I need to get over this, as in reality the only other choice is to go abroad.

As a professional remote working contractor, I always insist on examining a client's code (under NDA usually) before signing the dotted line.

If I see a lot of copy and paste with minor edits, I always walk away, even if it's a LOT of money on offer and even if it might damage my reputation for subsequent jobs. It's a superb sign that the gig isn't worth it for any money.

As you might be guessing, there are a lot of software shops which don't encourage making code reusable, and they encourage people who just copy and paste and tweak bits. This development pattern can deliver something which appears to work well enough for another round of funding quickly, and hence tends to be favoured by pseudo-startups, but the code created is a crock of s*** and should be thrown away as soon as is practically possible.

Now, of course there are always parts of a project which will be mostly copy and paste - unit tests are an excellent example of where that laziness isn't fatal. So concentrate on the quality in the main product, whatever it is they are shipping to customers or putting live on servers.

Anyway, I'd personally recommend you start looking for a new role as soon as possible if they've got a lot of copy and paste in their core product. They'll have gone bust in a few years anyway, so don't waste your time with them. And if so, I'm genuinely sorry this has happened to you, but it's luck of the draw unfortunately, it's almost impossible to tell from the outside before accepting a role.

Niall

funkey_monkey

Unfortunately I'm between a rock and a hard place.
This was the only place that offered me a job after I was made redundant in my last company - the company closed down.
If this fails I'm realistically looking at having to go abroad for work.
I'm in as a contractor so I've got a year to fulfil before doing anything else. I hope to see it out rather than quitting.

14ned

funkey_monkey wrote: »

Unfortunately I'm between a rock and a hard place.
This was the only place that offered me a job after I was made redundant in my last company - the company closed down.
If this fails I'm realistically looking at having to go abroad for work.
I'm in as a contractor so I've got a year to fulfil before doing anything else. I hope to see it out rather than quitting.

If you're a contractor, it's a bit different. Contractors are "temporary employees" and many places treat them as warm bodies filling a slot. You are there to follow orders and not think too hard. You are not there to be invested in or trained or to learn anything. You are there to do as you are told.

Which sucks, but at the low skilled end of contracting it is what it is. And even for high skilled contracting, the team lead which recruited you and highly valued you can change suddenly, and you get a new micromanaging team lead with very fixed and very ignorant opinions on how coding should be done. You've signed on for six months and sometimes a year and you're past the early out clause, so either you renege on your contract or you stick it out. Some colleagues of mine therefore refuse to ever sign any contract longer than six months, and prefer three months, but that's a lot of instability when you have kids.

Best for your career is to stick it out. It's only a year after all. I in the past have drawn up a Google Sheets with my incremental money count showing every time I hit F5. Every time you feel like quitting, go stare at that rising money count. Make it to the end of the contract, and get out.

Getting fired can be a blessing actually, far better for them to end the contract early than you. But I wouldn't try to hasten it by slow working or incompetent working. Just don't try too hard and go through the motions until your time is up. And keep punching that F5 on the spreadsheet!

Niall

funkey_monkey

Thanks for the replies. Now that I've had a chance to settle over the weekend, I've decided that I need/want to continue widening my skills base in order to make this process a lot easier in the future.

I'm looking to get some additional training in things like Git and also some more modern software problem solving techniques. I've prefer recognised courses as opposed to random pages on YouTube and Udemy.

So, any recommendations for courses which cover these bases?



Thanks.