Google面试题目

褐眼睛

Given a String pattern as "ABCDFGHK" write a function if input strings like XYZCDFGABHKERYT or LOPIKHFGDCBAYRT should return the starting index of the pattern and if the intput strings are XYZCDFGABBHKERYT or LOPIKHFDBAYRGCT it should return -1.

Do not use any data structures like dict or set to store all the possible combinations of the pattern string.
The interviewer said no to regular expressions too.

有谁会解答？

SotongJiang

去面试看到这题的话，肯定超时出局。当作编程练习还是能挤一挤脑汁。
按题意是coding不能用library的data structure或RE，越原始越好。

我的C/C++差不多还给老师了，唯有偷鸡用python如下，欢迎指教。

1. def match_pattern(inStr, pattern, p_len):
   
2.     summation = 0
   
3. 
   
4.     for c in pattern:
   
5.         c_cnt = inStr.count(c)
   
6.         if c_cnt==1:
   
7.             summation += c_cnt
   
8.         else:
   
9.             break
   
10. 
    
11.     if summation==p_len:
    
12.         return True
    
13. 
    
14.     return False
    
15. 
    
16. 
    
17. def find_pattern(inStr, pattern):
    
18.     p_len = len(pattern)
    
19.     s_len = len(inStr)
    
20. 
    
21.     i=0
    
22.     print '%s has pattern %s in it?' % (inStr, pattern)
    
23.     while (i < s_len):
    
24.         if pattern.count(inStr[i])>0:
    
25.             if s_len-i >= p_len:
    
26.                 if match_pattern(inStr[i:i+p_len], pattern, p_len):
    
27.                     
    
28.                     print 'Found it at index ',i
    
29.                     return i
    
30.                 else:
    
31.                     print 'Not found '
    
32.                     return -1
    
33.             else:
    
34.                 #pattern string not found throughout the inStr
    
35.                 return -1
    
36. 
    
37.         i += 1
    
38. 
    
39. 
    
40. find_pattern('XYZCDFGABHKERYT','ABCDFGHK')
    
41. find_pattern('LOPIKHFGDCBAYRT','ABCDFGHK')
    
42. find_pattern('XYZCDFGABBHKERYT','ABCDFGHK')
    
43. find_pattern('LOPIKHFDBAYRGCT','ABCDFGHK')
    
44.   
    
45.         
    
46. 
    

复制代码

褐眼睛

SotongJiang 发表于 27-3-2019 01:59 AM
去面试看到这题的话，肯定超时出局。当作编程练习还是能挤一挤脑汁。
按题意是coding不能用library的data structure或RE，越原始越好。

我的C/C++差不多还给老师了，唯有偷鸡用python如下，欢迎指教。

坦白说，我对Python不熟，但是在Visual Studio试了你的Code，结果是正确的：

3
4
-1
-1

从我在leetcode.com转载过来的那里，有关匿名人士没有给出答案，有些人就建议使用Permutation of Strings 或Anagram in Strings的方式，也有人提议用Hash 及 Sliding Window的方式。不过我请教了这里一位资深程序员，他说基本上在本地IT公司你的答案是过关的，只不过真正来说Google会不会接受则不得而知了。据我所了解，你用了str.Count这个功能。

谢谢你的参与，非常高兴看到本地也有人答题。

SotongJiang

褐眼睛 发表于 27-3-2019 06:03 PM
坦白说，我对Python不熟，但是在Visual Studio试了你的Code，结果是正确的：
从我在leetcode.com转载过来的那里，有关匿名人士没有给出答案，有些人就建议使用Permutation of Strings 或Anagram in Strings的方式 ...

嘿嘿，没错用了python string里的count(), 所以我说偷鸡啊。
当然另写一个count()也ok，那就完全符合“越原始越好”的题目本意。

你看那论坛的建议，都违背了题意, hash是data structure的一种(类似dict), permutation的话也会用到library（除非大神级的自己重写）。
程序员用惯了library，突然要求不能用了就很痛苦。

上回你po的图片压缩比赛，我就无能为力了。

chwk87

我的方法不过string要ABC-Z 而已
public class Test {

        public static void main(String[] args) {

                System.out.println(checkPattern("XYZCDFGABHKERYT", "ABCDFGHK"));
                System.out.println(checkPattern("LOPIKHFGDCBAYRT", "ABCDFGHK"));
                System.out.println(checkPattern("XYZCDFGABBHKERYT", "ABCDFGHK"));
                System.out.println(checkPattern("LOPIKHFDBAYRGCT", "ABCDFGHK"));
        }

