首页 > 代码库 > 网易的一道笔试题的参考解法---关于广告牌投放问题

网易的一道笔试题的参考解法---关于广告牌投放问题

    有N个广告牌(N<=10万)可以投放广告,有k个用户(k<10亿)在这些广告牌上投放广告.操作rent(i,j,k)将从i到j块广告牌展示用户k的广告,如果原来有别的广告就覆盖掉. 操作query(i)返回第i个广告牌上现在投放的是哪个广告. rent和query操作出现的频率相等.要求设计一个数据结构和相应的算法,尽可能快的实现这两种操作.

  1 package test;  2   3 import java.util.HashMap;  4 import java.util.Map;  5   6 public class Signboard {  7     private Map<Integer, AD> boards;  8   9     public Signboard() { 10         super(); 11         boards = new HashMap<Integer, AD>();//Integer参数记录广告牌的位置,AD参数记录广告内容 12     } 13  14     public void rent(int begin, int end, AD ad) { 15         for (int i = begin; i <= end; i++) { 16             boards.put(i, ad); 17         } 18     } 19  20     public AD query(int i) { 21         return boards.get(i); 22     } 23  24     public static void main(String[] args) { 25         Signboard signboard = new Signboard(); 26         User user = new User(1, "zhangsan", "手机号","邮箱"); 27         AD ad = new AD(1, "ad_content", user); 28         signboard.rent(3, 5, ad); 29         System.out.println(signboard.query(4)); 30  31     } 32 } 33  34 class User { 35     private int id; 36     private String name; 37     private String tel; 38     private String email; 39  40     public User() { 41         super(); 42         // TODO Auto-generated constructor stub 43     } 44  45     public User(int id, String name, String tel, String email) { 46         super(); 47         this.id = id; 48         this.name = name; 49         this.tel = tel; 50         this.email = email; 51     } 52  53     public int getId() { 54         return id; 55     } 56  57     public void setId(int id) { 58         this.id = id; 59     } 60  61     public String getName() { 62         return name; 63     } 64  65     public void setName(String name) { 66         this.name = name; 67     } 68  69     public String getTel() { 70         return tel; 71     } 72  73     public void setTel(String tel) { 74         this.tel = tel; 75     } 76  77     public String getEmail() { 78         return email; 79     } 80  81     public void setEmail(String email) { 82         this.email = email; 83     } 84  85     @Override 86     public String toString() { 87         return "User [id=" + id + ", name=" + name + ", tel=" + tel + ", email=" + email + "]"; 88     } 89 } 90  91 class AD { 92     int id; 93     String content; 94     User user;//广告拥有者的引用 95  96     public AD() { 97         super(); 98         // TODO Auto-generated constructor stub 99     }100 101     public AD(int id, String content, User user) {102         super();103         this.id = id;104         this.content = content;105         this.user = user;106     }107 108     public int getId() {109         return id;110     }111 112     public void setId(int id) {113         this.id = id;114     }115 116     public String getContent() {117         return content;118     }119 120     public void setContent(String content) {121         this.content = content;122     }123 124     public User getUser() {125         return user;126     }127 128     public void setUser(User user) {129         this.user = user;130     }131 132     @Override133     public String toString() {134         return "AD [id=" + id + ", content=" + content + ", user=" + user + "]";135     }136 }

 

网易的一道笔试题的参考解法---关于广告牌投放问题