Sparse Vector Dot Product

Sparse Vector Dot Product

Hard Programming Interview OOP 24 views
Explanation Complexity

Problem Statement

Two sparse vectors are provided as list of index:value pairs. Build SparseVector class with dot(other). Output dot product.

Input Format

Line1: n (size) a (nonzero count). Next a lines: idx val. Next line: b (count). Next b lines: idx val.

Output Format

One integer dot.

Example

5 2
0 1
3 4
2
0 2
4 3
2

Constraints

0

Input / Output Format

Input Format
Line1: n (size) a (nonzero count). Next a lines: idx val. Next line: b (count). Next b lines: idx val.
Output Format
One integer dot.
Constraints
0

Examples

Input:
5 2 0 1 3 4 2 0 2 4 3
Output:
2

Example Solution (Public)

Programming Interview 
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
ptr=0
n,a=map(int,lines[ptr].split()); ptr+=1
class SparseVector:
  def __init__(self,mp):
    self.mp=mp
  def dot(self,other):
    if len(self.mp)>len(other.mp):
      return other.dot(self)
    s=0
    for i,v in self.mp.items():
      if i in other.mp:
        s+=v*other.mp[i]
    return s
mpa={}
for _ in range(a):
  i,v=map(int,(lines[ptr] if ptr<len(lines) else '0 0').split()); ptr+=1
  mpa[i]=v
b=int(lines[ptr].strip()) if ptr<len(lines) else 0
ptr+=1
mpb={}
for _ in range(b):
  i,v=map(int,(lines[ptr] if ptr<len(lines) else '0 0').split()); ptr+=1
  mpb[i]=v
v1=SparseVector(mpa)
v2=SparseVector(mpb)
print(v1.dot(v2))

Official Solution Code

import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
ptr=0
n,a=map(int,lines[ptr].split()); ptr+=1
class SparseVector:
  def __init__(self,mp):
    self.mp=mp
  def dot(self,other):
    if len(self.mp)>len(other.mp):
      return other.dot(self)
    s=0
    for i,v in self.mp.items():
      if i in other.mp:
        s+=v*other.mp[i]
    return s
mpa={}
for _ in range(a):
  i,v=map(int,(lines[ptr] if ptr<len(lines) else '0 0').split()); ptr+=1
  mpa[i]=v
b=int(lines[ptr].strip()) if ptr<len(lines) else 0
ptr+=1
mpb={}
for _ in range(b):
  i,v=map(int,(lines[ptr] if ptr<len(lines) else '0 0').split()); ptr+=1
  mpb[i]=v
v1=SparseVector(mpa)
v2=SparseVector(mpb)
print(v1.dot(v2))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.