美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • TNT确定《末日孤舰》第四季首播日期
  • 《权力的游戏》倒数第二季发布夜王动态海报
  • NBC取消《芝加哥正义》,全家桶第四子止步第一季
  • 2000年前首台天文计算机复原:精密度惊人
  • 科学家声称收到外星来电:宇宙中已走60亿光年
  • 蛟龙号从地球最深处带回“深海居民”:如外星怪物
  • 4分钟科普围棋规则:瞬间懂了
  • 大学生7楼钓外卖 宿管阿姨手书警告看哭
  • 飞机头突然断掉:其实 金属也会累
  • 谷歌自主处理器TPU太猛:AlphaGo只用一颗便完虐人类
  • 被美国收养的子女不能为亲属办绿卡
  • 多点开花 AMD快hold不住它的洪荒之力了
  • 6个月高位:强劲数据、强硬言论助力欧元
  • 化敌为友,诺基亚“牵手”苹果探索健康业务
  • 美元大跌——成也特朗普,败也特朗普
  • 小瞧高通! 你可就错了
  • 黄金十字:逆势扭转,贵金属是要翻身了啊!
  • 焦点:特朗普"2018预算案"周二首秀
  • IBM:这个蓝色巨人正在老去?
  • 警告:小心债券市场带来寒意
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3075|回复: 21

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

[复制链接]

16

主题

231

帖子

263

积分

中级会员

Rank: 3Rank: 3

积分
263
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]
一直调换就可以了

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


--

【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

22

主题

91

帖子

136

积分

注册会员

Rank: 2

积分
136
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
: ...................



--

29

主题

112

帖子

171

积分

注册会员

Rank: 2

积分
171
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
: ...................



--

27

主题

84

帖子

139

积分

注册会员

Rank: 2

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


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

7

主题

286

帖子

299

积分

中级会员

Rank: 3Rank: 3

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


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

--

32

主题

113

帖子

190

积分

注册会员

Rank: 2

积分
190
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,..."




--

23

主题

82

帖子

134

积分

注册会员

Rank: 2

积分
134
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
: ...................




--

22

主题

106

帖子

152

积分

注册会员

Rank: 2

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


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

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

6

主题

265

帖子

273

积分

中级会员

Rank: 3Rank: 3

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


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

24

主题

97

帖子

146

积分

注册会员

Rank: 2

积分
146
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|唐人社区

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

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