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

- pornstar January 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Are you trying to show us that you are smart?

- Dumbo February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- puranjay sharma April 09, 2020 | Flag
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.

- Baffled All the Time June 14, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Gayle L McDowell July 08, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- DrEvil August 01, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you elaborate?

- ND April 10, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 18, 2011 | Flag
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.

- KillERdr August 06, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 04, 2012 | Flag
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)

- AA August 24, 2007 | Flag Reply
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.

- gee September 18, 2007 | Flag Reply
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!

- ThomasT October 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ThomasT October 31, 2007 | Flag
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 !!!

- IsaacM October 31, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous June 15, 2009 | Flag
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..

- anonym19 January 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My answer is 56, very close to ThomasT.

- Ama January 11, 2008 | Flag Reply
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.

- Mr. Different Perspective January 14, 2008 | Flag Reply
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!

- Sadineni.Venkat January 01, 2009 | Flag Reply
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.

Step3: 2 adjacent faces and 1 colur, not 3 adajacent faces

- Sadineni.Venkat January 01, 2009 | Flag Reply
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

- Nick May 27, 2009 | Flag Reply
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

- Nick May 27, 2009 | Flag Reply
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.

- Anonymous May 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 29, 2009 | Flag
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

- Jean June 10, 2009 | Flag Reply
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

- pornstar January 26, 2010 | Flag Reply
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

- abcd January 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon May 07, 2011 | Flag
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.

- Amit Priyadarshi August 01, 2010 | Flag Reply
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.

- Jason Schmurr December 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my answer is 8c6 or 8c2

- Anonymous March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my answer is 8c6 or 8c2

- vimal March 18, 2011 | Flag Reply
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

- vimal March 18, 2011 | Flag Reply
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.

- vimal March 18, 2011 | Flag Reply
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.

- Math PhD April 17, 2011 | Flag Reply
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).

- A humble Math MS October 19, 2011 | Flag Reply
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?".

- Xianshu Wang February 28, 2014 | Flag Reply
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...

- Vineta July 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vineta July 13, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More