查看: 1968|回复: 18
收起左侧

狗 vo L4

|只看干货
匿名用户-300  2022-8-18 11:19:27 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎

2022(7-9月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | 😃 Positive 😐 AverageOther | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 匿名 于 2022-8-17 22:26 编辑

前两天面的,给大家参考
您好!
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式


补充内容 (2022-08-26 05:15 +8:00):
跟大家更新一下,今天HR说过了,但因为freeze 所以让我等,说现在不能team match,要等到下周,甚至更久
总之不论如何 还是很开心的。至少没有白刷一场题。

评分

参与人数 3大米 +17 收起 理由
chenyx95 + 1 给你点个赞!
清道神君 + 15
JasperXXSI + 1 给你点个赞!

查看全部评分


上一篇:akuna capital 社招面经
下一篇:Audible 新鲜OA
地里匿名用户
匿名用户-5B8  2022-8-23 18:16:15
本楼: 👍   100% (1)
 
 
0% (0)   👎
本帖最后由 匿名 于 2022-8-23 05:19 编辑

第二题,题意似乎要保持原数组顺序:import java.util.*;

class Solution {
    public String solve(int[] arr, int target) {
        int len = arr.length;
        TreeMap<Double, String>[][] dp = new TreeMap[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                dp[j] = new TreeMap<>();
                if(i == j) {
                    dp[j].put(0d + arr,  "" + arr);
                }
            }
        }
        for(int l = 2; l <= len; l++) {
            for(int st = 0; st + l <= len; st++) {
                for(int split = st; split < st + l - 1; split++) {
                    for(Double res1: dp[st][split].keySet()) {
                        for(Double res2: dp[split + 1][st + l - 1].keySet()) {
                            dp[st][st + l - 1].put(res1 / res2, "(" + dp[st][split].get(res1) + "/" + dp[split + 1][st + l - 1].get(res2) + ")");
                            dp[st][st + l - 1].put(res1 + res2, "(" + dp[st][split].get(res1) + "+" + dp[split + 1][st + l - 1].get(res2) + ")");
                            dp[st][st + l - 1].put(res1 - res2, "(" + dp[st][split].get(res1) + "-" + dp[split + 1][st + l - 1].get(res2) + ")");
                            dp[st][st + l - 1].put(res1 * res2, "(" + dp[st][split].get(res1) + "*" + dp[split + 1][st + l - 1].get(res2) + ")");
                        }
                    }
                }
            }
        }
        Double find1 = dp[0][len - 1].ceilingKey(0d + target);
        Double find2 = dp[0][len - 1].floorKey(0d + target);
        if(find1 != null && Math.abs(find1 - target) < 0.0001) {
            return dp[0][len - 1].get(find1);
        }
        if(find2 != null && Math.abs(find2 - target) < 0.0001) {
            return dp[0][len - 1].get(find2);
        }
        return "";
    }
    public static void main(String[] args) {
        System.out.println(new Solution().solve(new int[] {2, 3, 5}, 25));
    }
}
回复

使用道具 举报

地里匿名用户
匿名用户-300  2022-8-22 09:46:37 来自APP
本楼: 👍   100% (1)
 
 
0% (0)   👎
本帖最后由 匿名 于 2022-8-21 20:50 编辑
匿名用户 发表于 2022-08-21 15:26:12
同情楼主了,第二题是真难,类似蠡口耳巴耳

嗯,我这个还有括号的。
就是进阶版282+224。
这么反过来想想,确实考的有点过分啊这道题……
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
第二题 写了一个dfs 的写法, 参考了力扣 679

class Point{
        double val;
        String exp;

