Adobe Interview Question for Software Development Managers

• 0

Country: India
Interview Type: Written Test

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

Just exclude one vertice and then connect all the n-1 vertices, it will be (n-1)C2 i.e. (n-1)(n-2)/2.

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

I guess it is nC1*(n-1)C2 .we have to select that one vetex as well

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

+1 to Anomymous.
Yes it should be n.(n-1).(n-2)/2

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

@Bazinga, Anonymous: No, the answer is (n-1)*(n-2)/2.

I challenge you to draw a disconnected undirected graph with no duplicate edges and no self loops that has n*(n-1)*(n-2)/2 edges like you said.

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

luv is correct leaving one node out of all make a graph disconnected

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

We have to select number of edges, not number of ways of choosing edges (which is also not correct :P ).

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

Sorry, I posted above note anonymously. It was me :-)

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

is it ((n-2)*(n-1)/2)

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

Complete graph -- one to one connection for n vertices needs 1+2+3+..+(n-1) edges.
which is (n-1)*n/2 edges...
Here we need to keep one vertex aside, and completely connect n-1 vertices..
which comes to (n-1)*(n-2)/2 edges..

Formula - 1+2+3+..+n = n*(n+1)/2

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

A graph is called as disconnected if there exists at least one pair of vertices (u,v) such that there is not any path between them.
To make the above definition correct, Separate one vertex & join the remaining n-1 vertices.
So, it can be done in n-1C2=(n-1)*(n-2)/2

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

Complete graph -- one to one connection for n vertices needs 1+2+3+..+(n-1) edges.
which is (n-1)*n/2 edges...
Here we need to keep one vertex aside, and completely connect n-1 vertices..
which comes to (n-1)*(n-2)/2 edges..

Formula - 1+2+3+..+n = n*(n+1)/2

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

when n is even its n-2 and when n is odd its [n/2] (upper ceiling function)

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

dat means for 4 it should be 2..but i thnk ans will be 3..for vertices A,B,C,D u can have edges AB,BC,CA

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

in any simple graph having n vertex max edges can be (n)C2 now we need max edges with a disconnected graph.

let us assume there are “X” vertex in one side & (n-x) vertex on other side.

We can say that max edges in the graph would be xC2 & (n-x)C2

Total edges in graph are P = xC2+(n-x)C2 which we need to maximize.

If we solve it by max & min concept we will get x =(n/2)

Which means we should divide it in two halves.

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

No, consider that having a complete graph on n-1 vertices and one disconnected vertex yields (n-1)(n-2)/2 edges.

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

Leave one vertex and connect rest n-1 vertices to each other. And that can be done in (n-1)! ways. So, the max edges possible are (n-1)!

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

It is ((n-2)*(n-1)/2) and not (n-1)!

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.