new questions other than leetcode(not done yet)

Q1: Robin-Karp
进行字符串匹配，Strstr， 利用对字符串进行hashing的做法，pattern : p (hash value for pattern), txt: t (hash value for txt) , hash value的计算： 基数*rst + 当前字符对应的ascII整数，这里基数是256（ascII个数），还需要一个h值，是pattern最高位的系数，方便后面移动窗口时下一个txt的计算，下一个txt的t = （d*(t - txt[i]* h) + txt[i+M]）%q,  去掉上一个的最高位，剩下的往左移，再加上新的元素值。q: 取的一个prime number， 为了避免当pattern字符串很长的时候，p的值会非常大，模q的话可以保证hash值在一个范围内。 当每次window内的值p == t的时候，我们就只需要去check这个window内的每一个char是否与pattern 匹配，如果匹配就找到了一个match， 如果不匹配，就继续sliding window.

// d is the number of characters in input alphabet

#define d 256

  

/*  pat  -> pattern

    txt  -> text

    q    -> A prime number

*/

void search(char *pat, char *txt, int q)

{

    int M = strlen(pat);

    int N = strlen(txt);

    int i, j;

    int p = 0;  // hash value for pattern

    int t = 0; // hash value for txt

    int h = 1;

  

    // The value of h would be "pow(d, M-1)%q"

    for (i = 0; i < M-1; i++)

        h = (h*d)%q;

  

    // Calculate the hash value of pattern and first window of text

    for (i = 0; i < M; i++)

    {

        p = (d*p + pat[i])%q;

        t = (d*t + txt[i])%q;

    }

  

    // Slide the pattern over text one by one

    for (i = 0; i <= N - M; i++)

    {

        

        // Check the hash values of current window of text and pattern

        // If the hash values match then only check for characters on by one

        if ( p == t )

        {

            /* Check for characters one by one */

            for (j = 0; j < M; j++)

            {

                if (txt[i+j] != pat[j])

                    break;

            }

            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]

            {

                printf("Pattern found at index %d \n", i);

            }

        }

         

        // Calculate hash value for next window of text: Remove leading digit,

        // add trailing digit          

        if ( i < N-M )

        {

            t = (d*(t - txt[i]*h) + txt[i+M])%q;

             

            // We might get negative value of t, converting it to positive

            if(t < 0)

              t = (t + q);

        }

    }

}

Q2: Counting sort && Radix sort

Q3: 正则表达式匹配

Q4：检查两个字符是否是rotated的，比如： abcade->cadeab true
case1: 如果这个string里面有重复字符，一个很tricky的做法是把第一个字符串copy一份放到自己的后面，然后查看第二个字符串是不是新字符串的子串。比如： abcadeabcade -> cadeab，如果是子串，那么这两个字符就是rotated的。
case2: 如果这个string里面没有重复字符，这个题目可以很巧妙地利用快慢指针来解，
abcade
s
   f     f
cadeab
i     i

Q5： design 类题目
          前缀提示器： 比如输入 “ab”, 在提示框里能够显示给定词库里所有以ab为头的词，并且支持添加，查找，删除的功能。

Q6： oodesign

建立一个10位电话号码查询类，查找每个电话对应的人名。