微软近期高频面试题分享 + 分析

YankeeDoodle

首先来理解一下题目，你怎么做到使得「吃得最多的那个人吃得最少」？
可以这样理解，我们先不管每个人只能吃两种特定葡萄的约束，你怎么让「吃得最多的那个人吃得最少」？
显然，只要平均分就行了，每个人吃 (a+b+c)/3 颗葡萄。即便不能整除，比如说 a+b+c=8，那也要尽可能平均分，就是说一个人吃 2 颗，另两个人吃 3 颗。
综上，「吃得最多的那个人吃得最少」就是让我们尽可能地平均分配，而吃的最多的那个人吃掉的葡萄颗数就是 (a+b+c)/3 向上取整的结果，也就是 (a+b+c+2)/3。
PS：向上取整是一个常用的算法技巧。大部分编程语言中，如果你想计算 M 除以 N，M / N 会向下取整，你想向上取整的话，可以改成 (M+(N-1)) / N。
好了，刚才在讨论简单情况，现在考虑一下如果加上「每个人只能吃特定两种葡萄」的限制，怎么做？
也就是说，每个人只能吃特定两种葡萄，你也要尽可能给三个人平均分配，这样才能使得吃得最多的那个人吃得最少。
这可复杂了，如果用 X, Y, Z 表示这三个人，就会发现他们组成一个三角关系：

Falldawn

YankeeDoodle 发表于 2021-4-15 10:22
首先来理解一下题目，你怎么做到使得「吃得最多的那个人吃得最少」？
可以这样理解，我们先不管每个人只能 ...

非常感谢大佬师兄，这题有意思，期待后续，感觉像解一个方程了

lyzinskey

zico 发表于 2021-4-14 23:09
看内部org，大佬你们组招的全是国人，给你点个赞！respect！

看内部org，这个大佬在北京office

abcd1992719g

针对回文问题(leetcode 336)做了一个视频讲解，没有用到最优的马拉车 (manacher's algorithm)因为感觉最优解有点too much, 面试中应该不需要。希望可以帮助到大家！

LC336视频讲解

zico

lyzinskey 发表于 2021-04-14 21:29:05
看内部org，这个大佬在北京office

那就make sense了..

Falldawn

abcd1992719g 发表于 2021-4-15 13:17
针对回文问题(leetcode 336)做了一个视频讲解，没有用到最优的马拉车 (manacher's algorithm)因为感觉最优 ...

非常感谢！那我把Leetcode上面的题解也分享给大家吧

Falldawn

本帖最后由 Falldawn 于 2021-4-15 23:57 编辑

https://leetcode.com/problems/palindrome-pairs/

參考：https://leetcode.com/problems/palindrome-pairs/solution/
这题参考答案的说明讲得非常详细，不过我更喜欢讨论区的答案https://leetcode.com/problems/pa ... stand-JAVA-Solution，不知道我的空间复杂度分析得对不对，这里假设每一个new出来的string 的空间都为O（1）

Solution 1: HashMap
There are several cases to be considered that isPalindrome(s1 + s2):
Case1: If s1 is a blank string, then for any string that is palindrome s2, s1+s2 and s2+s1 are palindrome.
Case 2: If s2 is the reversing string of s1, then s1+s2 and s2+s1 are palindrome.
Case 3: If s1[0:cut] is palindrome and there exists s2 is the reversing string of s1[cut+1:] , then s2+s1 is palindrome.
Case 4: Similar to case3. If s1[cut+1: ] is palindrome and there exists s2 is the reversing string of s1[0:cut] , then s1+s2 is palindrome.
To make the search faster, build a HashMap to store the String-idx pairs.
Let n be the number of words, and k be the average length of the word.
Time : O(n * k^2).
Space: O(n) for the HashMap. For each word, we're making a list of all possible pair words which is O(n * k), so O(n * k).

public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(words == null || words.length == 0){
return res;
}
//build the map save the key-val pairs: String - idx
Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < words.length; i++){
map.put(words[i], i);[/i]
[i] }[/i]
//special cases: "" can be combine with any palindrome string
Integer blankIdx = map.get("");
if(blankIdx != null){
for(int i = 0; i < words.length; i++){
if(i != blankIdx && isPalindrome(words, 0, words.length() - 1)){
res.add(Arrays.asList(blankIdx, i));
res.add(Arrays.asList(i, blankIdx));
}
}
}
//find all string and reverse string pairs
for(int i = 0; i < words.length; i++){
String reversed = new StringBuilder(words).reverse().toString();
Integer reversedIdx = map.get(reversed);
if (reversedIdx != null && reversedIdx != i) {
res.add(Arrays.asList(i, reversedIdx));
}
}
//find the pair s1, s2 that
//case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
//case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
for(int i = 0; i < words.length; i++){
String cur = words;
for(int cut = 1; cut < cur.length(); cut++){
if(isPalindrome(cur, 0, cut - 1)){
String right = cur.substring(cut);
String reversedRight = new StringBuilder(right).reverse().toString();
Integer found = map.get(reversedRight);
if(found != null && found != i) {
res.add(Arrays.asList(found, i));
}
}
if(isPalindrome(cur, cut, cur.length() - 1)){
String left = cur.substring(0, cut);
String reversedLeft = new StringBuilder(left).reverse().toString();
Integer found = map.get(reversedLeft);
if(found != null && found != i) {
res.add(Arrays.asList(i, found));
}
}
}
}
return res;
}
public boolean isPalindrome(String s, int i, int j){
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}

