Interview Questions And Answers 
-
A solution consists of four balls from a set of four different colors. The user
tries to guess the solution.If they guess the right color for the right
spot, record it as being in the correct ‘Location’. If it’s the right color,
but the wrong spot, record it as a correct ‘Color’. For example: if the
solution is ‘BGRR’ and the user guesses ‘RGYY’ they have 1 ‘Location’ and 1
‘Color’. A correct solution would be 4 ‘Location’ and 0 ‘Color’.Write a program to, given a solution and a
guess, calculate the response that we present to the user.2,098 Views |
(9 votes, avg: 3.11)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Actually the best thing is to sort the array in ascending order (u could use merge / heap sort). Now this takes care of umpteen number of colours also. So if your array has 4 different colours
RBBGYRRBBGGYYRR
after sorting would look like
BBBBGGGRRRRRYYY
this should solve the issue
/*my answer is O(n), where n is the size of the guess*/
string (string& sol, string& guess) {
int color=0, location=0;
int used[4];
used[0] = used[1] = used[2] = used[3] = 0;
for (int i = 0; i
aah well i was using a hashmap that stores the number of colors used. each time you check a color for location, if fails, then you check if there are still remaining. If there is then decrease the hashmap[color] by 1;
Here\’s a hint:
Just create two hashtables with color->count maps.
iterate over the guess, and increment colorcount;
Do a end to end scan to figure out what locations match.
O(n).
let us consider 4 location to fill [1],[2],[3],[4].
and four boxes containing balls of color blue[b],yellow[y],red[r],&green[g].
now [1] location can be filled by any type of balls.so it can be filled by any of 4 color balls.
now [2] location can be filled by any type of balls.so it can be filled by any of 4 color balls.
now [3] location can be filled by any type of balls.so it can be filled by any of 4 color balls.
now [4] location can be filled by any type of balls.so it can be filled by any of 4 color balls.
now the total of arrangements is equal to =4*4*4*4
=256
but at one time only one arrangement is possible with location.
so a chance that one will guess a right solution is =1\256.
a chance that one will guess wrong solution is 255\256.
hence our response to the user for a solution is 1\256
and for wrong guess is 255/256.
We can use 2 Lists one to hold elements of solution and one to hold elements of guess. We need 2 counters locCnt which counts number of Locations and clrCnt which counts number of colors. Now take each color in guess list and find the index of this color in Solution list if index of this color in solution list matches index of color in guess list matching location is found, increment location count and replace element at this location in solution list with a dummy value so that it is not used again, if color element is not found in solution at all continue with next element in guess list, if color element is found in solution list at an index different than that of the guess list check if guess list has same color at the index returned from solution list if so just continue as this will be accounted for later, if not increment the color count by one and replace the element in solution list with a dummy value so that it is not used again..
Lets say solution is ‘RGTS’
and the guess is ‘PSTO’
Put these two in two arrays
arr_sol = {R ,G ,T , S}
arr_guess = { P, S , T ,O}
now take two counter
location_count =0
colour_count = 0
logic for the same is :
(This logic is applicable for n colours of solution)
for (i =1 to length.arr_sol) {
for (j=1 to lenght.arr_guess){
if(arr_guess[j] == arr_guess[i]) {
if(j==i) {
location_count++;
}else{
colour_count++;
}
}//end of innner for
}//end of outer for
if (location_count == lenght.arr_guess && colour_count == 0){
print”This is the right solution ”
}else {
print ” The solution is incorrect”
}
print “The number of colur and location as :
colour_count and location_count “
We have to consider one more scenario in our answer:
correction solution: BYRG
guess:YYRG
Here, the correct response would be 1 location.
But using Chetna’s solution above, we will get 1 location, 1 color.
so we have to have n*n(where n are number of spots) comparisons to check this case out:
for(i=1; i
int pos = 0;
int col = 0;
for (int i = 0; i -1)
{
col++;
}
}
Sorry, the answer to the example above is 3 locations, 0 color
Leave an Answer/Comment