TopTal

       Some time ago I found a letter in my mail box inviting me to join www.toptal.com. A brief look told me that this was a kind of freelance portal, similar to oDesk.com and rentacoder.com (now freelancer.com) I worked on earlier. The difference is that TopTal makes you pass the screening process  before letting you in.

       After a brief Skype conversation with their recruiter, I was given a link to codility coding tasks. I do not consider freelance seriously any longer and didn't expect anything tough from "just another freelancer.com", so I decided to work on it on Friday evening after drinking couple of beers :). In fact I was wrong and that's where I failed.

       I do not remember all of those tasks, but one of them looked interesting. I made a screenshot and decided to solve it later, when I'm able to concentrate :)

So here is the task:

A non-empty zero-indexed array A consisting of N positive integers is given.

A LOGO turtle stands at (0,0) heading North. It moves A[0] steps forward and turns by 90 degrees clockwise. Then it moves A[1] steps forward and turns clockwise by 90 degrees. And so on.
For example, given:

A[0]=1 A[1]=3 A[2]=2 A[3]=5 A[4]=4 A[5]=4 A[6]=6 A[7]=3 A[8]=2

(0,0)   -> (0,1)     1st move, 1 step  North
(0,1)   -> (3,1)     2nd move, 3 steps East
(3,1)   -> (3,-1)    3rd move, 2 steps South
(3,-1)  -> (-2,-1)   4th move, 5 steps West
(-2,-1) -> (-2,3)    5th move, 4 steps North
(-2,3)  -> (2,3)     6th move, 4 steps East
(2,3)   -> (2,-3)    7th move, 6 steps South
(2,-3)  -> (-1,-3)   8th move, 3 steps West
(-1,-3) -> (-1,-1)   9th move, 2 steps North

In the 7th and 9th moves the turtle touches its previous path, namely:

at point (2,1) in the 7th move,
at point (2,-1) in the 7th move,
at point (-1,-1) in the 9th move

Write a function that, given a description of the turtle's walk in array A, returns the number of the first move in which the turtle touches its previous path, or 0 if no such situation occurs.


For example, given array A as defined above, the function should return 7, because the turtle touches its previous path at point (2,1) in the 7th move.


Assume that:

- N is an integer within the range [1..100,000];
- each element of array A 
  is an integer within the range [1..1,000,000].


Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1), beyond input storage   (not counting the storage required for input arguments).

Elements of input arrays can be modified.

My solution:

First of all it's clear that due to time/space requirements none of line segment intersection algorithms for common case cannot be used. Instead we can rely on fact, that intersection would never occur if A[i] > A[i-2] and would always occur otherwise. So despite we have intersection on step 7, the real problem is in step 6. Depending on length of segment 6, we can hit segment 2 or 4, or hit  no segment at all, in case segment 7 is short enough. In the latter case we will intersect with some segment if A[i] >= A[i-2] 

Below is C++ code snippet which does it (to my guess)

typedef std::vector movevec_t;

int solution(movevec_t& M) {

    size_t i, state = 0, dmax = 0;

    for(i = 2; i < M.size(); i++) {
        switch(state) {
            case 0:
                if(M[i] <= M[i-2]) {
                    dmax = (i >= 4 && M[i] + M[i-4] >= M[i-2]) ? 
                                         M[i-1] - M[i-3] : M[i-1];
                    state = 1;
                }
                break;
            case 1:
                if(M[i] >= dmax)
                    return i+1;
                else
                    dmax = M[i-1];
                break;
        }
    }

    return -1;
}

Solving this problem took me about an hour, and still I'm not completely sure about correctness. TopTal gratefully offers you 90 minutes for 3 (three) problems, other two being not much easier than this one. Upon success you have the next interview round, which is again problem solving, but now you have an interviewer watching all your keystrokes in a Skype chat. An absolute show stopper for me :)

I'm not sure what awaits those who pass all interview rounds as I'm not going to try it again. However this post clearly tells that it's unlikely a heaven for "those who deserve":

http://yuriybabenko.com/blog/my-experience-joining-toptal


So is it worth for you? You decide :)