一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 13676|回复: 43
收起左侧

Amazon OA1 Coding新题!!! T T

[复制链接] |试试Instant~ |关注本帖
ymqytw 发表于 2015-12-4 14:33:35 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Amazon - Other - 在线笔试 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
其他内容差不多。Coding遇到了新题,真是日了狗了。. 1point3acres.com/bbs
题目如下:
Maximum Minimum Path
给一个int[][]的matirx,对于一条从左上到右下的path p_i,p_i中的最小值是m_i,求所有m_i中的最大值。只能往下或右. 鍥磋鎴戜滑@1point 3 acres
比如:
[8, 4, 7]
[6, 5, 9]
有3条path:. 1point 3acres 璁哄潧
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5
. From 1point 3acres bbs
. From 1point 3acres bbs
补充内容 (2016-1-14 03:16):
这周拿到offer了,看来OA1的coding确实是选做的

评分

10

查看全部评分

本帖被以下淘专辑推荐:

kelmt 发表于 2015-12-5 00:00:31 | 显示全部楼层
int helper(int[][] matrix){
            int[] result = new int[matrix[0].length];
            result[0] = matrix[0][0];
            for(int i=1; i<matrix[0].length; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                    result[i] = Math.min(result[i-1], matrix[0][i]);
            }
            for(int i=1; i<matrix.length; i++){
                    result[0] = Math.min(matrix[i][0], result[0]);
                    for(int j=1; j<matrix[0].length; j++){
                            result[j] = (result[j]<matrix[i][j] && result[j-1]<matrix[i][j])?Math.max(result[j-1], result[j]):matrix[i][j];
                    }
            }
            return result[result.length-1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }

评分

2

查看全部评分

回复 支持 2 反对 1

使用道具 举报

marthew777 发表于 2015-12-4 15:10:31 | 显示全部楼层
  1.         private int maxMin;
  2.         public int maxMin(int[][] mat){
  3.                 maxMin = Integer.MIN_VALUE;
  4.                 dfs(mat, 0, 0, Integer.MAX_VALUE);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 return maxMin;
  6.         }
  7.         private void dfs(int[][] mat, int i, int j, int minSofar){. visit 1point3acres.com for more.
  8.                 if(mat.length==0 || mat[0].length==0) return;
  9.                 int M = mat.length, N = mat[0].length;
  10.                 if(i==M || j==N) return;

  11.                 minSofar = Math.min(minSofar, mat[i][j]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                 if(i==M-1 && j==N-1) {
  13.                         maxMin = Math.max(minSofar, maxMin);
  14.                 }       

  15.                 dfs(mat, i+1, j, minSofar);
  16.                 dfs(mat, i, j+1, minSofar);
  17.         }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!.鏈枃鍘熷垱鑷1point3acres璁哄潧

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2015-12-4 15:16):
相对老题,新题貌似南了一点嘛
回复 支持 3 反对 0

使用道具 举报

kevin1015666 发表于 2015-12-9 18:18:11 | 显示全部楼层
是这个
public static int maximumMinimumPath(int[][] matrix) {
                if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                        return 0;. 鍥磋鎴戜滑@1point 3 acres
                }
                int n = matrix.length;
                int m = matrix[0].length;
                int[][] dp = new int[n][m];
                dp[0][0] = matrix[0][0];.鏈枃鍘熷垱鑷1point3acres璁哄潧
                for (int i = 1; i < n; i++) {
                        dp[i][0] = Math.min(dp[i - 1][0], matrix[i][0]);
                }
                for (int i = 1; i < m; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        dp[0][i] = Math.min(dp[0][i - 1], matrix[0][i]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }
                for (int i = 1; i < n; i++) {
                        for (int j = 1; j < m; j++) {-google 1point3acres
                                dp[i][j] = Math.min(Math.max(dp[i - 1][j], dp[i][j - 1]),
                                                matrix[i][j]);
                        }
                }
                return dp[n - 1][m - 1];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
回复 支持 1 反对 0

使用道具 举报

firemanysome 发表于 2015-12-5 03:29:23 | 显示全部楼层
二维DP加维护最小值。
回复 支持 0 反对 1

使用道具 举报

阿色 发表于 2015-12-4 15:36:49 | 显示全部楼层
看来Amazon的OA1都开始启用新题了。
回复 支持 反对

使用道具 举报

dengke 发表于 2015-12-4 15:45:16 | 显示全部楼层
请问楼主是今天刚做完的吗??怎么看到最近两个OA1 Coding都是新题啊!!
回复 支持 反对

使用道具 举报

rosalind324 发表于 2015-12-4 21:53:20 来自手机 | 显示全部楼层
这个要求所有路径的最小值中的最大值 貌似只能DFS 并带着当前最小值走动 并保留一个global 更新
回复 支持 反对

使用道具 举报

kelmt 发表于 2015-12-4 21:53:29 来自手机 | 显示全部楼层
贴的code不对,用dp吧
回复 支持 反对

使用道具 举报

有所思5400 发表于 2015-12-4 23:59:32 | 显示全部楼层
这题要怎么下手,感觉毫无头绪
回复 支持 反对

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-12-5 00:29:05 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

kelmt 发表于 2015-12-5 00:33:49 | 显示全部楼层
cc11328 发表于 2015-12-5 00:29
我想看看怎么dp 一个求路径的题目

贴在了楼上,只是求一个值,并不用打印路径
回复 支持 反对

使用道具 举报

霸王祥云 发表于 2015-12-5 02:00:06 | 显示全部楼层
kelmt 发表于 2015-12-5 00:00. Waral 鍗氬鏈夋洿澶氭枃绔,
int helper(int[][] matrix){
            int[] result = new int[matrix[0].length];
            result[0] = matrix ...

kelmt 和我想法一样
回复 支持 反对

使用道具 举报

头像被屏蔽
liushixion30 发表于 2015-12-5 02:29:46 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-5 03:15:29 | 显示全部楼层
不知道C++接口是什么.瞎写了一个. 有新题真不是好消息....马上9号就due了好么....等在爆几个新题出来就搞起.

  1. void helper(int** matrix, int& row, int& col, \-google 1point3acres
  2.         int i, int j, int localmin, int& globalmax) {
  3.         if (i >= row || j >= col) return;
  4.         localmin = min(localmin, matrix[i][j]);
  5.         if (i == row - 1 && j == col - 1) {
  6.                 globalmax = max(globalmax, localmin);
  7.                 return;
  8.         }
  9.         helper(matrix, row, col, i + 1, j, localmin, globalmax);
  10.         helper(matrix, row, col, i, j + 1, localmin, globalmax);
  11. }
复制代码
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-5 03:15:59 | 显示全部楼层
leonidas1573 发表于 2015-12-5 03:15-google 1point3acres
不知道C++接口是什么.瞎写了一个. 有新题真不是好消息....马上9号就due了好么....等在爆几个新题出来就搞起 ...
. more info on 1point3acres.com
少了主函数.哈
  1. int minmax(vector< vector<int> >matrix, int row, int col) {
  2.         int globalmax = INT_MIN;
  3.         helper(matrix, row, col, 0, 0, matrix[0][0], globalmax);
  4.         return globalmax;
  5. }
复制代码
回复 支持 反对

使用道具 举报

loveonts 发表于 2015-12-5 03:36:06 | 显示全部楼层
等OA1中的表示 这道题和Leetcode上面的某两道题很像 最基本的DP
回复 支持 反对

使用道具 举报

flyinghx61 发表于 2015-12-5 06:25:11 | 显示全部楼层
为什么要叫Maximum Minimum Path? 如果只能向右或下,不就是在求所有可能路径的最大值吗?


补充内容 (2015-12-5 07:00):
理解错了,忽略,,,
回复 支持 反对

使用道具 举报

wwj722 发表于 2015-12-5 07:20:02 | 显示全部楼层
  1. public class MaximumMinimumPath {
  2.         private int min, max, row, col;
  3.         public int maxMinPath(int[][] matrix) {
  4.                 row = matrix.length;
  5.                 col = matrix[0].length;
  6.                 min = Integer.MAX_VALUE;
  7.                 max = Integer.MIN_VALUE;
  8.                 dfsHelper(matrix, min, 0, 0);
  9.                 return max;
  10.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  11.         public void dfsHelper(int[][] matrix, int min, int i, int j) {
  12.                 if (i >= row || j >= col)
  13.                         return;

  14.                 if (i == row - 1 && j == col - 1) {
  15.                         min = Math.min(min, matrix[i][j]);
  16.                         max = Math.max(max, min);
  17.                         return;
  18.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.                 min = Math.min(min, matrix[i][j]);
  20.                 dfsHelper(matrix, min, i, j + 1);
  21.                 dfsHelper(matrix, min, i + 1, j);
  22.         }
  23. }
复制代码
回复 支持 反对

使用道具 举报

firemanysome 发表于 2015-12-6 02:56:05 | 显示全部楼层
lz 的逻辑大体是什么?
回复 支持 反对

使用道具 举报

基督山伯伯 发表于 2015-12-6 06:41:19 | 显示全部楼层
有所思5400 发表于 2015-12-4 09:59. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这题要怎么下手,感觉毫无头绪

这是很基础的DP题,稍微熟悉一下DP大概10多分钟就能写出来。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-12 18:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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