## Google Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
16
of 20 vote

I can think of two approaches:

First approach - A naive approach using an adjacency map

The adjacency map is a Map whose keys are vertices and whose values are sets of vertices which are all the neighbors of the key vertex. For every vertex, we'll check for every pair of its neighbors whether there is an edge between them and increment the triangle counter if so.

The total number of triangles will be the number of triangles we counted divided by 6 (we count each triangle 6 times).

Code:

private static class Edge {
private final Object from;
private final Object to;

public Edge(Object from, Object to){
this.from = from;
this.to = to;
}

public Object getFrom(){return from;}

@Override
public String toString(){
return "(" + ((from!=null) ? from.toString() : null) + "," + ((to!=null) ? to.toString() : null) + ")";
}
}

if ((edges==null) || (edges.isEmpty())){
return Collections.<Object,Set<Object>>emptyMap();
}

Map<Object,Set<Object>> graph = new HashMap<>();
for (Edge e : edges){
if (!graph.containsKey(e.getFrom())){
graph.put(e.getFrom(), new HashSet<Object>());
}
if (!graph.containsKey(e.getTo())){
graph.put(e.getTo(), new HashSet<Object>());
}
}

return graph;
}

public static int getNumberOfTriangles1(List<Edge> edges){

int triangles = 0;
for (Set<Object> neighbors : graph.values()){
for (Object v2 : neighbors){
for (Object v3 : neighbors){
if ((!v2.equals(v3)) && (graph.get(v2).contains(v3))){
triangles++;
}
}
}
}

return (triangles/6);
}

Complexity: The overall run-time complexity is O(n*d^2) where n is the number of vertices and d is the maximum degree of a vertex in the graph. This is a good approach for graphs with small maximum vertex degree. But if the graph contains a vertex whose degree is O(n) then the overall complexity in this case would be O(n^3).

Second approach - Using matrix multiplication

Suppose A is the graph's adjacency matrix (A[i][j] = 1 if and only if there is an edge between i and j in the graph). It can be shown that trace(A^3)/6 is the number of triangles in the graph (using the fact that A^k[i][j] is the number of paths with k edges from i to j). This means that all we need to know the number of triangles is to calculate the matrix A^3 and its trace.

This means that our algorithm complexity would depend on the complexity of the matrix multiplication algorithm:
Naive: O(n^3)
Strassen: O(n^{2.8074})

I can post a code for this approach using Strassen matrix multiplication but it's rather long and isn't pretty.

Comment hidden because of low score. Click to expand.
5

Wow man, that matrix approach is brilliant!

Comment hidden because of low score. Click to expand.
0

Matrix approach is standard. But agree, it is brilliant.

Comment hidden because of low score. Click to expand.
1
of 1 vote

You must pay attention to the fact that Strassen and the other matrix multiplication algorithms are great asymptotically speaking but have a big overhead. You don't want to use them for matrices with size below 1000. I don't know if this practical consideration was part of the question, but in real life, one should keep this in mind before choosing to implement the "best" complexity algorithm. Personally I would stick to the naive approach which is way more readable.

Comment hidden because of low score. Click to expand.
5
of 5 vote

1. The undirected graph can be represented as:
class Vertex { List<Vertex> Adjacents; }
2. Traverse the undirected graph as BFS
- Use a queue to traverse
- Use a hash to track the vertices already visited
3. if current = current vertex
- get all adjacent vertices to current
- count the number of common vertices in current.adjacents
(I remove the processed adjacent node to avoid counting the same vertex twice)

.
class Vertex { List<Vertex> Adjacents; }

public static int GetNumberOfTriangles(Vertex source)
{
int count = 0;

Queue<Vertex> queue = new Queue<Vertex>();
HashSet<Vertex> visited = new HashSet<Vertex>();

queue.Enqueue(source);

while (!queue.IsEmpty())
{
Vertex current = queue.Dequeue();

// get all non-visited adjacent vertices for current vertex
.Where(v => !visited.Contains(v))
.ToList();

{

// count the number of common vertices
//     c != curr    => avoid counting itself */
//     !visited.Contains(c) => we haven't counted this yet
&& c != curr
&& !visited.Contains(c)
).Count();

// remove the vertex to avoid counting it again in next iteration

queue.Enqueue(curr);
}

// Mark the vertex as visited
}

