Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

My solution, using backtracking:

def findPercent(word, glossary):
    answer = 0

    for i in range(1, len(word) + 1):
        sub = word[:i]
        if sub in glossary:
            answer = max(answer, len(sub) + findPercent(word[i:], glossary))
        else:
            answer = max(answer, findPercent(word[i:], glossary))

    return answer


if __name__ == '__main__':
    word = "catdog"
    glossary = ["dog", "frog", "cat", "c"]

    print findPercent(word, glossary) * 100.0 / len(word)

- techinterviewquestion.com June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

lst = ['dog', 'frog', 'cat']
inputStr = sys.argv[1]
score = 0
for word in lst:
  if word in inputStr:
    score = score + (float(len(word))/float(len(inputStr)))
score = score*100
print 100 if score > 100 else score

- cs007 June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@cs007, I get 116.667% for below test case with your code which I believe is incorrect.

// list of words: ['dog', 'frog', 'cat', 'c']
// inputstr: "catdog"

- localghost June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

}

- xyyz June 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys
list=["dog","frog","cat"]
use=raw_input("Enter the input string ")

for x in range(0,(len(list)-1)) :
    for y in range(0,(len(use)-1)):
        if use[y:y+2] == list[x]:
            score=score+1




if score==3:print "100%"
elif score==2:print "66%"
elif score==1:print"33%"
else :print"--0%--"

- nandagirisaipranay June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- mithunstuff June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Modified Aho-Corasick Trie/FSM algorithm can do a search in O(n + m + k), where n - length of the input string, m - total length of all words in the dictionary, k - number of matches.

- passenger June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ToanVu June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def percent_match(an_list, mat_str):
    perc = []
    leng = 0
    for x in an_list:
        if x in mat_str:
            perc.append(x)
            leng += len(x)
    percent = (float(leng)/float(len(mat_str)))*100
    return percent

- Indraja.Punna June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chris June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- bobbyw June 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a doubt may be its trivial , but for the case

string = "dogdog" glossary = {"cat","dog","frog"}
what should the precentage match be ? (100% OR 50%)

- Shashidhar V G June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Also have a doubt for case

String = "dofrog" & glossary=["dof","cat","frog"]
what should the percentage match be ? 100% OR 66.66% ?

- shashidharvg June 28, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More