        public static int checkPattern(String input, String pattern) {

                int len = pattern.length();
                int[] patternLocation = new int[26];

                for (int i = 0; i < 26; i++) {
                        patternLocation = 0;
                }

                for (int i = 0; i < len; i++) {
                        char ch = pattern.charAt(i);
                        patternLocation[ch - 'A'] = 1;
                }
                int count = 0;
                int index = -1;
                for (int i = 0; i < input.length(); i++) {
                        char ch = input.charAt(i);
                        if (patternLocation[ch - 'A'] == 1) {
                                patternLocation[ch - 'A']= 0;
                                count=count+1;
                                index = i;
                        } else {
                                count = 0;
                                index = -1;
                        }
                        if (count == len) {
                                return index+1-len;
                        }

                }

                return -1;

        }

}

褐眼睛

chwk87 发表于 27-3-2019 10:35 PM

我用C#（改了一下，如charAt 改成ElementAt)，你的答案是正确的。
我发现你的方法很新颖，是Toggle Bit的方式来完成，不过有一个缺点，虽然和题目无关：无法使用相同字母作为String Pattern喔。

十分感谢你花时间来解决这道题！

martinng

1. C#：
   
2. 
   
3.     static void Main(string[] args)
   
4.     {
   
5.         string pattern = "ABCDFGHK";
   
6.         string inputString = "XYZCDFGABHKERYT";
   
7.         Console.WriteLine("Pattern = {0}", pattern);
   
8.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //3
   
9.         inputString = "LOPIKHFGDCBAYRT";
   
10.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //4
    
11.         inputString = "XYZCDFGABBHKERYT";
    
12.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //-1
    
13.         inputString = "LOPIKHFDBAYRGCT";
    
14.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //-1
    
15.         Console.WriteLine();
    
16. 
    
17.         pattern = "ABBBBACDXZMARTIN";
    
18.         inputString = "XYZCDFGABDZMARBBINTBAXCHKERYT";
    
19.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //7
    
20.         inputString = "XYZCDFGABDZMARBBINTBAABXCHKERYT";
    
21.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //9
    
22.         inputString = "XYZCDFGABDZMARBHBINTBAABXCHKERYT";
    
23.         Console.WriteLine("Input string = {0}, index = {1}", inputString, findPattern(inputString, pattern));  //-1
    
24. 
    
25.         Console.ReadKey();
    
26.     }
    
27. 
    
28.     static int findPattern(string inputString, string pattern)
    
29.     {
    
30.         int index = -1;
    
31.         int patternLength = pattern.Length;
    
32.         int inputStringLength = inputString.Length;
    
33.         long patternValue = 0;
    
34.         long inputStringValue = 0;
    
35.         int bFirst = 1;
    
36.         if (inputStringLength < patternLength) return index;
    
37.         for (int i = 0; i < inputStringLength; i++)
    
38.         {
    
39.             inputStringValue = 0;
    
40.             for (int j = i; j < (i + patternLength); j ++)
    
41.             {
    
42.                 if (bFirst == 1) patternValue += (long)1 << ((byte)(pattern[j - i]) - 65);
    
43.                 inputStringValue += (long)1 << ((byte)(inputString[j]) - 65);
    
44.             }
    
45.             bFirst = 0;
    
46.             if (patternValue == inputStringValue)
    
47.             {
    
48.                 index = i;
    
49.                 break;
    
50.             }
    
51. 
    
52.             if ((i + patternLength) >= inputStringLength) break;               
    
53.         }
    
54. 
    
55.         return index;
    
56.     }

复制代码

第五给example，其实pattern 已经改变了，变成"ABBBBACDXZMARTIN"了。
PS: 这个写得不够优化，不是O(N) running time，因为每次都重复计算inputStringValue。变成O(N^2)了。下面是更优化的版本。

martinng

1.         static int findPattern(string inputString, string pattern)
   