return count;
}

Comment hidden because of low score. Click to expand.
0

Nice one!
But your solution assumes that no three vertices will be on same line. And also there is no notion of length ( the question does not have this notion also )

Comment hidden because of low score. Click to expand.
3
of 11 vote

deep-first search.
record the last two steps to judge the triangle.

Comment hidden because of low score. Click to expand.
0

Hi can you explain your approach in a little more detail.

Comment hidden because of low score. Click to expand.
3

Let me explain.
If there is a triangle then its a closed loop. So from any vertex if i go 3 steps and reach it back then there is a closed loop of 3 edges => triangle. Now Since you will do this for all vertices of the graph final output will be number of triangles you found / 3
The scanning of the graph is done by DFS for this problem.

Comment hidden because of low score. Click to expand.
0

Total amount of visited edges is O(E), triangles is about O(V^3).

Comment hidden because of low score. Click to expand.
0

Does not work.

Comment hidden because of low score. Click to expand.
0

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
* Created by Majeed on 5/27/2014.
*/
public class TriangleCounter {
private static int total;
private static boolean visited[];

public static int countTriangles(ArrayList[] g) {
int n = g.length;
visited = new boolean[n];
for(int i = 0; i < n; ++i) {
visited[i] = true;
dfs(i, i, 0, g);
}
}

private static void dfs(int source, int v, int cnt, ArrayList[] g) {
++cnt;
for(int i = 0; i < g[v].size(); ++i) {
int to = (Integer) g[v].get(i);
if(!visited[to] && cnt < 3) {
visited[to] = true;
dfs(source, to, cnt, g);
}
else if(visited[to] && cnt == 3 && to == source) ++total;
}
visited[v] = false;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ArrayList g[];
int n = in.nextInt(), m = in.nextInt();
g = new ArrayList[n];
for(int i = 0; i < n; ++i) g[i] = new ArrayList();
for(int i = 0; i < m; ++i) {
int src = in.nextInt(), dest = in.nextInt();
}
/*
for(int i = 0; i < n; ++i) {
for(int j = 0; j < g[i].size(); ++j)
System.out.print(g[i].get(j) + " ");
System.out.println();
}
*/
System.out.println(countTriangles(g));
}
}

Comment hidden because of low score. Click to expand.
0

@kr.neerav's approach is correct just that in end answer would be /6 instead of /3.
Just because there are 2 ways to count same triangle from same source

Comment hidden because of low score. Click to expand.
3
of 5 vote

There are two things not explained in the problem:
1) Nodes have no X-Y locations. In Theory, there is no way to check it is a thriangle or not. In a Line or Not?
2) Is the memory a bottleneck?

Assume the two are not issues. Then the solution comes:
A: Using Matrix to store Graph in the Memory. (it is always faster).
B: The algorithm is:
1) New an empty std::unordered_set<std::string> to keep all triangles.
----------------
2) Loop each node (v1) in V. [Big-O: O(n)]
3) For each pair of connected nodes (v2 and v3). [Big-O: O(d^2), d is the average node degree]
4) Check whether v2 and v3 are connected. [Big-O: O(1)]
5) If 4) get 'YES', then sort the node IDs and push the new triangle into unordered_set. [Big-O: O(1)]
----------------
6) Finally, output triangles in the unordered_set. [Big-O: O(n)]

Thus, the total cost is Big-O: O(n * d * d), where d is the average node degree.
In a complete graph, it is n^3; In a tree, it is O(n); (even through tree does not make sense in this problem)

Comment hidden because of low score. Click to expand.
0

std::unordered_set<std::string> is a bad design. Should use objects here:
std::unordered_set<Triangle>

Comment hidden because of low score. Click to expand.
2
of 2 vote

