Home/Coding Guide/Matrices, Arrays & Unit Testing
⌂ Main Page
Coding Interview Preparation Guide

Matrices, Arrays & Unit Testing

2-D matrix challenges (rotation, spiral, zeroing), array problems, and unit-testing patterns for interviews.

Challenges on this page

THE MATRIX

Count paths

Can move only right or down from a cell in the matrix - count the ways
(i) Recursion - Recurse starting from a[m-1][n-1], upwards and leftwards, add the path count of both recursions and return count;
(ii) Dynamic Programming- Start from a[0][0].Store the count in a count matrix. Return count[m-1][n-1]
Time c. O(mn), space c. O(mn)

Python
# Time c. - exponential O(c**n)
def count_paths_rec(m, n): 

    if(m == 1 or n == 1): return 1
    
    return count_paths_rec(m-1, n) + count_paths_rec(m, n-1)             # If diagonal movements - add last term 


# Time & space = O(mn)
def count_paths(m, n):
        
    if m < 1 or n < 1: return -1
        
    # Count matrix
    count = [[None for j in range(n)] for i in range(m)]

    # Edge cases - matrix of size 1xn or mx1
    for i in range(n):
        count[0][i] = 1
    for j in range(m):
        count[j][0] = 1

    for i in range(1, m):
        for j in range(1, n):
                        
            # Number of ways to reach a[i][j] = number of ways to reach a[i-1][j] + a[i][j-1]
            count[i][j] = count[i - 1][j] + count[i][j - 1]

    return count[m - 1][n - 1]


# Time O(mn), space O(n)
# Topmost leftmost cell 1, 1
def count_paths_dp(m, n): 
      
    dp = [1 for i in range(n)]                    # Store results of subproblems 
        
    for i in range(1, m):                         # originally - for i in range(0, m - 1), why?
        for j in range(1, n):
            dp[j] = dp[j] + dp[j - 1]
                        
    return dp[n - 1]
Python
m, n = 5, 5
Python
print('Recursive:', count_paths_rec(m, n))
print('    Optim:', count_paths(m, n))
print(' Optim DP:', count_paths_dp(m, n))
Output
Recursive: 70
    Optim: 70
[1, 2, 1, 1, 1]
[1, 2, 3, 1, 1]
[1, 2, 3, 4, 1]
[1, 2, 3, 4, 5]
[1, 3, 3, 4, 5]
[1, 3, 6, 4, 5]
[1, 3, 6, 10, 5]
[1, 3, 6, 10, 15]
[1, 4, 6, 10, 15]
[1, 4, 10, 10, 15]
[1, 4, 10, 20, 15]
[1, 4, 10, 20, 35]
[1, 5, 10, 20, 35]
[1, 5, 15, 20, 35]
[1, 5, 15, 35, 35]
[1, 5, 15, 35, 70]
 Optim DP: 70

Rotate matrix clockwise, in place

Python
# Each operation is O(M): time O(2M) -> O(M), space O(1) where m=num cells in matrix OR n**2
class Solution(object):
    def rotate(self, matrix):
        self.transpose(matrix)
        self.reflect(matrix)
        
    def transpose(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] =\
                matrix[j][i], matrix[i][j]
                
    def reflect(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(n//2):
                matrix[i][j], matrix[i][-j-1] =\
                matrix[i][-j-1], matrix[i][j]
                
matrix = [[1,2,3],[4,5,6],[7,8,9]]
s = Solution()
s.rotate(matrix)
print(matrix)
Output
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Rotate matrix

Python
# transpose (top left invert)
def top_left_invert(matrix):
    new = []
    for row in matrix:
        for i, elem in enumerate(row):
            try:
                new[i].append(elem)
            except IndexError:
                new.insert(i, [])
                new[i].append(elem)
    return new

# OR
new = list(zip(*matrix))
for i in new:
    print(i)
Output
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)
Python
def rotate_clockwise(matrix):
    new = []
    for row in reversed(matrix):
        for i, elem in enumerate(row):
            try:
                new[i].append(elem)
            except IndexError:
                new.insert(i, [])
                new[i].append(elem)
    return new

def rotate_counterclockwise(matrix):
    new = []
    for row in matrix:
        for i, elem in enumerate(reversed(row)):
            try:
                new[i].append(elem)
            except IndexError:
                new.insert(i, [])
                new[i].append(elem)
    return new

def top_left_invert(matrix):
    new = []
    for row in matrix:
        for i, elem in enumerate(row):
            try:
                new[i].append(elem)
            except IndexError:
                new.insert(i, [])
                new[i].append(elem)
    return new

def bottom_left_invert(matrix):
    new = []
    for row in reversed(matrix):
        for i, elem in enumerate(reversed(row)):
            try:
                new[i].append(elem)
            except IndexError:
                new.insert(i, [])
                new[i].append(elem)
    return new


def print_matrix(matrix, name):
    print('{}:\n['.format(name))
    for row in matrix:
        print('  {}'.format(row))
    print(']\n')

Rotate matrix, Python way (not in place)

Python
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
Python
# transpose (top left invert)
new = list(zip(*matrix))
for i in new:
    print(i)
Output
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)
Python
# bottom left invert
new = list(zip(*reversed([reversed(i) for i in matrix])))
for i in new:
    print(i)
