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.
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:
Complexity:
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
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:
Complexity:
Elements of input arrays can be modified.
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 [ ]: