[Moderate] interview questions #15

[rygh4775]

Master Mind: The Game of Master Mind is played as follows: The computer has four slots, and each slot will contain a ball that is red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue). You, the user, are trying to guess the solution. You might, for example, guess YRGB. When you guess the correct color for the correct slot, you get a "hit:' If you guess a color that exists but is in the wrong slot, you get a "pseudo-hit:' Note that a slot that is a hit can never count as a pseudo-hit. For example, if the actual solution is RGBY and you guess GGRR, you have one hit and one pseudohit. Write a method that, given a guess and a solution, returns the number of hits and pseudo-hits.

[rygh4775]

Definition

• 4 slots, 4 colors RYGB.
  • Actual 4 slots, guess 4slots
• A hit: same color for same slot
• A pseudo-hit: same color but not in same slot.
  • A hit can never count as pseudo-hit.

    Examples

• Actual RGYB, guess GGRR
  • 1 hit: RGYB[1] == GGRR[1]
  • 1 pseudo-hit: RGYB[0] == GGRR[2]
• Actual RGYT, guess GGRY
  • 1 hit: RGYT[1] == GGRY[1]
  • 2 pseudo-hit: RGYT[0] == GGRY[2], RGYT[2] == GGRY[3]

    Solution

    
    class Result {
    public int hits = 0;
    public int pseudoHits = 0;
    }

// For index of an array int code(char c) { switch (c) { case 'R': return 0; case 'Y': return 1; case 'G': return 2; case 'B': return 3; default: return -1; } }

Result estimate(String actual, String guess) { if(actual.length() != guess.length()) return null;

Result res = new Result(); int[] freq = new int[guess.length()];

// count hit and make frequencies for(int i = 0; i < actual.length(); i++) { if(actual.chartAt[i] == guess.chartAt[i]) { res.hits++; } else { int idx = code(guess.chartAt[i]); freq[idx]++; } }

for(int i = 0; i < actual.length(); i++) { int idx = code(actual.chartAt[i]); if(actual.chartAt[i] != guess.chartAt[i] && freq[idx] > 0) { res.pesudoHits++; freq[idx]--; } }

return res; }