Friday, April 27, 2012

Programmers' Professional Networks

I have been observing the growing space of programmers' credibility repositories – the sites enabling programmers to present their professional profile. They offer a service similar to Linked-In profiles, but with a built-in domain knowledge that makes them best suited for software professionals presenting themselves to the public (i.e. colleagues and employers). In this case the domain knowledge is pretty straightforward: code and competencies are what matter most.

At one end of the spectrum are sites that accumulate a domain-specific footprint, but are not credibility repositories per se: SourceForge, GitHub, Codeplex, Bitbucket and GoogleCode. They are not always sufficient for assessing credibility – a military contractor will rarely post a code snippet on GitHub – but still, in many cases they contain useful information.

This end of the spectrum is rather solidified, with some brands operating for well over a decade. At the other end, sites like Whitetruffle or StackOverflowCareers approach the subject in the Linked-in fashion, i.e. as credibility repositories, however, specialized just for programmers. StackOverflowCareers is in an interesting position due to its strong connection to StackOverflow proper, enabling it to verify professional credibility based on the StackOverflow reputation.

As much as Linked-in is a leader among general-purpose credibility repositories, there is no clear leader among the programmer-specific ones. This situation has been used to advantage by Masterbranch.

Masterbranch allows professional developers to aggregate their programming credibility from most of the sources mentioned in this blogpost, ranging from SourceForge and GitHub, through StackOverflow and even general-purpose footprint repositories (including Twitter).

Moreover, the site enables programmers to register their on-line identities so that their profiles update automatically whenever any relevant activities occur at any of the sources. Similarly well-developed automation on the profile viewer's side makes it an interesting one-stop-shop for recruiters tracing programmers' digital footprints.

Greg Jakacki, CEO at Codility

Friday, April 13, 2012

Unlimited History and Higher Number of Simultaneous Tests!

Following our customers' feedback and suggestions, we have extensively revamped a number of our features.

Unlimited History

You can now enjoy unlimited history, which we indefinitely hold on our servers. Thus when you need to review even last year's results, they are immediately on hand!

Simultaneous Tests

In addition, we have extended the number of simultaneous tests to 20! And now your job seekers can complete the Codility programming tests at the same time. You can even run a small programming competition for your candidates! If you would like increased access please write to us at support@codility.com.

Wednesday, April 11, 2012

Pi 2012 Codility Programming Certificate Solution

Another month has arrived and it is time to show how the Codility Certificate codenamed $$\Pi$$ (Pi) can be solved. You can still give it a try, but no certificate will be granted. If you want to obtain a Codility Certificate, a new problem awaits you here.

In the $$\Pi$$ certificate problem, we are given an array of integers. For each element of the array we have to find the distance to the closest larger element in the array, called the closest ascender. (If there is no ascender, we assume that the distance equals zero.) The result is an array of distances to the closest ascenders.

Is this difficult? It depends on the desired time complexity. Let us focus for a while on a single element of the array, $$A[I]$$. One can easily find the distance to its closest ascender by increasing the distance $$D$$ until $$A[I-D]$$ or $$A[I+D]$$ is larger than $$A[I]$$. This way, for a given element of the array, the distance can be computed in $$O(N)$$ time, and the whole result can be computed in $$O(N^2)$$ time. Such a solution is correct and simple, although it is not optimal. Here is its implementation in Python:

  def array_closest_ascenders(A):
N = len(A)
ret = [0] * N
for I in xrange(N):
for D in xrange(1,N):
if (I-D >= 0) and (A[I-D] > A[I]):
ret[I] = D
break
if (I+D < N) and (A[I+D] > A[I]):
ret[I] = D
break
return ret


Let us simplify the problem. Instead of looking for the distance to the closest ascender, we can look for two distances: that to the closest ascender lying to the left, and that to the closest ascender lying to the right, called respectively the closest left ascender and the closest right ascender. These problems are symmetrical, so let us focus just on finding the distances to the closest left ascenders.

