Microsoft Interview Question
Software Engineer / DevelopersThe solution to this is really easy..
findHits(char *sol, char *guess)
{
int hits = 0, phits = 0;
int arrS[4]={0,0,0,0}, arrG[4]={0,0,0,0};
while(*sol != '\0') {
if(*sol == *guess) {
hits++;
}
else {
arrS[getIndex(*sol)]++;
arrG[getIndex(*guess)]++;
}
sol++; guess++;
}
for(int i = 0i i<4; i++) {
phits += min(arrS[i],arrG[i]);
}
// print hits n phits
}
Algo:
First check each char from guess with solution. If they match hit++, store the char. Take that char off from the solution.
Eliminate all the char which produce a hit (i.e. all Gs gone).
Sort the remaining (to remove all duplicates)
Then check if any of the remain char exist in the solution.
1. Hoping the algo is complete
2. Guessing that it is highly inefficient. If any one has ideas of how to make it more efficient / a more elegant solution please do post it
1. First scan the solution string and insert characters into the hashtable.
2. Now take the guess string.
a) Check if guess string char at i is equal to solution char at i
b) If it is then hits++
c) Otherwise, check if the guess string char is in the hashtable
d) If it is then pseudo-hits++
string solution = "RGGB";
string guess = "YRGB";
//creata hash entries for solution string
Hashtable HTable = new Hashtable();
HTable.Add(0, solution[0]);
HTable.Add(1, solution[1]);
HTable.Add(2, solution[2]);
HTable.Add(3, solution[3]);
for(int i = 0; i < guess.Length; i++)
{
if(guess[i] == solution[i])
{
hits++;
continue;
}
if(HTable.ContainsValue(guess[i]))
pseudoHits++;
}
I would also use a hashtable to allow O(1) lookup. Since the string is 4 characters, not including NULL, it's alright to search it iteratively by O(n). Basically, do a pairwise comparison...
Vars:
unsigned rHits=0;
unsigned pHits=0;
for(int i=0;i<str.length;i++)
if(str.charAt(i) != table.getValue(i))
rHits++;
else
pHits++;
btw checking if hashtable contains certain value is not O(1). hashtable runs in O(1) if you have key and retrieve the associated value. under different keys, if you store same values they will be mapped to different buckets so it is O(n). thus, not better than doing brute force linear search on solution array.
char *solution = "RGGB";
char *guess = "YRGB";
int realHit = 0;
int pseudoHit = 0;
for (int i=0; i<4; i++) {
if (solution[i] == guess[i]) {
realHit++;
guess[i] = 0;
solution[i] = 0;
}
}
for (i=0; i<4; i++) {
if (guess[i] == 0) continue;
for (int j=0; j<4; j++) {
if (guess[i] == solution[j]) {
pseudoHit++;
guess[i] = 0;
solution[j] = 0;
}
}
}
char *Soln = "RGGB"
char *Guess = "YRGB"
int iHit = 0;
int iPseudo = 0;
int iTemp = 0;
for(int i = 0;i < 4;i++) // First check for real hits
{
if(Soln[i] == Guess[i])
iHit++;
else
{
Soln[iTemp] = Soln[i];
Guess[iTemp] = Guess[i];
iTemp++;
}
}
for(int i = 0;i < iTemp;i++) // Check for Pseudo hits in the reduced array
{
for(int j = 0;j < iTemp;j++)
{
if(Guess[i] == Soln[j] && Soln[j] != 0)
{
iPseudo++;
Soln[j] = 0;
}
}
}
I just realized that you can do this in O(n) but we'd have to destroy the original string, but, thats fine because it is being done within a function.
Bugs and bashes welcome :)
Gayle- Awesome site!
Cheers!
Sunil Jagadish
-------------------------------------------
#include<stdio.h>
#include<string.h>
#define SIZE 10
void find_hits(char *, char *);
int main()
{
char org_str[SIZE], guess_str[SIZE];
printf("\nEnter the original string and the guess: ");
scanf("%s %s",org_str,guess_str);
find_hits(org_str, guess_str);
}
void find_hits(char *org, char *soln)
{
int hits=0, pseudohits=0;
int i=0;
char *c;
while(soln[i] != '\0')
{
if(tolower(soln[i]) == tolower(org[i]))
{
hits++;
i++;
continue;
}
// Get the first occurance of the character in the original str
ng
c = strchr(org, soln[i]);
if(c != NULL)
{
// If it is found, then set the character to '0' so that a
// second match isnt wrongly considered as a pseudo-hit
memset(c, '0', sizeof(char));
pseudohits++;
}
i++;
}
printf("\nOriginal string: %s\n\n", org);
printf("\nOutput:\nNo. of hits = %d\nNo. of pseudo-hits = %d\n\n",hits,
pseudohits);
}
This solution fails in some cases:
Suppose SIZE = 5, and
sol = rbbyr
org = rgbyg
then in the second iteration,
sol[1] != org[1], you find the pointer to location where 'b' lies in the org string, and replace it with '0'. But then in the third iteration, the sol string has 'b' in the correct position, but since org str has '0' in that position, this hit is not identified and also it is not identified as pseudo hit.
I hope its clear that the solution is not perfect. I think the hash table approach is good enough here. Please let me know if I am wrong here.
Solve in O(n)
string a1="RGGB";
string a2="YRGB";
map<char, bool> color;
int hit=0;
int p_hit=0;
for(int i=0;i<4;i++)
{
if(!color[a1[i]])
color[a1[i]]=1;
if(a2[i]==a1[i])
{
hit++;
a2[i]='0';
}
}
for(int i=0;i<4;i++)
{
if(a2[i]!='0')
if(color[a2[i]])
p_hit++;
}
cout<<hit<<":"<<p_hit<<endl;
Little improvement on J.C.'s solution. Your solution won't give correct answer if my guess string, ie.a2 in your case is 'GGGG' or 'BGBG'. it has a flaw that in color you need to swap the boolean value once you find a hit. below is the modified code. i made little modification.
#include <map>
string a1="RGGB";
string a2="BGBG";
map<char, bool> color;
int hit=0;
int p_hit=0;
int len = a1.length();
for(int i=0;i<len;i++)
{
if(!color[a1[i]])
color[a1[i]]=1;
if(a2[i]==a1[i])
{
hit++;
a2[i]='0';
color[a1[i]] = 0;
}
}
for(int i=0;i<len;i++)
{
if(a2[i]!='0')
if(color[a2[i]])
{
p_hit++;
color[a2[i]] = 0;
}
}
cout<<hit<<":"<<p_hit<<endl;
sorry it massed up i believe. my code is fine, but as this is first time i am posting on it, i didn't know the laws for pasting code. anyways my major changes are visible, but somehow map declration is massed up as well as for loop and cout. so please follow J.C.'s code for this fragments...
package com.careercup.book.four.one;
import java.util.HashMap;
import java.util.Map;
public class NINETEEN_FIVE {
public static void main(String[] args) {
char[] solution = new char[] { 'R', 'G', 'G', 'B' };
char[] guess = new char[] { 'Y', 'R', 'G', 'B' };
displayHits_PsuedoHits(solution, guess);
}
protected static void displayHits_PsuedoHits(char[] solution, char[] guess) {
Map<Integer, String> solutionMap = new HashMap<Integer, String>();
for (int i = 0; i < solution.length; i++) {
solutionMap.put(i, solution[i] + "");
}
int hits = 0, pseudoHits = 0;
for (int i = 0; i < guess.length; i++) {
if (guess[i] == solution[i]) {
hits++;
continue;
}
if (solutionMap.containsValue(guess[i] + "")) {
pseudoHits++;
}
}
System.out.println("Hits: " + hits);
System.out.println("pseudoHits: " + pseudoHits);
}
}
Output:
Hits: 2
pseudoHits: 1
thats really good thinking in writing the code but I want to point out some bugs in there. Please correct me if I am wrong.
- vikram January 16, 20061) Strings that you declared need to be declared as Arrays
2) You will have to delete the particular record from array and rearrange the array as soon as you find the "hit" because you will be comparing the non-hit ones with already hit ones. I hope you understand what I am trying to say.