2016创新工场涂鸦移动校园招聘测试题-软件工程师.docx

2016创新工场涂鸦移动校园招聘测试题-软件工程师1. 找出n个字符串中出现次数最多的字符串。C/C+:char* find(char *data，int n);Java:String find(String data);说明:1. data是字符串数组，n是数组中字符串的个数，返回值为出现次数最多的字符串。2. 若结果有多个，返回任意一个即可3. 不得使用任何库函数/API，如需使用类似功能, 请自行实现4. 算法效率尽可能高，尽量少的使用内存空间5. 必须要有代码注释和算法说明。例如：data里面的数据是“paper”,”cup”,”book”,”cup”,”pen”,”book”。n = 6。返回结果为”cup”或”book”。typedef struct nodestruct node *next;char *str;int value;node;bool cmpstr(const char *str1,const char *str2)while (*str1 = *str2 & *str1!=0)+str1;+str2;if (*str1 = 0& *str2 = 0)return true;return false;char* find(char *data, int n)char *max = NULL;node *head=new node;head-str = data0;head-value = 1;head-next=NULL;char *pt = *data;for (int i = 1; i next != NULL)if (cmpstr(phead-str, datai)+phead-value;break;phead=phead-next;if (phead-next = NULL)node *nextnode = new node;nextnode-value = 0;nextnode-next = NULL;nextnode-str = datai;+nextnode-value;phead-next = nextnode;char *pmax = NULL;int maxnumber = 0;while (head-next != NULL)if (head-value maxnumber)maxnumber = head-value;pmax = head-str;node *del = head;head = head-next;delete del;return pmax;2.将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并保证奇数之间顺序不变，偶数之间顺序不变。示例：交换前链表的顺序交换后链表的顺序45312 = 53142 1 = 1（链表仅含一个元素)21 =12 =(链表为空)C/C+:链表节点定义为：struct node struct node *next;int value;struct node *swap(struct node *list);Java:链表节点定义为：class Node public Node next;public int valueNode swap(Node list)注意点和要求如下:1. swap函数要求对节点的指针/引用进行操作（不得创建任何新的链表节点）2. 不得使用任何库函数/API，如需使用类似功能, 请自行实现3. 不得将链表转化为其他类型数据结构再进行交换，如数组等typedef struct node struct node *next;int value;node;bool is_odd(int number)/判断是否是奇数if (number % 2 = 1)return true;return false;struct node *swap(struct node *list)node *pfront = NULL;/指向前面奇数的最后一个结点node *prear = NULL;/指向遍历到的后面奇数结点node *temp = NULL;pfront = prear = list;if (!is_odd(list-value)/头结点为偶数while (!is_odd(prear-next-value)/找到第一个奇数结点作为头结点prear = prear-next;list = prear-next;prear-next = prear-next-next;list-next = pfront;pfront = list;prear = list;while (prear-next != NULL)if (is_odd(prear-next-value)temp = prear-next-next;prear-next-next = pfron