Google Interview Question for Software Engineers


Country: United States




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

dp solution

public int match (String target, String source){
		int [][] f = new int[target.length() + 1][source.length() + 1] ;
		for (int i = 0 ; i <= source.length() ; ++i) {
			f[0][i] = 1;
		}
		f[0][0] = 1;
		for (int i = 1 ; i <= target.length() ; ++i) {
		 for (int j = 1 ; j <= source.length() ; ++j) {
			 if (target.charAt(i - 1) == source.charAt(j - 1)) {
				 f[i][j] = f[i - 1][j - 1] + f[i][j - 1] ;  
			 } else{
				 f[i][j] = f[i][j - 1] ;
			 }
		 }
		}
		return f[target.length()][source.length()] ;

}

- Scott March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Scott.
Can you please explain me the question. I am not able to comprehend it correctly.
My confusion is isn't "cat" and "CATapult" a continuous match ?

- um01 March 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also why are we changing them to capital letters..

- Ramesh March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@umahida
the question is to count how many cat can be found in catapult

- Scott March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Scott got it
So its like we looking for subsequences of CAT in catapult ?

- um01 March 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scott, could you please explain why are you adding the top and top-left cells in case of equals?

- Sam March 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant top-left + left.

- Sam March 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant top-left + left.

- Sam March 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant top-left + left.

- Sam March 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Let me try to explain. f[i][j] means how many times target[0,i-1] appears in source[0,j-1]. So, if target[i] == source[j], f[i][j] = f[i-1][j-1](how many times target[0,i-2] appears in source[0,j-2]) + f[i-1][j] (how many times target[0,i-2] appears in source[0,j-1]).
if target[i] != source[j], f[i][j] = f[i][j-1](how many times target[0,i-1] appears in source[0,j-2]).

- wwu August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

One solution is recursion where each instance is to find all discontinuous matches of a string s1 in a string s2 for a certain substring of s1 and substring of s2.

Ex. Looking for "cat" in "catapault" involves looking for "at" in "atapault", "t" in "tapault", "t" in "pault", and "t" in "ult".

Base case is where the length of substring of s1 becomes 0 or the length of substring of s2 becomes 0

Pseudocode where s1 is smaller string, s2 is larger string, i is index in smaller string to start from, j is index in larger string to start looking from (i and j are just to reduce making new copies of strings)

fn(String s1, String s2, int i, int j) {
    
    if (i > s1.length - 1 || j > s2.length - 1) {
        return 0;
    }

    int total = 0;
    char firstChar = s1.get(i);
    for (int k = 0; k < s2.length; k++) {
        if (s2.get[k] == firstChar) {
            total += fn(s1, s2, i+1, k);
        }
    }
    return total;
}

Runtime: O(n^2)

- JW March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did the same thing, except i compare the last characters instead of the first. Good solution.

- Skor March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This code always returns 0 I guess, total is never updated, you are adding 0 to 0 in each recursion.

- tazo March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution::
Apologize for method and variable names

public class DiscontMatches {

	public static void main(String[] args) {
		Set<String> ans = findDiscMatches("cat", "catapult");
		for(String str : ans)
			System.out.println(str);
	}
	
	public static Set<String> findDiscMatches(String str1, String str2){
		Set<String> set = new TreeSet<>();
		Map<Character, List<Integer>> map = new LinkedHashMap<>();
		char [] arr = str2.toCharArray();
		char [] arr2 = str1.toCharArray();
		for(char c: arr2){
			int i = 0;
			for(char c2 : arr){
				if(c==c2){
					if(!map.containsKey(c))
						map.put(c, new ArrayList<Integer>());
					map.get(c).add(i);
				}
				i++;
			}
		}
		createSet(arr2, arr, set, map, 0, -1);
		return set;
	}
	
