Interview

01_DBS.md

DBS (Development Bank of Singapore) Data Analyst Interview

1. Python puzzle

   • Given a $2 \times 1$ non-negative integer array $\vec{a}$ and a $1 \times n$ integer array $\vec{b}$, write a function to return a $2 \times n$ logical matrix $x_{ij}$ such that $\sum_{j=1}^{n}x_{ij} = a_i$ and $\sum_{i=1}^{2}x_{ij} = b_j$. If there is no working matrix, please return string "impossible" (15 mins).
   • What is logical matrix? This is a matrix that $x_{ij} \in {0,1}$
   • Example: $\vec{a} = \begin{bmatrix} 3 \ 2\end{bmatrix}$, $\vec{b} = \begin{bmatrix} 2 & 1 & 1 & 0 & 1\end{bmatrix}$, one possible matrix is $\begin{bmatrix} 1 & 1 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 1\end{bmatrix}$
   • Solution:

     import numpy as np
     
     def logic_matrix(a, b):
         # initialize
         x = np.zeros((len(a), len(b)))
     
         for i in range(len(a)):
             if a[i][0] > len(b):
                 print("a[i][0] > len(b)")
                 return "impossible"
             
             for j in range(len(b)):
                 if b[j] > len(a):
                     print("b[j] > len(a)")
                     return "impossible"
                 
                 # Sum of all columns in a row
                 col_sum = x.sum(axis=1)
                 
                 # Sum of all rows in a column
                 row_sum = x.sum(axis=0)
                 
                 # logic
                 if (b[j] > 0) and (row_sum[j] < b[j]) and (col_sum[i] < a[i][0]):
                     x[i][j] = 1
                     
         # Final check
         col_sum = x.sum(axis=1).reshape(len(a),1)
         row_sum = x.sum(axis=0)
         
         if not np.array_equal(row_sum, b):
             print("row_sum != b")
             print(f"x: \n{x}")
             print(f"row_sum: \n{row_sum}")
             print(f"b: \n{b}")
             return "impossible"
         if not np.array_equal(col_sum, a):
             print("col_sum != a")
             print(f"x: \n{x}")
             print(f"col_sum: \n{col_sum}")
             print(f"a: \n{a}")
             return "impossible"
     
         return x
     
     a = np.array([
         [3],
         [2]
     ])
     
     b = np.array([2, 1, 1,  0, 1])
     
     print(logic_matrix(a, b))