Note: My solutions posted here are a bit verbose and can easily be trimmed. I just like to be safe and simply comment out my debugging prints.

Codility Question 1:

A rectangle is called 'rectilinear' if its edges are all parallel to the coordinate axes. Such a rectangle can be described by specifying the coordinates of its lower-left and upper-right corners.

Write a function:


In [4]:
def solution(K,L,M,N,P,Q,R,S):
    #Code goes here
    pass

that, given eight integers representing two rectilinear rectangles (one with lower-left corner (K,L) and upper-right corner (M,N), and another with lower-left corner (P,Q) and upper-right corner (R,S)), returns the area of the sum of the rectangles. If the rectangles intersect, the area of their intersection should be counted only once. The function should return -1 if the area of the sum exceeds 2,147,483,647.

For the input test case of (-4,1,2,6,0,-1,4,3), the area of the first box is 30, the area of the second is 16, and the area of the intersection is 4. Thus, the function should return 42.

Assume that:

  • K,L,M,N,P,Q,R, and S are integers with the range [-2,147,483,647...2,147,483,647]
  • K < M
  • L < N
  • P < R
  • Q < S

Complexity:

  • expected worst-case time complexity is O(1)
  • expected worst-case space complexity is O(1)

My corrected answer after submission:


In [7]:
def solution(K,L,M,N,P,Q,R,S):
    """    
    Test question 1 on codility. 
    (K,L) box 1 bottom left corner, (M,N) box 1 top right corner.
    (P,Q) box 2 bottom left corner, (R,S) box 2 top right corner.
    
    Original test values were:
    (-4,1,2,6,0,-1,4,3) # box 2 overlapping bottom right corner of box 1
    
    Extra tests for corner cases:
    (0,-1,4,3,-4,1,2,6) # box 2 overlapping top left corner of box 1
    (0,0,10,10,2,2,4,4) # box 2 completely inside box 1
    (0,0,10,10,5,-5,7,20) # box 1 and box 2 forming plus symbol
    (0,0,10,10,-1,-1,-1,-1) #box 2 being just a point
    
    # both boxes being hug and not intersecting totest the 
    # 'return -1 if tot_area>2147483647" rule.
    (-1e6,-1e6,1e6,1e6,1e6,1e6,5e6,5e6) 
    """
    #print 50*"*"
    # Find length and heights
    box1_height = abs(N-L)
    box1_length = abs(K-M)
    box2_height = abs(S-Q)
    box2_length = abs(R-P)
    # Find areas
    area1 = box1_height*box1_length
    area2 = box2_height*box2_length
    
    # First check if one or both of boxes has zero area
    tot_area = area1 + area2
    if (area1*area2)>0:
        # Calculate the overlap in x and y.  
        # Will be negative if no overlap, so, set it to zero in those cases.
        # This form checks for partial overlap, and the smaller box 
        # being completely inside the larger one.
        x_overlap = min(R,M)-max(P,K)
        if x_overlap<0:
            x_overlap = 0
        y_overlap = min(S,N)-max(Q,L)
        if y_overlap<0:
            y_overlap = 0
        #print repr(area1)
        #print repr(area2)
        #print repr(y_overlap*x_overlap)
        tot_area = area1 + area2 - (y_overlap*x_overlap)
        
        
    if tot_area>2147483647:
        tot_area = -1
    print "\n"+repr(tot_area)+"\n"
    return tot_area

Codility Question 2:

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P,Q) is called 'K-compmlementary' in array A if 0 <= P,Q < N and A[P] + A[Q] = K.

For the test case of A=[1,8,-3,0,1,3,-2,4,5] and K=6, the 6-complementary pairs are: (0,8),(1,6),(4,8),(5,5),(6,1),(8,0),(8,4). FOr instance, (4,8) is 6-complementary because A[4] + A[8] = 1 + 5 = 6.

Write a function:


In [8]:
def solution(K,A):
    #Code goes here
    pass

that, given an integer K and a non-empty zero-indexed array A consisting of N integers, returns the number of K-complementary pairs in array A.

The test case above for example, should return 7.

Assume that:

  • N is an integer within the range [1..40,000]
  • K is an integer within the range [-2,147,483,647...2,147,483,647]
  • each element of array A is an integer within the range [-2,147,483,647...2,147,483,647]

Complexity:

  • expected worst-case time complexity is O(N*log(N))
  • expected worst-case space complexity is O(N), beyond the input storage (not counting storage required for the input arguments)

Elements of input arrays can be modified.

My corrected answer after submission:


In [9]:
def solution(K,A):
    """
    THIS IS THE CORRECTED VERSION OF THE ONE I SUBMITTED.  THIS ONE IS CLOSER
    TO O(NLogN), WHEREAS THE ONE I SUBMITTED WAS O(N**2).
    
    Test question 2 on codility.
    A is an array of ints, K is the A[i]+A[j]=K value.
    
    Original test values were:
    A=[1,8,-3,0,1,3,-2,4,5],K=6
    
    Extra test cases:
    (K=6,A=[1,1,1,1,1,1,1,1,1,5,5,5,5,5,5,5,5,5,5,5,5])
    (K=6,A=[3])
    (K=-6,A=[-3])
    (K=6,A=[1])
    (K=0,A=[0])
    (K=2147483646,A=[int(2147483646/2.0)])
    (K=-2147483646,A=[int(-2147483646/2.0)])
    (K=2147483647,A=[int(2147483647/2.0)])
    (K=0,A=[])
    """
    #print 50*"*"
    count = 0
    # Documentation says this won't happen, but better to be safe...
    if (type(A)==list) or (type(K)==int):
        #First sort the array to change from O(N**2) to O(N*logN)
        A.sort()
        
        #Set up initial values of important counters and result lists.
        i = 0
        j = len(A)-1
        sames = []
        keep_going = True
        pairs = []
        #inds = []
        
        if len(A)>0:
            # Move from out to middle, adding up number of complimentary pairs
            while(keep_going):
                #print repr((i,j))
                if (A[i]+A[j]==K):
                    if (i==j) and (i not in sames):
                        count+=1
                        sames.append(i)
                        pairs.append((A[i],A[j]))
                        #inds.append((i,j))
                    else:
                        count+=2
                        pairs.append((A[i],A[j]))
                        #inds.append((i,j))
                if i<j:
                    i+=1
                elif i==j:
                    if j==0:
                        keep_going = False
                    i = 0
                    j-=1
            
        #print "pairs = "+repr(pairs)
        #print "inds = "+repr(inds)
    print "\n"+repr(count)
    return count

In [ ]: