美文网首页
程序员面试修炼05 | 网易2017笔试题

程序员面试修炼05 | 网易2017笔试题

作者: 淇奥qiaoqiao | 来源:发表于2018-05-11 18:50 被阅读0次

    其实,我尝试着使 Ruby 更自然,而不是简单。Ruby 看起来很简单,但内部是非常复杂的,就像我们的身体一样。 ——松本行弘,Ruby之父。

    image

    常用HTTP状态码(下)

    307(Temporary Redirect):临时重定向。与302类似。使用GET请求重定向。

    400(Bad Request):客户端请求的语法错误,服务器无法理解。

    401(Unauthorized):请求要求用户的身份认证。

    403(Forbidden):服务器理解请求客户端的请求,但是拒绝执行此请求。

    404(Not Found):服务器无法根据客户端的请求找到资源(网页)。通过此代码,网站设计人员可设置"您所请求的资源无法找到"的个性页面。

    500(InternalServer Error):服务器内部错误,无法完成请求。

    503(ServiceUnavailable):由于超载或系统维护,服务器暂时的无法处理客户端的请求。延时的长度可包含在服务器的Retry-After头信息中。

    image

    笔试/面试真题

    题目描述(网易-2017)

    一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理,现在需要设计一个方案让CPU处理完这批任务所需的时间最少,求这个最小的时间。

    输入描述:

    输入包括两行:
    第一行为整数n(1 ≤ n ≤ 50)
    第二行为n个整数lengthi,表示每个任务的长度为length[i]kb,每个数均为1024的倍数。

    输出描述:

    输出一个整数,表示最少需要处理的时间

    输入例子:

    5
    3072 3072 7168 3072 1024

    输出例子:

    9216

    解题思路

    该题可看作01背包问题,总任务时间是确定的,理论上最少的时间是(总时间/2),因此只需对一个CPU进行求解,看作一个容量为总时间一半的背包即可。

    下面来看解题代码(如果代码页面超出可以左右上下移动):

    1.  #include <iostream>  
    
    2.  #include <vector>  
    
    3.  #include <algorithm>  
    
    4.  using namespace std;  
    
    5.  int main()  
    
    6.  {  
    
    7.      int n,num,a=0,b=0,sum=0;  
    
    8.      cin >> n;  
    
    9.      vector<int> v;  
    
    10.    for (int i = 0; i < n; i++)  
    
    11.    {  
    
    12.        cin >> num;  
    
    13.        v.push_back(num/1024);//已知所有的任务耗时皆为1024的倍数,为了节省空间除以1024,方便后续使用  
    
    14.        sum += v[i];  
    
    15.    }  
    
    16.    vector<int> dp(sum / 2 + 1);//储存任务耗时,容量最大为sum/2  
    
    17.    for (int i = 0; i < n;i++)  
    
    18.    {  
    
    19.        for (int j = sum/2; j >=v[i]; j--)  
    
    20.        {  
    
    21.            dp[j] = max(dp[j],dp[j-v[i]]+v[i]);//dp[j]即为容量为j时候储存的最大任务耗时,因为我们的把单个CPU看作一个背包,容量为sum/2  
    
    22.                                                  //因此背包储存的越多,越接近理论值,即为最优解,这也正是求最大耗时的原因  
    
    23.        }  
    
    24.    }  
    
    25.    cout << max(dp[sum/2],sum-dp[sum/2])*1024 << endl;  
    
    26.} 
    
    
    image

    技术知识点

    Java中HashMap是如何实现的?

    在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。,Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

    当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标), 如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

    HashMap里实现了一个静态的内部类Entry,重要的属性有key,value,next,hash。map中的数据就存储在Entry[]中,每次我们put数据时,通过该key的hashcode,得到该key在Entry[]中的索引,然后以e.next遍历,如果存在对应value,返回value,不存在就将其添加到Entry[]。

    1.put(key,value)时,如果Entry[]的size超过threshold,则进行扩容,即table.length*2。

    2.get(key) 时先定位到该数组元素,再遍历该元素处的链表。

    如果我们再次放入同样的key会怎样呢?逻辑上,它应该替换老的value。事实上,它确实是这么做的。在迭代的过程中,会调用equals()方法来检查key的相等性(key.equals(k)),如果这个方法返回true,它就会用当前Entry的value来替换之前的value。

    image image

    相关文章

      网友评论

          本文标题:程序员面试修炼05 | 网易2017笔试题

          本文链接:https://www.haomeiwen.com/subject/bkkqdftx.html