I would use the BFS.
a. Color root gray and push it into a queue.
b. Pop from queue one by one. Scan the neighbours of current node based on BFS. If the node to which it is connected is in same level and the node is not black yet add one to count.
c. Color current scnned node to black.

import java.io.*;
import java.util.*;

public class Qs5988741646647296 {
private final static int WHITE = 0;
private final static int GRAY = 1;
private final static int BLACK = 2;

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);

ArrayList<ArrayList<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < V; ++i) {
}

for (int i = 0; i < N; ++i) {

int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());

if (hm.contains(v1))
list = hm.get(v1);
else

hm.put(v1, list);

if (hm.contains(v2))
list = hm.get(v2);
else

hm.put(v2, list);
}

boolean[] visitColor = new boolean[V];
Arrays.fill(visitColor, WHITE);

int[] level = new int[V];

for(int i = 0; i < V; ++i) {
if (visitcolor[i] == WHITE) {
q.push(i);
visitColor[i] = GRAY;
level[i] = 0;

int count = 0;

while(!q.isEmpty()) {
Integer num = q.pop();

ArrayList<Integer> list = listOfLists.get(num);
for (Integer integer:list) {
if (visitColor[integer] == WHITE) {
q.push(integer);
visitColor[integer] = GRAY;
level[integer] = level[num]+1;
}
else if(visitColor[integer] == GRAY)
if (level[integer] == level[num])
count++;
}

visitcolor[num] = BLACK;
}
}
}

out.println(count);

out.flush();
out.close();

System.exit(0);
}
}

Comment hidden because of low score. Click to expand.
1
of 3 vote

Steps

1) Create Adjacency List for nodes.

As in given example graph is undirected so adj list will look like this
0 -> 1,2
1->0,2
2-->0,1
4-->1

2) Pick one edge and get adj list for both nodes.
3) Count number of common elements in adj list
4) Repeat step 2 and 3 for all the edges

Number of triangles= (Number of common elements)/6 as it's undirected graph for directed graph it will be divided by 3

Comment hidden because of low score. Click to expand.
1
of 3 vote

Finding the number of cycles with three nodes can give us the result.

Comment hidden because of low score. Click to expand.
1
of 1 vote

a basic idea is to have 3 nested loops i, j, and k, then test if i,j,k can form a triangle, cost is o(n^3). with hashset, you can improve it to o(n ^ 2), because based on the first two edges, you can find if the set has the required remaining edge with a lookup.

#include <boost/unordered_set.hpp>
#include <iostream>
#include <utility>
#include <boost/foreach.hpp>

int count(std::vector<std::pair<int, int> > edges)
{
boost::unordered_set<std::pair<int, int> > set;

typedef std::pair<int, int> Edge;
BOOST_FOREACH(Edge p, edges)
{
set.insert(p);
}

int count = 0;
int size = edges.size();

for (int i = 0; i < size - 2; ++i)
{
std::pair<int, int> pair1 = edges[i];

for (int j = i + 1; j < size - 1; ++j)
{
std::pair<int, int> pair2 = edges[j];

int common, b, c;
if (pair2.first == pair1.first)
{
common = pair1.first;
b = pair1.second;
c = pair2.second;
}
else if (pair2.first == pair1.second)
{
common = pair2.first;
b = pair1.first;
c = pair2.second;
}
else if (pair2.second == pair1.first)
{
common = pair2.second;
b = pair2.first;
c = pair1.second;
}
else if (pair2.second == pair1.second)
{
common = pair2.second;
b = pair2.first;
c = pair1.first;
}
else
{
continue;
}

std::pair<int, int> pair3(b, c);

if (set.find(pair3) != set.end())
{
count++;
std::cout << common << "," << b << ", " << c << "\n";
continue;
}

std::pair<int, int> pair4(c, b);

if (set.find(pair4) != set.end())
{
count++;
std::cout << common << "," << b << ", " << c << "\n";
continue;
}
}
}

return count / 3;
}

