4.27腾讯音乐笔试
人生第二次笔试ak（第一次4.10字节）
3道算法题
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param a int整型ArrayList
* @return TreeNode类ArrayList
*/
public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
Set<Integer> set=new HashSet<>();
for(int i:a){
set.add(i);
}
// write code here
res=new ArrayList<>();
List<TreeNode> tem=new ArrayList<>();
tem.add(root);
if(!set.contains(1))res.add(root);
dfs(tem,1,set);
return res;
}
void dfs(List<TreeNode> nodes,int k,Set<Integer> set){
if(nodes.size()==0)return;
List<TreeNode> tem=new ArrayList<>();
//下一层是否被删除
boolean nextflag=false;
//表示这层是否要删除
boolean flag=false;
if(set.contains(k)){
flag=true;
}
if(set.contains(k+1)){
nextflag=true;
}
for(TreeNode n:nodes){
if(n.left!=null)tem.add(n.left);
if(n.right!=null)tem.add(n.right);
if(flag&&!nextflag){
if(n.left!=null)res.add(n.left);
if(n.right!=null)res.add(n.right);
}else if(!flag&&nextflag){
n.left=null;
n.right=null;
}
}
dfs(tem,k+1,set);
} /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回值的树节点中val表示节点权值
* @param root TreeNode类 给定的初始树节点中的val表示节点编号
* @param op int整型ArrayList<ArrayList<>> op的组成为[[id,v],[id,v],[id,v],...]
* @return TreeNode类
*/
public TreeNode xorTree (TreeNode root, ArrayList<ArrayList<Integer>> op) {
// write code here
Map<Integer,List<Integer>> map=new HashMap<>();
for(List<Integer> list:op){
List<Integer> tem=map.get(list.get(0));
if(tem==null){
tem=new ArrayList<>();
map.put(list.get(0),tem);
}
tem.add(list.get(1));
}
dfs(0,root,map);
return root;
}
void dfs(int pre,TreeNode root,Map<Integer,List<Integer>> map){
if(root==null)return;
List<Integer> tem=map.get(root.val);
root.val=0;
if(tem!=null){
for(int i:tem){
root.val^=i;
}
}
root.val^=pre;
if(root.left!=null)dfs(root.val,root.left,map);
if(root.right!=null)dfs(root.val,root.right,map);
} /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @param k int整型
* @return int整型
*/
public int howMany (String S, int k) {
int[] a=new int[26];
// write code here
for(int i=0;i<S.length();i++){
a[S.charAt(i)-'a']+=1;
}
int res=0;
for(int i=0;i<26;i++){
if(a[i]>=k)res++;
}
return res;
}问答题（微信朋友圈后台设计）
好友关系设计
数据库层面
用一张好友关系表来存储好友关系。
实现上述需求需要四个字段：id（自增主键，int） user1（关注的人id，int） user2（被关注的人id，int） relation（好友关系 ，1表示好友，同时接受朋友圈，0表示好友但是不然他看朋友圈 int）
给user1，user2和relation加上索引，因为之后每次发布朋友圈都会对此进行查询。
规则层面
当user1向user2发送了一条好友请求并接受时，数据会增加两条记录，一条user1和user2的好友关系，一条user2和user1的好友关系。如果有一方不想让对方看朋友圈，那么另一方的关注关系就为0。
朋友圈设计
数据库层面
用一张朋友圈表来存储朋友圈消息，实现上述需求需要4个字段：id（自增主键，int），userId（发布者的id，int），content（朋友圈信息内容，varchar（200）），pictureId（图片序列号id，varchar），time（发布时间，datetime）
用一张朋友圈消息关系表来存储用户可见的朋友圈，需要3个字段：id（自增主键，int），userId（用户的id，int），contentId（消息id，int），可以对userId设置索引。
对于图片存储，我们可以利用文件服务器MongoDB或者云服务厂商提供的服务（比如阿里云、腾讯云的对象存储服务等等）来进行存储。存储完成后往往会返回一个序列号，利用此序列号我们就可以找到对应的图片。
规则层面
当发布朋友圈时，会上传图片，此时先进行图片上传，此时可以向服务器发送一个文件传输请求用于存储图片，并返回相应序列号。用户进行编辑文本后，可以选择仅部分好友可见，此时就是选择对应的好友id，点击发布发布后，向服务器发送请求。这时服务器将其存储为朋友圈消息表的一条记录，同时请求中会带有部分可见的userId或部分不可见的userId。
对于部分可见，我们只需对朋友圈消息关系表中增加n条记录即可；
对于部分不可见，我们需要查出默认的可见范围，查询朋友关系表user2位朋友圈消息发布者id并且朋友关系relation为0的用户user1，此时意味着这条朋友圈消息对于这些用户而言是可见的。
对于用户朋友圈消息的获取，我们可以选择主动推的方式去发送数据，可以利用利用消息队列+socket机制对这些消息进行推送；
当然我们也可以选择拉的方式（建议拉）获取朋友圈消息，具体逻辑如下：当用户连上网络时，并在朋友圈页面时，每隔10s去服务器获取一次差异数据，对朋友圈消息关系表进行查询找到当前用户能看到的消息id集合，然后通过消息id去朋友圈消息表查找对应朋友圈消息内容，然后进行返回，此时用户便得到了他能看到的朋友圈消息了。
