HashMap Lookup
When we traverse the list, we might have pre-computed some values/partial solutions. Sometimes, HashMap lookup of previous values could help to provide O(1) deterministic answer at index i.
e.g. preSum and Two Sum problems.
If we want to know if there is SUM[i, j]= k, we can leverage the fact that k = SUM[i, j] = SUM[0, j] - SUM[0, i-1]. The problem becomes checking if there is a SUM[0, i-1] = SUM[0, j] - k, where j>i.
Use a complex / customised object type as Key of HashMap/HashSet
Some time we need to hash lookup an object, not a simple number or string. 1) we can use a string hack to do it or 2) we define the object and implement the equals and hashCode method.
**also note that Java List object supplies the hashCode and equals methods, so we can use a list object as key.
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
Example 1:
Given points = [[1,1],[-1,1]], return true.
Example 2:
Given points = [[1,1],[-1,-1]], return false.
Follow up: what if any line, not vertical lines only.
Ans:
1) Preprocess by putting all points into a HashSet
2) pick any point as pivot, then there are O(n) possible lines, find the perpendicular bisector as the symmetry line. line P1 P2, line P1 P3, line P1, P4 ...
3) Check if all points are symmetric against this line. Another possibility is the line itself P1 Pi is the symmetry line.
class Solution {
public boolean isReflected(int[][] points) {
Set<Point> pointsSet = new HashSet<>();
int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
for(int[] point: points){
minX = Math.min(minX, point[0]);
maxX = Math.max(maxX, point[0]);
pointsSet.add(new Point(point[0], point[1]));
}
for(int[] point: points) {
Point ref = new Point(minX + maxX - point[0], point[1]);
if(!pointsSet.contains(ref)) return false;
}
return true;
}
}
class Point {
private int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
Point other = (Point) obj;
return other.x == this.x && other.y == this.y;
}
@Override
public int hashCode() {
return x*23 + y*31;
}
}
Use HashMap to Eliminate Duplicated Work
Cracking the Coding Interview
Some time it is useful to enumerate the list (to generate pairs) that the hashed key pointing to.
Example: Print all positive integer solutions to the equation a^3 + b^3
= c^3 + d^3
and a,b,c,d are integers between 1 and 1000.