Currently:
At a SWE role
exp: 4.5 yrs
Interview question:
Given 2 integer lists of unequal lengths, lengths could be equal, return the intersection of those lists
meaning
input:
A=[2,1,2,1,2, 3]
B = [4,1,1,1,2]
output:
C=[1,1,2]
The trick/gotcha here is/was that we return the duplicates/common ones with their min counts i.e. 1 appears 2 times in list A but 3 times in B(smaller list), so we return 1 in the output list two times only, similarly 2 appears 1 time in list B but >1 times in list A, we only add 2 once to the resultant list
Verdict: Did not go through.
My approach: I thought this could work? I first talked or mentioned to him that we can use a map to maintain a count of element -> count from list A, similarly maintain a map for list B.
Then determine the smaller list/map out of those and finally iterate over it to determine the small count <-- this is the statement i could not write code for since I got confused in my train of thought.
After the interview I coded something up like this(Note: code will have bugs):
import java.io.*;
import java.util.*;
class Solution {
public static List<Integer> listIntersection(List<Integer> a, List<Integer> b) {
if (a == null || b == null) {
return null;
}
Map<Integer, Integer> m1 = new HashMap<>();
Map<Integer, Integer> m2 = new HashMap<>();
m1 = createMapping(a);
m2 = createMapping(b);
Map<Integer, Integer> smaller = m1.entrySet().size() >= m2.entrySet().size() ? m2 : m1;
Map<Integer, Integer> larger = m1.entrySet().size() >= m2.entrySet().size() ? m1 : m2;
List<Integer> result = new ArrayList<Integer>();
Set<Integer> largerKeys = larger.keySet();
for(Map.Entry<Integer, Integer> entry: smaller.entrySet()) {
Integer key1 = entry.getKey();
System.out.println("At key "+ key1);
if (largerKeys.contains(key1)) {
int value1 = Integer.valueOf(smaller.get(key1));
int value2 = Integer.valueOf(larger.get(key1));
if (value1 <= value2) {
for (int ctr = 0; ctr < value1; ctr ++) {
System.out.println("Adding " + key1);
result.add(key1);
}
} else {
for (int ctr = 0; ctr < value2; ctr ++) {
System.out.println("Adding " + key1);
result.add(key1);
}
}
}
}
return result;
}
private static Map<Integer, Integer> createMapping(List<Integer> a) {
if (a == null) {
return null;
}
Map<Integer, Integer> m = new HashMap<>();
for (int elem: a) {
if (m.containsKey(elem)) {
m.put(elem, m.get(elem) + 1);
} else {
m.put(elem,1);
}
}
return m;
}
public static void main(String[] args) {
List<Integer> a = Arrays.asList(2,1,2,1,2,3);
List<Integer> b = Arrays.asList(2,1,2,1,2,3); //op: [1,1,2,2,2,3]
System.out.println(Solution.listIntersection(a, b));
}
}
Let me know what you folks think.
I am new to Leetcode, solved only 40 problems, wanted to get my a** kicked for this and a lesson on how much I have to prepare, maybe a bad approach maybe a good one, I don’t care, but just thought of sharing this over here, since Leetcode community folks are awesome at helping each other out.
Cheers all and keep on grinding.