Output
(9, 6, 3)
(8, 5, 2)
(7, 4, 1)
Python
# clockwise
new = list(zip(*reversed(matrix)))
for i in new:
    print(i)
Output
(7, 4, 1)
(8, 5, 2)
(9, 6, 3)
Python
# counter clockwise
new = list(zip(*[reversed(i) for i in matrix]))
for i in new:
    print(i)
Output
(3, 6, 9)
(2, 5, 8)
(1, 4, 7)

Search in sorted matrix

Python
# Search a key in a row wise and column wise sorted (non-decreasing) matrix.
# m - Number of rows in the matrix
# n - Number of columns in the matrix
# T(n)- O(m+n)
#


def search_in_a_sorted_matrix(mat, m, n, key):
    i, j = m-1, 0
    while i >= 0 and j < n:
        if key == mat[i][j]:
            print ('Key %s found at row %s, column %s' % (key, i+1, j+1))
            return
        if key < mat[i][j]:
            i -= 1
        else:
            j += 1
    print ('Key %s not found' % (key))
Python
mat = [
       [2, 5, 7],
       [4, 8, 14],
       [9, 11, 15],
       [12, 17, 20]
      ]
key = 14
search_in_a_sorted_matrix(mat, len(mat), len(mat[0]), key)
Output
Key 14 found at row 2, column 3

Spiral traversal

Python
def spiral_traversal(matrix):
    res = []
    if len(matrix) == 0:
        return res
    row_begin = 0
    row_end = len(matrix) - 1
    col_begin = 0
    col_end = len(matrix[0]) - 1

    while row_begin <= row_end and col_begin <= col_end:
        for i in range(col_begin, col_end+1):
            res.append(matrix[row_begin][i])
        row_begin += 1

        for i in range(row_begin, row_end+1):
            res.append(matrix[i][col_end])
        col_end -= 1

        if row_begin <= row_end:
            for i in range(col_end, col_begin-1, -1):
                res.append(matrix[row_end][i])
        row_end -= 1

        if col_begin <= col_end:
            for i in range(row_end, row_begin-1, -1):
                res.append(matrix[i][col_begin])
        col_begin += 1

    return res
Python
mat = [[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]]

print(spiral_traversal(mat))
Output
[1, 2, 3, 6, 9, 8, 7, 4, 5]

ARRAYS

Max subarray sum (only sum)

From "Competitive Programmer’s Handbook" - very interesting book: terse and to the point. We don’t reset current_sum to 0 because arr can be all negatives => the result will be the largest negative

Python
# O(n) while "traditional" solutions use 2 or 3 nested loops => O(n^2) or O(n^3)
def maximum_sum(arr):
        
    if len(arr)==0: return 0                                 # edge case
        
    max_sum = curr_sum = arr[0]
    
    for i in range(1, len(arr)):
        curr_sum = max(arr[i], curr_sum + arr[i])
        max_sum = max(max_sum, curr_sum)
    
    return max_sum

arr = [-1, 5, 3, -3, 5, -9, 5, ]
maximum_sum(arr)
Output
10

Max subarray sum (sum + indices)

Largest continuous sum in array of integers (positive and negative).

If arr = all positive => sum(arr).

Algo: start summing up in current_sum. After each addition check if current_sum > max_sum; update max_sum if yes. Keep adding as long as current_sum > 0. If current_sum < 0, start new current_sum (negative current_sum will only decrease sum of future sequence). We don’t reset current_sum to 0 because arr can be all negatives => the result will be the largest negative

Python
def large_cont_sum(arr): 
        
    if len(arr)==0: return 0                                 # edge case
        
    max_sum = curr_sum = arr[0]
    start, tstart, end = 0, 0, 0                             # store start & end indices
            
    for i in range(1, len(arr)):        
                
        # two-liner for this for loop if not keeping the start and end points
        #curr_sum = max(curr_sum + num, num)            # current sum = the higher of the two        
        #max_sum = max(curr_sum, max_sum)                  # max = the higher of current sum & current max
                
        if arr[i] > curr_sum + arr[i]:            
            curr_sum = arr[i]
            tstart = i
        else:
            curr_sum += arr[i]

        if curr_sum > max_sum:
            max_sum = curr_sum
            start = tstart
            end = i
        
    return max_sum, arr[start:end+1]
