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

 找回密码
 立即注册
  • 不可思议!雨滴全速撞击地面后变成了这样...
  • 白天久坐10小时:每天10000+步也没用
  • 旅美大熊猫回国一个月:已习惯四川话和窝窝头
  • 没有蛇的国度新西兰出现了史上第一条:下场是安乐死
  • 私人飞机之巅:造价5亿!内饰堪称艺术品
  • 国外渔夫用无人机意外钓得鲨鱼:选择合影后放生
  • 没sei了!英国造神奇机器人:一年能建150座房子
  • 中国自主大型直升机:AC313大雨中试飞成功
  • 从太空看地球 这是几十年来最别致的一张
  • 中国全新纵向卧铺动车组下线:舒服极了!
  • 新iPhone的发行将会刺激苹果股价,不容错过的股票啊!
  • Ryzen会在竞争中脱颖而出吗?
  • 苹果:再一次恐慌?
  • 开撕:赛门铁克失去了谷歌的信任
  • 站在悬崖上:PayPal的未来会如何
  • 投资者对AMD的做空,并没有受到Ryzen处理器上市的影响
  • 站在悬崖上:PayPal的未来会如何
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3063|回复: 21

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

[复制链接]

16

主题

227

帖子

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

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


--

【COACH美国代购总群】99634155
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

20

主题

85

帖子

128

积分

注册会员

Rank: 2

积分
128
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

主题

107

帖子

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
: ...................



--

26

主题

80

帖子

133

积分

注册会员

Rank: 2

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


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

7

主题

280

帖子

284

积分

中级会员

Rank: 3Rank: 3

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


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

--

31

主题

106

帖子

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

主题

77

帖子

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
: ...................




--

21

主题

100

帖子

144

积分

注册会员

Rank: 2

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


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

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

5

主题

258

帖子

266

积分

中级会员

Rank: 3Rank: 3

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


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

23

主题

94

帖子

142

积分

注册会员

Rank: 2

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

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

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