void put_edge(std::vector<std::pair<int, int> >& edges, int a, int b)
{
if (a < b)
edges.push_back(std::pair<int, int>(a, b));
else
edges.push_back(std::pair<int, int>(b, a));
}

int main()
{
std::vector<std::pair<int, int> > edges;
put_edge(edges, 0, 1);
put_edge(edges, 0, 2);
put_edge(edges, 1, 2);
put_edge(edges, 0, 3);
put_edge(edges, 1, 3);
put_edge(edges, 2, 3);
put_edge(edges, 2, 5);

int c = count(edges);
std::cout << c << "\n";
return 0;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Some of the codes above are so complex .Heres the easiest solution.

public void printRectangles(Edge[] arr)
{
int rectangleCount =0;
HashMap<String ,String>cycle = new HashMap<String,String>();

for(int i=0;i<arr.size();i++)
{
if(cycle.containsKey(arr[i].start) && cycle.containsKey(arr[i].finish) rectangleCount++
else{
cylce.put(arr[i].start,arr[i].start);
cycle.put(arr[i].finish,arr[i].finish);
}
}
System.out.println(rectangleCount);
}

public Class Edge{
String start,finish;
public Edge(String start,String finish)
{
this.start =start;
this.finish=finish;
}
}

Comment hidden because of low score. Click to expand.
0

It doesnt work..

01
2 3
1 2

out put - 1 --> wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

Steps

1) Create Adjacency List for nodes.

As in given example graph is undirected so adj list will look like this
0 -> 1,2
1->0,2
2-->0,1
4-->1

2) Pick one edge and get adj list for both nodes.
3) Count number of common elements in adj list
4) Repeat step 2 and 3 for all the edges

Number of triangles= (Number of common elements)/6 as it's undirected graph for directed graph it will be divided by 3

Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Edge
{
int v1;
int v2;
}

int FindTriangles(Edge[] edges)
{
Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
foreach (Edge e in edges)
{
if (graph.find(e.v1))
{
}
else
{
}

if (graph.find(e.v2))
{
}
else
{
}
}

HashSet<int> visited = new HashSet<int>();
int count = 0;
// iterate through every node in the graph.
// for each node, find if any two adjacent nodes are connected each other.
foreach (KeyValuePair pair in graph)
{
if (!visited.find(pair.Key))
{
List<int> neighbors = pair.Value;
for (int i = 0; i < neighbors.Length; ++i)
{
if (!visited.find(neighbors[i]))
{
for (int j = i + 1; j < neighbors.Length; ++j)
{
if (!visited.find(neighbors[j]))
If (IsNeighbor(i, j))  { count++; }
}
}
}
}
}
return count;
}

Comment hidden because of low score. Click to expand.
0

Here is an updated version using c#