	private static void createSet(char [] str1, char [] str2, Set<String> set,
			Map<Character, List<Integer>> map, int str1Pos, int prevCharPos) {
		if(str1Pos == str1.length-1) {
			List<Integer> locations = map.get(str1[str1Pos]);
			for(int i : locations){
				if(i<=prevCharPos)
					continue;
				
				char [] clone = str2.clone();
				clone[i]-=32;
				set.add(new String(clone));
			}
		} else if(str1Pos < str1.length-1) {
			List<Integer> locations = map.get(str1[str1Pos]);
			for(int i : locations){
				if(i<=prevCharPos)
					continue;
				char [] clone = str2.clone();
				clone[i]-=32;
				createSet(str1, clone, set, map, str1Pos+1, i);
			}
		}
	}

}

- kn March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is similar except I computed only the "count" as the question asks only the
number of discontinuous matches.

Logic behind the code:

If "cat" is present in "catapult" then "at is present in "atapult" and "t" is present in "tapult". So by recursively adding the number of occurrences of each character in the substring we can get the number of discontinuous matches.

public static int discontinousMatch(String s1, String s2)
	{
		int total = 0;
		if(s1.length() == 1)
		{
			int count =0;
			while(s2.contains(s1))
			{
				count++;
				s2 = s2.substring(s2.indexOf(s1.charAt(0))+1);
				
			}
			return count;
		}
		
		char c = s1.charAt(0);
		
		int index = s2.indexOf(c);
		while (index < s2.length() && index > -1)
		{
			
			total += discontinousMatch(s1.substring(1), s2.substring(index+1));
			index = s2.indexOf(c, index+1);
		}
		
		return total;
	}

- Vijay March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use dynamic programming and modified LCS

- Anonymous March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DP Python code (only # of matches)

def DisconMatch(strA,strB):
    if not strA:
        return 0
    if not strB:
        return 0
    if len(strA)>len(strB):
        return 0

    m=len(strA)
    n=len(strB)

    DPmatrix=[[(0,-1) for x in range(n)] for y in range(m)]  # DP will remember (number, index) for matches found

    for i in range(m):
        for j in range(n):
            if strA[i]==strB[j]:
                if j==0 and i==0:
                    DPmatrix[i][j]=(1,j)
                elif i==0:
                    DPmatrix[i][j]=(DPmatrix[0][j-1][0]+1,j)
                elif j<i:
                    DPmatrix[i][j]=(0,-1)
                else:
                    DPmatrix[i][j]=(DPmatrix[i-1][j-1][0]+DPmatrix[i][j-1][0],j)

            else:
                if j==0:
                    DPmatrix[i][j]=(0,-1)
                else:
                    DPmatrix[i][j]=(DPmatrix[i][j-1][0],-1)

    print(DPmatrix)
    return DPmatrix[m-1][n-1]

print(DisconMatch("cat","catapult"))

- bboczeng March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it can be optimized by reducing the size of memoization matrix (since only the last row is used)

- bboczeng March 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Outputs the results in the requested format:
short string:
cat
long string:
catapult
3 => CATapult, CAtapulT, CatApulT,

std::vector<std::string> results;
char shortStr[128], longStr[128];

void DisconMatch(char* pShort, char* pLong)
{
   while ((pLong = strchr(pLong, *pShort)) != NULL)
   {
      *pLong = toupper(*pLong);
      if (!pShort[1])
         results.push_back(longStr);
      else
         DisconMatch(pShort+1, pLong+1);   
      *pLong++ = tolower(*pLong);
   }
}



void main()
{
   while (1)
   {
      printf("short string:\n");
      gets(shortStr);
      printf("long string:\n");
      gets(longStr);
      DisconMatch(shortStr, longStr);
      printf("%d => ", results.size());
      for (int i = 0; i < results.size(); i++)
         printf("%s, ", results[i].c_str());
      printf("\n");
      results.clear();     
   }
}

- tjcbs2 March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int countDiscontinuousMatches(String input, String word) {

        if (input == null || word == null || input.isEmpty() || word.isEmpty() || input.length() > word.length()) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) == input.charAt(0)) {
                count++;
                int n = countDiscontinuousMatches(input.substring(1), word.substring(i + 1));
                if (n != 0) {
                    count *= n;
                }
            }
        }
        return count;
    }

