Infosys Interview Question for Software Engineer / Developers

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

This is a problem requiring the use of Burnside's lemma. You consider
the 24 symmetries of a cube and sum all those symmetries that keep
colours fixed. The number of non-equivalent configurations is then the
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and
the side faces 3, 4, 5, 6 (clockwise)

You should hold a cube and follow the way the cycle index is
calculated as described below. The notation

(1)(23)(456) = (x1)(x2)(x3)

means that we have a permutation of 3 disjoint cycles in which face 1
remains fixed, face 2 moves to face 3 and 3 moves to face 2, face 4
moves to 5, 5 moves to 6 and 6 moves to 4. (This is is not a possible
permutation for our cube, it is just to illustrate the notation.) We
now calculate the cycle index.

(1)e = (1)(2)(3)(4)(5)(6); index = (x1)^6
(2)3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3)3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4)3 further as above but counterclockwise; index 3(x1)^2.(x4)
(5)6 permutations like (15)(23)(46); index 6(x2)^3
(6)4 permutations like (154)(236); net index 4(x3)^2
(7)4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the
generating function:

(I shall use r=red and b=blue, y=yellow as the three colours)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2
+ 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4)
+ 8(r^3+b^3+y^3)^2]

and putting r=1, b=1, y=1 this gives

=(1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

= (1/24)[729 + 243 + 162 + 162 + 72]

= 1368/24

= 57

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

Are you trying to show us that you are smart?

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

Well actually the real answer is 56! But this was close

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

This question is not complete .. may be you are missing some part of the question ..
If you paint the cube still you will have one cube, until and unless you cut it in some plane.

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

I've edited the question to what I think it's trying to ask. Hope it makes more sense now.

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

120!
6P3 = 6!/3! = 120

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

can you elaborate?

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

6p3 wont be since we can use same colour to paint all the sides. which not includes in the 6p3

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

6p3 wont be since we can use same colour to paint all the sides. which not includes in the 6p3 .
instead of it can be 8c6 or 8c2 (6+3-1c6)ie,combination with repetition

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

Wouldn't it be 729? Each side has three colors that it could possibly be colored. 6 different sides results in 3^6 = 729.

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

It is a symmetrical figure...you cant do 3^6..

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

I agree with killErdr, there are 6 faces of a cube and each can be painted in 3 ways.. so power(3,6)

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

I would say 4^6 as you should be allowed not to paint a face.

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

This problem is solved using Polya's Enumeration Formula. The specific equation for the cube is:

1/24 * (c^6 + 3*c^4 + 12*c^3 + 8*c^2)

where c is the number of colors. For 3 the value is thus 57. When I was taking combinatorics, I found that Polya's formula was the most amazing thing I'd ever seen. The original application was for enumerating unique molecules in organic chemistry (to put it VERY briefly). The formula derivation involves identifying symmetry groups, in this case rotational symetries of the cube about various axes.

The answers above are way WAY off simply because they do not take into account the rotational symetries that result in equivalent colorings.

No doubt there will be skeptics who will not believe the low number (57) above. All I can say is, this formula is defined in, "An Introduction to Abstract Algebra," by Derek John Scott Robinson, page 95. This question is a classic application of Polya's formula.

Cheers!

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

Important comment on my own note. The answer is quite different if the question is phrased, "each color must be used at least once".

A variation of this modified question is, how many ways can a cube be colored using 6 colors, where each color must be used once? The answer to this question is 30.

To derive this, think of the number of ways a cube can be colored. A cube has 6 faces. Pick any face. The first face can be colored with 6 colors, the second 5, the third 4, etc. This is 6! = 6 * 5 * 4 * 3 * 2 * 1. You must then divide this by the number of "cycle groups" for a cube. The cycle groups are defined as rotations about various axes that create equivalent colorings. It is beyond what I can reproduce here, but the number of cycle groups for a cube is 24 (consider it 6 * 4 if you wish, although in actuality it is 1 + 3 + 6 + 6 + 8). So, the answer is (6 * 5 * 4 * 3 * 2 * 1) / (6 * 4) = 5 * 3 * 2 = 30.

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

I agree to KillERdr's answer of 3^6 w/o any restrictions...

But what happens if the question had asked about the no. of ways we can paint the faces so that the adjacent faces have dissimilar colours ??? Any Takers !!!

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

restriction: to paint faces such that adjacent faces have dissimilar paints.

Answer: 6 factorial (1st face 6 colors, 2nf face (6-1)5 colors....) therefore: 6*5*4..1

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

why do u need the 24..i dont feel the need for it..

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

My answer is 56, very close to ThomasT.

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

1. 3 colours of paint.
2. Colours of paint can be combined.
3. Cube need not be coloured based on sides (i.e., you can paint abstract items).

Based on (2) or (3), you pretty much have infinte ways of colouring any cube (assuming a reasonably sized cube and brush).

I'm pretty sure this isn't what the question was asking for, but thinking outside the cube is more fun.

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

If the adjacent faces are to be colored differently, then my opinion is:
6*3 + 4*2 + 3*1 = 29 ways.

Step1: 6 faces and 3 colors
Step2: 4 adjacent faces and 2 colors
Step3: 3 adjacent faces and 1 color

Please comment if this is right or not. Thanks!

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

* Correction
it should be: 6*3 + 4*2 + 2*1 = 28 ways.

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

Each side can be colored in 3 ways (becoz 3 colors) hence 3!
So six sides would make it 6 x 3! = 36 ways

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

Each side can be colored in 3 ways (becoz 3 colors) hence 3!
So six sides would make it 6 x 3! = 36 ways

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

It's like asking how many ways can 3 toilets be used by 6 users ? (3 colors/6 sides)
_ _ _ = 6*5*4 = 6P3 = 120.

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

sorry..i thing I'll go with ThomasT's answer

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

3 colors plus no colr, 4 possibilities for each side.
so pow(4,6), however, the cub is symmetric, thus pow(4,6)/2=2048

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

This is a problem requiring the use of Burnside's lemma. You consider
the 24 symmetries of a cube and sum all those symmetries that keep
colours fixed. The number of non-equivalent configurations is then the
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and
the side faces 3, 4, 5, 6 (clockwise)

You should hold a cube and follow the way the cycle index is
calculated as described below. The notation

(1)(23)(456) = (x1)(x2)(x3)

means that we have a permutation of 3 disjoint cycles in which face 1
remains fixed, face 2 moves to face 3 and 3 moves to face 2, face 4
moves to 5, 5 moves to 6 and 6 moves to 4. (This is is not a possible
permutation for our cube, it is just to illustrate the notation.) We
now calculate the cycle index.

(1)e = (1)(2)(3)(4)(5)(6); index = (x1)^6
(2)3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3)3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4)3 further as above but counterclockwise; index 3(x1)^2.(x4)
(5)6 permutations like (15)(23)(46); index 6(x2)^3
(6)4 permutations like (154)(236); net index 4(x3)^2
(7)4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the
generating function:

