Questions:

Dot product of two sparse vectors.

• I proposed and started implementing the hash map solution first - iterating over smallest keyset, interviewer wanted more.
• suggested and implemented binary search in L2 for each [index, val] in L1 to handle the case of L1 being sparse and L2 being not so sparse - O(L1 log L2) time.

Kth Largest Element in array:

• suggested and implemented O(N log N) sort as an initial solution
• mentioned bucket sort as a possible O(N) solution if the range of values was small.
• followed up by implementing min priority queue - O(N log k)
• failed to mention quickselect. I had read about this but had forgotten