美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 比尔·盖茨一句话:美国网友全炸了
  • 中学语文教材惊现黄色网站链接 家长看懵
  • 罕见一幕!女儿念了一首诗:李彦宏快哭了...
  • 北京紧急叫停共享电动单车:不符合上牌标准且存安全隐患
  • 三星掌门人李在镕正式被关进拘留室:如此生活悲催
  • 求大神PS照片…又来一帮不怕死的网友
  • 北影艺考复试继续引网友围观:靓女颜值吸睛
  • 中国人去美国必须交出社交账号!或者……
  • 电竞女主播上相亲节目称要生一整支战队:玩家点赞
  • 今非昔比!杨幂10年前旧照曝光 曾为刘亦菲撑伞
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3055|回复: 21

    内推面经 -问个G家面试题- 唐人社区|北美华人论坛

    [复制链接]

    15

    主题

    226

    帖子

    257

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    257
    QQ
    发表于 2016-8-27 07:53:00 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-问个G家面试题
      JobHunting
    标 题: 问个G家面试题


    输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过
    int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,
    然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间

    打个比方,比如一个字符串数组是"cat", "rabbit","dog", "mouse",int数组给的2,0
    ,3,1,意思是string数组第0个词是cat,它本来的位置是在哪呢,我们要看int数组,
    int数组的0在index 1上,所以说cat之前应该是1号位的,同理rabbit在string数组的1
    号位,而index数组3号位的值是1,说明rabbit这个词之前应该在3号位上的,依次类推
    ,所以变换前的字符串数组应该是 dog, cat, mouse, rabbit

    再打个比方,如果输入是Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat,
    mouse, rabbit

    再打个比方,如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4,输出会
    是dog, cat ,moutse, rabbit, lion, tiger

    这个题感觉从变换前的数组求变换后的数组很好做,假设string数组是S,int数组是A
    , 直接一位一位循环遍历,当A != i 时候把A 与 A[A]以及S 与S[A]
    一直调换就可以了

    但这个题是要从变换后的数组求变换前的数组,做了半天也没做出个好的解法,估计跪


    --


    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    19

    主题

    84

    帖子

    125

    积分

    注册会员

    Rank: 2

    积分
    125
    QQ
    发表于 2016-8-27 08:28:06 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    看不出有什么trick…一个一个swap

    【 在 Picard (皮卡尔舰长) 的大作中提到: 】
    : 输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过
    : int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,
    : 然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间
    : 打个比方,比如一个字符串数组是"cat", "rabbit","dog", "mouse",int数组给的2
    ,0
    : ,3,1,意思是string数组第0个词是cat,它本来的位置是在哪呢,我们要看int数组,
    : int数组的0在index 1上,所以说cat之前应该是1号位的,同理rabbit在string数组
    的1
    : 号位,而index数组3号位的值是1,说明rabbit这个词之前应该在3号位上的,依次类推
    : ,所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
    : 再打个比方,如果输入是Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat,
    : mouse, rabbit
    : ...................



    --

    28

    主题

    105

    帖子

    167

    积分

    新手上路

    Rank: 1

    积分
    167
    QQ
    发表于 2016-8-27 08:44:04 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    so easy


    【 在 Picard (皮卡尔舰长) 的大作中提到: 】
    : 输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过
    : int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,
    : 然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间
    : 打个比方,比如一个字符串数组是"cat", "rabbit","dog", "mouse",int数组给的2
    ,0
    : ,3,1,意思是string数组第0个词是cat,它本来的位置是在哪呢,我们要看int数组,
    : int数组的0在index 1上,所以说cat之前应该是1号位的,同理rabbit在string数组
    的1
    : 号位,而index数组3号位的值是1,说明rabbit这个词之前应该在3号位上的,依次类推
    : ,所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
    : 再打个比方,如果输入是Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat,
    : mouse, rabbit
    : ...................



    --

    25

    主题

    79

    帖子

    128

    积分

    注册会员

    Rank: 2

    积分
    128
    QQ
    发表于 2016-8-27 08:53:53 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    没看懂,就这么简单?
    --

    7

    主题

    277

    帖子

    284

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    284
    QQ
    发表于 2016-8-27 08:55:15 | 显示全部楼层
    JobHunting
    标  题: Re: 问个狗家面试题


    楼主有点紧张了,我还是没理解题目的输入输出是什么

    --

    31

    主题

    102

    帖子

    175

    积分

    注册会员

    Rank: 2

    积分
    175
    QQ
    发表于 2016-8-27 08:56:18 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题



    【 在 Picard (皮卡尔舰长) 的大作中提到: 】
    : 正向转换是你说的这样,比如
    : dog, cat ,moutse, rabbit, lion, tiger和2,0,1,3,5,4,用数字数组的输出会
    : 是Cat mouse dog rabbit, tiger, lion,很直观的就是dog数字数组对应的是2,所以
    : dog放到2号位,cat数字数组对应的值是0,放到0号位
    : 但现在题目的要求是给你的输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5
    ,4
    : ,要你得到dog, cat ,moutse, rabbit, lion, tiger,也就是说一个字符串数组,按
    : 你下面说的方法变成另外一个字符串数组之后,让你再想办法变回来

    例子不是很简单吗?
    input_string="cat,mouse,..."
    input_sequence="2,0,..."
    不就是
    output
    =input_string[input_sequence]
    =input_string[2,0,...]
    ="cat,mouse,..."[2,0,...]
    ="dog,cat,..."




    --

    21

    主题

    76

    帖子

    120

    积分

    注册会员

    Rank: 2

    积分
    120
    QQ
    发表于 2016-8-27 09:24:45 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    public static void invert(String[] strings, int[] indices) {
      String tmp = null;
      for(int i = 0, n = strings.length; i < n; i++) {
        int index = indices[i];
        if (index < i) {
          do {
            index=indices[index];
          } while (index < i);
          indices[i]=index;
        }
        tmp = strings[i];
        strings[i] = strings[index];
        strings[index]=tmp;
      }
    }
    【 在 Picard (皮卡尔舰长) 的大作中提到: 】
    : 输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过
    : int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,
    : 然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间
    : 打个比方,比如一个字符串数组是&quot;cat&quot;, &quot;rabbit&quot;,&quot;dog&quot;, &quot;mouse&quot;,int数组给的2
    ,0
    : ,3,1,意思是string数组第0个词是cat,它本来的位置是在哪呢,我们要看int数组,
    : int数组的0在index 1上,所以说cat之前应该是1号位的,同理rabbit在string数组
    的1
    : 号位,而index数组3号位的值是1,说明rabbit这个词之前应该在3号位上的,依次类推
    : ,所以变换前的字符串数组应该是 dog, cat, mouse, rabbit
    : 再打个比方,如果输入是Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat,
    : mouse, rabbit
    : ...................




    --

    20

    主题

    99

    帖子

    124

    积分

    注册会员

    Rank: 2

    积分
    124
    QQ
    发表于 2016-8-27 09:28:27 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    如果我没理解错的话,反着变也可以转化成正着变,但int数列要变一下:

    比如int数列第i个位置上是a[i],反着变的时候只需要换成a[a[i]]应该就可以了。
    --

    4

    主题

    256

    帖子

    246

    积分

    注册会员

    Rank: 2

    积分
    246
    QQ
    发表于 2016-8-27 09:29:14 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    lz举的例子,难道不是直接拿数字数组的书作为字符串数组的index,按顺序输入就好
    了?
    --

    22

    主题

    90

    帖子

    137

    积分

    注册会员

    Rank: 2

    积分
    137
    QQ
    发表于 2016-8-27 09:40:01 | 显示全部楼层
    JobHunting
    标  题: Re: 问个G家面试题


    解法非线性,循环移位就n^2了


    【 在 Foxman(今狐冲) 的大作中提到: 】
    <br>: public static void invert(String[] strings, int[] indices) {
    <br>:   String tmp = null;
    <br>:   for(int i = 0, n = strings.length; i
    --
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -问个G家面试题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -问个G家面试题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

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