Sparse Vector Dot Product
Programming Interview
Hard
10 views
Problem Description
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.
Sample Test Case
Input:
5 2
0 1
3 4
2
0 2
4 3
Official Solution
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))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!