Interview questions and answers for Pratheeban

interview.md

Question 1

Sequence is defined by -

• A0 = 1
• Ai+1 = Ai + 1 or Ai * 2

Now given An = some number find the smallest n.

def find_smallest_n(An):
    if An <= 2:    return An
    if An % 2 == 0:    return find_smallest_n(An / 2) + 1
    else:    return find_smallest_n(An - 1) + 1       
    
find_smallest_n(18)

Question 2

Find saddle points of a given matrix (not using numpy). Ref: https://en.wikipedia.org/wiki/Saddle_point

def maxima_minima(A, M, N, axis=0):
    """Returns a MxN matrix where the elements are
    +1 if it is a local maxima or -1 if it is a local minima
    or 0 if neither. (along the given axis)
    """
    result = [[0 for i in range(N)] for j in range(M)]
    for i in range(1, M - 1):
        for j in range(1, N - 1):
            if axis == 0:
                # along the row
                current_is_bigger_than_next = int(A[i][j] - A[i][j + 1] > 0)
                current_is_bigger_than_prev = int(A[i][j] - A[i][j - 1] > 0)
                
            else:
                # along the column
                current_is_bigger_than_next = int(A[i][j] - A[i + 1][j] > 0)
                current_is_bigger_than_prev = int(A[i][j] - A[i - 1][j] > 0)                
                
            if current_is_bigger_than_next and current_is_bigger_than_prev:
                result[i][j] = +1
            elif (not current_is_bigger_than_next) and (not current_is_bigger_than_prev):
                result[i][j] = -1
            else:
                result[i][j] = 0
    return result

def find_saddle_points(A):
    """A is a 2D matrix whose saddle points must be found.
    
    Ref: https://en.wikipedia.org/wiki/Saddle_point
    """
    M, N = len(A), len(A[0])
    maxima_minima_row = maxima_minima(A, M, N, axis=0)
    maxima_minima_col = maxima_minima(A, M, N, axis=1)
    
    saddle_check_matrix = [[maxima_minima_row[i][j] * maxima_minima_col[i][j]
                            for j in range(N)]
                           for i in range(M)]            

    saddle_points = []
    for i in range(1, M - 1):
        for j in range(1, N - 1):
            # Either maxima in row & minima in col or vice versa
            if saddle_check_matrix[i][j] == -1:
                saddle_points.append((i, j))

    return saddle_points

Question 3

Optimize the following function

def solution(A):
    result = 0
    N = len(A)
    for i in xrange(N):
        for j in xrange(N):
            if A[i] == A[j]:

                result = max(result, abs(i - j))

    return result

The optimized function -

def optimized_solution(A):
    N = len(A)
    for distance in range(N - 1, 0, -1):
        # Check if there are similar numbers at this distance (i)
        try:
            for i in range(1, N):
                if A[i] == A[i + distance]:
                    return distance 
        except IndexError:
            pass
    return 0
        
optimized_solution([4, 6, 2, 3, 7, 9, 1])

Question 4

Compute the number of castles that can be built

land_heights = [2, 2, 3,   4, 3, 3,   2, 2, 1,   1, 2, 5]
land_heights = [1, 3, 4, 2, 8]
land_heights = [1, 0, 1, 1, 1, 1, 1]
land_heights = [-3, 3]
land_heights = [-3, -3]
land_heights = [0, ]

def compute_number_of_castles(land_heights):
    N = len(land_heights)
    
    # Remove duplicates to make computations easier
    land_heights = ([land_heights[0], ] +
                    [land_heights[i] for i in range(1, N)
                     if land_heights[i - 1] != land_heights[i]])
    # Add duplicates of neighbors to start and end to ensure they are
    # counted as peaks or valleys if the other side satisfies
    land_heights = [0, ] + land_heights + [0, ]
    N = len(land_heights)

    # print(land_heights)
    # First difference comparins current and next
    diff1 = [land_heights[i] - land_heights[i + 1]
             for i in range(1, N - 1)]
    # Second difference comparing current and previous
    diff2 = [land_heights[i] - land_heights[i - 1]
             for i in range(1, N - 1)]
    peak_or_valley_at_both_diff = [int(diff1[i] * diff2[i] > 0)
                                   for i in range(N - 2)]
    
    return peak_or_valley_at_both_diff.count(1)

compute_number_of_castles(land_heights)