int FindTriangles(Edge[] edges)
{
SortedDictionary<int, List<int>> nodes = new SortedDictionary<int, List<int>>();
foreach (Edge e in edges)
{
if (nodes.Find(e.v1))
{
}
else
{
}
if (nodes.Find(e.v2))
{
}
else
{
}
}

int count = 0;
foreach (KeyValuePair kv in nodes)
{
foreach(int i = 0; i < kv.Value.Length - 1; ++i)
{
if (kv.Value[i] < kv.Key) continue;
foreach (int j = i + 1; j < kv.Value.Length; ++j)
{
if (kv.Value[j] < kv.Key) continue;
if (nodes[kv.Value[i]].IndexOf(kv.Value[j]) != -1)
{
count++;
}
}
}

return count;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class Triangle
{
public Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();

public void createList()
{
l =  maplist.get(2);
l =  maplist.get(4);
l =  maplist.get(1);
}

{
Iterator itr = maplist.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry pairs = (Map.Entry)itr.next();
System.out.println("Node:" + pairs.getKey() + "List:" + pairs.getValue());
}
}

public int numberOfTriangles()
{
int count = 0 ;
for(int key: maplist.keySet())
{
for(int item: l)
{
if(!visited.containsKey(item))
visited.put(item, true);
else if (visited.containsKey(key) && visited.get(item)) // finding out the common nodes
{
count++;
}
}
}
return count;

}

public static void main(String[] args)
{
Triangle t = new Triangle();
t.createList();
int num = t.numberOfTriangles();
System.out.println(num);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is an example in Java of using matrix multiplication to find the number of triangles. A separate class Connections keeps track of the nodes that can be reached after a specific number of steps (multiplication by adjacency matrix).

public static int getTriangles(int[][] adjMatrix) {
//initialize from adjacency matrix the nodes that can be reached with one step:
con.multiply(adjMatrix);        //nodes reached in exactly two steps
con.multiply(adjMatrix);        //nodes reached in exactly three steps
return con.getSumPolygons();
}

class Connections {
public int steps; //keep track of number of steps
public int[][] m; //matrix that holds all connections after exactly steps

public Connections(int[][] m) {
this.m = Arrays.copyOf(m, m.length);
this.steps = 1;
}

public void multiply(int[][] f) {  //matrix multiplication
int[][] n = new int[m.length][m.length];
for(int i = 0; i < m.length; i++) {
for(int j = 0; j < m.length; j++) {
for(int k = 0; k < m.length; k++ ) {
n[i][j] += f[i][k] * m[k][j];
}
}
}
steps++;   //increment number of steps used
m = n;     //assign result of multiplication to class attribute
}

public int getSumPolygons() {
int sum = 0;
for(int i = 0; i < m.length; i++) {
//m[i][i] holds the number of paths that node i can be reached in s steps in both directions
sum += m[i][i];
}
//divide by steps and 2 to avoid counting all nodes in path in both directions:
return sum/steps/2;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

HI i would do something like this :-

Do a union find algorithm (reason to choose this is that this algo is used to find loops in a graph and remember a triangle is a loop). While doing union-find do following steps as well -
1) for every vertex or node maintain a count as to how far is it from the parent. ( after doing the path compression and rank in algorithm)
2) if an edge comes that creates a loop check the attribute i.e. the height from parent and if it's the same then it's a triangle else skip that edge and continue.

Comment hidden because of low score. Click to expand.
0
of 0 vote

using BFS algorithm, find the number of triangles for each level, and sum them up, divided by 6.
public static void main(String[] args){
Node n0 = new Node(0);
Node n1= new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);

ArrayList<Node> list = new ArrayList<Node>();

int triangle = findTotalTrangle(list, 5);
triangle = triangle/6;

System.out.println("the number of triangle is "+ triangle);
}

public static int findTotalTrangle(ArrayList<Node> root, int size){
int count =0;
ArrayList<Node> visited = new ArrayList<Node>();
ArrayList<Node> queue = new ArrayList<Node>();
ArrayList<Node> second = new ArrayList<Node>();
while(!queue.isEmpty()){
second.clear();
queue.removeAll(visited);
count += findTrangleByLevel(queue, second);
for(Node node: queue){
if(!visited.contains(node)){
}
}
queue.clear();
if(visited.size() == size ){
break;
}
}
return count;
}

public static int findTrangleByLevel(ArrayList<Node> list, ArrayList<Node> second){
int count = 0;
//ArrayList<Node> second = new ArrayList<Node>(); //find all the neighbors of the list.
ArrayList<Node> third = new ArrayList<Node>(); //find all the neighbors of the second list.
for(Node node: list){
for(Node neigh : node.connections){
if(!second.contains(neigh)){
}
}
}
if(!second.isEmpty()){
for(Node node: second){
for(Node neighb : node.connections){
if(list.contains(neighb)){
count++;
}

}
}
}

return count; //this is the triangle number begining with the node in the first list.
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose that a graph has been constructed as follows:
- All nodes are ordered by its value.
- Each node has an sorted list of edges.
- An edge belongs to only at a single node with less value among two nodes.

For example, the above graph will be represented by
0: {1, 2}
1: {2, 4}
2: {}
4: {}

Then, the number of triangles can be obtained by counting the number of common nodes between every pair of nodes (n0, n1) where n0 < n1.

typedef uint64_t node_t;
typedef set<node_t> nodeset_t;
typedef map<node_t, nodeset_t> graph_t;

uint64_t countIntersection(nodeset_t::const_iterator f0,
nodeset_t::const_iterator l0,
nodeset_t::const_iterator f1,
nodeset_t::const_iterator l1)
{
if ((f0 == l0) || (f1 == l1)) {
return 0;
}

uint64_t counter = 0;
nodeset_t::const_iterator i0 = f0, i1 = f1;
node_t n0 = *i0, n1 = *i1;

do {
if (n0 == n1) {
++counter;
if (++i0 == l0) break;
if (++i1 == l1) break;
n0 = *i0;
n1 = *i1;
}
else if (n0 < n1) {
if (++i0 == l0) break;
n0 = *i0;
}
else {
if (++i1 == l1) break;
n1 = *i1;
}
} while (true);
return counter;
}

uint64_t countTriangles(const graph_t &g)
{
uint64_t num = 0;
graph_t::const_iterator i0 = g.begin();
graph_t::const_iterator i0_E = g.end();
for (; i0 != i0_E; ++i0) {
const node_t &c0 = i0->first;
const nodeset_t &E0 = i0->second;

nodeset_t::const_iterator i1 = E0.begin();
nodeset_t::const_iterator i1_E = E0.end();
for (; i1 != i1_E; ++i1) {
const node_t &c1 = *i1;
const nodeset_t &E1 = _graph[c1];
num += countIntersection(i1, i1_E, E1.begin(), E1.end());
}
}
return num;
}

The time complexity of this algorithm consists of two parts. First, constructing the graph will be inserting each edge to the proper node. Each insertion of an edge takes O(E/N). (Assume that the number of edges connected for each node is even). So, graph construction takes O(E*log(E/N)).
Second, counting the number of triangles takes O(N * E/N * E/N). The outer loop and inner loop iterate N and E/N times, respectively, and countIntersection takes O(E/N).

If we assume dense graph, i.e., E=O(N^2), then the time complexity is O(N^3). If it is sparse, i.e., E=O(N), then O(N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1

1
"""

def _get_triangles_common_edge(edge, connections):
n1, n2 = edge
n1_nodes = set(connections[n1])
n2_nodes = set(connections[n2])
count = len(n1_nodes.intersection(n2_nodes))
return count

def get_num_triangles(list_node_pair):
"""
@param list_node_pair, a list of edges which are
represented as tuples.
"""
connections = {}
for item in list_node_pair:
a = item[0]
b = item[1]
if a in connections:
connections[a].append(b)
else:
connections[a] = [b]
if b in connections:
connections[b].append(a)
else:
connections[b] = [a]
mysum = 0
for key in connections:
for item in connections[key]:
edge = (key, item)
mysum += _get_triangles_common_edge(edge, connections)
res = mysum / 6
return res

Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1

1
"""

def _dfs(level, root, node, connections):
N = 3
if level == N:
if root == node:
return 1
else:
return 0
else:
res = 0
for item in connections[node]:
res += _dfs(level + 1, root, item, connections)
return res

def get_num_triangles_dfs(list_node_pair):
"""
@param list_node_pair, a list of edges which are
represented as tuples.
"""
nodes = set()
connections = {}
for item in list_node_pair:
a = item[0]
b = item[1]
if a in connections:
connections[a].append(b)
else:
connections[a] = [b]
if b in connections:
connections[b].append(a)
else:
connections[b] = [a]
mysum = 0
for item in nodes:
mysum += _dfs(0, item, item, connections)
res = mysum / 6
return res

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is by using the adjacency matrix.
if a[0][1]==1 and a[1][2]==1 then we check if a[0][2]==1 then one triangle exists
We scan the matrix just downwards in the upper half of the marix
for example if we have 5 nodes then
scan starts from 0th node from a[0][1] and check starts from a[1][2]
And then 1st node from a[1][2] and compared with next node from a[2][3] and so on
In this way we avoid making duplicates

#include<iostream>
using namespace std;
int main()
{
int n,i,j,k,entries,no=0;
cout<<"enter no of nodes:\n";
cin>>n;
int a[n][n];
cout<<"enter no of entries:\n";
cin>>entries;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
a[i][j]=0;
}
for(i=0;i<entries;i++)
{
cin>>j>>k;
a[j][k]=1;
a[k][j]=1;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i][j]==1)
{
for(k=j+1;k<n;k++)
{
if(a[j][k]==1)
{
if(a[i][k]==1)
no++;
}
}
}
}
}
cout<<"no of triangles="<<no<<endl;
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

from itertools import combinations

nodes = dict()

edges = dict()

for line in sys.stdin:

pair = [int(node) for node in line.strip().split()]

nodes[pair[0]] = True

nodes[pair[1]] = True

edges[(pair[0],pair[1])] = True

edges[(pair[1],pair[0])] = True

num_triangles = 0

for combination in combinations(nodes, 3):

a, b, c, = tuple(combination)

if edges.has_key((a, b)) and edges.has_key((b, c)) and edges.has_key((c, a)):

num_triangles = num_triangles + 1

print num_triangles

Comment hidden because of low score. Click to expand.
0
of 0 vote

I simply used BFS and checked if the value of the node I was visiting at that moment existed in the list of Nodes left to visit.

This scenario occurs when a triangle is present because of the following:
Suppose nodes 1, 2, and 3 are connected to each other. Start at node 1.
- Node 1 is visited, adding 2 and 3 to the list of nodes to visit.
- Node 1 is marked as visited.
- Node 2 is visited, adding 3 to the list of nodes to visit (only add nodes that have not been visited, so node 1 is skipped).
- Node 3 is visited, node 3 observes that it is still on the list of nodes to visit. Mark 3 as visited and incrementing triangles count. Also remove the duplicate node 3 entry from the to visit list.

Code:

class Node
{
public int data;
public boolean visited;

public Node(int data)
{
this.data = data;
this.visited = false;
}

public static int triangles(Node start) {
int triangles = 0;

while(toVisit.isEmpty() == false) {
Node n = toVisit.removeFirst();

//Check if duplicate of current node exists on toVisit list. Start from back as it is most likely closer to the end.
for(int i = toVisit.size() - 1; i >= 0; i--) {
if(n == toVisit.get(i)) {
triangles++;
toVisit.remove(i);
}
}
n.visited = true;    //mark as visited

//Add adjacent nodes to toVisit list only if they have not been visited yet
for(int i = 0; i < n.nodes.size(); i++) {
Node newNode = n.nodes.get(i);
if(newNode.visited == false) {
}
}
}
return triangles;
}
}

Complexity is O(n^2) as each node must check the list of nodes yet to visit.

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++;
}
}

}