2.         {
   
3.             int index = -1;
   
4.             int patternLength = pattern.Length;
   
5.             int inputStringLength = inputString.Length;
   
6.             long patternValue = 0;
   
7.             long inputStringValue = 0;
   
8.             long firstCharValue = 0;
   
9.             int bFirst = 1;
   
10.             if (inputStringLength < patternLength) return index;
    
11.             for (int i = 0; i < inputStringLength; i++)
    
12.             {
    
13.                 if (bFirst == 1)
    
14.                 {
    
15.                     for (int j = i; j < (i + patternLength); j++)
    
16.                     {
    
17.                         patternValue += (long)1 << ((byte)(pattern[j - i]) - 65);
    
18.                         inputStringValue += (long)1 << ((byte)(inputString[j]) - 65);
    
19.                         if (i == j) firstCharValue = (long)1 << ((byte)(inputString[j]) - 65);
    
20.                     }
    
21.                     bFirst = 0;
    
22.                 }
    
23.                 else
    
24.                 {
    
25. //Sliding window algorithm， 每次前进一个字母，都是减去上次的第一个字母和加上这个新字母。
    
26.                     inputStringValue = inputStringValue - firstCharValue + ((long)1 << ((byte)(inputString[i + patternLength - 1]) - 65));
    
27.                     firstCharValue = (long)1 << ((byte)(inputString[i]) - 65);
    
28.                 }
    
29. 
    
30.                 if (patternValue == inputStringValue)
    
31.                 {
    
32.                     index = i;
    
33.                     break;
    
34.                 }
    
35. 
    
36.                 if ((i + patternLength) >= inputStringLength) break;               
    
37.             }
    
38. 
    
39.             return index;
    
40.         }
    

复制代码

这个才是真正O(N) running time，就是只要loop inputstring 字母数目，就能找到答案。
P/S：程式写得很不精简，有时间再refactor吧。

martinng

SotongJiang 发表于 27-3-2019 08:09 PM
嘿嘿，没错用了python string里的count(), 所以我说偷鸡啊。
当然另写一个count()也ok，那就完全符合“越原始越好”的题目本意。

你看那论坛的建议，都违背了题意, hash是data structure的一种(类似dict), per ...

你误解了hash的真正定义了。dict 内部可能是用hash，但hash不一定就是dict，所以hash 不是一个data structure，而是algorithm。
其实leetcode 有个鬼佬（就是那个说用sliding window + hash）已经把正确解答方式说出来了。他的所谓Hash，是为Pattern取Hash值。只是他没有讲出来到底如何取Hash值，这个才是这个题目的重点。第二个重点就是：在比较pattern hash和 input string时，必须是最多loop N次，N就是input string的长度。如果call instr，substring，indexOf等等built in function，可能会在内部执行更多次数的loop，所以不鼓励用。

martinng

1.         static int findPattern(string inputString, string pattern)
   
2.         {
   
3.             if (inputString.Length < pattern.Length) return -1;
   
4.             long patternValue = 0, inputStringValue = 0;
   
5.             bool bPatternHashed = false;
   
6.             for (int i = 0; (i + pattern.Length) <= inputString.Length; i++)
   
7.             {
   
8.                 if (!bPatternHashed)
   
9.                 {
   
10.                     for (int j = i; j < (i + pattern.Length); j++)
    
11.                     {
    
12.                         patternValue += (long)1 << ((byte)(pattern[j]) - 65);
    
13.                         inputStringValue += (long)1 << ((byte)(inputString[j]) - 65);
    
14.                     }
    
15.                     bPatternHashed = true;
    
16.                 }
    
17.                 else inputStringValue -= ((long)1 << ((byte)(inputString[i - 1]) - 65)) - ((long)1 << ((byte)(inputString[i + pattern.Length - 1]) - 65));
    
18.                 if (patternValue == inputStringValue) return i;
    
19.             }
    
20.             return -1;
    
21.         }

复制代码

刚刚refactor了。

martinng

我们全都理解错这个问题啦。其实这个问题是考对Rabin Karp rolling hash 的理解和应用能力。这个问题的正确要求：
1）pattern 的字元顺序必须一致。ABC不等于CBA。
2）是要所有occurrence，并不是first occurrence而已。 ABC，“AZX【ABC】XXTML【ABC】D”
关于2），有一个疑惑：就是如果pattern是“AA”，string 是 “AAAA”，所有occurrence到底是 0，1，2（有重叠）还是0和2而已（不重叠）

chwk87

褐眼睛 发表于 28-3-2019 12:53 AM
我用C#（改了一下，如charAt 改成ElementAt)，你的答案是正确的。
我发现你的方法很新颖，是Toggle Bit的方式来完成，不过有一个缺点，虽然和题目无关：无法使用相同字母作为String Pattern喔。

十分感谢你花 ...

改用incremental or decremental因该就可以了