- Anonymous March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int countDiscontinuousMatches(String input, String word) {

        if (input == null || word == null || input.isEmpty() || word.isEmpty() || input.length() > word.length()) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) == input.charAt(0)) {
                count++;
                int n = countDiscontinuousMatches(input.substring(1), word.substring(i + 1));
                if (n != 0) {
                    count *= n;
                }
            }
        }
        return count;
    }

- recursive solution March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Solution:

public int findDisc(String a, String b) {
	
	return findDiscHelper(a, b);
}

public int findDiscHelper(String a, String b) {
	
	int count = 0;

	for (int i = b.length() - 1; i >= 0; i--) {

		if (b.charAt(i) == a.charAt(a.length()- 1)) {

			count += (a.length() <= 1) ? 1 : findDiscHelper(a.substring(0, a.length() - 1), b.substring(0 , i) );
		}
	}

	return count;
}

}

- SK March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DiscontinuedMatch {
	public static void main (String[] args) {
		System.out.println(discMatch("cat", "catapult"));
	}
	
	public static int discMatch(String a, String b) {
		if(a == null || b == null || a.length() > b.length()) return 0;
		return match(a, b, 0, 0);
	}
	
	public static int match(String a, String b, int ai, int bi) {
		if(ai >= a.length()) return 1;
		if(bi >= b.length()) return 0;
		
		int count = 0;
		
		for(int i=bi; i<b.length(); i++) {
			if(a.charAt(ai) == b.charAt(i)) {
				count+= match(a,b,ai+1,i+1);
			}
		}
		return count;
	}
}

- Anonymous March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry guys -- What is a discontinous match ? Can someone explain..

- Ramesh March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Efficient solution in Java below (uses helper function that tracks starting indices in order to avoid creating new substrings when calling the substring method on a String).

public class DiscontinuousMatches {

    public static int numMatches(String s1, String s2) {
        return numMatchesHelper(s1, s2, 0, 0);
    }

    private static int numMatchesHelper(String s1, String s2, int start1, int start2) {
        if (s1.length() - start1 > s2.length() - start2) return 0;
        if (s1.length() - start1 == 0) return 0;

        int nMatches = 0;

        if (s1.charAt(start1) == s2.charAt(start2)) {
            if (start1 == s1.length() - 1) {
                nMatches += 1;
            } else {
                nMatches += numMatchesHelper(s1, s2, start1 + 1, start2 + 1);
            }
        }

        nMatches += numMatchesHelper(s1, s2, start1, start2 + 1);

        return nMatches;
    }

    public static void main(String[] args) {
        System.out.println(numMatches(args[0], args[1]));
    }

}

- Siddharth March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution works, verified

- Shiv March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Quick Python solution:-

def findAllMatches(a, b):
    if len(a) == 0:
        return 1
    count = 0
    for i in range(len(b)):
        if b[i] == a[0]:
            count += findAllMatches(a[1:], b[i+1:])
    return count

- Jas March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findAllMatches(a, b):
    if len(a) == 0:
        return 1
    count = 0
    for i in range(len(b)):
        if b[i] == a[0]:
            count += findAllMatches(a[1:], b[i+1:])
    return count

- Jas March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;


public class DiscontiniousMatches {

public static int matches(String s, String t){
int m = s.length();
int n = t.length();
int p = Math.min(m,n);
int [][] res = new int[m+1][n+1];
for(int i = 0;i<m;i++){
char c = s.charAt(i);
int x = 0;
for(int j = 0;j<n;j++){
char d = t.charAt(j);
if(c==d){
if(i == 0)
res[i+1][j+1] = ++x;
else
res[i+1][j+1] = res[i][j+1] + res[i+1][j];
}
else{
res[i+1][j+1] = res[i+1][j];
}

}
System.out.println(Arrays.toString(res[i]));
}

System.out.println(Arrays.toString(res[m]));

return res[m][n];
}

public static void main(String arg[]){
System.out.println(matches("cata","caataat"));
}
}

- x March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int solution(string pattern, string str) {
	vector<int> dp(pattern.length(), 0);
	for (int it = 0; it < str.length(); ++it) {
		for (int i = pattern.length()-1; i >= 0; --i) {
			if (pattern[i] == str[it])
				dp[i] += (i > 0 ? dp[i-1] : 1);
		}
	}
	return dp[pattern.length()-1];
}