return result;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CountTriangles {
public static void main(String[] args) {

System.out.println("Number of triangles in the graph: " + numOfTriangles(list));
}

public static int numOfTriangles(LinkedList<Integer>[] list) {
int counter = 0;

for(int i = 0; i < list.length; i++)
counter += countTriangles(list, i);

return counter;
}

public static int countTriangles(LinkedList<Integer>[] list, int node) {
int u, v, counter = 0;

for(int i = 0; i < list[node].size() - 1; i++) {
u = list[node].get(i);
if(u < node)
continue;
for(int j = i + 1; j < list[node].size(); j++) {
v = list[node].get(j);
l = list[v];
if(l.contains(u)) {
counter++;
break;
}
}
}

return counter;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_triangles(pairs):
results = []
for pair in pairs:
if not isinstance(pair, tuple):
raise ValueError("Incorrect input data")

if r not in results:
results.extend([r])

return len(results), results

print (find_triangles( ( (0, 1), (2, 1), (0, 2), (4, 1), (4, 2), (2, 3), (3, 4), (0, 4))))
>>> (4, [{0, 1, 2}, {0, 2, 4}, {1, 2, 4}, {2, 3, 4}])

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dont know why people write this mammoth code for simple problems.
Will google appreciate this and will you have enough time on blackboard to explain all these ..

public void findTriangle(Node curr, Node prev) {

if (next.visited() {
if ((perv != next) && existsEdge(prev, next))
printTriangle(prev, curr, next);

} else  {
findTriangle(next, curr);
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

A minor modification, mark the visited node ..

public void findTriangle(Node curr, Node prev) {

if (next.visited() {
if ((perv != next) && existsEdge(prev, next))
printTriangle(prev, curr, next);

} else  {
next.setVisited(true);
findTriangle(next, curr);
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do that in O(n^2) and no BFS / DFS

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

vector<int> edge1 = {0,2,0,4};
vector<int> edge2 = {1,1,2,1};

unordered_map<int , unordered_set<int> > allEdges;

int countTriangles()
{
int count = 0 ;

for (int i = 0 ; i < edge1.size() ; ++i)
{
allEdges[edge1[i]].insert(edge2[i]);
allEdges[edge2[i]].insert(edge1[i]);
}

for(auto aNode : allEdges)
{
int a = aNode.first;

for(auto b : allEdges[a])
{
for (auto c : allEdges[b])
{
if( (b != a) && (allEdges[c].find(a)!= allEdges[c].end()) )
{
++count;
}
}

}
}

return count/6;
}

int main()
{
cout<<countTriangles();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1、we have a two-dimensional array to represent the adjacent between two vertexes;
also each vertex have a adjacent list of vertexes whose id are larger than the vertex itself;
2、For every vertex list,we check its adjacent vertex pair,and find the reasonable pairs through the 2-dim array;
Time complexity is min(O(edge^2),O(n*d^2));(d represent the degree of the vertex),but I think my solution avoid the redundant computation. A little better than the first solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is O(N^2) worst-case solution:
1. build HashTable/HashSet based on all existing edges with the key of a kind "Elow-Ehigh" where Elow - lower node index, Ehigh - higher node index (e.g. "0-1", "0-2", "1-2")
2. use adjacency list representation of an array, iterate over all edges and their respective adjacent counterpart edge (say for 0-1 edge its adjacent counterpart edges are 1-2, 0-2, and 1-4 since they share at least on of the nodes) and check if there exists an edge which completes a triangle by using previously build HashTable

Time complexity:
1. building a HashTable takes O(M) where M - number of edges
2.a. in a worst case we will have a dense graph which have N^2 edges (by N-1 edges for each node in a graph) and therefore we will need to make n^2 iterations and perform O(1) lookup in a HashTable
2.b. for sparse graph we have O(1) edges and therefore the solution will give O(N) time complexity

Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with a solution that has O(|E|) time complexity and O(|E|) space complexity, with E is the set of edge.

Assume that the set E doesn't contain duplicate edge, i.e. (B,A) should not exist if (A,B) already existed, as the graph is undirected.

0. Initialize hashmap V<Integer, ArrayList<Integer>>
1. Loop through the set E: let say at the edge (a,b), we add to the value list V.get(max(a,b)) the vertex min(a,b), this take O(|E|)
2. Number of triangles: num = 0
3. Loop through the value set of V: num += C(2, V.get(i).length()), where C(k,n) is a k-combination of a set size n. This take O(|E|)

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use adjacency matrix representation to provide an answer in O(E*V).

01234
0 x  x
1    x
2
3
4

For every edge (x) go along to rows, eg. 0 and 1 for edge 01, to check if there are columns where both rows have x in it. Do it for every edge.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

For each vertex traverse all its edges in pairs. For each edge pair see if the vertices are connected, if so its a triangle. Since the same triangle will be reported 3 times (for each vertex), divide the result by 3. This algorithm is O(n) complexity.

For example above:

0 1
2 1
0 2
4 1

Vertex 0 edge pair (0,1) and (0,2) , select any of the 2 connected vertices and see if there is an edge between them. There is (2,1) so add 1 to traingle count.

Repeat for vertices 1,2,4. your triangle count will be 3. Divide by 3 and you will get 1 which is the answer.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.