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去朋友圈消息表查找对应朋友圈消息内容，然后进行返回，此时用户便得到了他能看到的朋友圈消息了。