复制代码

Solution 2: HashMap with one pass
If we look closely at case 1 and case 2, they are actually the special cases of case 3 and case 4 and we can merge them together with just one pass.
Time : O(n * k^2).
Space: O(n) for the HashMap. For each word, we're making a list of all possible pair words which is O(n * k), so O(n * k).

public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
if(words == null || words.length <= 1){
return res;
}
//build the map save the key-val pairs: String - idx
Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < words.length; i++){
map.put(words, i);
}
//find the pair s1, s2 that
//case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
//case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
for(int i = 0; i < words.length; i++){
String cur = words;
for(int cut = 0; cut < cur.length(); cut++){
if(isPalindrome(cur, 0, cut - 1)){
String right = cur.substring(cut);
String reversedRight = new StringBuilder(right).reverse().toString();
Integer found = map.get(reversedRight);
if(found != null && found != i) {
res.add(Arrays.asList(found, i));
if (right.isEmpty()) {// handle "" in words list
res.add(Arrays.asList(i, found));
}
}
}
if(isPalindrome(cur, cut, cur.length() - 1)){
String left = cur.substring(0, cut);
String reversedLeft = new StringBuilder(left).reverse().toString();
Integer found = map.get(reversedLeft);
if(found != null && found != i) {
res.add(Arrays.asList(i, found));
if (left.isEmpty()) {// handle "" in words list
res.add(Arrays.asList(found, i));
}
}
}
}
}
return res;
}
public boolean isPalindrome(String s, int i, int j){
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}

复制代码

参考答案对Trie解法的讲解也非常详细，不过讨论区的大牛分析也非常好https://leetcode.com/problems/pa ... with-Trie-structure

Both building and searching the Trie structure take O(n * k^2), which sets the total time complexity of the solution.
The Trie is the main space usage. In the worst case, each of the O(n⋅k) letters in the input would be on separate nodes, and each node would have up to n indexes in its list. This gives us a worst case of O(n2⋅k), which is strictly larger than the input or the output.
Here is the complete Java program:

