一亩三分地论坛

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

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

[找工就业] 问下AMAZON的OA2两道题最优解

[复制链接] |试试Instant~ |关注本帖
stalin 发表于 2015-11-6 07:14:56 | 显示全部楼层 |阅读模式

2016(7-9月)-[16]CS本科+fresh grad 无实习/全职 - 网上海投| 码农类全职@Amazonfresh grad应届毕业生

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

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

x
之前做OA2的时候遇到过两个题,大家的面经也都包括了

其一是rotate matrix by 90 degrees. 1point3acres.com/bbs
可以这样写,时间O(MN)空间O(MN):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
static int [][] rotateR(int [][] input){

    int n =input.length;
    int m = input[0].length;
    int [][] output = new int [m][n];

    for (int i=0; i<n; i++)
        for (int j=0;j<m; j++)
            output [j][n-i-1] = input[j];
   
    return output;
                }

        static int [][] rotateL(int[][] input)
        {
    int n =input.length;
    int m = input[0].length;
    int [][] output = new int [m][n];

    for (int i=0; i<n; i++)
        for (int j=0;j<m; j++)
            output [m-j-1] = input[j];
    return output;
        }
感觉这个就是最优的解法。。。

但我还看到有先transpose的解法,差不多是这样的:
        public static int[][] transpose(int[][] input)
        {
    int[][] sol = new int[input[0].length][input.length];
    for(int i=0;i<sol.length;++i)
        for(int j=0;j<sol[0].length;++j)
            sol[j] = input[j];
    return sol;
        }

        public static int[][] rotate(int[][] input, int flag)
        {
    int[][] transposed = transpose(input);
    if(flag==0)
    {
        for(int i=0;i<transposed.length;++i)
            for(int j=0;j<transposed.length/2;++j)
            {
                swap(transposed[j], transposed[transposed.length-j-1]);
            }
    }
    else
    {
        for(int i=0;i<transposed[0].length;++i)
            for(int j=0;j<transposed.length/2;++j)
            {
                swap(transposed[j],transposed[length-j-1]);
            }
    }
    return transposed;

        }
好像这个看上去复杂点的transpose方法用的时间却还多一些。。。
是不是没有更好的解法了?

第二个是简化版game of life,给一个数组,里面元素不是0就是1,如果一个元素两边的元素相等,那么这个元素就是0,否则是1,问n天后的状态
最简单的写法就是新开一个数组然后循环n次,每次循环都检查一下两边元素进行更新
有没有谁可以说一下in place的解法呢?





天空无语 发表于 2015-11-7 06:30:22 | 显示全部楼层
这是video的节奏了?? 我周四video ,rotate那题也没想到更好的方法
回复 支持 反对

使用道具 举报

 楼主| stalin 发表于 2015-11-7 07:52:08 | 显示全部楼层
天空无语 发表于 2015-11-7 06:30. 鍥磋鎴戜滑@1point 3 acres
这是video的节奏了?? 我周四video ,rotate那题也没想到更好的方法

嗯漫长等待终于有消息了……看来只要OA2结束一周没消息就是video了
我是16号才video……rotate这题你是一个个直接换还是先transpose做的?
祝你video顺利
回复 支持 反对

使用道具 举报

fiona8957 发表于 2015-11-7 12:11:07 | 显示全部楼层
第二个题的in-place,我觉得只要用个previous变量记录i-1的值,temp=i的值. 等当前的i值update之后,prev=temp.
回复 支持 反对

使用道具 举报

albee_fighting 发表于 2015-11-7 12:16:48 | 显示全部楼层
stalin 发表于 2015-11-7 07:52
嗯漫长等待终于有消息了……看来只要OA2结束一周没消息就是video了. From 1point 3acres bbs
我是16号才video……rotate这题你是 ...

楼主大概等了多久收到了video啊
回复 支持 反对

使用道具 举报

 楼主| stalin 发表于 2015-11-7 12:39:41 | 显示全部楼层
albee_fighting 发表于 2015-11-7 12:16. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主大概等了多久收到了video啊

一。个。月。

字字带泪
回复 支持 反对

使用道具 举报

albee_fighting 发表于 2015-11-7 13:11:53 | 显示全部楼层
stalin 发表于 2015-11-7 12:39. 1point 3acres 璁哄潧
一。个。月。

字字带泪

我天那么久```那我还是等等吧```刚做完oa2五天就快等不了了````
回复 支持 反对

使用道具 举报

wxr.dal 发表于 2015-11-7 13:22:22 | 显示全部楼层
  1.         static int[] state(int[] A, int n) {
  2.                     for (int i = 0; i < n; ++i) {
  3.                                 int pre = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.                                 for (int j = 0; j < A.length; ++j) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                                     if (j == A.length - 1)
  6.                                                 A[j] = pre ^ 0;
  7.                                     else {. From 1point 3acres bbs
  8.                                                 int cur = A[j];
  9.                                                 A[j] = A[j + 1] ^ pre;. 1point3acres.com/bbs
  10.                                                 pre = cur;
  11.                                     }
  12.                                 }
  13.                     }. 鍥磋鎴戜滑@1point 3 acres
  14.                     return A;
  15.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| stalin 发表于 2015-11-7 13:37:00 | 显示全部楼层

多谢多谢!好人一生平安!
回复 支持 反对

使用道具 举报

天空无语 发表于 2015-11-8 06:58:17 | 显示全部楼层
stalin 发表于 2015-11-7 07:52. Waral 鍗氬鏈夋洿澶氭枃绔,
嗯漫长等待终于有消息了……看来只要OA2结束一周没消息就是video了
我是16号才video……rotate这题你是 ...

我是一个一个直接换的,没有想到更好的办法,你有什么更有效的方法吗?
回复 支持 反对

使用道具 举报

 楼主| stalin 发表于 2015-11-10 04:47:53 | 显示全部楼层
天空无语 发表于 2015-11-8 06:58
我是一个一个直接换的,没有想到更好的办法,你有什么更有效的方法吗?

我觉得这就是最好方法了
首先确定空间一定是M*N因为rotate以后不能inplace
然后肯定要填满这个matrix,那时间也必然是N*M了

记得video完来发一下面经~~
回复 支持 反对

使用道具 举报

firemanysome 发表于 2015-11-30 08:39:46 | 显示全部楼层
这个貌似还真有in place的解法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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