Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
public class percentage {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
String str1 = input.nextLine();
String str2;
float percentage=0;
List<String> lt = new ArrayList();
for( int i=0;i < 2; i++)
{
str2 = input.nextLine();
lt.add(str2);
}
for( int i =0; i<2; i++ )
{
String strfind = lt.get(i);
System.out.println("it is here 1"+ strfind);
if( str1.contains(strfind))
{
System.out.println("it is here"+ strfind);
percentage = percentage + (strfind.length()*100.0f/str1.length());
}
}
System.out.println("the percentage for this"+percentage);
}
}
public static double percentMatch(string str, List<string> list)
{
double result = 0;
foreach(string word in list)
{
int n = word.Length;
int pos = 0;
while(pos + n <= str.Length)
{
if(percentMatch(str, pos, word))
{
result += word.Length;
break;
}
pos += n;
}
}
return result / str.Length;
}
private static bool percentMatch(string str, int pos, string word)
{
for(int i=0; i<word.Length; i++)
{
if(word[i]!=str[pos+i])
{
return false;
}
}
return true;
}
import java.util.ArrayList;
public class MatchDictionary {
public static void main(String[] args){
ArrayList<String> dictionary = new ArrayList<>();
dictionary.add("cat");
dictionary.add("dog");
dictionary.add("frog");
System.out.println(formatOutput(getMatch("catkddogfhat", dictionary)));
}
private static float getMatch(String text, ArrayList<String> dictionary){
if (dictionary.contains(text)){
return 1f;
}
if (text.length() ==0){
return 0;
}
float max = 0f;
float length = text.length() * 1f;
for (int i = 1; i< length; i++){
float temp = i/length * getMatch(text.substring(0, i), dictionary) + (length-i)/length *getMatch(text.substring(i, text.length()), dictionary);
if (max < temp){
max = temp;
}
}
return max;
}
private static String formatOutput(float rate){
return String.format("%.2f %%", rate*100);
}
}
it's a DP problem:
c[i]=max(c[i-l]+l, c[i-l]) / if a match (length l) was found, for all matches ending at position i
c[i]=c[i-1] / if no matches end in i
c[i]=0 / if i =0 (supose the input string starts at 0)
result is: c[n] *100 / input string length
the code:
#include <vector>
#include <string>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int StartsWith(const string& input, int off, const string& match);
int PercentageMatch(const string& input, const list<string>& dict)
{
if (input.size() == 0) return 100;
vector<int> c(input.size()+1, 0);
for (int i = 0; i < input.size(); ++i)
{
for (list<string>::const_iterator di = dict.begin(); di != dict.end(); ++di)
{
int l = StartsWith(input, i, *di);
if (l > 0) c[i + l] = max(c[i + l], c[i] + l);
}
c[i + 1] = max(c[i + 1], c[i]);
}
return 100 * c[input.size()] / input.size();
}
int main()
{
list<string> dict1({ "dog", "frog", "cat" }); // it said a list in the question
cout << "case 1: " << PercentageMatch("catdog", dict1) << "%" << endl;
cout << "case 2: " << PercentageMatch("cardog", dict1) << "%" << endl;
list<string> dict2({ "a", "b", "c", "da", "daf", "fghjkl" });
cout << "case 3: " << PercentageMatch("abc", dict2) << "%" << endl;
cout << "case 4: " << PercentageMatch("adaf", dict2) << "%" << endl;
cout << "case 5: " << PercentageMatch("dafghjkl", dict2) << "%" << endl; // here he must backtrack, the greedy version will not have 100% because it takes daf and misses the fghjkl
}
int StartsWith(const string& input, int off, const string& match)
{
// depending on the count of items and the length of the input string it may pay off creating a trie and using it character by character
// from the outher loop below
if (input.size() - off < match.size()) return 0;
for (int i = 0; i < match.size(); ++i)
{
if (input[off + i] != match[i]) return 0;
}
return match.size();
}
import java.util.Arrays;
public class MatchString {
public static void main(String[] args) {
System.out.println(findMatch("cardog", new String[] { "cat", "frog",
"dog" }));
}
static double findMatch(String word, String[] glossary) {
String mask = word;
final char maskChar = '\0';
for (int i = 0; i < glossary.length; i++) {
String filler = fill(glossary[i].length(), maskChar);
mask = mask.replace(glossary[i], filler);
}
int match = 0;
for (int i = 0; i < mask.length(); i++) {
if (mask.charAt(i) == maskChar) {
match++;
}
}
return (100.0 * ((double) match) / ((double) word.length()));
}
static String fill(int length, char charToFill) {
if (length > 0) {
char[] array = new char[length];
Arrays.fill(array, charToFill);
return new String(array);
}
return "";
}
}
My solution, using backtracking:
- techinterviewquestion.com June 08, 2016