Sparse Vector and Matrix Operations
Bloomberg LP● HardFULLTIMEPHONE SCREENProblem statement
Maintain one sparse vector and one sparse matrix. Unset entries are zero, and setting an entry to zero removes it from sparse storage. Process these commands:
VSET index value,VGET index.VDOT k i1 v1 ... ik vk: dot the stored vector with the supplied sparse vector ofkdistinct index-value pairs.MSET row column value,MGET row column.RDOT row k i1 v1 ... ik vk: dot one stored matrix row with a supplied sparse vector over columns.CDOT column k i1 v1 ... ik vk: dot one stored matrix column with a supplied sparse vector over rows.
Return the results of GET and DOT commands in order. Store the matrix with synchronized row and column sparse views.
Function
processSparseOperations(vectorLength: int, rowCount: int, columnCount: int, operations: String[]) → long[]Examples
Example 1
vectorLength = 1000000rowCount = 1000columnCount = 1000operations = ["VSET 5 7","VSET 20 -2","VGET 5","VDOT 3 5 4 6 9 20 3","MSET 2 5 10","MSET 2 8 -1","MGET 2 8","RDOT 2 2 5 3 8 4","CDOT 5 2 2 6 9 7"]return = [7,22,-1,26,60]The vector dot is 7×4 + (-2)×3 = 22. Row 2 dots to 10×3 + (-1)×4 = 26, and column 5 contributes 10×6 = 60.
Example 2
vectorLength = 10rowCount = 10columnCount = 10operations = ["VSET 1 5","VSET 1 0","VGET 1","MSET 3 4 9","MSET 3 4 0","MGET 3 4","RDOT 3 1 4 7","CDOT 4 1 3 7"]return = [0,0,0,0]Zero assignments remove both vector and synchronized matrix entries.
Constraints
1 <= vectorLength, rowCount, columnCount <= 10^9.1 <= operations.length <= 50000.- All indices are in range; each sparse operand lists distinct indices and
kmatches its pair count. - Values are signed 32-bit integers. Every product, intermediate accumulated dot-product sum, and returned value fits a signed 64-bit integer.