Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
With a little more consideration, the entire approach, which is easy to read now, can be improved to operate at quicker:
public static void bullsAndCows(String p1, String p2){
if(p1 == null){
throw new NullPointerException();
}
if(p2 == null){
throw new NullPointerException();
}
int bulls = 0;
int index = 0;
int[] p1Counts = new int[256];
int[] p2Counts = new int[256];
while(index < p1.length() && index < p2.length()){
char p1C = p1.charAt(index);
char p2C = p2.charAt(index);
if(p1C == p2C){
bulls++;
}
p1Counts[p1C]++;
p2Counts[p2C]++;
index++;
}
for(index; index < p1.length(); index++){
p1Counts[p1.charAt(index)]++;
}
for(index; index < p2.length(); index++){
p2Counts[p2.charAt(index)]++;
}
int cows = 0;
for(int i = 0; i < p1Counts.length; i++){
cows += Math.min(p1Counts[i], p2Counts[i]);
}
cows -= bulls;
System.out.println("Bulls - "+bulls+", Cows = "+cows);
}
There are two things missing:
1. "The characters are case insensitive."
2. how about A - forum B - fourm, bulls - 3 cows - 2, but your code would be wrong.
public static void bullsAndCows(String p1, String p2){
if(p1 == null || p2 ==null)
throw new NullPointerException();
int[] p1Counts = new int[256];
int[] p2Counts = new int[256];
int n=p1.length();
int m=p2.length();
// find the bulls at the same location k
int k=0, bulls=0;
while (k<m && k<n) {
if (p1.toLowerCase().charAt(k) == p2.toLowerCase().charAt(k)) {
bulls++;
}
k++;
}
// store each char in array
for(int i=0; i < n; i++){
p1Counts[p1.toLowerCase().charAt(i)]++;
}
for(int j=0; j < m; j++){
p2Counts[p2.toLowerCase().charAt(j)]++;
}
int cows = 0;
for(int i = 0; i < 256; i++){
cows += Math.min(p1Counts[i], p2Counts[i]);
}
cows -= bulls;
System.out.println("Bulls = "+bulls+", Cows = "+cows);
}
public static void main (String[] args ) {
bullsAndCows("Picture","Epic");
bullsAndCows("forum","four");
}
correct me if I am wrong. Thx
This is a simple java code.
import java.util.ArrayList;
import java.util.HashMap;
public class BullsAndCows {
public static int[] getBullsAndCows(String A, String B) {
int bulls = 0;
int cows = 0;
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
A = A.toLowerCase();
B = B.toLowerCase();
for(int i=0; i<A.length(); i++) {
int a = A.charAt(i);
if(!hm.containsKey(a)) {
ArrayList<Integer> array = new ArrayList<Integer>();
array.add(i);
hm.put(a, array);
}
else {
ArrayList<Integer> array = hm.get(a);
array.add(i);
hm.put(a, array);
}
}
for(int i=0; i<B.length(); i++) {
int b = B.charAt(i);
if(hm.containsKey(b)) {
ArrayList<Integer> array = hm.get(b);
if(array.contains(i)) {
bulls++;
}
else {
cows++;
}
}
}
int res[] = new int[2];
res[0] = bulls;
res[1] = cows;
return res;
}
public static void main(String args[]) {
int array[] = getBullsAndCows("forum", "four");
System.out.println("Bulls = " + array[0] + "," + "Cows =" + array[1]);
}
}
def cows(a, b):
bull_count, cow_count = 0, 0
x = [x.lower() for x in a]
y = [y.lower() for y in b]
for i in range(len(y)):
if i < len(x): # prevent out of bounds
if x[i] == y[i]:
bull_count += 1
elif y[i] in x:
cow_count += 1
else:
break
print("A - {} B - {}, bulls - {}, cows - {}".format(a, b, bull_count, cow_count))
def cows_and_bulls(word_a, word_b):
'''
@param word_a: word a chose
@type word_a: str
@param word_b: word b chose
@type word_b: str
@return: 2-tuple with bulls and cows count
@rtype: (int,int)
'''
word_a = list(word_a.lower())
word_b = list(word_b.lower())
bulls_count = 0
cows_count = 0
for i in range(0, min(len(word_a), len(word_b))):
if word_a[i] == word_b[i]:
bulls_count += 1
elif word_b[i] in word_a:
cows_count += 1
return (bulls_count, cows_count)
print(cows_and_bulls("Picture", "Epic")) # (0,4)
print(cows_and_bulls("forum", "four")) # (2,2)
Here is java version - would love to head any other solution which would reduce the time complexity.
output
Words: forum,four; Bulls: 2, Cows: 2
Words: Picture,epic; Bulls: 0, Cows: 4
Words: forum,four; Bulls: 2, Cows: 2
Words: Picture,epic; Bulls: 0, Cows: 4
public class CowsnBullsGame {
/**
* o(n square)
* @param playerA
* @param playerB
*/
private static void findCowsandBulls(String playerA, String playerB){
//if any of the strings are null, the game cannot be played
if( playerA == null || playerB == null ) return;
int bulls = 0;
int cows = 0;
//for the string selected by player A
for( int i = 0; i < playerA.length(); i++ ){
char runnerChar = playerA.charAt(i);
//run thru all the characters in word selected by player B
for( int j = 0; j < playerB.length(); j++ ){
char playerBChar = playerB.charAt(j);
//character match - change to lower because case does not matter
if( Character.toLowerCase(runnerChar) == Character.toLowerCase(playerBChar) ){
if( i == j ){ //position match
bulls++;
}
else{ //contains relation
cows++;
}
}
}
}
System.out.println("Words: " + playerA + "," + playerB + "; Bulls: " + bulls + ", Cows: " + cows);
}
/**
* o(m+n) //length of both the strings
* @param playerA
* @param playerB
*/
private static void findCowsandBullsWithArray(String playerA, String playerB){
//if any of the strings are null, the game cannot be played
if( playerA == null || playerB == null ) return;
int bulls = 0;
int cows = 0;
//put the string the array
List playerBList = new ArrayList();
for (char c : playerB.toCharArray()) {
playerBList.add(Character.toLowerCase(c));
}
//for the string selected by player A
for( int i = 0; i < playerA.length(); i++ ){
char runnerChar = Character.toLowerCase(playerA.charAt(i));
if( playerBList.contains(runnerChar)){
if( playerBList.indexOf(runnerChar) == i){ //position match
bulls++;
}
else{
cows++;
}
}
}
System.out.println("Words: " + playerA + "," + playerB + "; Bulls: " + bulls + ", Cows: " + cows);
}
public static void main(String[] args) {
CowsnBullsGame.findCowsandBulls("forum", "four");
CowsnBullsGame.findCowsandBulls("Picture", "epic");
CowsnBullsGame.findCowsandBullsWithArray("forum", "four");
CowsnBullsGame.findCowsandBullsWithArray("Picture", "epic");
}
}
public int[] CowsGame(String A, String B) {
int[] result = new int[2];
if (A == null || B == null) {
return result;
}
int cowCount = 0, bullCount = 0;
// convert all characters into lowercase
A = A.toLowerCase();
B = B.toLowerCase();
for (int i = 0; i < B.length(); i++) {
for (int j = 0; j < A.length(); j++) {
if (B.charAt(i) == A.charAt(j)) {
if (i == j) {
cowCount++;
} else {
bullCount++;
}
}
}
}
result[0] = cowCount;
result[1] = bullCount;
return result;
}
public int[] CowsGame(String A, String B) {
int[] result = new int[2];
if (A == null || B == null) {
return result;
}
int cowCount = 0, bullCount = 0;
// convert all characters into lowercase
A = A.toLowerCase();
B = B.toLowerCase();
for (int i = 0; i < B.length(); i++) {
for (int j = 0; j < A.length(); j++) {
if (B.charAt(i) == A.charAt(j)) {
if (i == j) {
cowCount++;
} else {
bullCount++;
}
}
}
}
result[0] = cowCount;
result[1] = bullCount;
return result;
}
enum Result {
BULL, COW;
}
public static void guess(String str1, String str2) {
Result[] result = new Result[str1.length()];
for (int i = 0; i < str2.length(); i++) {
int index = str1.indexOf(str2.charAt(i));
if (index == -1) {
continue;
} else {
if (i < str1.length() && str1.charAt(i) == str2.charAt(i)) {
result[index] = Result.BULL;
} else if (result[index] == null) {
if (index == i) {
result[index] = Result.BULL;
} else {
result[index] = Result.COW;
}
}
}
}
int bulls = 0;
int cows = 0;
for (int i = 0; i < result.length; i++) {
if (result[i] == Result.BULL) {
bulls++;
} else if (result[i] == Result.COW) {
cows++;
}
}
System.out.println("Bulls: " + bulls + " Cows: " + cows);
}
This solution work only if there are no duplicates:
public class BullsnCows {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String A,B;
A = "forum";
B = "four";
int cow = 0;
int bull = 0;
//int minLength = Math.min(A.length(),B.length());
for(int i=0;i<A.length();i++){
char a = A.charAt(i);
for(int j=0;j<B.length();j++){
if(a == B.charAt(j)){
if(i!=j){
cow++;
}
else{
bull++;
}
}
}
}
System.out.println("The number of cows are: "+cow+" and bulls: "+bull);
}
}
Logic:
1. Take the longest string and create countMap by storing the number of occurrences of its character
2. Iterate over the small string and check for exact position match
3. If matches then increment bull
4. Else, Look for the character presence in the countMap
4.1 If character present, then increment cows, decrement the countMap at the corresponding position
5. Stop
public class CowBull {
public static int[] hashify(String str){
char ch[] = str.toCharArray();
int arr[] = new int[256];
for(int i=0; i<256;i++){
arr[i] = 0;
}
for(int i=0; i<str.length();i++){
arr[ch[i]] += 1;
}
return arr;
}
public static void computeCowBull(String str1, String str2){
int len1 = str1.length();
int len2 = str2.length();
int countMap[], min, i, cows=0, bulls=0;
if(len1 > len2){
min = len2;
countMap = hashify(str1);
}
else{
min = len1;
countMap = hashify(str2);
}
char ch1[] = str1.toCharArray();
char ch2[] = str2.toCharArray();
for(i=0;i<min;i++){
if(ch1[i]==ch2[i]){
bulls++;
}
else{
if(min==len1){
if(countMap[ch2[i]] > 0){
cows++;
countMap[ch2[i]] -=1;
}
}
else{
if(countMap[ch1[i]] > 0){
cows++;
countMap[ch1[i]] -=1;
}
}
}
}
System.out.println("Cow is: "+cows);
System.out.println("Bull is: "+bulls);
}
public static void main(String[] args){
computeCowBull("ape","apple");
}
}
public static void bullsAndCows(String p1, String p2) {//duplicate element may lead to different result, thus we do'not consider that condition
if(p1==null||p2==null){
return ;
}
int bulls=0;
int cows=0;
HashMap<Character,Integer> map= new HashMap<>();
for(int i=0;i<p1.length();i++){
map.put(p1.charAt(i), i);
}
for(int j=0;j<p2.length();j++){
char cur=p2.charAt(j);
if(map.containsKey(cur)){
if(map.get(cur)==j){
bulls++;
}else
cows++;
}
}
System.out.println("bulls"+bulls+"cows"+cows);
}
public class CowsAndBulls {
public static void printResult(String A, String B){
int cows = 0, bulls =0;
int a = A.length();
int b = B.length();
for(int i = 0; i <A.length(); i++) {
for(int j = 0; j< B.length(); j++) {
if((i==j) && A.charAt(i) == B.charAt(j)) {
bulls++;
} else if(A.charAt(i) == B.charAt(j)) {
cows++;
}
}
}
System.out.println("cows:" +cows +" bulls:" +bulls);
}
public static void main(String[] args) {
String A = "Picture";
String B = "Epic";
printResult(A.toLowerCase(), B.toLowerCase());
}
}
public class CowsAndBulls {
public static void printResult(String A, String B){
int cows = 0, bulls =0;
int a = A.length();
int b = B.length();
for(int i = 0; i <A.length(); i++) {
for(int j = 0; j< B.length(); j++) {
if((i==j) && A.charAt(i) == B.charAt(j)) {
bulls++;
} else if(A.charAt(i) == B.charAt(j)) {
cows++;
}
}
}
System.out.println("cows:" +cows +" bulls:" +bulls);
}
public static void main(String[] args) {
String A = "Picture";
String B = "Epic";
printResult(A.toLowerCase(), B.toLowerCase());
}
}
What are you thinking to do with duplicates? Should we keep a track for them too?
Here is my implementation for the same in c++
Complexity: O(m+n)
#include<iostream.h>
int cows=0, bulls=0;
string a,b;
bool find(char ch)
{
for(int i=0;i<a.length();i++)
{
if(a[i]==ch)
return true;
}
return false;
}
int main()
{
int i=0;
cout<<"\n Enter a and b";
cin>>a>>b;
while(i<a.length()&&i<b.length())
{
if(a[i]==b[i]) bulls++;
else
{
if(find(b[i])) cows++;
}
i++;
}
int j= b.length();
j-=-a.length();
if(j>0)
{
if(find(b[j--])) cows++;
}
cout<<bulls<<" "<<cows;
return 0;
}
I believe the correct answer for A - Picture B- Epic is Bulls - 0, Cows = 2, A - forum B - four, bulls - 2 cows - 2.
Here's the code.
#include <iostream>
#include <string>
#include <tr1/unordered_map>
using namespace std;
int main()
{
string str1 = "forum";
string str2 = "four";
tr1::unordered_map<char,int> str_map;
string::iterator it;
for(it=str1.begin(); it!= str1.end(); ++it)
str_map[*it] = 1;
unsigned int i = 0, cows = 0, bulls = 0;
while(i != str1.length() && i != str2.length())
{
char a = str1.at(i);
char b = str2.at(i);
if(a == b)
bulls++;
else if(str_map.count(b))
cows++;
i++;
}
cout<<"\nBulls = "<<cows<<"\tCows = "<<cows<<"\n";
}
For
A - Picture
B- Epic
Answer should be Bulls - 0, Cows = 4. Isn't it?
B[0] = 'E' is in A at A[6]
B[1] = 'p' is in A[0]
B[2] = 'i' is in A[1]
B[3] = 'c' is in A[2]
/**
The cows and bulls game, Player A chooses a word and player B guesses a word. You say bulls when a character in the player B's guess match with a character in player A's word and also it is in the corect position as in A's word. You say cows, when a character in the player B's word match the character in player A, but it is not in the correct position. The characters are case insensitive. Given two words player A's and player B's,Write a function that return the number of bulls and no of cows. For example,
A - Picture B- Epic, bulls -0, cows - 4
A - forum B - four, bulls - 3 cows - 1
*
*/
/**
A functions to get the count of cows and bulls.
*/
ArrayList<Integer> getCowsandBulls(String s1, String s2){
// This result array is to hold the results.
List<Integer> result = new ArrayList<>(); // result[0] is bulls, result[1] is cows
// A set of characters to be used primarily for finding char in a set
Set<Character> chars = new HashSet<>();
int l1 = str1.length();
int l2 = st2.length();
Char a1[] = s1.toArray();
Char a2[] = s2.toArray();
int bulls = 0, cows = 0;
// Travserse over the array A and put its character in a character set.
for(int i=0;i<l1;i++){
chars.put(a1[i]);
}
int i = 0;
while(i != l1 && i != l2)
{
if(a1[i] == a2[i]){
bulls++;
}
if(chars.contains(a2[i]))
{
cows++;
}
i++;
}
result[0] = bulls;
result[1] = cows;
return result;
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class BullsAndCows {
static List<Integer> result = new ArrayList<>();
static void getCowsandBulls(String s1, String s2){
// This result array is to hold the results.
// result[0] is bulls, result[1] is cows
// A set of characters to be used primarily for finding char in a set
Set<Character> chars = new HashSet<>();
int l1 = s1.length();
int l2 = s2.length();
char a1[] = s1.toLowerCase().toCharArray();
char a2[] = s2.toLowerCase().toCharArray();
int bulls = 0, cows = 0;
// Travserse over the array A and put its character in a character set.
for(int i=0;i<l1;i++){
chars.add(a1[i]);
}
int i = 0;
while(i != l1 && i != l2)
{
if(a1[i] == a2[i]){
bulls++;
}
if(chars.contains(a2[i]))
{
cows++;
}
i++;
}
result.add(bulls);
result.add(cows);
return;
}
public static void main(String[] args){
getCowsandBulls("Picture","epic");
System.out.println("Bulls : " + result.get(0));
System.out.println("Cows : " + result.get(1));
}
}
O(length(A) + length(B)) time solution:
#include <iostream>
using namespace std;
int charSet[256];
int main()
{
string A = "Picture";
string B = "Epic";
for(int i = 0; i<A.length(); i++) A[i] = toupper(A[i]);
for(int i = 0; i<B.length(); i++) B[i] = toupper(B[i]);
for(int i = 0; i<A.length(); i++) charSet[A[i]] =1;
int bull = 0, cow = 0;
for(int i = 0; i<B.length(); i++){
if (i<A.length())
bull += A[i] == B[i];
cow += charSet[B[i]];
};
cow -= bull;
cout <<"bull = "<<bull<<endl<<"cow = "<<cow<<endl;
return 0;
}
void bullsAndCows(string s1, string s2) {
if (!s1.size() || !s2.size()) {
cout << "A - " << s1 << " B - " << s2 << ", bulls - 0, cows - 0" << endl;
return;
}
bool* charset = new bool[256]();
for_each(s1.begin(), s1.end(), [charset](char c){charset[tolower(c)] = true; });
int bull(0), cow(0);
for (int i = 0; i < s2.size(); ++i) {
if (charset[tolower(s2[i])]) {
if (i < s1.size() && tolower(s1[i]) == tolower(s2[i])) ++bull;
else ++cow;
}
}
cout << "A - " << s1 << " B - " << s2 << ", bulls - " << bull << ", cows - " << cow << endl;
return;
}
This can be easily computed in O(n + m) (where n is length of p1 and m is length of p2) by checking the bulls, and then computing the number of matches based on char type - number of bulls to answer the cows. Assuming the chars are unicode.
- zortlord November 12, 2014