## Microsoft Interview Question for Software Engineer / Developers

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

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.
1) 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.

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

The 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
}``````

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

Good Solution!!

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

what's getIndex???

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

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

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

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++

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

Save your optimizing for elsewhere -- we're talking about only four elements!

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

string solution = "RGGB";
string guess = "YRGB";

//creata hash entries for solution string
Hashtable HTable = new Hashtable();

for(int i = 0; i < guess.Length; i++)
{
if(guess[i] == solution[i])
{
hits++;
continue;
}

if(HTable.ContainsValue(guess[i]))
pseudoHits++;
}

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

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++;

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

the code feed got messed up

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

let's try that again w/ a minor bug fix...

for(int i=0;i<str.length;i++)
if(str.charAt(i) != table.getValue(i))
pHits++;
else
rHits++;

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

the 2nd condition should be...

!table.getValue(str.charAt(i))

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

You could try using an array but since the worst case is 16 comparisons, the overhead of using a hash table would probably be smaller than creating an array of 2^32 characters, assuming each color is a byte and 1 byte=8 bits.

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

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.

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

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;
}
}
}

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

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;
}
}
}

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

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!

-------------------------------------------

#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);
}

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

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.

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

The original string is actually destroyed because it is passed as a reference to the function :)

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

I think, in above solution, even if the outer for loop is O(n), we are not considering the complexity of strchr function. Its not some magic function, but internally searches the string sequentially to find out the occurrence.

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

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;

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

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;``````

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

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...

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

static hash[26];
j=0;
for(i=0;i<n;++i)
{
if(solu[i]== guess[i])hit++;
else { guess[j++]= guess[i]; hash[tolower(solu[i])-97]= 1;
}

for(i=0;i<j;++i)
if(hash[tolower(guess[i])-97)]==1){ pseudohit++; hash[tolower(guess[i])-97)]= 0;}

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

static hash[26];
j=0;
for(i=0;i<n;++i)
{
if(solu[i]== guess[i])hit++;
else { guess[j++]= guess[i]; hash[tolower(solu[i])-97]= 1; }
}

for(i=0;i<j;++i)
if(hash[tolower(guess[i])-97)]==1){ pseudohit++; hash[tolower(guess[i])-97)]= 0;}

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

``````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

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

I don't understand that code. The user doesn't guess anything and there's no interaction. How is that supposed to work?

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

I used the hashtable approach with O(n) but I got rejected. He guided me to use replace characters approach which is O(n^2). I tried to explain why I used hashtable but he wasn't interested and he said time is up and they rejected me after

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.