Learn and practice the Hash Maps and Knowing What to Track patterns to solve coding interview problems.

Speedrun the Meta Coding Interview: Top Problems in Python

Hash maps are powerful data structures that enable programmers to design more efficient solutions for certain problems. After practicing solving problems using hash maps, we will move to the more general problem-solving skill of figuring out the key characteristics of a problem, using various techniques to track them, in order to design remarkably efficient solutions for seemingly complex problems.

Hashing and Tracking

What is the result of the dot product of the sparse vectors `nums1` $= [0,4,0,0,0,0,7]$ and `nums2` $= [3,0,0,0,0,5,0]$?

What is the result of the dot product of the sparse vectors <code>nums1</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>4</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>7</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [0,4,0,0,0,0,7]</annotation></semantics></math>=[0,4,0,0,0,0,7] and <code>nums2</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>3</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>5</mn><mo separator="true">,</mo><mn>0</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [3,0,0,0,0,5,0]</annotation></semantics></math>=[3,0,0,0,0,5,0]?

Given `nums1` $= [2,0,0,0,5]$ and `nums2` $= [1,0,0,0,3]$, what is the output of their dot product?

Given <code>nums1</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>2</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>5</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [2,0,0,0,5]</annotation></semantics></math>=[2,0,0,0,5] and <code>nums2</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>1</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>3</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [1,0,0,0,3]</annotation></semantics></math>=[1,0,0,0,3], what is the output of their dot product?

What is the dot product of the vectors `nums1` $= [1,2,0,4]$ and `nums2` $= [0,0,3,0]$?

What is the dot product of the vectors <code>nums1</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>4</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [1,2,0,4]</annotation></semantics></math>=[1,2,0,4] and <code>nums2</code> <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>=</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo separator="true">,</mo><mn>3</mn><mo separator="true">,</mo><mn>0</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">= [0,0,3,0]</annotation></semantics></math>=[0,0,3,0]?

Dot Product of Two Sparse Vectors

Dot Product of Two Sparse Vectors

class SparseVector:
    def __init__(self, nums):
        # Write your code here
        pass             

    def dot_product(self, vec):
        # Write your code here
        return  -1

Help me debug only the function(s) `__init__, dot_product`. I don't need the corrected code, just some hints on how to use the "Hash Maps" pattern to solve this problem. I don't want explanations. Just provide me with the exact error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the provided failed test case. Don't give me the corrected code. Just some hints on how to use the "Hash Maps" pattern to improve my solution or fix the error. First, check whether the given pattern is used or not. If yes, then Just provide me the exact error that helps me run the code successfully on the test cases provided.

Your current task is to review only the `__init__, dot_product` function(s) and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function `__init__, dot_product`. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, answer the following questions: Is the "Hash Maps" pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function(s) `__init__, dot_product`. While calculating time complexity, include the time complexity of built-in Python functions invoked by the code. The answer should be to the point and in a few lines.

Please provide a brief space complexity analysis of the function(s) `__init__, dot_product`. While calculating space complexity, include the space complexity of built-in Python functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The answer should be to the point and in a few lines.

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        class SparseVector:
            def __init__(self, nums):
                self.hashmap = {}
                for i, n in enumerate(nums):
                    if n != 0:
                        self.hashmap[i] = n 

            def dot_product(self, vec):
                sum = 0
                for i, n in self.hashmap.items():
                    if i in vec.hashmap:
                        sum += n * vec.hashmap[i]
                return sum
        
        v1 = SparseVector(self.__inputs[0])
        v2 = SparseVector(self.__inputs[1])
        expected = v1.dot_product(v2)
        # multiple outputs will be added at each index respectively for a single test_case

        expected_outputs = []
        expected_outputs.append(expected)
            
        actual = self.__actual_outputs[0]

        if json.dumps(expected) == json.dumps(actual):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

from sparse_vector import SparseVector


def main(input_1, input_2):
    v1 = SparseVector(input_1)
    v2 = SparseVector(input_2)
    ans = v1.dot_product(v2)

    return ans



