Google Interview Question Software Developers
Country: Switzerland
Express your graph as a 2D array (hint: you only need top part).
size_t countTriangles(const bool** g, size_t n)
{
auto res = 0;
for (auto row = 0; row < n - 1; ++row) {
for (auto col = 0; col < n - 1; ++col) {
if (g[row][col]) {
for (auto match = col + 1; match < n; ++match) {
if (g[row][match] && g[match][col]) { ++res; }
}
}
}
}
return res;
}
The complexity is n^3 as there is a maximum if n^3 triplets.
package cup;
import java.util.*;
import java.util.Map.Entry;
public class CountTraingles {
public static void main(String[] args) {
System.out.println(getTraingleCount(getGraph()));
}
public static int getTraingleCount(Map<Node<Character>, Set<Node<Character>>> map){
int count=0;
Set<Node<Character>> visitedNodeSet = new HashSet<>();
for(Entry<Node<Character>, Set<Node<Character>>> entry : map.entrySet()){
Set<Node<Character>> neighbourSet = entry.getValue();
removeVisitedValFromList(neighbourSet, visitedNodeSet);
List<Node<Character>> neighbourList = new ArrayList<>(neighbourSet);
for(int i=0; i<neighbourList.size(); i++){
for(int j=i+1; j<neighbourList.size(); j++){
if(checkIfPathExistsBetweenNeighbourNodes(neighbourList.get(i), neighbourList.get(j), map)){
count++;
}
}
}
visitedNodeSet.add(entry.getKey());
}
return count;
}
private static boolean checkIfPathExistsBetweenNeighbourNodes(Node<Character> node1, Node<Character> node2, Map<Node<Character>, Set<Node<Character>>> map){
return (map.containsKey(node1) && map.get(node1).contains(node2));
}
private static void removeVisitedValFromList(Set<Node<Character>> neighbourList, Set<Node<Character>> visitedNodeSet){
for(Node<Character> node: visitedNodeSet){
neighbourList.remove(node);
}
}
public static Map<Node<Character>, Set<Node<Character>>> getGraph(){
Map<Node<Character>, Set<Node<Character>>> map = new HashMap<>();
Set<Node<Character>> list = new HashSet<>();
list.add(new Node<>('B'));
list.add(new Node<>('C'));
list.add(new Node<>('D'));
map.put(new Node<>('A'), list);
list = new HashSet<>();
list.add(new Node<>('C'));
list.add(new Node<>('A'));
list.add(new Node<>('E'));
list.add(new Node<>('D'));
map.put(new Node<>('B'), list);
list = new HashSet<>();
list.add(new Node<>('A'));
list.add(new Node<>('B'));
map.put(new Node<>('C'), list);
list = new HashSet<>();
list.add(new Node<>('B'));
list.add(new Node<>('D'));
map.put(new Node<>('E'), list);
list = new HashSet<>();
list.add(new Node<>('A'));
list.add(new Node<>('E'));
list.add(new Node<>('B'));
map.put(new Node<>('D'), list);
return Collections.unmodifiableMap(map);
}
static class Node<T>{
T node;
public Node(T node){
this.node = node;
}
@Override
public int hashCode(){
return node.hashCode();
}
@Override
public boolean equals(Object o){
if(o == null || !(o instanceof Node)){
return false;
}
return ((Node<?>)o).node == node;
}
}
}
package cup;
import java.util.*;
import java.util.Map.Entry;
public class CountTraingles {
public static void main(String[] args) {
System.out.println(getTraingleCount(getGraph()));
}
public static int getTraingleCount(Map<Node<Character>, Set<Node<Character>>> map){
int count=0;
Set<Node<Character>> visitedNodeSet = new HashSet<>();
for(Entry<Node<Character>, Set<Node<Character>>> entry : map.entrySet()){
Set<Node<Character>> neighbourSet = entry.getValue();
removeVisitedValFromList(neighbourSet, visitedNodeSet);
List<Node<Character>> neighbourList = new ArrayList<>(neighbourSet);
for(int i=0; i<neighbourList.size(); i++){
for(int j=i+1; j<neighbourList.size(); j++){
if(checkIfPathExistsBetweenNeighbourNodes(neighbourList.get(i), neighbourList.get(j), map)){
count++;
}
}
}
visitedNodeSet.add(entry.getKey());
}
return count;
}
private static boolean checkIfPathExistsBetweenNeighbourNodes(Node<Character> node1, Node<Character> node2, Map<Node<Character>, Set<Node<Character>>> map){
return (map.containsKey(node1) && map.get(node1).contains(node2));
}
private static void removeVisitedValFromList(Set<Node<Character>> neighbourList, Set<Node<Character>> visitedNodeSet){
for(Node<Character> node: visitedNodeSet){
neighbourList.remove(node);
}
}
public static Map<Node<Character>, Set<Node<Character>>> getGraph(){
Map<Node<Character>, Set<Node<Character>>> map = new HashMap<>();
Set<Node<Character>> list = new HashSet<>();
list.add(new Node<>('B'));
list.add(new Node<>('C'));
list.add(new Node<>('D'));
map.put(new Node<>('A'), list);
list = new HashSet<>();
list.add(new Node<>('C'));
list.add(new Node<>('A'));
list.add(new Node<>('E'));
list.add(new Node<>('D'));
map.put(new Node<>('B'), list);
list = new HashSet<>();
list.add(new Node<>('A'));
list.add(new Node<>('B'));
map.put(new Node<>('C'), list);
list = new HashSet<>();
list.add(new Node<>('B'));
list.add(new Node<>('D'));
map.put(new Node<>('E'), list);
list = new HashSet<>();
list.add(new Node<>('A'));
list.add(new Node<>('E'));
list.add(new Node<>('B'));
map.put(new Node<>('D'), list);
return Collections.unmodifiableMap(map);
}
static class Node<T>{
T node;
public Node(T node){
this.node = node;
}
@Override
public int hashCode(){
return node.hashCode();
}
@Override
public boolean equals(Object o){
if(o == null || !(o instanceof Node)){
return false;
}
return ((Node<?>)o).node == node;
}
}
}
public static int countTriangles(int[][] graph) {
int count = 0;
for (int v = 0; v < graph.length; v++) {
for(int e1 = v + 1; e1 < graph.length; e1++) {
if(graph[v][e1] == 0) {
continue;
}
for(int e2 = e1 + 1; e2 < graph.length; e2++) {
if(graph[v][e2] == 0) {
continue;
}
count += graph[e1][e2] == 1 ? 1 : 0;
}
}
}
return count;
}
public static int countTriangles(int[][] graph) {
int count = 0;
for (int v = 0; v < graph.length; v++) {
for(int e1 = v + 1; e1 < graph.length; e1++) {
if(graph[v][e1] == 0) {
continue;
}
for(int e2 = e1 + 1; e2 < graph.length; e2++) {
if(graph[v][e2] == 0) {
continue;
}
count += graph[e1][e2] == 1 ? 1 : 0;
}
}
}
return count;
}
We can use dfs to solve this problem. Code as follows, assume that V is the number of vertex.
static const int V = 100010;
vcetor<int> G[V];
bool visited[V];
void dfs(int u, int par, int grand, vector<vector<int> > &ans) {
visited[u] = true;
for (int v : G[u]) {
if (v == grand) {
ans.push_back({u, par, grand});
}
else if (!visited[v])
dfs(v, u, par, ans);
}
}
vector<vector<int> > Triangles() {
vector<vector<int> > ans;
for (int i = 0; i < V; ++i) {
if (!visited[i])
dfs(i);
}
return move(ans);
}
You should Build the Adjacency matrix of the graph let's call it A, then compute the matrix B=A^3. The entry (i,j) in B is the number of paths of length 3 from i to j, thus the answer is trace(B)/6.
Complexity is the complexity of matrix multiplication which is about n^2.4
Store Graph as follows
class GraphNode{ public int value; Hashset<GraphNode> neighbours; } //Add all graph nodes to a list or somethingNow go to each graph node and among its neighbours , which are say N
- smarthbehl July 15, 2015try to find two neighbours which are neighbour of each other , this forms a triangle.. this will be N square for each node having N neighbours , so worst case graph with N nodes having N-1 neighbours each , N^3 is the solution