        public Point(double val, String exp){
            this.val = val;
            this.exp = exp;
        }
    }

    private Set<Double> set;
    public List<String> solution(int[] input, int target){
        List<Point> nums = new ArrayList<>();
        set = new HashSet<>();
        for(int num: input){
            nums.add(new Point((double)num, ""+num));
            set.add((double)num);
        }

        List<String> res = new ArrayList<>();
        dfs(nums,target,res);
        return res;
    }

    private void dfs(List<Point> nums, int target, List<String> res) {
        int n = nums.size();
        //base case
        if (n == 1) {
            if (Math.abs(nums.get(0).val - target) < 0.001) {
                res.add(nums.get(0).exp);
            }
            return;
        }

        //get two nums
        //for each recursion n(n-1)/2 *6 = 3n(n-1)
        //3( n(n-1) * (n-1)(n-2) *.....2*1) = 3^(n-1) n! (n-1)!
        //the maximum time required for any node will be
        // O(outer_two_for_loops)* O(array_copy + inner_for_loop) = O(N(N-1)/2)*O(N + 6) = O(N^(3))
        // tc : N^(3) 3^(n-1) n! (n-1)!
        for (int i = 0; i < n - 1; i++) {  //n(n-1)/2 pair
            for (int j = i + 1; j < n; j++) {
                Point num1 = nums.get(i), num2 = nums.get(j);
                //compute the product of i, j
                List<Point> operations = computeOp(num1, num2);
                for (int m=0;m<operations.size();m++) { //o(6)
                    List<Point> next = new ArrayList<>();
                    for (int k = 0; k < n; k++) {
                        if (k == i || k == j) continue;
                        next.add(nums.get(k));
                    }

                    //add in the product and rest of nums to next round
                    next.add(operations.get(m));

                    dfs(next, target, res);
                }
            }
        }
    }

    private List<Point> computeOp(Point a, Point b) {
        List<Point> res = new ArrayList<>();
        double aval = a.val, bval=b.val;
        res.add(new Point(aval + bval, "("+a.exp+"+"+b.exp+")"));
        res.add(new Point(aval - bval, "("+a.exp+"-"+b.exp+")"));
        res.add(new Point(bval - aval, "("+b.exp+"-"+a.exp+")"));
        res.add(new Point(aval * bval, a.exp+"*"+b.exp));
        res.add(new Point(aval / bval, a.exp+"/"+b.exp));
        res.add(new Point(bval / aval, b.exp+"/"+a.exp));
        return res;
    }

    public static void main(String[] args) {
        expressionTarget res = new expressionTarget();
        System.out.println(res.solution(new int[] {2, 3, 5}, 25));
        System.out.println(res.solution(new int[] {4, 1, 7,8}, 24));
    }
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (8)
 
 
11% (1)    👎
后续怎么样呢?有feedback吗?好难呀
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (2536)
 
 
5% (152)    👎
好难啊
next permutation还有小数字点…是个什么死亡劝退题
回复

使用道具 举报

地里匿名用户
匿名用户-300  2022-8-22 05:18:52
本楼: 👍   0% (0)
 
 
0% (0)   👎
akdhfikbk 发表于 2022-8-21 15:55
好难啊
next permutation还有小数字点…是个什么死亡劝退题

额,我觉得这道题是一个找规律题,如果比较幸运刷到过就知道规律啦。
next 排列不能用DFS做,不然时间复杂度是ON!,要用那个找规律的方法。
比如你看12432 的下一个排序数这么找
1. 先找到第一个,不是倒叙,但后面是倒叙的数,比如在12432里,“432”是倒叙,那第一个不是倒叙的数就是2
2. 再找到第一个比2大的,倒叙数里面的数,就是3,
3. 交换,数字此时变成了13422
4. 还没完,要把422转过来,最后数字就变成了13224,这就是下一个排列数

然后这个里面有一个corner case,就是 全倒叙的要特殊处理一下,比如4321 , 下一个排列数是1234
就是如果你扫完所有数,发现没找到第一步的那个数字,那说明已经是最后一个排列数了,需要回到第一个排列数,就是把整个数字倒转一下。

那么在这个基础上,我们添加小数点,就是一样的,数字还是按照原来的方法处理。
什么时候小数点向右移动呢?只有当数字排列是最后一个数字排列的时候,就是数字挪无可挪了,比如43.21,的下一个就应该是123.4,不然你小数点的位置是不需要动的。
那么什么时候小数点向左移动呢?只有一种情况,就是小数点在最右边且数字是最后一个排序,比如4321. 那么下一个就应该是.1234

就是在全数字排列的基础上,先记住小数点的位置,然后你处理完数字,看看小数点要不要动。


我感觉我这三轮比较难的是第二题,就是,我当时也想不出来什么优化的方法,结果又臭又长,写了两个DFS,一个是添加加减乘除的,一个是计算器本身的。写的我快报警了最后。也不知道有没有什么别的好办法

评分

参与人数 2大米 +6 收起 理由
raingstar + 1 赞一个
清道神君 + 5

查看全部评分

回复

使用道具 举报

地里匿名用户
匿名用户-300  2022-8-22 05:19:28
本楼: 👍   0% (0)
 
 
0% (0)   👎
eax65536 发表于 2022-8-21 01:34
后续怎么样呢?有feedback吗?好难呀

还没有feedback,HR说再过几天才能采集完所有feedback。不知道这么久是不是等于凉了……
回复

使用道具 举报

地里匿名用户
匿名用户-27B  2022-8-22 06:26:12
本楼: 👍   0% (0)
 
 
0% (0)   👎
同情楼主了,第二题是真难,类似蠡口耳巴耳
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
我靠, 第二题是要往死里整啊。 一点也不googleness啊 , 要是不想要, 直接再加上开方, power 这些operator吧。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
第二题都是digits么? digits间可以合并么? 那样就更刺激了。
回复

使用道具 举报

地里匿名用户
匿名用户-300  2022-8-22 09:45:39 来自APP
本楼: 👍   0% (0)
 
 
0% (0)   👎
tisep 发表于 2022-08-21 17:53:12
第二题都是digits么? digits间可以合并么? 那样就更刺激了。
这是个好问题,我直接按不能合并处理的…但也许确实可以?我居然当时没有想到去问一下…
完了这道题,我肯定死很惨。估计hr要告诉我这道题挂了。
我感觉像是进阶版的282跟224的合体,把俩hard拼一起。
这道题是个不苟言笑的印度姐姐出的,真的好凶残。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表