dot_product_of_two_sparse_vectors.yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [1,0,0,0,0,2,3]
    - 2 : [0,0,4,0,0,0,5]
    output: 
    - 1 : 15
  - name: "testcase 2"
    inputs:
    - 1: [1,0,0,0,0,0,5]
    - 2: [0,6,0,0,0,7,0]
    output:
    - 1 : 0
  - name: "testcase 3"
    inputs:
    - 1: [1,2,0,4]
    - 2: [0,0,3,0]
    output:
    - 1 : 0
  - name: "Test Case 1 (Edge Case Minimum Length Vectors)"
    inputs:
      - 1:  [27]
      - 2:  [82]
    output:
      - 1: 2214
  - name: "Test Case 37 (Edge Case All Elements Non Zero)"
    inputs:
      - 1:  [82, 56, 58, 67, 39, 98, 77, 100, 31, 30, 99, 19, 74, 58, 12, 57, 62, 92, 32, 18, 38, 56, 60, 62, 89, 66, 22, 100, 22, 68, 84, 6, 50, 53, 30, 62, 59, 82, 92, 34, 34, 98, 88, 53, 36, 4, 39, 28, 77, 21, 41, 83, 85, 40, 39, 33, 33, 31, 53, 99, 94, 14, 76, 80, 42, 88, 93, 34, 31, 77, 29, 43, 82, 80, 17, 81, 13, 67, 5, 81, 100, 24, 77, 57, 71, 26, 67, 25, 41, 50, 54, 58, 11, 30, 1, 82, 47, 98, 48, 23, 12, 2, 99, 49, 30, 50, 27, 5, 55, 36, 46, 13, 33, 52, 39, 95, 80, 70, 50, 58, 82, 43, 3, 45, 77, 38, 1, 34, 13, 44, 88, 33, 27, 72, 10, 8, 30, 16, 9, 15, 59, 24, 83, 40, 15, 40, 76, 3, 84, 38, 90, 63, 76, 86, 25, 13, 30, 68, 66, 81, 18, 38, 80, 78, 80, 38, 68, 30, 24, 41, 67, 78, 57, 6, 61, 3, 35, 57, 92, 34, 100, 67, 13, 44, 40, 46, 96, 92, 45, 80, 9, 14, 46, 91, 26, 73, 27, 49, 79, 66, 63, 67, 95, 8, 59, 34, 2, 92, 5, 47, 32, 8, 68, 36, 47, 25, 18, 85, 39, 92, 93, 50, 12, 20, 98, 18, 20, 38, 81, 38, 43, 72, 75, 38, 16, 3, 78, 68, 17, 82, 83, 94, 89, 45, 31, 59, 96, 67, 56, 46, 38, 63, 82, 19, 96, 24, 25, 37, 10, 64, 98, 90, 68, 73, 28, 77, 49, 76, 29, 82, 40, 54, 23, 50, 39, 3, 56, 9, 14, 2, 15, 40, 4, 40, 11, 36, 88, 94, 35, 74, 68, 1, 54, 20, 25, 3, 59, 18, 21, 8, 62, 20, 32, 91, 71, 8, 6, 69, 26, 5, 39, 5, 79, 82, 36, 35, 26, 57, 10, 27, 67, 65, 70, 14, 52, 27, 87, 38, 83, 80, 25, 90, 42, 63, 94, 46, 57, 63, 71, 62, 19, 30, 54, 99, 73, 84, 86, 51, 45, 61, 64, 2, 88, 100, 68, 39, 50, 48, 56, 69, 28, 94, 29, 20, 58, 53, 26, 44, 71, 65, 10, 58, 94, 71, 99, 17, 10, 61, 3, 16, 20, 55, 61, 44, 26, 16, 81, 32, 75, 44, 19, 38, 7, 94, 3, 81, 63, 73, 10, 91, 26, 95, 4, 57, 32, 1, 11, 76, 41, 98, 6, 57, 24, 57, 13, 89, 51, 5, 74, 100, 63, 10, 84, 70, 33, 55, 74, 10, 5, 80, 35, 14, 60, 71, 15, 8, 96, 18, 89, 7, 69, 5, 54, 77, 3, 20, 8, 98, 65, 68, 13, 52, 64, 98, 85, 7, 13, 13, 1, 16, 13, 18, 35, 50, 21, 38, 52, 40, 23, 44, 28, 52, 35, 14, 49, 73, 88, 8, 11, 52, 44, 24, 73, 91, 18, 7, 81, 14, 62, 57, 44, 9, 32, 2, 36, 80, 61, 42, 55, 44, 96, 58, 50, 2, 20, 98, 15, 87, 16, 24, 66, 80, 77, 31, 90, 91, 34, 14, 93, 25, 25, 11, 98, 16, 40, 41, 87, 90, 6, 44, 56, 98, 99, 49, 60, 80, 7, 15, 35, 1, 16, 44, 99, 44, 84, 10, 70, 53, 14, 13, 69, 27, 57, 11, 13, 55, 30, 89, 30, 5, 88, 54, 60, 41, 92, 74, 55, 66, 88, 97, 10, 76, 98, 79, 91, 29, 70, 87, 13, 94, 90, 7, 56, 29, 82, 87, 17, 63, 71, 4, 45, 78, 37, 76, 32, 68, 99, 63, 15, 7, 83, 49, 74, 10, 93, 53, 84, 99, 56, 86, 5, 94, 66, 26, 31, 14, 81, 41, 3, 82, 58, 72, 91, 60, 78, 57, 77, 41, 77, 15, 94, 75, 9, 44, 91, 4, 37, 32, 48, 38, 32, 32, 78, 100, 65, 98, 13, 97, 87, 24, 31, 88, 44, 54, 75, 57, 77, 54, 33, 11, 25, 53, 6, 96, 68, 45, 42, 43, 10, 64, 50, 76, 13, 53, 59, 95, 94, 80, 3, 54, 57, 26, 41, 43, 64, 12, 37, 29, 48, 48, 93, 53, 56, 70, 51, 30, 41, 28, 42, 56, 80, 68, 5, 55, 77, 99, 53, 99, 3, 14, 59, 35, 98, 33, 92, 27, 28, 94, 43, 57, 33, 75, 96, 20, 40, 100, 5, 7, 60, 66, 33, 88, 21, 86, 1, 38, 5, 16, 47, 52, 67, 74, 47, 3, 42, 34, 41, 25, 80, 96, 91, 56, 93, 70, 36, 24, 8, 83, 6, 85, 97, 4, 30, 47, 77, 41, 7, 27, 33, 35, 8, 40]
      - 2:  [83, 50, 60, 46, 59, 16, 76, 71, 56, 87, 39, 5, 93, 97, 100, 96, 26, 32, 10, 80, 41, 69, 27, 6, 35, 55, 41, 41, 26, 91, 42, 29, 49, 27, 78, 11, 48, 50, 80, 93, 12, 94, 27, 20, 8, 31, 5, 77, 76, 59, 29, 5, 67, 10, 58, 90, 63, 11, 99, 32, 59, 95, 73, 78, 42, 58, 5, 30, 89, 87, 59, 36, 72, 78, 84, 16, 66, 9, 34, 88, 82, 99, 61, 66, 45, 67, 54, 77, 49, 99, 80, 89, 67, 44, 53, 87, 41, 13, 47, 30, 24, 4, 80, 33, 82, 11, 41, 6, 42, 19, 44, 69, 9, 25, 41, 1, 49, 23, 10, 34, 84, 1, 83, 79, 86, 59, 37, 72, 54, 47, 22, 38, 66, 87, 69, 86, 36, 15, 33, 75, 2, 51, 45, 63, 37, 94, 73, 99, 21, 41, 24, 89, 59, 50, 75, 21, 7, 1, 74, 31, 42, 23, 96, 89, 16, 58, 92, 15, 79, 20, 76, 25, 62, 84, 50, 85, 18, 75, 10, 29, 8, 48, 32, 59, 4, 4, 77, 55, 53, 59, 72, 57, 44, 47, 30, 99, 64, 37, 1, 59, 8, 49, 70, 99, 47, 89, 99, 75, 40, 30, 9, 11, 27, 64, 61, 60, 97, 59, 3, 30, 67, 40, 51, 80, 96, 93, 71, 71, 48, 93, 52, 6, 65, 48, 5, 75, 31, 43, 98, 12, 47, 48, 27, 85, 81, 10, 42, 33, 95, 46, 95, 4, 71, 45, 5, 5, 23, 54, 91, 19, 59, 37, 63, 60, 89, 26, 59, 34, 91, 15, 69, 51, 20, 2, 100, 95, 80, 48, 26, 53, 69, 47, 39, 9, 99, 83, 41, 69, 57, 86, 58, 35, 13, 42, 61, 86, 79, 65, 95, 55, 41, 98, 11, 9, 77, 19, 91, 19, 54, 9, 92, 76, 29, 22, 27, 33, 2, 93, 14, 97, 56, 74, 3, 9, 48, 66, 67, 22, 78, 83, 70, 60, 63, 40, 7, 87, 40, 80, 47, 27, 50, 61, 66, 86, 53, 2, 23, 84, 83, 50, 19, 84, 79, 81, 62, 43, 26, 53, 69, 64, 58, 24, 4, 15, 54, 86, 86, 36, 42, 76, 16, 14, 1, 81, 74, 52, 52, 24, 34, 12, 100, 89, 70, 78, 47, 95, 40, 61, 3, 85, 34, 51, 7, 85, 44, 1, 78, 23, 42, 88, 50, 3, 75, 53, 2, 71, 46, 55, 30, 8, 3, 86, 15, 87, 73, 80, 13, 92, 92, 2, 85, 77, 39, 52, 19, 31, 56, 50, 53, 22, 61, 33, 44, 6, 46, 78, 72, 72, 84, 25, 98, 79, 17, 14, 6, 77, 20, 39, 16, 91, 89, 67, 8, 88, 8, 36, 65, 83, 48, 70, 51, 62, 43, 21, 49, 29, 82, 88, 98, 67, 29, 41, 13, 44, 2, 24, 50, 87, 25, 12, 40, 33, 25, 85, 29, 6, 30, 67, 87, 88, 79, 56, 2, 42, 14, 9, 1, 85, 87, 40, 48, 25, 65, 81, 88, 14, 33, 57, 21, 1, 88, 33, 50, 95, 37, 17, 45, 12, 100, 37, 40, 73, 10, 39, 95, 73, 17, 59, 62, 9, 82, 92, 66, 47, 23, 28, 70, 24, 74, 61, 89, 4, 97, 35, 94, 12, 24, 6, 73, 21, 90, 48, 36, 60, 34, 28, 49, 78, 86, 5, 98, 50, 95, 91, 24, 83, 22, 86, 53, 9, 23, 82, 9, 31, 29, 76, 73, 51, 10, 35, 64, 35, 74, 63, 56, 41, 1, 39, 39, 1, 33, 33, 82, 18, 17, 15, 11, 10, 52, 20, 15, 73, 50, 7, 53, 91, 29, 81, 8, 60, 45, 17, 8, 62, 65, 83, 51, 79, 77, 53, 98, 8, 8, 34, 85, 15, 72, 23, 94, 45, 45, 93, 37, 21, 96, 63, 28, 51, 37, 6, 46, 61, 61, 62, 36, 32, 8, 86, 12, 38, 15, 39, 73, 23, 31, 62, 12, 15, 92, 4, 2, 47, 36, 24, 13, 97, 78, 62, 23, 22, 12, 99, 7, 33, 78, 35, 65, 47, 66, 40, 44, 56, 30, 10, 76, 93, 37, 34, 27, 20, 47, 62, 37, 18, 15, 84, 69, 27, 91, 97, 86, 27, 15, 44, 6, 33, 12, 28, 32, 30, 57, 1, 9, 55, 8, 57, 99, 85, 13, 50, 53, 46, 52, 91, 81, 74, 87, 29, 28, 37, 32, 91, 56, 76, 35, 79, 47, 81, 94, 93, 63, 33, 17, 40, 45, 11, 81, 47, 89, 14, 40, 5, 65, 97, 90, 19, 22, 4, 77, 54, 30, 10, 54, 100, 55, 85, 75, 1, 53, 12, 99, 78]
    output:
      - 1: 1868830

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 def is_valid_1d_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list
 
 return all(isinstance(elem, int) and not isinstance(elem, bool) for elem in arr)
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 nums1 = self.__inputs[0]
 nums2 = self.__inputs[1]

 if not is_valid_1d_array(nums1):
 self.store_result(("Not a Valid 1D Integer 'nums1' Array."), ValidationFunction.FAIL)
 elif not is_valid_1d_array(nums2):
 self.store_result(("Not a Valid 1D Integer 'nums2' Array."), ValidationFunction.FAIL)
 elif not (len(nums1) == len(nums2)):
 self.store_result ("'nums1' and 'nums2' must have same length", ValidationFunction.FAIL)
 elif not (1 <= len(nums1) <= 1000 and 1 <= len(nums2) <= 1000):
 self.store_result ("'nums1' and 'nums2' to have 1 <= size <= 1000", ValidationFunction.FAIL)
 elif not all(0 <= num <= 100 for num in nums1):
 self.store_result ("'nums1' must consist of values from 0 to 100 only", ValidationFunction.FAIL)
 elif not all(0 <= num <= 100 for num in nums2):
 self.store_result ("'nums2' must consist of values from 0 to 100 only", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the Dot Product of Two Sparse Vectors problem.

Hash Maps

Knowing What to Track

Conclusion

Statement

Examples

Understand the problem

Figure it out!

Try it yourself