头条一面挂经 后台研发岗

第一题是个rand5生成rand7的经典题，关键在于若m>n，则randm()可以直接生成randn()，只要randm()生成1到n之间返回即可，生成的数大于n就重新调用。然后可以用(randm() - 1) * m + randm()来生成1到m^2的随机数。楼主用三进制的做法，此时命中率是(2*89)/(3^5)即178/243。其实也可以生成3^6=729以内的数，然后在8*89=712以内返回，结果对89求余后加1即可，命中率是712/729，只不过每次要多调用1次rand3()。如果要深抠命中率的话就太麻烦了。第二题好像在哪里看过原题，记录子串起始位置，整个迭代过程中子串保持不含重复字符的性质，每次不能保持该性质时比较下最大长度。写了下还是磕磕绊绊的，主要是之前命名太随意导致各种写错…… int longest_unique_substr_len(const std::string& s) { constexpr size_t kInitPos = -1; std::vector<size_t> hashmap(26, kInitPos); size_t low = 0; size_t maxlen = 0; for (size_t i = 0; i != s.size(); ++i) { size_t key = s[i] - 'a'; if (hashmap[key] != kInitPos && hashmap[key] >= low) { maxlen = std::max(maxlen, i - low); low = hashmap[key] + 1; } hashmap[key] = i; } return std::max(maxlen, s.size() - low); }

import java.util.HashMap; public static int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; int len = s.length(); int max = 0, leftBound = 0; HashMap<Character, Integer> map = new HashMap<>(); for (int i = 0; i < len; i++) { char c = s.charAt(i); int tempBound = map.containsKey(c) ? map.get(c) + 1 : 0; leftBound = Math.max(leftBound, tempBound);// 滑动窗口的左门限 max = Math.max(max, i - leftBound + 1); map.put(c, i); } return max; }

第一题是有一个专门的算法的，由1-a生成1-b的随机数

第一个是洗牌算法吧

第二题滑动窗口吧O(n)

楼主这样都挂了啊 而且还是一面。。。

楼主是5.19面的后台研发吗，感觉和我面得题目差不多

第二题还好，第一题没做过还真不好一下想出来……

第二个题，可以双指针？

怎么挂掉的？感觉比我的难…

第一个算法题，应该是一致性hash吧