It turns out that it is possible to find all the closest left ascenders in $$O(N)$$ time. The main observation is that not all elements of the array can possibly be closest left ascenders. Let $$0 \le K < J < I < N$$. If $$A[K] < A[J]$$ then $$A[K]$$ cannot be the closest left ascender of $$A[I]$$. Let us filter the list $$[0, 1, \dots, I-1]$$ and narrow it to include only the indices of those elements that can possibly be the closest left ascenders of $$A[I]$$, regardless of its actual value. Such a list of indices is increasing, and the elements to which these indices point form a decreasing sequence. We process the elements of the array from left to right, updating the list of indices of possible closest left ascenders. When processing $$A[I]$$ we can remove from the list all indices of the elements not larger than $$A[I]$$. Since the sequence of indexed elements is decreasing, we remove some trailing part of the list of indices. The last element left is the closest left ascender of $$A[I]$$. Then, by appending $$I$$ to the list of indices, we obtain a list of indices of possible closest left ascenders of $$A[I+1]$$. Below is a Python function calculating the array of distances to the closest left ascenders.


INF = 1000000123

def left_closest_ascenders(A):
N = len(A)
if (N == 0): return A
ret = [0] * N
stack = [0] * N
stack_size = 0
for I in xrange(N):
while (stack_size > 0) and (A[stack[stack_size-1]] <= A[I]):
stack_size -= 1
if (stack_size == 0):
ret[I] = INF
else:
ret[I] = I - stack[stack_size-1]
stack[stack_size] = I
stack_size += 1
return ret


What is the time complexity of this function? The outer for loop performs $$N$$ steps. The inner while loop can perform up to $$O(N)$$ steps. However, if we use amortized cost analysis, it turns out that the overall time complexity is smaller than $$O(N^2)$$. With each step of the while loop, stack_size decreases by 1. Its initial value is 0, it is increased by 1 with each step of the outer for loop, and it never takes negative values. Hence, the overall time complexity of this function is $$O(N)$$.

In other words, each element of the array is pushed onto the stack once and can be popped only once. Hence, the while loop does not influence the time complexity.

The array of distances to the closest right ascenders is just a reversed array of distances to the closest left ascenders, computed for the reversed array of elements. By combining the arrays of distances to the closest left and right ascenders, we instantly obtain the result. Below is a Python implementation of the solution's main function:

  def array_closest_ascenders(A):
N = len(A)
left = left_closest_ascenders(A)
A.reverse()
right = left_closest_ascenders(A)
right.reverse()
ret = [0]*N
for I in xrange(N):
ret[I] = min(left[I], right[I])
if ret[I] == INF:
ret[I] = 0
return ret


Friday, April 6, 2012

Programming Challenge Results!

Uhhh… was it really so easy, or are you that good…? We have granted more than 330 Pi 2012 Gold Certificates and more than 1400 Silver ones! It seems that we will need to prepare something harder next month!

If you want to practice, after reading the blog post, you can still do the certification task. You will be able to see how your code performs, but you are no longer able to earn certificates for correct solutions.

Wednesday, April 4, 2012

Bible Of Internships - How to find a great job at Google, Facebook, Microsoft?

If the title sounds familiar, this is for you! I wrote this blog post as a tribute to the great blog post which helped me very much a few months ago.

After dozens of interviews and hours on the phone, I decided to share my knowledge and create this, not so short, but very enriching post.

So, have you ever imagined a situation where you receive job offers from Google, Facebook and Microsoft? And... you have to reject most of them because you just cannot be in several places at once? For sure you did. I wanted to know how this feels, so I did some research. Do you want to know more? Read on.

The core business of Codility is strictly about recruiting: we help billion-dollar companies as well as startups to hire coders. But we are programmers ourselves and we have been on the other side of the table too. I was in internship interviews with all the companies mentioned above. In preparation for the interviews I talked to my older university colleagues who were internship veterans, who has been to all possible internship already and even rejected some offers just because they have grown bored of spending holidays this way. I realized that I have a great opportunity to sum everything up and to create a wrap-up for internship wannagets.

Stages of recruitment

