谷歌 ng 2021 start 岗位最新OA（新题！）

刚做完的谷歌 6月开的 2021 start 岗位的OA,两道新题，附个人的解法，个人第二题写了点bug，交上去后才发现，应该是没了，发出来造福大众吧！

第一题：（没有图片） 给一个用字符串描述的数字N，例如 N = “20011”，把这个N分成两部分，A和B，求所有可能构成的pair中 差值的绝对值最小的结果
比如：2001 可以分成， 20，01 差值是20 - 1 = 19，可以分成 2， 00

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一组left 和 right，将所有pair的和 与 target的差值存到res里，然后返回的结果就是 target + 最小的差值 res）。


第二题如果大佬们有更好的解法或者找到原题，请赐教

1877原题

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. class Solution {
   
2.     public int minPairSum(int[] nums) {
   
3.         Arrays.sort(nums);
   
4.         int left = 0;
   
5.         int right = nums.length - 1;
   
6.         int currentMax = 0;
   
7.         while(right > left){
   
8.             currentMax = Math.max(currentMax, nums[right] + nums[left]);
   
9.             left++;
   
10.             right--;
    
11.         }
    
12.         return currentMax;
    
13.         
    
14.         
    
15.     }
    
16. }

复制代码

第二题我的想法，先sort再两头指针同时往里缩，要确保每一个pair都尽可能小的情况下就用最小的加最大的，然后第二小的加第二大的，以此类推。
不知道有没有不需要sort的方法

碰到了一模一样的题目，我10分钟秒了然后额外花了半小时一句一句的读过去就怕有什么问题。。。1.
求最大是LC原题，可以参考lee神的代码: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/

1. def solution(A):
   
2.    return max(a+b for a,b in zip(sorted(A),sorted(A)[::-1]))

复制代码

2.
刚开始还以为是DP。。。

1. def solution(A):
   
2.    A = str(A)
   
3.    res = []
   
4.    for i in range(1,len(A)):
   
5.       a,b = int(A[:i]),int(A[i:])
   
6.       res.append(abs(a-b))
   
7.    return min(res) if res else None

复制代码

匿名者 发表于 2021-7-6 18:57
碰到了一模一样的题目，我10分钟秒了然后额外花了半小时一句一句的读过去就怕有什么问题。。。1.
求最大是 ...

谢谢层主写的答案!!