Python
a = [1, 2, -1, 3, 4, 10, 10, -10, -1]
b = [1, 2, -1, 3, 4, -1]
c = [-1, 1]

for arr in [a, b, c]:
    print('Largerst sum = {:2} in subarray {}'.format(*large_cont_sum(arr)))
Output
Largerst sum = 29 in subarray [1, 2, -1, 3, 4, 10, 10]
Largerst sum =  9 in subarray [1, 2, -1, 3, 4]
Largerst sum =  1 in subarray [1]

All unique non-contiguous pairs that sum up to k (unsorted array)

Insert and find operations of a set are O(1) => O(N).
Linear pass, for each elem: if (k - element) not in seen, add it to seen; if yes - found a pair

Python
def pair_sum(arr, k):
    
    if len(arr) < 2: return
        
    seen, output = set(), set()                                   # for tracking
        
    for num in arr:
        if k-num not in seen:                                     # add to set if not seen
            seen.add(num)
        else:            
            output.add( (min(num,k-num),  max(num,k-num)) )       # otherwise add pair    
    
    return '\n'.join(map(str,list(output)))
Python
print(pair_sum([1,3,2,2],4))
print()
print(pair_sum([1,9,2,8,3,7,4,6,5,5,13,14,11,14,1],10))
Output
(1, 3)
(2, 2)

(4, 6)
(5, 5)
(2, 8)
(1, 9)
(3, 7)

One non-contigous pair whose sum is closest to k (sorted array)

Examples:
Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10
Simple solution - every pair, time c. O(n2)
Efficient solution - O(n) time:
1) Initialize var diff as infinite (difference between pair and x) => need to find min diff
2) Initialize leftmost index l = 0
3) Initialize rightmost index r = n-1
3) While l < r
(a) If abs(arr[l] + arr[r] - k) < diff => update diff, result
(b) If (arr[l] + arr[r]) > k: r++, else l-- (sorted array)

Python
MAX_VAL = 1000000000
  
def closest_sum(arr, n, k):
    
    res = 0, 0                                                     # indices of correct pair    
    l, r, diff = 0, n-1, MAX_VAL                                   # left and right indexes, difference between pair sum and x 
        
    while l < r: 
        
        if abs(arr[l] + arr[r] - k) < diff:                        # is this pair closer than the prev one 
            res = l, r 
            diff = abs(arr[l] + arr[r] - k) 
      
        if arr[l] + arr[r] > k:                                    # if this sum greater, move to smaller, else to greater        
            r -= 1
        else:       
            l += 1
          
    return arr[res[0]], arr[res[1]] 


arr = [10, 22, 28, 29, 30, 40]
n = len(arr) 
k = 52
closest_sum( arr, n, k )
Output
(22, 30)

Max (min) sum of subarray of size k

Simple Solution - generate all subarrays of size k with time c. O(n*k)

Efficient Solution - sum of subarray (window) of size k is obtained in O(1) time using sum of previous subarray (window) of size k. Except for the first k-length subarray, compute sum by removing first element of last window and adding last element of current window

Time c. O(n), space c. O(1)

Python
# O(n)
def max_sum(arr, n, k):  
    
    if (n < k):                                 # edge case 
        return -1      
     
    res = 0
    for i in range(k):                          # sum of first window of size k
        res += arr[i] 
  
    # remaining sums - remove first elem of prev window, add last elem of current window
    curr_sum = res 
    for i in range(k, n):      
        curr_sum += arr[i] - arr[i-k] 
        res = max(res, curr_sum) 
  
    return res 
  

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] 
k = 4
n = len(arr) 
print(max_sum(arr, n, k))
Output
24

All contiguous subarrays with sum k (neg or pos)

Sub-case: k=0

Time c. O(n), space c. O(n)
Works for all cases (neg or pos); taken from here. The version on geeksforgeeks doesn't work for all of their own cases (their all-positives case)
How it works: * Maintain curr_sum of elems in arr[:i] * If it's k, found a subarray * Also, if curr_sum-k in hash_map => sum(arr[0:j]) was curr_sum-k, while arr[0:i] is curr_sum => sum([ j:i+1 ]) is k * Insert current sum into the hash map

Python
from collections import defaultdict

def findSubarraysWithSumK(arr, k):
    
    hash_map = defaultdict(list)                      # key = sum, value = end indices of subarray w/sum    
    res      = []                                     # subarrays
    curr_sum = 0

    for i in range( len(arr) ):

        curr_sum += arr[i]
        if curr_sum == k:
            res.append(arr[:i+1])                     # or res.append((0, i+1))

        if curr_sum-k in hash_map:                        
            for value in hash_map[ curr_sum-k ]:
                res.append( arr[ value+1:i+1 ] )      # or res.append((value+1, i+1))
                                
        hash_map[ curr_sum ].append(i)
                
    return res
