返回

2021年美团程序员面试题

第1题:


 k链表翻转。给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,则翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现。



 

typedef struct node {

    struct node *next;

    int data;

} node;

void createList(node **head, int data)

{

    node *pre, *cur, *new;

    pre = NULL;

    cur = *head;

    while (cur != NULL) {

        pre = cur;

        cur = cur->next;

    }

    new = (node *)malloc(sizeof(node));

    new->data = data;

    new->next = cur;

    if (pre == NULL)

    *head = new;

    else

    pre->next = new;

}

void printLink(node *head)

{

    while (head->next != NULL) {

        printf("%d ", head->data);

        head = head->next;

    }

    printf("%dn", head->data);

}

int linkLen(node *head)

{

    int len = 0;

    while (head != NULL) {

        len ++;

        head = head->next;

    }

    return len;

}

node* reverseK(node *head, int k)

{

    int i, len, time, now;

    len = linkLen(head);

    if (len < k) {

        return head;

        } else {

        time = len / k;

    }

    node *newhead, *prev, *next, *old, *tail;

    for (now = 0, tail = NULL; now < time; now ++) {

        old = head;

        for (i = 0, prev = NULL; i < k; i ++) {

            next = head->next;

            head->next = prev;

            prev = head;

            head = next;

        }

        if (now == 0) {

            newhead = prev;

        }

        old->next = head;

        if (tail != NULL) {

            tail->next = prev;

        }

        tail = old;

    }

    if (head != NULL) {

        tail->next = head;

    }

    return newhead;

}

int main(void)

{

    int i, n, k, data;

    node *head, *newhead;

    while (scanf("%d %d", &n, &k) != EOF) {

        for (i = 0, head = NULL; i < n; i ++) {

            scanf("%d", &data);

            createList(&head, data);

        }

        printLink(head);

        newhead = reverseK(head, k);

        printLink(newhead);

    }

    return 0;

}


第2题:


 有一个随机数发生器,以概率P产生0,概率(1-P)产生1,请问能否利用这个随机数发生器,构造出新的发生器,以1/2的概率产生0和1。请写明结论及推理过程。



 这道题想等概率产生0、1,就需要找到两个独立事件,这个两个独立事件发生的概率相同,已知随机数生成器可以以p产生0,以1-p产生1,所以有下面4个独立事件,用随机数生成器产生00,01,10,11,各自的概率分别为p*p,p*(1-p),(1-p)*p,(1-p)*(1-p)可以发现生成01,10的概率相同,因此只保留这两种情况敏感词舍弃,然后将01映射为0,10映射为1,则等概率0,1随机数生成器可得到


第3题:


 4个足球队打小组单循环,计分方式:胜3分平1分负0分,如果计分相同,则净胜球多的队伍排名靠前,如果净胜球还一样,则进球多的球队排名靠前。小组前两名出线。问可能出线的最低分数是多少。请说明推理过程。 备注:单循环赛是指所有参加比赛的队两两之间都比赛一次,最后按各队在全部比赛中的积分,得失分率排列名次。



 第一名的最坏成绩是所有球队之间都是平,但是它与其他三支球队之间的比赛累积进球最多的。所以第二名的最坏成绩最差是三平,而且球队累积进球第二多。所以最差是三分。


第4题:


 从1到1000000的所有自然数,数字“1”一共出现了多少次?例:自然数101中,数字“1”出现了2次,自然数1011中,数字“1”出现了3次,请写明计算过程及结果。



 1-999,999:10的5次方 * 6=600,000
1,000,000 : 1次

加起来一共600,001次


第5题:


 请找出下面代码中的所有错误
说明:以下代码是把一个字符串倒序,如“abcd”倒序后变为“dcba”

#include"string.h"

main()

  {

   char*src="hello,world";

   char* dest=NULL;

   int len=strlen(src);

   dest=(char*)malloc(len);

    char* d=dest;

   char* s=src[len];

   while(len--!=0)

       d++=s--;

   printf("%s",dest);

   return 0;

 }



 方法1:

int main()

 {

  char* src = "hello,world";

  int len = strlen(src);

  char* dest = (char*)malloc(len+1);//要为\0分配一个空间

  char* d = dest;

  char* s = &src[len-1];//指向最后一个字符

  while( len-- != 0 )

  *d++=*s--;

  *d = 0;//尾部要加\0

  printf("%s\n",dest);

  free(dest);// 使用完,应当释放空间,以免造成内存汇泄露

  return 0;

 }

方法2:

main()

{

   char str[]="hello,world";

   int len=strlen(str);

   char t;

   for(int i=0; i   {

    t=str[i];

    str[i]=str[len-i-1]; str[len-i-1]=t;

   }

   printf("%s",str);

   return 0;

}


第6题:


 以下代码功能:找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的符号,如果有多个元素满足这个条件,则返回其中序号最大的。请找出下面代码中所有错误,直接在代码右侧空白处修改


Int bisearch(char**arr, int b, int e, char*v){

    Int minIndex = b, maxIndex = e, midIndex;

    while(minIndex<maxindex){

        midIndex=(minIndex+maxIndex)/2;

        if(strcmp(arr[midIndx],v<=0)){

            minIndex = midIndex;

        }else{

            maxIndex=minIndex;

        }

   }

        

    if(!strcmp(arr[maxIndex],v)){

        return maxIndex;

    }else{

        return -1;

    }

}

   




 int BinarySearch(char **ar,int begin,int end,char *v)
{
    int result=-1;
    while(begin <= end)
    {
        int mid=begin+(end-begin)/2;
        if(strcmp(ar[mid],v) > 0)
            end=mid-1;
        else if(strcmp(ar[mid],v) < 0)
            begin=mid+1;
        else
        {
            if(result < mid)
                result=mid;
            begin=mid+1;
        }
    }
    return result;
}


第7题:


 字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到。请编程实现以下检测:字符串S1是否可以由字符串S2通过循环移位而得到。 语言不限(推荐C/C++,不推荐写伪码)



 

public class Question2 {

    private static void reverseCharArr(char[] arr, int left, int right) {

        if (arr == null || left > right) return;

 

        while (left < right) {

            char tmp = arr[left];

            arr[left] = arr[right];

            arr[right] = tmp;

 

            left++;

            right--;

        }

    }

 

    public static void main(String[] args) {

        System.out.println(isRotate("ABCD", "DABC"));

    }

 

    private static String rotate(String str, int i) {

        if (str == null || i > str.length()) return null;

 

        char arr[] = str.toCharArray();

        reverseCharArr(arr, 0, i-1);

        reverseCharArr(arr, i, arr.length-1);

        reverseCharArr(arr, 0, arr.length-1);

 

        return new String(arr);

    }

 

    public static boolean isRotate(String s1, String s2) {

        if (s1 == null || s2 == null || s2.length() != s1.length()) return false;

 

        int indexOfFirst = s2.indexOf(s1.charAt(0));

 

        if (indexOfFirst == -1) return false;

 

        System.out.println(indexOfFirst);

 

        String tmp = rotate(s2, indexOfFirst);

        System.out.println(tmp);

 

        if (tmp.equals(s1)) {

            return true;

        }

        return  false;

    }

 

 

}


相关知识