今日头条2018校招前端方向（第二批）-k6k4.com

编程题

1、用户喜好

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输入描述:

输入：第1行为n代表用户的个数第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度第3行为一个正整数q代表查询的组数第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。数据范围n <= 300000,q<=300000 k是整型

输出描述:

输出：一共q行，每行一个整数代表喜好值为k的用户的个数

输入例子1:

1 2 3 3 5

1 2 1

2 4 5

3 5 3

输出例子1:

例子说明1:

样例解释:

有5个用户，喜好值为分别为1、2、3、3、5，

第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1

第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0

第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

代码：

#include <iostream>
using namespace std;
 
int main()
{
    int n, q;
    cin >> n;
    int user[n + 1];
    for (int i = 1; i <= n; i++) cin >> user[i];
    cin >> q;
    int l, r, k;
    while (q--) {
        cin >> l >> r >> k;
        int count = 0;
        for (int i = l; i <= r; i++)
            if (user[i] == k) count++;
        cout << count << endl;
    }
 
    return 0;
}

2、手串

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:

第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

输出描述:

一个非负整数，表示该手链上有多少种颜色不符需求。

输入例子1:

5 2 3

3 1 2 3

2 2 3

1 2

1 3

输出例子1:

例子说明1:

第一种颜色出现在第1颗串珠，与规则无冲突。

第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。

第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。

总计有2种颜色的分布是有问题的。

这里第2颗串珠是透明的。

代码：

#include
using namespace std;
int main()
{
    int n, m, c;
    cin >> n >> m >> c;
    int color[c + 1], first_color[c + 1];
    for (int i = 1; i <= c; i++) color[i] = 0, first_color[i] = 0;
 
    for (int i = 1; i <= n; i++) {
        int zhu;
        cin >> zhu;
        while (zhu--) {
            int zhu_color = 0;
            cin >> zhu_color;
            if (color[zhu_color] == -1) continue;   // 已经不符合要求
            if (first_color[zhu_color] == 0) {   // 该颜色第一次出现
                color[zhu_color] = i;
                first_color[zhu_color] = i + n;
            } else if (i - color[zhu_color] >= m && first_color[zhu_color] - i >= m) {
                color[zhu_color] = i;   // 暂时符合要求，更新该颜色的最新串珠位置
            } else color[zhu_color] = -1;   // 不符合要求
        }
    }
    int count = 0;
    for (int i = 1; i <= c; i++)
        if (color[i] == -1) count++;
    cout << count;
    return 0;
}

问答题

1、以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-1。请指出程序代码中错误或不符最佳实践的地方（问题不止一处，请尽量找出所有你认为有问题的地方）

int BinarySearchMax(const std::vector<int>& data, int target)
{
  int left = 0;
  int right = data.size();
  while (left < right) {
      int mid = (left + right) / 2;
      if (data[mid] <= target)
          left = mid + 1;
      else
          right = mid - 1;
  }
  if (data[right] == target)
      return right;
  return -1;
}

修改过后代码：

int BinarySearchMax(const std::vector<int>& data, int target)
{
   int left = 0, ret = -1;
   int right = data.size()-1;
   while (left <= right) {
       int mid = (left + right) / 2;
       if (data[mid] <= target) {
            if(data[mid] == target) ret = mid;
           left = mid + 1;
       } else right = mid - 1;
   }
    return ret;
}

2、设计一个TODO List，页面结构如下图所示，要求：

使用HTML与CSS完成界面开发

实现添加功能：输入框中可输入任意字符，按回车后将输入字符串添加到下方列表的最后，并清空输入框

实现删除功能：点击列表项后面的“X”号，可以删除该项

实现模糊匹配：在输入框中输入字符后，将当前输入字符串与已添加的列表项进行模糊匹配，将匹配到的结果显示在输入框下方。如匹配不到任何列表项，列表显示空

注：以上代码实现需要能在浏览器中正常显示与执行。

代码：

