[2017-02-10] 百度面试

1. 第一轮技术面

第一题

   /**
     *
     * @param nStr 一个表示整数的字符串
     * @param notation 2-16 表示nStr所表示的整数的进制
     * @return nStr 所表示的整数
     */
    public int convert(String nStr,int notation){
        //...
        return ;
    }

注意点

异常的处理
- 不合法的输入
- nStr所表示的数字超过了整型所能表示的范围
- 只有一个负号的情况
测试用例
- 正常案例
- 异常案例
- 边缘案例

第二题

/**
* @param nStr   一个有'0'和'1'组成的字符串，其所表示的整数超过long能表示的范围
* @param divide 一个质数
* @return nStr所表示的整数对divide取余后的数字
*/
public int extra(String nStr, int divide) {
   //不考虑输入的合法性
   int result = ;
   for (int i = ; i < nStr.length(); i++) {
       result = (result<< + nStr.charAt(i)-'0')%divide;
   }
   return result;
}

思路

这里用到了一个同余定理

设 P mod n = c
有 1. (P+Q) mod n = (c+Q) mod n
2. kP mod n = kc mod n
有1且2 => (kP+Q) mod n = (kc+Q) mod n

注意 kP+Q 有可能越界，但是kc+Q不会越界，我们这里只要求最后的余数，所以可以通过这种方式

其他

Spring-boot有哪些特性
- Create stand-alone Spring application
- Embed Tomcat, Jetty or Undertow directly (no need to deploy WAR files)
- Provide opinionated ‘starter’ POMs to simplify your Maven configuration
- Automatically configure Spring whenever possible
- Provide production-ready features such as metrics, health checks and externalized configuration
- Absolutely no code generation and no requirement for XML configuration

2. 第二轮技术面

第三题

public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/**
 * @param numbers
 * @param start
 * @param end
 * @return
 */
public int recursiveFind(int[] numbers, int start, int end) {
    if (start == end) return numbers[start];
    int pivot = numbers[start];
    int head = start, tail = end;
    while (head < tail) {
        while (head < tail && numbers[tail] > pivot) tail--;
        if (head == tail) break;
        swap(numbers, head + , tail);
        head++;
    }
    swap(numbers, start, head);

    if ((head - start) %  == )
        return recursiveFind(numbers, start, head);
    else
        return recursiveFind(numbers, head + , tail);
}

/**
 * @param numbers 一个一共有3m+1个数的数组 其中有m个数字出现了3次，一个数字出现了1次
 * @return 数组中那个只出现一次的数
 */
public int find(int[] numbers) {
    return recursiveFind(numbers, , numbers.length - );
}