Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,227 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineering Intern at Google:
Jan 24, 2012
if we had a list of n nodes, what are the maximum number of edges there can be for a directed acyclic graph?
Add Tags
[?]
See more for this Google Software Engineering Intern Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (3)
0 of 3 people found this helpful
Feb 2, 2012
I think the answer is (n - 1). Iterative approach,
Graph with 3 vertexes, has at most 2 edges before creating a cycle (adding third edge would create a triangle of edges hence a loop).
Same with 4 vertex graph, and so on..
Graph with 3 vertexes, has at most 2 edges before creating a cycle (adding third edge would create a triangle of edges hence a loop).
Same with 4 vertex graph, and so on..
Helpful Answer?
Yes |
No
Inappropriate?
3 of 3 people found this helpful
Feb 15, 2012
Lilit's answer only applies for UNDIRECTED graphs.
If you look at a graph of size 1, it's 0.
2, it's 1.
3, it's 3 (a -> b, a ->c, b ->c)
4, it's 6 (a -> b, a -> c, a ->d, b->c, b->d, c->d)
If you notice, the first node points to all of the other nodes except itself, the next node points to all the other nodes except the first node and itself, and this keeps decreasing by one, so you get (n-1) + (n-2) + ... + 2 + 1
Knowing that the sum from 0 to n = (n*(n+1))/2, this is the sum of 1 to n-1, which is (n*(n-1))/2.
If you look at a graph of size 1, it's 0.
2, it's 1.
3, it's 3 (a -> b, a ->c, b ->c)
4, it's 6 (a -> b, a -> c, a ->d, b->c, b->d, c->d)
If you notice, the first node points to all of the other nodes except itself, the next node points to all the other nodes except the first node and itself, and this keeps decreasing by one, so you get (n-1) + (n-2) + ... + 2 + 1
Knowing that the sum from 0 to n = (n*(n+1))/2, this is the sum of 1 to n-1, which is (n*(n-1))/2.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineering Intern Interview Questions, Google Interview
3 of 4 people found this helpful
by Interview Candidate: