一亩三分地论坛

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

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

[归纳]12月亚麻OA1已经爆出来的3个新题

[复制链接] |试试Instant~ |关注本帖
leonidas1573 发表于 2015-12-6 10:32:34 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 其他@Amazon - Other - 技术电面 |Other其他

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

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

x
亚麻12月开始在OA1中加了几个新题, 版上已经爆出来3个, 原帖链接:. 1point3acres.com/bbs
滑动窗口求最小  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156373
搜索杨氏表 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156577
矩阵路径最小值的最大值 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156378

滑动窗口求最小:
阿色 : 给了一个ArrayList:4, 2, 12, 11, -5,窗口size为2,返回的ArrayList为:2, 2, 11, -5。这里窗口size是一个参数。
Leetcode是求最大.差不多.  https://leetcode.com/problems/sliding-window-maximum/

搜索杨氏表:
霸王祥云: code的确也是新题。但就是leetcode原题Search a 2D Matrix II,相信大家都会做的了,那我就不贴代码了。

Leetcode原题 https://leetcode.com/problems/search-a-2d-matrix-ii/

矩阵路径最小值的最大值:
ymqytw: 给一个int[][]的matirx,对于一条从左上到右下的path p_i,p_i中的最小值是m_i,求所有m_i中的最大值。只能往下或右

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Good luck啦大家. 如果遇到这些题的话求诸位记一下函数的输入输出行长什么模样(Java/C++) 有助后来人哟.


评分

5

查看全部评分

本帖被以下淘专辑推荐:

sean51623 发表于 2015-12-6 16:24:50 | 显示全部楼层
我剛剛做的12/9due的 OA1, coding又碰到新題:
題目有點長,名稱好像是findOptimalWeights,但大致是這樣:
/* 一個已經預設好的class */
class Container {
    public double first;
    public double second;
}

現在給某個容量(double capacity), 還有一個array(double[] weights), 和int numOfContainers
主要是要在array中選出兩個weights總和小於等於capacity但最接近capacity
然後指定到一個Container object並且return
first和second的順序並不影響. from: 1point3acres.com/bbs
numOfContainer在java裡好像也是沒有用的,因為double[]本身就自帶length資訊
public Container findOptimalWeights(double capacity, double[] weights, int numOfContainers) . 1point3acres.com/bbs

最後用了最簡單的方法兩個 for loop找總和最接近capacity的pair
總共8個test cases直接就過了

评分

4

查看全部评分

回复 支持 3 反对 0

使用道具 举报

ancen 发表于 2015-12-7 03:54:43 | 显示全部楼层
  1. public Container findOptimalWeights(double capacity, double[]weights, int numOfContainers){
  2.         Container res = new Container();
  3.         if(weights == null || weights.length <= 0) return res;
  4.         weights.sort();
  5.         if(weight[0] >= capacity) return res;. 1point3acres.com/bbs
  6.         int begin = 0, end = weights.length-1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.         while(begin < end && weights[begin] + weights[end] > capacity){
  8.                 end--;. more info on 1point3acres.com
  9.         }
  10.         while(begin < end && weights[begin] + weights[end] <= capacity){
  11.                 begin++;
  12.         }
  13.         res.first = begin--;
  14.         res.second = end;
  15.         return res;
  16. }
复制代码


我思路跟@bihuang0910 差不多, 这是我的代码,不知道对不对,请各位多指教

补充内容 (2015-12-7 04:23):. 鍥磋鎴戜滑@1point 3 acres
第四行应该是Arrays.sort(nums); 写错了
回复 支持 1 反对 0

使用道具 举报

ninacc 发表于 2015-12-9 07:20:57 | 显示全部楼层
昨天做的12,7 due的, 题目是search in 2d matrix II, 贴一段自己写的maxMinPath的DP代码, 没跑,不知道对不,供参考。祝大家好运啦~

  1. public class MinPathValue {
  2.         public int minPathValue(int[][] grid){
  3.                 int N = grid.length;
  4.                 int M = grid[0].length;
  5.                 // DP Array, f[i][j], min weigh on path from 0,0 to i,j
  6.                 int[][] f = new int[N][M];
  7.                 //initialization
  8.                 int min1 = Integer.MAX_VALUE;
  9.                 int min2 = Integer.MAX_VALUE;. 1point3acres.com/bbs
  10.                 for(int i=0;i<N;i++){
  11.                         f[i][0] = Math.min(min1, grid[i][0]);
  12.                 }
  13.                 for(int i=1;i<M;i++){
  14.                         f[0][i] = Math.min(min2, grid[0][i]);
  15.                 }
  16.                 // DP formula
  17.                 for(int i=1;i<N;i++){
  18.                         for(int j=1;j<M;j++){. 鍥磋鎴戜滑@1point 3 acres
  19.                                 f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]), grid[i][j]);
  20.                         }
  21.                 }
  22.                 return f[N-1][M-1];
  23.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

ilovemango 发表于 2015-12-6 13:09:46 | 显示全部楼层
谢谢了楼主啦,辛苦了。
回复 支持 反对

使用道具 举报

bihuang0910 发表于 2015-12-6 13:32:01 | 显示全部楼层
LZ有没有看到12月份OA1不是这三道的面经呢?印象中好像没有看到
回复 支持 反对

使用道具 举报

刘小然 发表于 2015-12-6 13:40:04 | 显示全部楼层
THX!竟然换题
回复 支持 反对

使用道具 举报

 楼主| leonidas1573 发表于 2015-12-6 14:26:52 | 显示全部楼层
bihuang0910 发表于 2015-12-6 13:32
LZ有没有看到12月份OA1不是这三道的面经呢?印象中好像没有看到

12月刚刚开始嘛.所以暂时就这些了.希望表再增加了....
回复 支持 反对