(I shall use r=red and b=blue, y=yellow as the three colours)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2
+ 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4)
+ 8(r^3+b^3+y^3)^2]

and putting r=1, b=1, y=1 this gives

=(1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

= (1/24)[729 + 243 + 162 + 162 + 72]

= 1368/24

= 57

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

This is a problem requiring the use of Burnside's lemma. You consider
the 24 symmetries of a cube and sum all those symmetries that keep
colours fixed. The number of non-equivalent configurations is then the
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and
the side faces 3, 4, 5, 6 (clockwise)

You should hold a cube and follow the way the cycle index is
calculated as described below. The notation

(1)(23)(456) = (x1)(x2)(x3)

means that we have a permutation of 3 disjoint cycles in which face 1
remains fixed, face 2 moves to face 3 and 3 moves to face 2, face 4
moves to 5, 5 moves to 6 and 6 moves to 4. (This is is not a possible
permutation for our cube, it is just to illustrate the notation.) We
now calculate the cycle index.

(1)e = (1)(2)(3)(4)(5)(6); index = (x1)^6
(2)3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3)3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4)3 further as above but counterclockwise; index 3(x1)^2.(x4)
(5)6 permutations like (15)(23)(46); index 6(x2)^3
(6)4 permutations like (154)(236); net index 4(x3)^2
(7)4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the
generating function:

