4.7腾讯音乐笔试情况
三道编程题,每个30分,一道问答题,10分。编程ac2.3道。
问答题,给你一个大文件,你怎么传输,提高性能和可靠性(从物理通道,网络,操作系统等方面回答):压缩+mapreduce+udp传输+kakfa异步。
编程题一,给你一个n位的字符串,至少两个连续的字符在一起才算一个合格的序列,再给一个k,需要满足这个字符串有k个合格的字符串,问有多少种情况。
比较绕,我发下我的code,只过了30%,最后想到有一点点问题,但是也就没改了。
public class Solution4 { @Test public void myTest() { System.out.println(numsOfStrings(5, 2)); } static final int MOD = (int) Math.pow(10, 6); //A(n-k,k)*A(26,k)*[25*(n-2k)] //A(n-k,k)代表在所有堆中(k+(n-2k))中选择k堆用来选择 //A(26,k)代表k堆的排列 //lastNum代表最后剩余的可选择数量,如果n==2k,这部分就是1. public int numsOfStrings(int n, int k) { // write code here long x = 1, y = 1, z = 1; for (int i = n - k + 1; i <= n - k; i++) { x *= i; x %= MOD; } for (int i = 26 - k + 1; i <= 26; i++) { z *= i; z %= MOD; } long lastNum = n == 2 * k ? 1 : 25 * (n - 2 * k); return (int) (n == 2 * k ? z : x * z * lastNum); } }
第二题就很逗,看着比较难,在想怎么用dp做,后来随便一写就ac了。。。给一个数组a,可以对其中的某一个数减k次,每次减x,问最后这个数组的最大值是多少。
尤其这题给你几个数,没说输入是什么,看了半天对照着核心方法知道了第一个是k,第二个是x。
刚开始我在暴力,没想到pq,然后没过,发现我理解错了,就是了pq一下就ac了。。
public int minMax(ArrayList<Integer> a, int k, int x) { // write code here //[7,2,1],3,2 //2 PriorityQueue<Integer> pq = new PriorityQueue<>((b, c) -> (c - b)); for (int i = 0; i < a.size(); i++) { pq.offer(a.get(i)); } for (int i = 0; i < k; i++) { Integer poll = pq.poll(); poll -= x; pq.offer(poll); } return pq.poll(); }第三题更逗,问给你一个二进制字符串,每次操作可以删除其中的一个字符,问最少多少次后可以将这个字符串改成2的幂,比如,”111“是7,删除前面两个1就是1,1是2的0次方。题目给的案例具有迷惑性,我还以为只能从前往后删除呢。思前想后,感觉只留下一个1不就行了。。。代码粘出来,注释的地方是我之前想得复杂了。
public int minCnt(String s) { // write code here int cnt = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1') cnt++; } // for (int i = 0; i < 16; i++) { // arr[i] = (int) Math.pow(2, i); // } // long x = Integer.parseInt(s, 2); // long temp = x; // long cnt = 0; // while (temp != 0) { // temp &= temp - 1; // cnt++; // } // for (int i = 0; i < s.length(); i++) { // for (int j = 0; j < arr.length; j++) { // if (fun(s.substring(i, s.length()), arr[i])) return // } // } return (int) (cnt - 1); }