Yelp Interview Question Software Engineers
Country: United States
package vector;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class DotProduct {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String noElements = in.nextLine();
String[] kn = noElements.split("\\s+");
int k = Integer.parseInt(kn[0]);
int n = Integer.parseInt(kn[1]);
Map<Integer, Integer> vector1 = new HashMap<Integer, Integer>();
Map<Integer, Integer> vector2 = new HashMap<Integer, Integer>();
int size = 0;
for(int i=0; i<k; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
vector1.put(key, value);
size = size>key ? size : key;
}
for(int i=0; i<n; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
vector2.put(key, value);
size = size>key ? size : key;
}
int dotProd = 0;
for(int i=0; i<=size; i++) {
if(vector1.get(i) != null && vector2.get(i) != null) {
dotProd += (vector1.get(i) * vector2.get(i));
}
}
System.out.println(dotProd);
}
}
Here is the more efficient solution:
public class SparseVectorDotProduct {
public static void main(String args[]){
Scanner in = new Scanner(System.in);
String noElements = in.nextLine();
String[] kn = noElements.split("\\s+");
int firstVector = Integer.parseInt(kn[0]);
int secondVector = Integer.parseInt(kn[1]);
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
int result = 0;
for(int i=0; i<firstVector; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
map.put(key, value);
}
for(int i=0; i<secondVector; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
if(map.containsKey(key) && map.get(key)!=null) {
int tempvalue = map.get(key) * value;
result += tempvalue;
}
}
System.out.print(result);
}
}
public class SparseVectorDotProduct {
public static void main(String args[]){
Scanner in = new Scanner(System.in);
String noElements = in.nextLine();
String[] kn = noElements.split("\\s+");
int firstVector = Integer.parseInt(kn[0]);
int secondVector = Integer.parseInt(kn[1]);
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
int result = 0;
for(int i=0; i<firstVector; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
map.put(key, value);
}
for(int i=0; i<secondVector; i++) {
String line = in.nextLine();
String[] split = line.split("\\s+");
int key = Integer.parseInt(split[0]);
int value = Integer.parseInt(split[1]);
if(map.containsKey(key) && map.get(key)!=null) {
int tempvalue = map.get(key) * value;
result += tempvalue;
}
}
System.out.print(result);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution
{
public static void main (String[] args)
{
// your code goes here
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int [][] arrm = new int[m][2];
int [][] arrn = new int[n][2];
for(int i=0;i<m;i++){
arrm[i][0] = in.nextInt();
arrm[i][1] = in.nextInt();
}
for(int i=0; i<n;i++){
arrn[i][0] = in.nextInt();
arrn[i][1] = in.nextInt();
}
int result=0;
for(int i=0;i<arrm.length;i++){
if(arrm[i][0]==arrn[i][0]){
result = result + (arrm[i][1]* arrn[i][1]);
}
}
System.out.println(result);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution
{
public static void main (String[] args)
{
// your code goes here
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int [][] arrm = new int[m][2];
int [][] arrn = new int[n][2];
for(int i=0;i<m;i++){
arrm[i][0] = in.nextInt();
arrm[i][1] = in.nextInt();
}
for(int i=0; i<n;i++){
arrn[i][0] = in.nextInt();
arrn[i][1] = in.nextInt();
}
int result=0;
for(int i=0;i<arrm.length;i++){
if(arrm[i][0]==arrn[i][0]){
result = result + (arrm[i][1]* arrn[i][1]);
}
}
System.out.println(result);
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution
{
public static void main (String[] args)
{
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int [][] arrm = new int[m][2];
int [][] arrn = new int[n][2];
for(int i=0;i<m;i++){
arrm[i][0] = in.nextInt();
arrm[i][1] = in.nextInt();
}
for(int i=0; i<n;i++){
arrn[i][0] = in.nextInt();
arrn[i][1] = in.nextInt();
}
int result=0;
for(int i=0;i<arrm.length;i++){
if(arrm[i][0]==arrn[i][0]){
result = result + (arrm[i][1]* arrn[i][1]);
}
}
System.out.println(result);
}
}
Keep a hashtable (Call it h)
- Skor March 20, 2015Keep a sum which represents the dot product value (Call it s)
Now, the idea is that we will add to h whatever mapping we encounter when reading the lines. If there is no such mapping for the vector position, we will add the mapping. if there is, then we simply multiply the value by the mapped value and then add it to the sum (s)
Return s.
For example, we first add the key value pair <1, 4>
When we encounter <1, 7>, we see that there already exists a mapping for the key <1>
So we look at the value to that key (4) and multply it by our current value (7) and add to the sum. Same thing happens when <5, 3> is originally added - nothing happens, but when we see that we can add <5, 1>, we multply 3 and 1 and add to the sum.