• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

2016头条校招笔试题(LRU)算法之JAVA实现

技术杂谈 勤劳的小蚂蚁 2个月前 (02-04) 101次浏览 已收录 0个评论 扫描二维码


操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,则会按照最近访问时间进行排序,并将最老的数据淘汰。假设现在内存空间大小为5,原本内存中没有数据,对内存中数据的访问顺序如下:1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次?

JAVA的简单实现:
首先实现一个固定长度的集合队列
    1. import java.util.Collection;  
    2. import java.util.Iterator;  
    3. import java.util.LinkedList;  
    4. import java.util.Queue;  
    5. /**
    6. * 实现一个固定长度的集合队列
    7. * 在开发中,有时候我们会遇到这样的需求:
    8. * 对一个集合操作,提前为集合指定最大大小,在我们不断向集合中添加数据的时候,当数据内容超过最大值的时候,自动将最先入队的元素移除队列。
    9. * @param <E>
    10. */  
    11. publicclassLimitQueue<E>implementsQueue<E>{  
    12.    /**
    13.     * 队列长度,实例化类的时候指定  
    14.     */  
    15.    privateint limit;    
    16.    Queue<E> queue =newLinkedList<E>();    
    17.    publicLimitQueue(int limit){    
    18.        this.limit = limit;    
    19.    }
    20.    /**
    21.     * 入队
    22.     */  
    23.    @Override    
    24.    publicboolean offer(E e){    
    25.        if(queue.size()>= limit){    
    26.            //如果超出长度,入队时,先出队    
    27.            queue.poll();    
    28.        }  
    29.        return queue.offer(e);    
    30.    }    
    31.    /**
    32.     * 出队  
    33.     */  
    34.    @Override    
    35.    public E poll(){    
    36.        return queue.poll();    
    37.    }    
    38.    /**
    39.     * 获取队列  
    40.     */  
    41.    publicQueue<E> getQueue(){    
    42.        return queue;    
    43.    }    
    44.    /**
    45.     * 获取限制大小
    46.     */  
    47.    publicint getLimit(){    
    48.        return limit;    
    49.    }    
    50.    @Override    
    51.    publicboolean add(E e){    
    52.        return queue.add(e);    
    53.    }    
    54.    @Override    
    55.    public E element(){    
    56.        return queue.element();    
    57.    }    
    58.    @Override    
    59.    public E peek(){    
    60.        return queue.peek();    
    61.    }    
    62.    @Override    
    63.    publicboolean isEmpty(){    
    64.        return queue.size()==0?true:false;    
    65.    }    
    66.    @Override    
    67.    publicint size(){    
    68.        return queue.size();    
    69.    }    
    70.    @Override    
    71.    public E remove(){    
    72.        return queue.remove();    
    73.    }    
    74.    @Override    
    75.    publicboolean addAll(Collection<?extends E> c){    
    76.        return queue.addAll(c);    
    77.    }    
    78.    @Override    
    79.    publicvoid clear(){    
    80.        queue.clear();    
    81.    }    
    82.    @Override    
    83.    publicboolean contains(Object o){    
    84.        return queue.contains(o);    
    85.    }    
    86.    @Override    
    87.    publicboolean containsAll(Collection<?> c){    
    88.        return queue.containsAll(c);    
    89.    }    
    90.    @Override    
    91.    publicIterator<E> iterator(){    
    92.        return queue.iterator();    
    93.    }    
    94.    @Override    
    95.    publicboolean remove(Object o){    
    96.        return queue.remove(o);    
    97.    }    
    98.    @Override    
    99.    publicboolean removeAll(Collection<?> c){    
    100.        return queue.removeAll(c);    
    101.    }    
    102.    @Override    
    103.    publicboolean retainAll(Collection<?> c){    
    104.        return queue.retainAll(c);    
    105.    }    
    106.    @Override    
    107.    publicObject[] toArray(){    
    108.        return queue.toArray();    
    109.    }    
    110.    @Override    
    111.    public<T> T[] toArray(T[] a){    
    112.        return queue.toArray(a);    
    113.    }    
    114. }
    执行方法:
    1. package com.itstyle.list;
    2. import java.util.ArrayList;
    3. import java.util.List;
    4. /**
    5. * 操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,
    6. * 则会按照最近访问时间进行排序,并将最老的数据淘汰。假设现在内存空间大小为5,原本内存中没有数据,对内存中数据的访问顺序如下:
    7. * 1, 2, 5, 3, 4, 6,1, 4, 3, 6, 7, 8, 3, 9 问访问过程中发生缺页的次数是多少次?
    8. *
    9. */
    10. publicclass LRU {
    11.    publicstaticvoid main(String[] args){
    12.        LimitQueue<String> list =newLimitQueue<String>(5);
    13.        Integer[] array =new  Integer[]{1,2,5,3,4,6,1,4,3,6,7,8,3,9};
    14.        List<Integer> page =newArrayList<Integer>();
    15.        for(Integer i :array){
    16.            if(list.contains(i.toString())){
    17.                list.remove(i);
    18.            }else{
    19.                page.add(i);
    20.            }
    21.            list.offer(i.toString());
    22.        }
    23.        System.out.println("缺页数量"+page.size()+",缺页数据"+page.toString());
    24.    }
    25. }
    最终执行结果:缺页数量10,缺页数据[1, 2, 5, 3, 4, 6, 1, 7, 8, 9]


      丨极客文库, 版权所有丨如未注明 , 均为原创丨
      本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
      转载请注明原文链接:2016头条校招笔试题(LRU)算法之JAVA实现
      喜欢 (0)
      [247507792@qq.com]
      分享 (0)
      勤劳的小蚂蚁
      关于作者:
      温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

      您必须 登录 才能发表评论!

      • 精品技术教程
      • 编程资源分享
      • 问答交流社区
      • 极客文库知识库

      客服QQ


      QQ:2248886839


      工作时间:09:00-23:00