- Willy March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Succinct C++ recursive version

#include <iostream>

int count = 0;

void findSubstring(char* target, char* space)
{
        if(strlen(target) == 0) //all characters are found
                count ++;

        for (int i = 0; i < strlen (space) ; i++)
                if (target[0] == space [i])
                        findSubstring(target + 1, space + i);
}

int main()
{
        findSubstring("cat", "catapult");
        std::cout<<count;

        return 0;
}

- cdhsiung March 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question can be solved with recursion. Lets take the given example, for every character in the substring "CAT" :

'T' is at index (2->1), (7->1) , return a HashMap<index, count>
'A' has to come before T so A's acceptable indexes should be smaller than T's, and index 1 can be paired two times with index 2 and 7 so at this level return (1->2),(3->1)
Similarly, for 'C', index 0 can be paired with both 1,3 so adding the values of key 1 and key 3, return (0->3)

The returning value of the function would be a HashMap<Integer, Integer>, the value of key at index 0 will give the answer.

- Namita March 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another recursive option called with both strings and 0 (for s1Idx and s2Idx).

int countMatches(String str1, String str2, int s1Idx, int s2Idx) {

	if(s1Idx >= str1.length()) return 0;  

	int count = 0;
	for(int index=s2Idx; index<str2.length(); index++) {
	
		if(str1.charAt(s1Idx) == str2.charAt(index)) {
			if(str1.length()-1 == s1Idx) {
				count++;
			else
				count += findMatches(str1, str2, s1Idx+1, index+1);
		}
	}

	return count;
}

- YD March 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*

1. scan from left to right, if a character matches, look for the next char to match

2. if the whole string found, find occurrences of the last matched char to the end 

3. when end is reached, come back the previous location where entire string match found, 

and start scanning for the previous char until end

4. continue the recursion
    

*/

public class FindDiscontinuousMatches {

	char[] contentBuf = null;

	char[] matchBuf = null;


	public FindDiscontinuousMatches(String content, String toMatch) {

		contentBuf = content.toCharArray();
		
		matchBuf = toMatch.toCharArray();
	}

	public void countDiscontinuousMatch() {

		System.out.println(findCharMatchFromString(contentBuf, matchBuf, 0, 0));

	}


	public int findCharMatchFromString(char[] contentBuf, char[] matchBuf, int matchIndex, int contentIndex) {
	
		int count = 0;
	
		if(contentIndex  < contentBuf.length && matchIndex < matchBuf.length) {


			if((matchIndex == matchBuf.length - 1) && (matchBuf[matchIndex] == contentBuf[contentIndex])) {

				count++;
			}
		
			
			if(matchBuf[matchIndex] == contentBuf[contentIndex]) {

				
				count += findCharMatchFromString(contentBuf, matchBuf, matchIndex + 1, contentIndex + 1);
				
			}
					
			count += findCharMatchFromString(contentBuf, matchBuf, matchIndex, contentIndex + 1);
		}

		return count;
	}


	public static void main(String [] args) {
	
		new FindDiscontinuousMatches("CATAPULT", "CAT").countDiscontinuousMatch();
	
	}
}

- sandipdeveloper March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*

1. scan from left to right, if a character matches, look for the next char to match

2. if the whole string found, find occurrences of the last matched char to the end 

3. when end is reached, come back the previous location where entire string match found, 

and start scanning for the previous char until end

4. continue the recursion
    

*/

public class FindDiscontinuousMatches {

	char[] contentBuf = null;

	char[] matchBuf = null;


	public FindDiscontinuousMatches(String content, String toMatch) {

		contentBuf = content.toCharArray();
		
		matchBuf = toMatch.toCharArray();
	}

	public void countDiscontinuousMatch() {

		System.out.println(findCharMatchFromString(contentBuf, matchBuf, 0, 0));

	}


	public int findCharMatchFromString(char[] contentBuf, char[] matchBuf, int matchIndex, int contentIndex) {
	
		int count = 0;
	
		if(contentIndex  < contentBuf.length && matchIndex < matchBuf.length) {


			if((matchIndex == matchBuf.length - 1) && (matchBuf[matchIndex] == contentBuf[contentIndex])) {

				count++;
			}
		
			
			if(matchBuf[matchIndex] == contentBuf[contentIndex]) {

				
				count += findCharMatchFromString(contentBuf, matchBuf, matchIndex + 1, contentIndex + 1);
				
			}
					
			count += findCharMatchFromString(contentBuf, matchBuf, matchIndex, contentIndex + 1);
		}

		return count;
	}


	public static void main(String [] args) {
	
		new FindDiscontinuousMatches("CATAPULT", "CAT").countDiscontinuousMatch();
	
	}
}

- sandipdeveloper March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry for the duplicate post. Not able to delete this post.

- sandipdeveloper March 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int discontinuousMatch(String pattern, String str) {
		return discontinuousMatch(pattern, str, 0, 0);
	}

	private int discontinuousMatch(String pattern, String str, int patternIndex, int strIndex) {
		if (patternIndex == pattern.length()) {
			return 1;
		} else if (strIndex == str.length()) {
			return 0;
		} else {
			int count = 0;
			for (int i = strIndex; i < str.length(); ++i) {
				if (pattern.charAt(patternIndex) == str.charAt(i)) {
					count += discontinuousMatch(pattern, str, patternIndex + 1,i + 1);
				}
			}
			return count;
		}
	}

- hm3shah March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This sounds immediately like a recursive problem, so let's think about the base cases. First off, if either string is empty, then there are no possible matches. If the two strings are equal, then there's only one match. If the strings have the same length but aren't equal, there's no match. If they're of different lengths, then we must be looking for all the matches of the shorter string in the longer string. So let's call the shorter string the search string and the longer string the target string.
What's the recursion? Well, if the first characters of both strings don't match, then we need to look for the full search string starting at the second character of the target string. In other words, given "act" and "react", we can recurse to ("act", "eact") and then to ("act", "act"). If the first characters do match, then we have two options: match the first character and recurse with both strings shortened by the matched character, or don't match the first character, hoping to find another match later. E.g, given ("act", "acting") we recurse to both ("ct", "cting") and ("act", "cting"). If we ever use up the last character in the search string, we add a match. Let's write up this recursive solution:

def match(search, target):
    if not search or not target:
        return 0
    if search == target:
        return 1
    if len(search) == len(target):
        return 0
    if len(search) > len(target):
        search, target = target, search

    if search[0] == target[0]:
        if len(search) == 1:
            return 1 + match(search, target[1:])
        else:
            return match(search[1:], target[1:]) + match(search, target[1:])
    else:
        return match(search, target[1:])

This gets us the right answer but is unfortunately rather slow on long strings. Why? Because the recursive stack can get very deep - any time there's a character match, we're splitting into two recursive calls, giving us O(N^2) worst case behavior. However, we'll note that there are only M possible search strings and N possible target strings. Our recursive calls must be repeatedly evaluating the same subproblems. That means we can use a dynamic programming approach - we'll store the results of previous calls by allocating an array.

import numpy as np

def match(search, target):
    if len(search) > len(target):
        search, target = target, search
    m, n = len(search), len(target)
    
    #Some base cases
    if not search or not target:
        return 0
    if search == target:
        return 1
    if m == n:
        return 0
    
    #Allocate the array
    table = np.zeros((m, n), dtype=int)
    
    #Fill in the bottom row (matching the last character of the search string)
    i = m - 1
    for j in range(n)[::-1]:
        if j < n - 1:
            table[i,j] = table[i,j+1]
        if search[i] == target[j]:
            table[i,j] += 1
            
    #Fill in the rest of the table
    for i in range(m - 1)[::-1]:
        for j in range(n - 1)[::-1]:
            if search[i] == target[j]:
                table[i,j] = table[i+1,j+1] + table[i,j+1]
            else:
                table[i,j] = table[i,j+1]
                
    #Return the final value
    return table[0,0]

Now this runs quite fast --- it takes only O(MN) time with the nested loop. However, it also takes O(MN) space to store the table. But we don't actually need the whole table! At each point, we only need the next column over. So we can reduce this to O(M) space by shrinking the table:

import numpy as np

def match(search, target):
    if len(search) > len(target):
        search, target = target, search
    m, n = len(search), len(target)
    
    #Some base cases
    if not search or not target:
        return 0
    if search == target:
        return 1
    if m == n:
        return 0
    
    #Allocate the array
    table = np.zeros((m, 2), dtype=int)
    
    #Fill in the bottom right element (match the last two characters)
    if search[-1] == target[-1]:
        table[-1, 0] = 1  #First column because it will be shifted over in the loop
        
    #Iterate through all the columns
    for j in range(n - 1)[::-1]:
        #Copy the left column over to the right
        table[:,1] = table[:,0]
        #Bottom row
        if search[m - 1] == target[j]:
            table[m - 1, 0] += 1
        #Remaining rows
        for i in range(m - 1)[::-1]:
            if search[i] == target[j]:
                table[i,0] = table[i+1,1] + table[i,1]
            else:
                table[i,0] = table[i,1]
                
    #Return the final value
    return table[0,0]

- brett.olsen March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is equivalent to finding longest common subsequences. Specifically, any discontinuous occurrence of a pattern P in a search string S is by definition a longest common subsequence. We just want the number of matches rather than the length, and we want to return zero in case the length of the LCS is less than that of P (i.e., no full match exists).

We build an array c[i,j] which represents the number of matches of P[0, ..., i-1] in S[0, ..., j-1]. This naturally satisfies the following recurrences:

c[i,j] = c[i-1, j-1] + c[i, j-1] if P[i] = S[j] (number of matches using the current character, plus number of matches using only prior characters);

c[i,j] = c[i, j-1] if P[i] != S[j].

Here's a direct implementation of this in Python:

def discontinuous_matches(p, s):
    c = [[0 for i in range(0, len(s) + 1)] for j in range(0, len(p) + 1)]

    for i in range(0, len(s) + 1):
        c[0][i] = 1

    for i in range(1, len(p) + 1):
        for j in range(1, len(s) + 1):
            if p[i-1] == s[j-1]:
                c[i][j] = c[i-1][j-1] + c[i][j-1]
            else:
                c[i][j] = c[i][j-1]

    return c[len(p)][len(s)]

I personally find a recursive approach a lot more comprehensible, though. The idea is simpler. We look at each index of the search string and find the number of occurrences of the pattern starting at that index. We add up all these results.

The number of occurrences of the pattern p and index i of the search string s, if s[i] == p[0], is simply the number of occurrences of the *rest* of the pattern in the remainder of the string.

def discontinuous_matches_recursive(p, s):
    if len(p) == 0:
        return 1

    count = 0

    for i, c in enumerate(s):
        if p[0] == c:
            count += discontinuous_matches_recursive(p[1:], s[i+1:])

    return count

- nilkn March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Anonymous April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int

- Anonymous April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int

- xyz April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int num_of_squares(int n) {
		if (n==0)
			return 0;
		if (n==1)
			return 1;
		int x = (int) Math.sqrt(n);
		int rem = n - (int)Math.pow(x, 2);
		return 1+num_of_squares(rem);

}

- abhaar April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int num_of_squares(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
int x = (int) Math.sqrt(n);
int rem = n - (int)Math.pow(x, 2);
return 1+num_of_squares(rem);
}

- abhaar April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive and DP solution

int num_dc_matches_dp(const std::string& s, const std::string& t)
{
    const auto sn = s.length();
    const auto tn = t.length();
    auto d = new int*[sn + 1];
    for (auto i = 0; i < sn + 1; ++i) d[i] = new int[tn + 1];
    for (auto i = 0; i < sn + 1; ++i) d[i][0] = 1;
    for (auto j = 1; j < tn + 1; ++j) d[0][j] = 0;
    for (auto i = 1; i < sn + 1; ++i)
    {
        for (auto j = 1; j < tn + 1; ++j)
        {
            if (s[i - 1] == t[j - 1])
            {
                d[i][j] = d[i - 1][j - 1] + d[i - 1][j];
            }
            else
            {
                d[i][j] = d[i - 1][j];
            }
        }
    }
    auto rv = d[sn][tn];
    for (auto i = 0; i < sn + 1; ++i) delete[] d[i];
    delete[] d;
    return rv;
}

int num_dc_matches(char* s, char* t, int sn, int tn)
{
    if (0 == s || 0 == t) return 0;
    if (tn > sn) return 0;
    if (tn == sn) return (strcmp(s, t) == 0) ? 1 : 0;
    if (0 == tn) return 1;
    if (*s == *t)
    {
        return num_dc_matches(s + 1, t + 1, sn - 1, tn - 1) + num_dc_matches(s + 1, t, sn - 1, tn);
    }
    else
    {
        return num_dc_matches(s + 1, t, sn - 1, tn);
    }
}

- Omri.Bashari May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's a simple DP problem

int NumberOfMatch(string s, string t)
{
	int m = s.size(), n = t.size(), *dp[2];

	dp[0] = new int[n](); dp[1] = new int[n](); dp[0][0] = s[0] == t[0] ? 1 : 0;

	for (int i = 1; i < m; ++i)
	{
		dp[i & 1][0] = dp[(i - 1) & 1][0] + (s[i] == t[0] ? 1 : 0);

		for (int j = 1; j < n; ++j) dp[i & 1][j] = dp[(i - 1) & 1][j] + (s[i] == t[j] ? dp[(i - 1) & 1][j - 1] : 0);
	}

	int ans = dp[(m - 1) & 1][n - 1];  delete[] dp[0]; delete[] dp[1];

	return ans;
}

- malinbupt May 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A dp solution I can think of is:
iterate through string, at each character determine if it completes a match or adds to a match. If it completes a match, save the Indexes (use it display later on). If it adds to an incomplete match save indexes in a separate data structure to use in the case that a later character completes the match. T = O(n^2)

void findDiscontinuousMatches(string s, string p, int slength, intplength)
{
	if(slength == 0 || plength == 0 || plength > slength)
		return null;
		
	list<string> incompleteMatches;
	vector<vector<int>> incompleteIndices;
	vector<vecotr<int>> completeIndices;
	
	incompleteMatches.push_front("");
	vector<int> placeHolder v;
	incompleteIndices.push_back(v);
	
	for(int i = 0; i<slength; i++)
	{
		auto it2 = incompleteIndices.begin();
		for(auto it = incompleteMatches.begin(); it != incompleteMatches.end(); it++)
		{
			if(it2 = incompleteIndices.end())
				break;
				
			//completes a match
			if( (it->first + s[i]).equals(p) )
			{
				vector<int> completedIndex (it2->first);
				completedIndex.push_back(i);
				completeIndices.push_back(completedIndex);
			}
			
			//adds to an incomplete match
			if( p.startsWith(it->first + s[i]) )
			{
				incompleteMatches.push_front(it->first + s[i]);
				vector<int> incompleteIndex (it2->first);
				incompleteIndex.push_back(i);
				completeIndices.push_back(incompleteIndex);
			}
			it2++;
		}
	}
	printDiscontinuous(s, completeIndices);	//Didn't write this method
}

- abhiV June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python nice and short

a='cat'
b='catapult'

def num_of_matches(a,b):
    if len(a)==1:
        return b.count(a)
    else:
        count=0
        for ind in range(len(b)):
            if a[0]==b[ind]:                
                count+=num_of_matches(a[1:],b[ind:])
        return count
    return 0

num_of_matches(a,b)

- gb92 February 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public static int findMatches(String source, String target) {
if(source.length() == 0) {
return 1;
}
if(target.length() == 0)
return 0;

int num = 0;
for(int i = 0; i < target.length() - source.length() + 1; i++) {
if(source.charAt(0) == target.charAt(i)) {
num += findMatches(source.substring(1), target.substring(i+1));
}
}
return num;
}

- zd March 04, 2015 | 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