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

 找回密码
 立即注册
  • 《阿凡达》四部续集确定上映时间
  • 《速度与激情》系列有可能出衍生电影?
  • 泰国女子如厕马桶内发现异物:拉出1.5米眼睛王蛇
  • 国产大飞机C919成功“高抬腿”:距首飞仅一步之遥
  • 中国又创记录 107篇学术论文造假被出版商撤稿
  • 手脏了用水洗 水脏了怎么“洗”?
  • 野外碰到熊 装死就可以了?那是找死!
  • 有人想用尿液炼出黄金 没想到竟发现了……
  • 太空是高真空环境 也会发生腐蚀吗?
  • 希望重燃!有人宣称找到了MH370的位置
  • 在自动驾驶汽车技术的推动下,苹果更加强大
  • 标普500低于50日平均移动线,接下来将是横向盘整时期
  • 今年5大股票支撑着市场
  • 阿里巴巴增长超越市场预期,阿里云会进一步扩大
  • 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
搜索
查看: 3068|回复: 21

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

[复制链接]

16

主题

228

帖子

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

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


--


【返利网站】返利额度最高的海外购物返利网站Topcashback:平均返利7~10%,注册就送$10点我注册
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

21

主题

87

帖子

131

积分

注册会员

Rank: 2

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

主题

110

帖子

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

主题

82

帖子

133

积分

注册会员

Rank: 2

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


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

7

主题

281

帖子

284

积分

中级会员

Rank: 3Rank: 3

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


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

--

32

主题

109

帖子

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,..."




--

21

主题

78

帖子

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

主题

102

帖子

144

积分

注册会员

Rank: 2

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


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

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

5

主题

261

帖子

266

积分

中级会员

Rank: 3Rank: 3

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


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

24

主题

95

帖子

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

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

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