笔试题 讨论一下

Question

昨天晚上参加baidu笔试的2个题目，大家讨论一下：1.序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…] 类似与excel的排列，任意给出一个字符串s=[a-z]+(由a-z字符组成的任意长度字符串），请问s是序列Seq的第几个。2.需求：需要引入用户对搜索结果相关性的评分100分制，希望用户的打分能帮助搜索引擎排序，但又要避免恶意投票，作弊等，请设计一个比较公平的评分系统。

Answer 1

A: 1
B: 2
...
Z: 26AA = 1 * 26^1 + 1 = 27
AAA = 1 * 26^2 + 1 * 26^1 + 1 = 703
将字母序列从右往左依次编号为 i，最右边一位为 0，最左边一位为 n，
在 i 位上字母的值为 K[i]，则序列为：
          n
        -----
seq =    \      K[i] * 26^i
         /
        -----
         i=0

Answer 2

排序会按照用户评分来排？呵呵，我看是按百度竞价来排的吧，
不信大家可以在百度上搜搜“Struts”看看第一个结果是啥。

Answer 3

26...A -- 1 * pow(26, 0)
B -- 2 * pow(26, 0)
.
.
.
AA -- A * pow (26, 1) + A * pow(26, 0)
.
.
.

Answer 4

嗯，第一题就是26进制，第二题我想说用PageRank，不过估计百毒不让

Answer 5

public class Test1 {
    
    public static void main(String[] args) {
        int n = letter2Number("abc");
        System.out.println(n);
    }
    
    public static int letter2Number(String letters) {
        if(!letters.matches("[a-zA-Z]+")) {
            throw new IllegalArgumentException("Format ERROR!");
        }
        char[] chs = letters.toLowerCase().toCharArray(); 
        int result = 0;
        for(int i = chs.length - 1, p = 1; i >= 0; i--) {            
            result += getNum(chs[i]) * p;
            p *= 26;
        }
        return result;
    }
    
    private static int getNum(char c) {
        return c - 'a' + 1;
    }
}

Answer 6

String str = abcdefghi……xyz;public int getNum(String oneChar){//传一个字母
    String index = str.indexOf(oneChar);//这里返回的值应该是0到25
    int num = Integer.getInteger(index)+1;//得到了这个字母对于的十进制数
    return num;
} public int changeToNum(String moreChar){//传的是一个字符串
     int all = 0; 
    char[] newOne = moreChar.toCharArray();
    //挨个字母换成十进制数，然后再运算
    for(int i = 0 ;i <newOne.length ; i++){
        int num = getNum(newOne[i].toString);
        all = all + num*(26^i);//26的i次方是这样写的吧，我忘了
    }
    return all;
}这样应该可以把一个abc换成一个十进制数了，效率可能会低点

Answer 7

String str = "abcdefghijklmnopqrstuvwxyz"; 
public int getNum(String oneChar){//传一个字母 
    return str.indexOf(oneChar)+1; 
} 
public int q26(int a){
if(a==0){
return 1;
}
else if(a==1){
return 26;
}
else{
return 26*q26(a-1);
}
}
public int changeToNum(String moreChar){//传的是一个字符串 
    int all = 0; 
    int p = 0;
    char[] newOne = moreChar.toCharArray(); 
    //挨个字母换成十进制数，然后再运算 
    for(int i = 0 ;i <newOne.length ; i++){ 
     String tag = Character.toString(newOne[i]);
        int num = getNum(tag);
        all = all + num*q26(newOne.length-i-1);
    } 
    return all; 
} 
经过测试了，传aa=27 ab =28 ac = 29

Answer 8

那么麻烦?JDK里面就有了,一句话:ava.lang.Integer.parseInt(String "abc", 26);int java.lang.Integer.parseInt(String s, int radix) throws NumberFormatException
Parses the string argument as a signed integer in the radix specified by the second argument. The characters in the string must all be digits of the specified radix (as determined by whether java.lang.Character.digit(char, int) returns a nonnegative value), except that the first character may be an ASCII minus sign '-' ('\u002D') to indicate a negative value. The resulting integer value is returned. An exception of type NumberFormatException is thrown if any of the following situations occurs: The first argument is null or is a string of length zero. 
The radix is either smaller than java.lang.Character.MIN_RADIX or larger than java.lang.Character.MAX_RADIX. 
Any character of the string is not a digit of the specified radix, except that the first character may be a minus sign '-' ('\u002D') provided that the string is longer than length 1. 
The value represented by the string is not a value of type int. 
Examples:  parseInt("0", 10) returns 0
 parseInt("473", 10) returns 473
 parseInt("-0", 10) returns 0
 parseInt("-FF", 16) returns -255
 parseInt("1100110", 2) returns 102
 parseInt("2147483647", 10) returns 2147483647
 parseInt("-2147483648", 10) returns -2147483648
 parseInt("2147483648", 10) throws a NumberFormatException
 parseInt("99", 8) throws a NumberFormatException
 parseInt("Kona", 10) throws a NumberFormatException
 parseInt("Kona", 27) returns 411787
 
Parameters:
s the String containing the integer representation to be parsed
radix the radix to be used while parsing s.
Returns:
the integer represented by the string argument in the specified radix.
Throws:
NumberFormatException if the String does not contain a parsable int.

Answer 9

baidu出这样的题目，真是一种讽刺
希望用户的打分能帮助搜索引擎排序，但又要避免恶意投票，作弊等，

Answer 10

呵呵
现在感觉搜中文的有些baidu也不如google了。

Answer 11

呵呵，当然这和版主的帖子主题不一致了。不过baidu有一种竞价排名之类的东西。不过google.cn搜英文的东西反而不方便了，只要把它的默认搜索语言设为英文

Answer 12

楼主也是年末要毕业的？
一星期前也去参加了baidu的校园招聘，但是被鄙视了！
笔试的题目和楼主说的是一个类型。如果你有面试机会的话，一定要把你笔试题目能明白，一面一开始就是让你把做过的题目再做一遍的！祝福.....

Answer 13

顶8楼,偶也是这样做的.同顶22楼, 说实话,百度其实真的有点一般呢, 这种不说外语的冒牌外企, 等拿到offer后鄙视之. 鄙视的另外原因之一是,不负责的笔试, 看看现场的笔试环境,严重鄙之.

Answer 14

如果排序过就2分搜索,复杂度O(logN)
如果是不重复的就用Hash,复杂度是O(1)
其他复杂度的不予考虑.

Answer 15

//获得字符串str的序列号
//strLen为字符串的长度
GetSeqNum(char *str, int strLen)
{
int i; //递归变量字符串
for (i=0; i<strLen; ++i)
{
//如果字符串长度为1则返回
if (1 == strLen)
return (str[0] - 'a' + 1);
//否则继续遍历
else
{
return ((26*(str[0]-'a' + 1)) + GetSeqNum(str+1, strLen-1));
}
}
return ERROR;
}
对代码如有更好意见，欢迎交流

Answer 16

有意思，我也贴两个        static double FindIndex(string keystring)
        {
            double value = 0;
            for (int i = 0; i < keystring.Length; i++)
            {
                value += (Convert.ToInt32(keystring[i]) - 96) * Math.Pow(26, keystring.Length - i - 1);
            }            return value; 
        }//这个是改进版
        static double FindIndex2(string keystring)
        {
            //假如最大是5位，更多依此类推，预先计算后更快
              //26 0:1
            //26 1:26
            //26 2:676
            //26 3:17576
            //26 4:456976
            //26 5:11881376 
            double[] pow = new double[] { 11881376, 456976, 17576, 676, 26, 1 };            double value = 0;
            for (int i = 0; i < keystring.Length; i++)
            {
                value += (Convert.ToInt32(keystring[i]) - 96) * pow[keystring.Length - i - 1];
            }
            return value; 
        }//请有心人测试一下吧
        static void Main()
        {
            string[] find = new string[] { "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy", "abcde", "dfsdf", "iojoj", "uonhy" };            Console.WriteLine("timebegin:{0}", DateTime.Now.ToString("mm:ss.fffffff"));
            for (int i = 0; i < find.Length; i++)
            {
                Console.WriteLine("{1}:{2}:{0}", FindIndex(find[i]), DateTime.Now.ToString("mm:ss.fffffff"),find[i]);
            }
            Console.WriteLine("timeend:{0}", DateTime.Now.ToString("mm:ss.fffffff"));            Console.WriteLine("timebegin:{0}", DateTime.Now.ToString("mm:ss.fffffff"));
            for (int i = 0; i < find.Length; i++)
            {
                Console.WriteLine("{1}:{2}:{0}", FindIndex2(find[i]), DateTime.Now.ToString("mm:ss.fffffff"),find[i]);
            }
            Console.WriteLine("timeend:{0}", DateTime.Now.ToString("mm:ss.fffffff")); 
  
        }

Answer 17

35楼的 parseInt（'ab',26）得出的结果和 火龙果程序的结果不一样呢？the sequeue of ab is 28 --> 对本题而言，这个明显是正确的
the radix of ab is 271  --> parseInt('ab',26)的结果，貌似ParseInt('a',26)的结果是10
咋回事呢，这个radix 26 代表啥？

Answer 18

不完全等于26进制，进制中有0的存在，而a-z表示中没有........
如0000相同于0,而aaaa不同于a,如果a-z表示中加入一个0的话就是27进制.............
假设ch指向s的头，则
for(ch=s.begin,ch!=s.end,ch++)
total+=total*26+ch-a+1;

Answer 19

这个数太大了，估计BigDecimal都不行，我觉得这个题主要靠得是你的思路，做到火龙果的那个算法就差不多了。另外，这个题是27进制，0,a,b,...,z共27个，而不是26进制

Answer 20

int GetSeqNum(char *str, int strLen)
{
    int itotal=0;
    for (i=0; i<strLen; ++i)
    {
        itotal+=26*itotal+str[i]-'a'+1;
    }
    return itotal;
}

Answer 21

错了，多了个+...............
int GetSeqNum(char *str, int strLen) 
{ 
    int itotal=0; 
    for (i=0; i <strLen; ++i) 
    { 
        itotal=26*itotal+str[i]-'a'+1; 
    } 
    return itotal; 
}