一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 7254|回复: 43
收起左侧

Amazon OA1 Coding新题!!! T T

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

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

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

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

x
其他内容差不多。Coding遇到了新题,真是日了狗了。
题目如下:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Maximum Minimum Path
给一个int[][]的matirx,对于一条从左上到右下的path p_i,p_i中的最小值是m_i,求所有m_i中的最大值。只能往下或右
比如:
[8, 4, 7]. from: 1point3acres.com/bbs
[6, 5, 9]
有3条path:
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5


补充内容 (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++){
                    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;-google 1point3acres
  4.                 dfs(mat, 0, 0, Integer.MAX_VALUE);
  5.                 return maxMin;
  6.         }. from: 1point3acres.com/bbs
  7.         private void dfs(int[][] mat, int i, int j, int minSofar){
  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. . from: 1point3acres.com/bbs
  12.                 minSofar = Math.min(minSofar, mat[i][j]);
    . from: 1point3acres.com/bbs
  13.                 if(i==M-1 && j==N-1) {
  14.                         maxMin = Math.max(minSofar, maxMin);
  15.                 }       

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

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

补充内容 (2015-12-4 15:16):. 1point3acres.com/bbs
相对老题,新题貌似南了一点嘛
回复 支持 3 反对 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-4 21:53
贴的code不对,用dp吧

我想看看怎么dp 一个求路径的题目
回复 支持 反对

使用道具 举报

kelmt 发表于 2015-12-5 00:33:49 | 显示全部楼层
cc11328 发表于 2015-12-5 00:29-google 1point3acres
我想看看怎么dp 一个求路径的题目
.鐣欏璁哄潧-涓浜-涓夊垎鍦
贴在了楼上,只是求一个值,并不用打印路径
回复 支持 反对

使用道具 举报

霸王祥云 发表于 2015-12-5 02:00:06 | 显示全部楼层
kelmt 发表于 2015-12-5 00:00
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了好么....等在爆几个新题出来就搞起.. 鍥磋鎴戜滑@1point 3 acres

  1. void helper(int** matrix, int& row, int& col, \
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
不知道C++接口是什么.瞎写了一个. 有新题真不是好消息....马上9号就due了好么....等在爆几个新题出来就搞起 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
少了主函数.哈
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;. more info on 1point3acres.com
  3.         public int maxMinPath(int[][] matrix) {
  4.                 row = matrix.length;
  5.                 col = matrix[0].length;. from: 1point3acres.com/bbs
  6.                 min = Integer.MAX_VALUE;
  7.                 max = Integer.MIN_VALUE;
  8.                 dfsHelper(matrix, min, 0, 0);
  9.                 return max;
  10.         }

  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. Waral 鍗氬鏈夋洿澶氭枃绔,
这题要怎么下手,感觉毫无头绪
. 鍥磋鎴戜滑@1point 3 acres
这是很基础的DP题,稍微熟悉一下DP大概10多分钟就能写出来。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 09:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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