It is important to understand that every company has a slightly different recruitment process. Sometimes you have to wait one month for the interview, sometimes a day. Sometimes you just have to send your CV, sometimes it is better to use a backdoor. Nevertheless most of them follow a pattern that looks something like that:
1. You realize that the firm is recruiting interns and you want to work for them or you are contacted directly by a recruiter (recruiters will hunt for you in some places, e.g. programming contests).
2. You send a CV/resume.
3. Your CV is noticed. (This is usually the last step for most candidates. Your CV isn't impressive enough. But remember, the reason is not because you are not impressive: it's because you are too lazy to learn how to write a good CV.)
4. If you obtain the honor ;) of being contacted by a recruiter, you will usually get some kind of pre-screening task, for example, a simple project to do at home, an on-line test (Codility!) or the like.
5. Phone interviews. (Both technical and behavioral questions. People generally underestimate the importance of behavioral questions, don't make this mistake!)
6. Possible on-site interview.
7. Offer.
8. Great internship.

Secondly, you have to be good with computers, but you don't have to know everything. This is just an internship, not a senior engineer job. A very common mistake is a lack of self-confidence. Many people say: An internship in Microsoft? I don't have a chance. Maybe next year. What? Of course you don't have a chance, because you don't try! Stick this motto over your bed: A quitter never wins and a winner never quits. Try, try, try until you win. On the other hand if ε > 0 your_skill < ε, you'd better go back to the lessons.

The main content of an interview is technical questions. Good news, they tend to be very typical. Best way to polish your programming is to take part in several programming contents. If you failed to do so, try this:
1. Solve problems from past contests (i.e. Google Code Jam) or just participate in TopCoder.
2. Codility is heavily used by recruiters during internship season, similarly our certificate challenges take heavy traffic. Take advantage of them to work out before the fight.
3. Participate in as many interviews as you can. Just for the experience. It costs nothing (for you at least, but who cares, these companies have craploads of cash anyway).

Another common mistake is that you can't stand the fact, that you won't completely solve the task during interview. It may not be the point. The recruiter wants to see whether you have analytical skills. Sometimes the problem has no solution at all. Show as many ideas as you can, even stupid ones. This shows that you can think.

I have met several geniuses who were rejected in the interviews, and several smart-but-not-ingenious people who made it. Technical skills are necessary, but not sufficient, it shows. Here is a bunch of hacks and tricks that increase your chances (in random order):
1. Let's be serious. A typical billion-dollar company has hundreds of thousands of candidates to screen. Sending a CV through their website is not the best possible way to apply. BETTER: Find a recruiter's profile on Linked-in or Facebook, ask friends whether they know any recruiters in this particular firm, and contact them directly. It's simple but doubles your chances.
2. Behavioral questions during phone interview. Create a few pages with answers for every question you might expect. Make the table with all the best things you can say about your former projects, the hardest bugs you came across and some information about the type of company you want to work for. Never ever answer uh... to a question like Why do you want to work for us?. They won't take you no matter how many LISP compilers you have written in kindergarten.
3. In most cases, after you pass interviews you arrive at the rotting pool, waiting to be picked up by a host. Why not contact them directly, like in point (1)? Better to wait with folded hands?
4. Have I already mentioned that you are talking to humans, not machines? Show some empathy. Ask How do you do? at the beginning, say Have a nice day. at the end.
5. Forty minutes is too short to show your awesomeness just answering the questions. But there are other ways to achieve it. Ask THEM questions. It usually helps to ask something in a way that smuggles some information about you. My favorites:
• Do you use any source code control systems, i.e. SVN or GIT?
• Is agile methodology important in your job?
• In my last project I had to solve a big problem with memory leaks. Do you experience any problems related to memory leaks in the project I am about to join?
6. Resume advice. The average time spent on screening one CV is four seconds. What are the screeners looking for? If you are smart and really can code. That's all.
Your CV should be elegant, aesthetic and simple. The KISS principle works perfectly in this field. Do you think that someone wants to read a long CV? Your CV has to fit on one page. No more, no way! It is good to show that you have a passion other than programming. Sailing? Great. Bodybuilding? Great. But no one cares that you love eating honey. Provide only essential information.
7. In every How to get this job. tutorial you read Don't lie. - I agree, the facts are simple to check. But... if 90% of people lie in their CVs, wouldn't you lose your internship to them for just being honest? This sounds purely like prisoner's dilemma.
Be honest, but present yourself in the best way possible.
Winner of many programming contests, including team programming. sounds better than Winner of small regional team contest for the school cup.
8. Show an interest. Treat every company exceptionally. Demonstrate your knowledge about it's culture and history. Ask questions showing that you have did your homework.
9. Last but not least. You are not just answering their questions. You are demoing yourself.

Hope it helps. This text may not amuse veterans, but is written for students by a student.

Rafał Bielenia is a student of Computer Science at Warsaw University and former Codility Intern.