使用道具 举报

wendy920217 发表于 2015-12-6 17:04:08 | 显示全部楼层
sean51623 发表于 2015-12-6 16:24
我剛剛做的12/9due的 OA1, coding又碰到新題:
題目有點長,名稱好像是findOptimalWeights,但大致是這樣:
/ ...

这不是two sum 变形?
回复 支持 反对

使用道具 举报

sean51623 发表于 2015-12-6 17:45:29 | 显示全部楼层
wendy920217 发表于 2015-12-6 17:04
这不是two sum 变形?

算是
姑且稱作two sum smaller (in double)吧
回复 支持 反对

使用道具 举报

bihuang0910 发表于 2015-12-7 00:32:05 | 显示全部楼层
sean51623 发表于 2015-12-6 17:45
算是
姑且稱作two sum smaller (in double)吧

这个题用sort加two pointers做是不是可以更优一些呢?
回复 支持 反对

使用道具 举报

sean51623 发表于 2015-12-7 01:38:07 | 显示全部楼层
bihuang0910 发表于 2015-12-7 00:32
这个题用sort加two pointers做是不是可以更优一些呢?

恩  這樣或許更好  不過我沒試過
最開始的時候沒有讀到題目裡first & second的順序並不影響, 以為要按照原本array裡面的順序
寫完了檢查了時候才看到題目裡的這行敘述, 不過細節怎麼寫要稍微再想想
回复 支持 反对

使用道具 举报

wwj722 发表于 2015-12-7 03:08:54 | 显示全部楼层
bihuang0910 发表于 2015-12-7 00:32
这个题用sort加two pointers做是不是可以更优一些呢?

类似于leetcode上的3 sum closet吧?
回复 支持 反对

使用道具 举报

348210207 发表于 2015-12-7 05:49:08 | 显示全部楼层
ancen 发表于 2015-12-7 03:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
我思路跟@bihuang0910 差不多, 这是我的代码,不知道对不对,请各位多指教

补充内容 (2015-12-7 04: ...

c++程序猿~
回复 支持 反对

使用道具 举报

blueGinko 发表于 2015-12-7 10:20:29 | 显示全部楼层
ancen 发表于 2015-12-7 03:54
我思路跟@bihuang0910 差不多, 这是我的代码,不知道对不对,请各位多指教

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷补充内容 (2015-12-7 04: ...

res.first = begin--; ???
while(...) 结束后 weights[begin] + weights[end] 不是刚好大于 capacity 吗. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

luoweiyueming 发表于 2015-12-7 10:40:30 | 显示全部楼层
ancen 发表于 2015-12-7 03:54
我思路跟@bihuang0910 差不多, 这是我的代码,不知道对不对,请各位多指教 . from: 1point3acres.com/bbs

补充内容 (2015-12-7 04: ...
-google 1point3acres
我也感觉你这个答案不对啊。。container里面不应该存weight的值么你存index干啥。。
回复 支持 反对

使用道具 举报

ancen 发表于 2015-12-7 10:55:33 | 显示全部楼层
blueGinko 发表于 2015-12-7 10:20
res.first = begin--; ???
while(...) 结束后 weights + weights[end] 不是刚好大于 capacity 吗

我是这么想的,第一个while循环找到结尾end+最开始的begin只和小于capacity的end的最大可能位置,然后再递增找到begin+end刚好大于capacity的临界位置,这样begin--就必然是不大于capacity且最接近capacity的组合对应的较小的那个元素的下标。而之前的while循环已经确定了较大的元素对应的下标
回复 支持 反对

使用道具 举报

ancen 发表于 2015-12-7 10:56:28 | 显示全部楼层
luoweiyueming 发表于 2015-12-7 10:40
我也感觉你这个答案不对啊。。container里面不应该存weight的值么你存index干啥。。

对,应该是返回元素,谢谢指正
回复 支持 反对

使用道具 举报

ancen 发表于 2015-12-7 14:22:14 | 显示全部楼层
仔细分析了一下,begin--会在有些test case导致out of bound.不知大家是否有其他好的思路实现O(n)的算法?
回复 支持 反对

使用道具 举报

Sense 发表于 2015-12-12 05:55:53 | 显示全部楼层
sean51623 发表于 2015-12-6 16:24
我剛剛做的12/9due的 OA1, coding又碰到新題:
題目有點長,名稱好像是findOptimalWeights,但大致是這樣:
/ ...
. more info on 1point3acres.com
这题应该是two sum的变种吧?我用two pointer做的,写了个test case过了,应该是对的
#include <iostream>
#include <algorithm>
using namespace std;
class Container{
public:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        double first;
        double second;
};. 1point3acres.com/bbs
. 1point 3acres 璁哄潧
Container findOptimalWeight(vector<double>& nums, double target){
        Container res;
        res.first = 0, res.second = 0;
        if(nums.size() < 2) return res;
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size() - 1, res1 = i, res2 = j;
        while(i < j){
                if(nums + nums[j] == target){
                        res.first = nums, res.second = nums[j];
                        return res;
                }
                else if(nums + nums[j] > target) j--;.1point3acres缃
                else{
                        if(target < nums[res1] + nums[res2] || . 鍥磋鎴戜滑@1point 3 acres
                        (target - (nums[res1] + nums[res2]) > target - (nums + nums[j]))) res1 = i, res2 = j;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        i++;
                }
        }       
        res.first = nums[res1], res.second = nums[res2];
        return res;
}

int main(){. 1point 3acres 璁哄潧
        vector<double> nums = {0.1, 2.3784, 3.2541, 9.2589, 5.3451, 6.79322, 5.3478};
        Container res = findOptimalWeight(nums, 15.0);
        cout << res.first << " + " << res.second << " = " << res.first + res.second << endl;
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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