Python
arr = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7
print(findSubarraysWithSumK(arr, k))
print()

# Geeksforgeeks cases that worked only for one of the solutions, but there was no solution that would cover all of these!
arr = [-10, 10, -12, 2, -2, -20, 10]
k = -10
print(findSubarraysWithSumK(arr, k))
print()

# previous cases from a) and b)
arr = [15, 2, 4, 8, 9, 5, 10, 23] 
k = 23  
print(findSubarraysWithSumK(arr, k))
print()

arr = [10, 2, -2, -20, 10]  
k = -10 
print(findSubarraysWithSumK(arr, k))
Output
[[3, 4], [3, 4, -7, 1, 3, 3], [1, 3, 3], [3, 3, 1]]

[[-10], [-10, 10, -12, 2], [-12, 2], [2, -2, -20, 10], [-20, 10]]

[[2, 4, 8, 9], [23]]

[[10, 2, -2, -20], [2, -2, -20, 10], [-20, 10]]

All non-contiguous triplets with sum < given value

Simple solution - brute force with three nested loops to get all triplets and their sums. Time c. = O(n^3)

res = 0  
for i in range( 0 ,n-2):  
    for j in range( i+1 ,n-1):  
        for k in range( j+1, n):  
            if (arr[i] + arr[j] + arr[k]) < sum:  
                res += 1

A O(n^2) solution is possible with below:

Python
# Time c. O(n^2); uses sort() and smart iteration
def count_triplets(arr, k): 
    
    arr.sort()
    n     = len(arr)
    count = 0      
    
    for i in range(n-2):                                      # first elem of triplet = arr[i]           
        
        start = i + 1                                         # corner elements
        end   = n - 1  
        
        while start < end:                                    # meet in the middle              
            if (arr[i] + arr[start] + arr[end]) >= k:         # decrease index
                end -= 1              
            else:
                count += (end-start)                # array sorted => (end-start) third elements w/sum < k
                start += 1
      
    return count 

arr = [5, 1, 3, 4, 7]  
sum = 11
print(count_triplets(arr, sum))
Output
3

All non-contiguous triplets with sum = 0 (sub-type of previous)

Python
# Time c. O(n^2), space c. O(1)
def findTriplets(arr):
        
    arr.sort()
    n     = len(arr)
    count = 0
        
    for i in range(0, n-2):
        
        start = i + 1
        end   = n - 1
                
        while start < end:
        
            if arr[i] + arr[start] + arr[end] == 0:
                count += 1
                start += 1
                end   -= 1
            
            elif (arr[i] + arr[start] + arr[end] < 0):          # If sum < 0, increment on left side
                start += 1
            
            else:                                               # if sum > 0, decrement on right side
                end -= 1
        
    return count

arr = [0, -1, 2, -3, 1]
findTriplets(arr)
Output
2

Equilibrium index of an array

Equilibrium index - sum of elements at lower indexes is equal to the sum of elements at higher indexes.
Example:

Input: A = [-7, 1, 5, 2, -4, 3, 0}] => Output: 3 because A[0] + A[1] + A[2] = A[4] + A[5] + A[6] Input: B = [1, 2, 3] => Output: -1

Time c.: O(n)

Python
def equilibrium(arr):  
    
    rightsum = sum(arr)
    leftsum  = 0
    
    for i, num in enumerate(arr):
        rightsum -= num
        if leftsum == rightsum: 
            return i
        leftsum += num       
    
    return -1 
      

arr = [-7, 1, 5, 2, -4, 3, 0] 
print ('First equilibrium index is ', 
       equilibrium(arr))
Output
First equilibrium index is  3

Find the Missing Element

Python
def finder(arr1, arr2):
    
    res = 0 
    for num in arr1 + arr2: 
        res ^= num 
        print(res, end=' ')        # to see the result of XOR
        
    return res

Other solutions: * go through every element in second array and check if it's in the first array - O(n**2) as 2 for loops; mind duplicates! * sorth both arr, iterate simulataneously, once iterators are not equal - missing number; O(NlogN) * using hashing (O(n)):

Python
from collections import defaultdict

def finder2(arr1, arr2): 
    
    d = defaultdict(int)            # dict of counts    
    for num in arr2:                # count for elements in arr2
        d[num]+=1    
   
    for num in arr1:                # check if num not in dict
        if d[num]==0: 
            return num        
        else: d[num]-=1             # otherwise, decrease count
Python
arr1 = [5,4,4,7,7]
arr2 = [5,4,7,7]