(I shall use r=red and b=blue, y=yellow as the three colours)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2
+ 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4)
+ 8(r^3+b^3+y^3)^2]

and putting r=1, b=1, y=1 this gives

=(1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

= (1/24)[729 + 243 + 162 + 162 + 72]

= 1368/24

= 57

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

what the hell permutations???
It's so straight forward:
you have 6 positions with 3 possible options for each. It's like 6-digit number with a base of 3.
The total number of combinations is 3*3*3*3*3*3 = 3^6, which is 729

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

r u mad anonymous the cube has symmetry
what the hell r u writing

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

Hi Gayle,
Can we have an answer to this? seems like an interesting question

Cube has too much symmetry so permutaiotn will not wrk straightforward .. to many solutions will overlap.

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

ThomasT and abcd are both correct. The answer is 57. The reason that 3^6=729 is NOT correct is that two colorings should be considered the same if one can be turned into the other by simply rotating the cube. So, many of the 729 "possible" colorings are actually the same.

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

my answer is 8c6 or 8c2

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

my answer is 8c6 or 8c2

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

my answer is 8c6 or 8c2
combination with repetition, r=6 n=3

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

my answer is 8c6 or 8c2
combination with repetition, r=6 n=3
this will true when one side is using one colour.

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

Yes, the correct answer is indeed 57 for exactly the reason ThomasT gave. As one of the posts above said, because a cube is considered a rigid object capable of 3-dimensional motion (i.e. rotations, flips, etc.), by simply taking 3^6, one is over-counting greatly. As an example, by thinking the answer is 3^6, you are in fact suggesting that painting the front of the cube black and everything else white is different from painting the bottom of the cube black and everything else white, when in fact you can simply rotate the cube to reach the same thing. To answer the question, you need to consider the symmetric group of the cube (which has order 24), the fixed point set of each element in the group, and then use the Cauchy-Frobenius-Burnside Theorem to count all possible paintings. The answer for three different colors is indeed 57.

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

Yep. 57. Excellent explanation given by comments above and Wikipedia (look Burnsides' lemma).

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

I got 57 by using color combinations and spatial recognition without the need to learn Burnside's theorem and group theory.

1. All 6 faces are painted with only one color, red, blue, or green. There are obviously 3 ways total in this group.

2. All 6 faces are painted with two and only two colors. There are apparently 3 2-color combinations: red and blue, red and green, and blue and green. For each 2-color combination, there are 5 sub-combinations, for instance for red and blue combination, they are 1r5b, 2r4b, 3r3b, 4r2b, and 5r1b. The number of ways to paint the cube in these sub-combinations is 1, 2, 2, 2, and 1, respectively. The total number of ways stands at 3 x 8 = 24.

3. All 6 faces are painted with three colors. There are three combinations for these 6 faces to be painted in terms of number of faces painted by each color: 1, 1, 4; 1, 2, 3; and 2, 2, 2. For 1, 1, 4, it could be 1r, 1b, 4g, or 1r, 1g, 4b, or 1b, 1g, 4r, 3 sub-combinations. In each sub-combination, there are 2 ways to paint the cube and the total is 3 x 2 = 6. For 1, 2, 3, there are 6 sub-combinations, namely 1r2b3g, or 1r2g3b, or 1b2r3g, or 1b2g3r, or 1g2r3b, or 1g2b3r. In each sub-combination, there are 3 ways to paint the cube and so the total is 6 x 3 = 18. For 2r, 2b, 2g, there are 6 ways to paint the cube.

Eventually, there are a total of 3 + 24 + 6 + 18 + 6 = 57 distinct ways to paint the cube considering rotational symmetry.

With this method, you can get the answers for many questions framed differently, like "how many ways can you paint the cube with 3 colors when each color must be used for at least one face?".

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

My answer is 53. It is based on "Are you smart enough to work at Google" book, but they forgot about 4 sides one color and one another color and one the third color...

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

Sorry, it gives 3 more, so my answer ir 56...

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.