class TrieNode {
TrieNode[] next;
int index;
List<Integer> list;
TrieNode() {
next = new TrieNode[26]; // record next letter in a word, a is 0, b is 1, c is 2 ..., z is 25
index = -1; // record if this trieNode is a word, means from root to this trienode can form a word in words array and the index in words array. if no word ends on this node, index is -1.
list = new ArrayList<>(); // if from this letter in a word to beginning of this word can form a palindrome, add the word index in the words array.
}
}
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
TrieNode root = new TrieNode();
for (int i = 0; i < words.length; i++) {
addWord(root, words, i);
}
for (int i = 0; i < words.length; i++) {
searchPalindrome(words, res, root, i);
}
return res;
}
private void addWord(TrieNode node, String word, int indexInWords) {
for (int i = word.length() - 1; i >= 0; i--) {
int trieIndex = word.charAt(i) - 'a';
if (node.next[trieIndex] == null) {
node.next[trieIndex] = new TrieNode();
}
// if from this trienode to the beginning of a word is palindrome.
if (isPalindrome(word, 0, i)) {
node.list.add(indexInWords);
}
node = node.next[trieIndex];
}
node.index = indexInWords;// end of word, set word index
}
private void searchPalindrome(String word, List<List<Integer>> res, TrieNode node, int indexInWords) {
// search part 1: compare the word to trie (the word may longer than the counterparty in trie)
//case1 : s1[j:] is palindrome and s1[0:j) = reverse(s2) => (s1, s2)
for (int i = 0; i < word.length(); i++) {
if (node.index != -1 && node.index != indexInWords && isPalindrome(word, i, word.length() - 1)) {
res.add(Arrays.asList(indexInWords, node.index));
}
node = node.next[word.charAt(i) - 'a'];
if (node == null) {
return;
}
}
// search part 2: the word is end, only check the rest in trie. (the counterparty in trie may longer than the word )
// if it is the last trienode of a word, add to result.
// Two words are the same length, form a palindrome
if(node.index != -1 && indexInWords != node.index){
res.add(Arrays.asList(indexInWords, node.index));
}
// if from this trienode to the beginning of a word can form a palindrome, add it to the result.
//case2 : s2[0:cut] is palindrome and s1[] = reverse(s2[cut:]) => (s1, s2)
for (int k : node.list) {
if (indexInWords != k) {
res.add(Arrays.asList(indexInWords, k));
}
}
}
private boolean isPalindrome(String word, int i, int j) {
while (i < j) {
if (word.charAt(i) != word.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}

复制代码

参考答案最后还对Online Algorithms进行了说明

baxon

最近也拿了一个别的组的offer，非常感兴趣贵组，大佬求带！！

YankeeDoodle

本帖最后由 YankeeDoodle 于 2021-4-16 09:36 编辑

开始想了下回溯算法暴力穷举的可能性：
对于每一颗葡萄，可能被谁吃掉？有两种可能呗，那么我写一个回溯算法，把所有可能穷举出来，然后求个最值行不行？
理论上是可行的，但是暴力算法的复杂度一般都是指数级，如果你以葡萄为「主角」进行穷举，看看变量 a, b, c 都是 long 型的数据，这个复杂度已经让我脊梁沟冒冷汗了。
那么这道题还是得取巧，思路还是要回到如何「尽可能地平均分配」上面，那么事情就变得有意思起来。
如果把葡萄的颗数 a, b, c 作为三条线段，它们的大小作为线段的长度，想一想它们可能组成什么几何图形？我们的目的是否可以转化成「尽可能平分这个几何图形的周长」？
三条线段组成的图形，那不就是三角形嘛？不急，我们小学就学过，三角形是要满足两边之和大于第三边的，假设 a < b < c，那么有下面两种情况：
如果 a + b > c，那么可以构成一个三角形，只要在这个三角形中间画一个顶点都在边 a, b, c 上的等边三角形，这三点就一定可以把这个三角形的周长平分成三份，且每一份都包含两条边，如下图图1

也就是说，这种情况下，三个人依然是可以平均分配所有葡萄的，吃的最多的人最少可以吃到的葡萄颗数依然是 (a+b+c+2)/3。
如果 a + b <= c，这三条边就不能组成一个封闭的图形了，那么我们可以将最长边 c「折断」，也就是形成一个四边形。
这里面有两种情况，如下图图2
对于情况一，a + b 和 c 的差距还不大的时候，可以看到依然能够让三个人平分这个四边形，那么吃的最多的人最少可以吃到的葡萄颗数依然是 (a+b+c+2)/3。
随着 c 的不断增大，就会出现情况二，此时 c > 2*(a+b)，由于每个人口味的限制，为了尽可能平分，X 最多吃完 a 和 b，而 c 边需要被 Y 或 Z 平分，也就是说此时吃的最多的人最少可以吃到的葡萄颗数就是 (c+1)/2，即平分 c 边向上取整。

以上就是全部情况，翻译成代码如下：
long solution(long a, long b, long c) {
long[] nums = new long[]{a, b, c};
Arrays.sort(nums);
long sum = a + b + c;

// 能够构成三角形，可完全平分
if (nums[0] + nums[1] > nums[2]) {
return (sum + 2) / 3;
}
// 不能构成三角形，平分最长边的情况
if (2 * (nums[0] + nums[1]) < nums[2]) {
return (nums[2] + 1) / 2;
}
// 不能构成三角形，但依然可以完全平分的情况
return (sum + 2) / 3;
}
至此，这道题就被巧妙地解决了，时间复杂度仅需 O(1)，关键思路在于如何尽可能平分。

milanism

楼主你好，在Linkedin上加了发消息一直没有回音，请问是否有邮箱或者其他的联系方式？

[高频题] 微软近期高频面试题分享 + 分析

评分