print('Missing per finder1:', finder(arr1,arr2))
print()
print('\nMissing per finder2:', finder2(arr1,arr2))
Output
Missing per finder1: 4

5 1 5 2 5 0 4 3 4 
Missing per finder2: 4
Python
arr1, arr2 = [1,2,3,4,5,6,7], [5,7,2,1,4,6]
print('Missing per finder1:', finder(arr1,arr2))
print()
print('\nMissing per finder2:', finder2(arr1,arr2))
Output
Missing per finder1: 3

1 3 0 4 1 7 0 5 2 0 1 5 3 
Missing per finder2: 3

How it works: XOR works in binary, but for decimals XOR of a number with itself results in 0 => x ^ x = 0, then y ^ 0 = y
Example: if we have [5,8,12,5,12] (one element doesn't have a pair as in our case):
* 1st iter: res = 0^5 = 5 * 2nd iter: res = 5^8 * 3rd iter: res = 5^8^12 * 4th iter: res = 5^8^12^5 = 0^8^12 = 8^12 * 5th iter: res = 8^12^12 = 8^0 = 8

Arrays - supplementary

Partition problem 1

Determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same 1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2

Python
# Recursive, t. complexity = 2**n
def isSubsetSum(arr, n, sum_):
    # return true if there is a subset of arr[] with sum = target sum
    
    # Base cases
    if sum_ == 0:
        return True
    if n == 0 and sum_ != 0:
        return False
 
    # If last elem > sum, ignore it
    if arr[n-1] > sum_:
        return isSubsetSum(arr, n-1, sum_)
 
    # else, check if sum is obtained by (a) including last elem, (b) excluding it 
    return isSubsetSum(arr, n-1, sum_) or isSubsetSum(arr, n-1, sum_-arr[n-1])
Python
# t.c.= O(n*sum)
def isSubsetSum_dp(arr, n):    
    
    sum_ = 0
    for i in range(n) :
        sum_ += arr[i]
    if sum_ % 2 != 0:                                        #if sum is odd, cannot find two subsets
        return 0    
    
    part = [0] * ((sum_ // 2) + 1)                           #initialize with 0 (False)
        
    # part[j] = true if there is a subset with sum equal to j, otherwise false
    for i in range(n):                                       # fill in bottom up        
        for j in range(sum_ // 2, arr[i]-1, -1) :
           
            if (part[j - arr[i]] == 1 or j == arr[i]):       # elem to be included in sum cannot be > sum
                part[j] = 1                                  # can sum-arr[i] be formed from subset before indecx i
 
    return part[sum_ // 2]
Python
arr = [3, 1, 5, 9, 12, 1, 1]
n   = len(arr)

sum_ = 0
for i in range(0, n):
    sum_ += arr[i]
if sum_ % 2 != 0:                                            #if sum is odd, cannot find two subsets
    print("Can't be done")

res = isSubsetSum(arr, n, sum_ // 2)

if res:
    print("Can be done")
else:
    print("Can't be done")
Output
Can be done
Python
arr = [3, 1, 5, 9, 12, 1, 1]
n   = len(arr)
isSubsetSum_dp(arr, n)
Output
1

Partition problem 2 (subtype of 1)

Partition a set into two subsets such that the difference of subset sums is minimum

Python
# t.c.= O(2**n)
def findMinRec(arr, i, sumCalculated, sumTotal):
  
    # If reached last elem, sum of one subset = sumCalculated,
    # sum of other subset = (sumTotal-sumCalculated). Return absolute difference
    if i == 0:
        return abs( (sumTotal-sumCalculated) - sumCalculated )
  
    # For each arr[i], (1) we can exclude it from first set, (2) we can include it
    # return min of two choices
    return min( findMinRec( arr,
                            i-1,
                            sumCalculated + arr[i-1],
                            sumTotal
                          ),
                findMinRec( arr,
                            i-1,
                            sumCalculated,
                            sumTotal
                          )
              )


def findmin_recursive(arr,  n):
  
    # total sum of arr
    sumTotal = 0
    for i in range(n):
        sumTotal += arr[i]

    return findMinRec(arr, n, 0, sumTotal)
Python
# t.c,= O(n*sum)
def findmin(arr, n):
    pass
Python
arr = [3, 1, 4, 2, 2, 1, 125]
n = len(arr)

print("Minimum possible difference =", findmin_recursive(arr, n))
#print("Minimum possible difference =", findmin(arr, n))
Output
Minimum possible difference = 112

K’th Smallest/Largest Element in Unsorted Array

O(N logN) solution - quicksort then get kth element
Other solutions are either long or have no Python implementation

Convert array in zigzag fashion

Array of DISTINCT elements, rearrange its elements in zig-zag fashion in O(n) time: a < b > c < d > e < f

A traditional approach would first sort, then do the zigzag - O(n logn). To convert to O(n): * Maintain an alternating flag representing the order (< or >). * If current 2 elements are not in that order, swap them; otherwise not

Python
# Time c. = O(n)
def zigzag(arr):
        
    # Flag true, then "<" is expected; else ">" is expected. First expected "<" 
    flag = True
        
    for i in range(len(arr) - 1): 
         
        if flag is True:
                        
            # If A > B > C, then swap B and C 
            if arr[i] > arr[i+1]: 
                arr[i],arr[i+1] = arr[i+1],arr[i] 
             
        else: 
            # If A < B < C, then swap B and C     
            if arr[i] < arr[i+1]:
                arr[i],arr[i+1] = arr[i+1],arr[i]
                                
        flag = bool(1 - flag)
                
    print(arr)

arr = [4, 3, 7, 8, 6, 2, 1] 
zigzag(arr)
Output
[3, 7, 4, 8, 2, 6, 1]

Longest subarray with contiguous elements

Array of DISTINCT integers, find length of the longest subarray consisting of a continuous sequence of numbers.

Examples: [10, 12, 11] => 3; [14, 12, 11, 20] => 2

Trick: if all elements are distinct, then a subarray has contiguous elements if and only if the difference between max and min elements in subarray = difference between last and first indexes of subarray => keep track of min and max element in every subarray

Python
def min(x, y): 
    return x if (x < y) else y 


def max(x, y): 
    return x if (x > y) else y 


def findLength(arr):
      
    # Initialize result 
    max_len = 1
    for i in range(len(arr) - 1):
      
        # Initialize min and max for all subarrays starting with i 
        mn = arr[i]
        mx = arr[i]
  
        # All subarrays starting w/i and ending w/j 
        for j in range(i + 1, len(arr)):
          
            # Update min and max, if needed 
            mn = min(mn, arr[j]) 
            mx = max(mx, arr[j]) 
  
            # If current subarray has all contiguous elements
            if ((mx - mn) == j - i): 
                max_len = max(max_len, mx - mn + 1)
          
    return max_len 
  
arr = [1, 56, 58, 57, 90, 92, 94, 93, 91, 45] 
print("Length of longest contiguous subarray:", findLength(arr))
Output
Length of longest contiguous subarray: 5

Smallest positive integer that cannot be represented as sum of any subset of a given array

Sorted non-decreasing array of positive numbers - time c. O(n).

Examples: {1, 3, 6, 10, 11, 15} => 2; {1, 1, 1, 1} => 5; {1, 1, 3, 4} => 10; {1, 2, 5, 10, 20, 40} => 4

Simple Solution: start from value 1 and check all values one by one if they can sum to values in the given array - reduces to subset sum problem (well known NP Complete Problem).

Better solution: initialize result as 1 (smallest possible results) and traverse => two possibilities for next element at index i:

Python
def findSmallest(arr, n):  
    res = 1                                         # initialize result    
    for i in range(n):                              # traverse and increment 'res' if arr[i] <= 'res'
        if arr[i] <= res: 
            res = res + arr[i] 
        else: 
            break                        
    return res


arr1 = [1, 3, 4, 5] 
n1 = len(arr1) 
print(findSmallest(arr1, n1)) 
  
arr2= [1, 2, 6, 10, 11, 15] 
n2 = len(arr2) 
print(findSmallest(arr2, n2)) 
  
arr3= [1, 1, 1, 1] 
n3 = len(arr3) 
print(findSmallest(arr3, n3)) 
  
arr4 = [1, 1, 3, 4] 
n4 = len(arr4) 
print(findSmallest(arr4, n4))
Output
2
4
5
10

Maximum j – i such that arr[j] > arr[i]

Geeksforgeeks
Example: {34, 8, 10, 3, 2, 80, 30, 33, 1} => 6 (j = 7, i = 1)
Simple solution = two nested loops, O(n^2)
Better solution - O(n logn)
Best solution - time O(n), space O(n)

Python
# Better solution - O(n logn)
def max_diff(arr):

    #To store the index of an element. 
    index = dict()
    n = len(arr)
    for i in range(n): 
        if a[i] in index: 

            #append to list (for duplicates) 
            index[a[i]].append(i)   
        else: 

            #if first occurrence 
            index[a[i]] = [i]    

    #sort the input array 
    a.sort()      
    maxDiff = 0

    # Temporary variable to keep track of minimum i 
    temp = n      
    for i in range(n): 
        if temp > index[a[i]][0]: 
            temp = index[a[i]][0] 
        maxDiff = max(maxDiff, index[a[i]][-1]-temp) 

    return maxDiff


# Output: 6  (j = 7, i = 1)
a = [34, 8, 10, 3, 2, 80, 30, 33, 1]
print(max_diff(a))


#Output: 8 ( j = 8, i = 0)
a = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]
print(max_diff(a))

#Output: 5  (j = 5, i = 0)
a = [1, 2, 3, 4, 5, 6]
print(max_diff(a))

#Output: 0 
a = [6, 5, 4, 3, 2, 1]
print(max_diff(a))
Output
6
8
5
0
Python
# Best solution O(n)
def max(a, b):
    return a if a > b else b
    
    
def min(a,b):
    return a if a < b else b


def max_diff_best(arr):
    
    n = len(arr)
    maxDiff = 0
    LMin = [0] * n
    RMax = [0] * n
  
    # LMin[i] stores min(arr[0:i+1] = from 0 to i)  
    LMin[0] = arr[0] 
    for i in range(1, n): 
        LMin[i] = min(arr[i], LMin[i - 1]) 
  
    # RMax[j] stores max(arr[j:n] = from j to n-1 
    RMax[n - 1] = arr[n - 1] 
    for j in range(n - 2, -1, -1): 
        RMax[j] = max(arr[j], RMax[j + 1]); 
  
    # Traverse both arrays left -> right, find optimum j - i. Similar to merge() of MergeSort 
    i, j = 0, 0
    maxDiff = -1
    while (j < n and i < n): 
        if (LMin[i] < RMax[j]): 
            maxDiff = max(maxDiff, j - i) 
            j = j + 1
        else: 
            i = i+1
  
    return maxDiff 


# Output: 6  (j = 7, i = 1)
a = [34, 8, 10, 3, 2, 80, 30, 33, 1]
print(max_diff_best(a))


#Output: 8 ( j = 8, i = 0)
a = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]
print(max_diff_best(a))

#Output: 5  (j = 5, i = 0)
a = [1, 2, 3, 4, 5, 6]
print(max_diff_best(a))

#Output: -1 
a = [6, 5, 4, 3, 2, 1]
print(max_diff_best(a))
Output
6
8
5
-1

Find kth Smallest Value Among m Sorted Arrays (FB)

You have m arrays of sorted integers. The sum of the array lengths is n. Find the kth smallest value of all the values.

For exmaple, if m = 3, n=8, and we have these lists:

list1 = [3,6,9] list2 = [8,15] list3 = [4, 7, 12]

if k = 1, then returned value should be 3 if k = 2, then returned value should be 4 if k = 3, then returned value should be 6

brute foce: combine all arrays and find kth smallest: O(n)

Python
# time c. nlog(n), space c. O(n)
def find_kth(arr, k):
    
    for idx, array in enumerate(arr):
        if not array:
            arr.remove(idx)
    
    if not arr:
        raise exception
        #return None

    array_lengths = [len(item) for item in arr]    
    temp_array = []
    
    for i in range(k):
        min_len = min(array_lengths)
        if k == min_len:
            idx = array_lengths.index(min_len)
            arr.remove(idx)            
        temp_array.extend([item[i] for item in arr])
        
    temp_array = sorted(temp_array)      
        
        
    return temp_array[k-1]
    
list1 = [3,6,9]
list2 = [8,15]
list3 = [4, 7, 12]

arr = [ list1, list2, list3, ]
k   = 2
find_kth(arr, k)
Output
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [24], in <cell line: 33>()
     31 arr = [ list1, list2, list3, ]
     32 k   = 2
---> 33 find_kth(arr, k)

Input In [24], in find_kth(arr, k)
     17     if k == min_len:
     18         idx = array_lengths.index(min_len)
---> 19         arr.remove(idx)            
     20     temp_array.extend([item[i] for item in arr])
     22 temp_array = sorted(temp_array)      

ValueError: list.remove(x): x not in list

Code testing

Types of tests

Basics of unittest library

What you need for a unit test:
* test fixture - preparations for test: creating temporary or proxy databases,
directories, or starting a server. * test case - individual unit of testing, checks response to a particular set of inputs
(base class, TestCase, to create new test cases). * test suite - collection of test cases, test suites, or both: to aggregate tests together. * test runner - orchestrates the execution of tests and provides the outcome.

Additional

Main assertions: assertEqual(), assertTrue(), assertFalse(), assertRaises()
unittest.main() - command-line interface to run the test script
Test discovery via CLI finds all unittest files in the directory structure
Unittest can skip individual tests and whole classes of tests, marking a test as
an “expected failure,” (shouldn’t be counted as a failure on a TestResult)
Unittest can distinguish small differences in tests (e.g. in some parameters)
using the subTest() context manager. Doctest can test docstrings

Python
#%tb
import unittest

class TestStringMethods(unittest.TestCase):

    def test_upper(self):
        self.assertEqual('foo'.upper(), 'FOO')

    def test_isupper(self):
        self.assertTrue('FOO'.isupper())
        self.assertFalse('Foo'.isupper())

    def test_split(self):
        s = 'hello world'
        self.assertEqual(s.split(), ['hello', 'world'])
        # check that s.split fails when the separator is not a string
        with self.assertRaises(TypeError):
            s.split(2)

# entry point for running test
if __name__ == '__main__' and '__file__' in globals():
    unittest.main()
Python
import unittest
# Class containing unit tests
class TestStringMethods(unittest.TestCase):
    def setUp(self):
        # Setup required resources
        self.string = "hello world"
        self.empty_string = ""
        self.whitespace_string = "   "
        self.numeric_string = "12345"
    def tearDown(self):
        # Clean up resources
        pass
    def test_upper(self):
        self.assertEqual(self.string.upper(),
                         "HELLO WORLD")    
    def test_isupper(self):
        self.assertFalse(self.string.isupper())
        self.assertTrue("HELLO".isupper())    
    def test_islower(self):
        self.assertTrue(self.string.islower())
        self.assertFalse("Hello".islower())       
    def test_split(self):
        self.assertEqual(self.string.split(),
                         ["hello", "world"])
        with self.assertRaises(TypeError):
            s.split(2)
# Entry point for running the tests
if __name__ == '__main__':
    unittest.main()
Python
                        
    def test_isspace(self):
        self.assertTrue(self.whitespace_string.isspace())
        self.assertFalse(self.string.isspace())
        self.assertFalse(self.empty_string.isspace())
    
    def test_isdigit(self):
        self.assertTrue(self.numeric_string.isdigit())
        self.assertFalse(self.string.isdigit())

    def test_empty_string(self):
        self.assertEqual(self.empty_string.upper(), "")
        self.assertEqual(self.empty_string.split(), [])
        self.assertTrue(self.empty_string.islower())

pytest

Third-party unittest framework with a lighter-weight syntax for writing tests.
In example below: we drop the TestCase, any use of classes, and the command-line entry point

Python
import pytest

# Fixture for setup and teardown
@pytest.fixture
def string_data():
    data = {
        "string": "hello world",
        "empty_string": "",
        "whitespace_string": "   ",
        "numeric_string": "12345"
    }
    return data

# Test functions
def test_upper(string_data):
    assert string_data["string"].upper() == "HELLO WORLD"

def test_isupper(string_data):
    assert not string_data["string"].isupper()
    assert "HELLO".isupper()

def test_islower(string_data):
    assert string_data["string"].islower()
    assert not "Hello".islower()

def test_split(string_data):
    assert string_data["string"].split() == ["hello", "world"]
    assert string_data["string"].split('o') == ["hell", " w", "rld"]

def test_isspace(string_data):
    assert string_data["whitespace_string"].isspace()
    assert not string_data["string"].isspace()
    assert not string_data["empty_string"].isspace()

def test_isdigit(string_data):
    assert string_data["numeric_string"].isdigit()
    assert not string_data["string"].isdigit()

def test_empty_string(string_data):
    assert string_data["empty_string"].upper() == ""
    assert string_data["empty_string"].split() == []
    assert string_data["empty_string"].islower()

# Run the tests
if __name__ == '__main__':
    pytest.main()

Type Hints

Python
from typing import Optional

# var of specified type or None
def get_user_email(user_id: int) -> Optional[str]:
    emails = {1: "alice@example.com", 4: "bob@example.com"}
    return emails.get(user_id, None)

email = get_user_email(1)
print(email)              # Output: alice@example.com

email = get_user_email(2)
print(email)              # Output: None
Python
from typing import Any

# any type. E.g. Dict[str, Any]
def print_value(value: Any) -> None:
    print(f"Value: {value}")

print_value(42)         # Output: Value: 42
print_value("Hello")    # Output: Value: Hello
print_value([1, 2, 3])  # Output: Value: [1, 2, 3]
Python
from typing import Union

# var is one of several types
def process_data(data: Union[int, str]) -> str:
    if isinstance(data, int):
        return f"Processed integer: {data}"
    elif isinstance(data, str):
        return f"Processed string: {data}"
Python
from typing import Callable

# var is func or method
def execute_function(
    func: Callable[[int, int], int],
    a: int,
    b: int,
) -> int:
    return func(a, b)

def add(x: int, y: int) -> int:
    return x + y

result = execute_function(add, 5, 3)
print(result)  # Output: 8

REFERENCES

Google Interview Questions (Geekstogeeks)

General: https://www.geeksforgeeks.org/google-interview-preparation/
More coding challanges from Google: https://practice.geeksforgeeks.org/explore/?company%5B%5D=Google&page=1