<code class="lang-html">
 
    TODO list
 
        body{
            margin:0;
            padding:0;
        }
        .todoContainer{
            width: 400px;
            margin: 150px auto;
        }
        .inputContainer{
            position: relative;
            width: 100%;
            height: 40px;
            box-shadow: 2px 2px 8px 2px rgba(128,128,128,.3);
        }
        .inputContainer .todoInput{
            box-sizing: border-box;
            width: 100%;
            height: 100%;
            background-color: #fff;
            padding: 0 20px;
            border: none;
        }
        .inputContainer .todoInput:focus{
            outline: 0 none;
        }
        .searchContainer{
            position: absolute;
            top:40px;
            left: 0;
            padding: 0;
            margin-top: 10px;
            width: 100%;
            box-shadow: 2px 2px 8px 2px rgba(128,128,128,.3);
            z-index: 100;
        }
        .inputContainer .hide{
            visibility:hidden;
        }
        .searchContainer .searchItem{
            box-sizing: border-box;
            list-style: none;
            width:100%;
            height: 40px;
            line-height: 40px;
            padding-left: 20px;
            padding-right: 30px;
            overflow: hidden;
            text-overflow: ellipsis;
            word-break: break-all;
            white-space: nowrap;
            background-color: #fff;
            border-bottom: 1px solid rgba(128,128,128,.3);
        }
        .listContainer{
            margin-top: 70px;
            width: 100%;
            padding: 0;
            box-shadow: 2px 2px 8px 2px rgba(128,128,128,.3);
        }
        .listItem{
            position: relative;
            box-sizing: border-box;
            list-style: none;
            width:100%;
            height: 40px;
            line-height: 40px;
            padding-left: 20px;
            padding-right: 30px;
            overflow: hidden;
            text-overflow: ellipsis;
            word-break: break-all;
            white-space: nowrap;
            background-color: #fff;
            border-bottom: 1px solid rgba(128,128,128,.3);
        }
        .listItem:last-child{
            border-bottom: none;
        }
        .delete{
            position: absolute;
            right: 0;
            top: 0px;
            width: 30px;
            height: 40px;
            line-height: 40px;
            font-size: 20px;
            text-align: center;
            cursor: pointer;
        }
 
                搜索结果1
                搜索结果2
 
            这是一个todo list1x
            这是一个todo list2x
            这是一个todo list3x
            这是一个todo list4x
 
    /**
     * 添加一个todo list
     */
    function addTodoItem(text){
        var deleteContainer = document.createElement("div"),
            deleteIcon = document.createTextNode("x"),
            listItem = document.createElement("li"),
            listItemText = document.createTextNode(text);
        var listContainer = document.querySelector(".listContainer")
        deleteContainer.className = "delete";
        deleteContainer.appendChild(deleteIcon);
        listItem.className = "listItem";
        listItem.appendChild(listItemText);
        listItem.appendChild(deleteContainer);
        listContainer.appendChild(listItem);
    }
    /**
     * 构造搜索结果列表
     */
    function processSearchResult($container,arr){
        if (arr.length) {
            $container.innerHTML = "";
            arr.forEach(function(val){
                var searchItemContainer = document.createElement("li"),
                    searchItemText = document.createTextNode(val);
                searchItemContainer.className = "searchItem";
                searchItemContainer.appendChild(searchItemText);
                $container.appendChild(searchItemContainer);
            })
        }
    }
    /**
     * 给输入框绑定事件，按下enter之后添加todo list
     */
    var inputField = document.querySelector(".todoInput");
    inputField.addEventListener('keyup',function(e){
        var inputValue = inputField.value;
        if (e.keyCode === 13) {
            addTodoItem(inputValue);
            inputField.value = "";
        }
        else{
            var reg = new RegExp(inputValue)
            var todoList = document.querySelectorAll(".listItem");
            var res = []
            for(var i = 0; i<todoList.length; i++){
                if (inputValue) {
                    if (reg.test(todoList[i].firstChild.nodeValue)) {
                        res.push(todoList[i].firstChild.nodeValue)
                    }
                }
            }
            var searchContainer = document.querySelector(".searchContainer")
            if (res.length!==0) {
                processSearchResult(searchContainer,res);
            }
            if(res.length!==0 && searchContainer.classList.contains("hide")){
                searchContainer.classList.remove("hide");
            }else if (res.length === 0 && !searchContainer.classList.contains("hide")) {
                searchContainer.classList.add("hide");
            }
        }
    });
    /**
     * 给列表添加事件代理，如果点击到x，则删除x的父节点
     */
    var listContainer = document.querySelector(".listContainer");
    listContainer.addEventListener("click",function(e){
        var target = e.target;
        if (target.className === "delete") {
            var parentNode = target.parentNode;
            listContainer.removeChild(parentNode);
        }
        // if (listContainer.childElementCount === 0) {
        //     listContainer.classList.add("hide");
        // }
    });
</code>

个人资料

crazybean
等级：8
文章：61篇
访问：15.7w
排名： 5

推荐圈子

今日头条笔试面试圈