songofsp3
BAN USER
Comments (5)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
public int getNumberOfTriangles(int[] v){
HashMap<Integer, HashSet<Integer>> edges = new HashMap<Integer, HashSet<Integer>>();
int result = 0;
for(int i = 0; i < v.length / 2; i++){
int i1 = v[2 * i];
int i2 = v[2 * i + 1];
HashSet<Integer> hs1 = edges.get(i1);
if(hs1 == null){
hs1 = new HashSet<Integer>();
edges.put(i1, hs1);
}
HashSet<Integer> hs2 = edges.get(i2);
if(hs2 == null){
hs2 = new HashSet<Integer>();
edges.put(i2, hs2);
}
for(Integer test : hs1){
if(hs2.contains(test)){
result++;
}
}
hs1.add(i2);
hs2.add(i1);
}
return result;
}
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Moving window on B; O(b * a) ?
- songofsp3 April 19, 2014public boolean hasAnagramSubstring(String a, String b){
if(a == null || b == null || a.length() > b.length()){
return false;
}
int[] targetCounts = new int[256];
int[] windowCounts = new int[256];
for(int i = 0; i < a.length(); i++){
targetCounts[a.charAt(i)]++;
windowCounts[b.charAt(i)]++;
}
int length = a.length();
for(int endCursor = a.length() - 1; endCursor < b.length();){
boolean test = isAnagram(targetCounts, windowCounts);
if(test){
return true;
}
windowCounts[b.charAt(endCursor - length + 1)]--;
endCursor++;
if(endCursor >= b.length()){
break;
}else{
windowCounts[b.charAt(endCursor)]++;
}
}
return false;
}
private boolean isAnagram(int[] targetCounts, int[] windowCounts){
for(int i = 0; i < targetCounts.length; i++){
if(targetCounts[i] > 0 && targetCounts[i] != windowCounts[i]){
return false;
}
}
return true;
}