一亩三分地论坛

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

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

02/26 Amazon Intern Phone Interview新鲜跪经

[复制链接] |试试Instant~ |关注本帖
zhangxy9999 发表于 2016-2-27 03:00:59 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 实习@Amazon - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
是个来自加拿大的烙印,说一句话重复三遍才能听明白,both sides. 上来就做题,就做了一道 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1. 找到字符串中最后一个出现过两次的char.鏈枃鍘熷垱鑷1point3acres璁哄潧

本来挺简单,一紧张写加debug了将近半个小时。妥妥跪了。不甘心的Move on


补充内容 (2016-2-27 03:31):
Follow up 就是问怎么test,烙印全程语气轻佻不耐烦,还不爱听我一边打字一边写码
我用的HashMap,用stack动态规划可能更快,但是最快也就O(n)
不要像我一样跪简单题啊同志们!!!TTTTT____TTTTT

补充内容 (2016-2-27 03:31):. 1point 3acres 璁哄潧
*一边说话一边写码

评分

1

查看全部评分

jiudechenxin 发表于 2016-2-27 03:14:07 | 显示全部楼层
楼主,我一会儿2点面, 这道题你是咋做的啊??好紧张
回复 支持 反对

使用道具 举报

Irisazure 发表于 2016-2-27 03:19:16 | 显示全部楼层
jiudechenxin 发表于 2016-2-27 03:14
楼主,我一会儿2点面, 这道题你是咋做的啊??好紧张

面完求面经…… 不知道那个字符串里是只有字母还是数字字母都有
回复 支持 反对

使用道具 举报

babylu 发表于 2016-2-27 03:29:09 | 显示全部楼层
我刚被印度口音虐了一通……整个人都不好了……
回复 支持 反对

使用道具 举报

AlexPinhead 发表于 2016-2-27 03:57:17 | 显示全部楼层
string里是只有英文字母还是啥都有啊,前者用char[26] counter过一遍,再从字符串后往前过一遍就好吧?
如果啥字符都有的话用hashmap, two passes也是O(n),请教楼主用stack怎么dp啊?
回复 支持 反对

使用道具 举报

 楼主| zhangxy9999 发表于 2016-2-27 04:01:01 | 显示全部楼层
AlexPinhead 发表于 2016-2-27 03:57
string里是只有英文字母还是啥都有啊,前者用char[26] counter过一遍,再从字符串后往前过一遍就好吧?. 1point 3acres 璁哄潧
如 ...
-google 1point3acres
啥都有 就是用的你说的解决方法 但是我写码花的时间太长了
stack dp是我瞎猜的。。。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 04:05:00 | 显示全部楼层
zhangxy9999 发表于 2016-2-27 04:01.鐣欏璁哄潧-涓浜-涓夊垎鍦
啥都有 就是用的你说的解决方法 但是我写码花的时间太长了
stack dp是我瞎猜的。。。。

啥事stack dp......
回复 支持 反对

使用道具 举报

AlexPinhead 发表于 2016-2-27 04:06:06 | 显示全部楼层
zhangxy9999 发表于 2016-2-27 04:01
啥都有 就是用的你说的解决方法 但是我写码花的时间太长了
stack dp是我瞎猜的。。。。

哦。。。。。那你不怕对面直接问你啥是stack dp吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 04:13:53 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. visit 1point3acres.com for more.
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
  1.         public Character lastAppearTwiceChar(String input)
  2.         {
  3.                 if(input.length()==0)
  4.                 {
  5.                         //do what they ask to do
  6.                 }
  7.                 char result = 0;
  8.                 Map<Character,Integer> map = new HashMap<Character,Integer>();. 鍥磋鎴戜滑@1point 3 acres
  9.                 -google 1point3acres
  10.                 for(int i =0; i < input.length();i++)
  11.                 {
  12.                         if(map.containsKey(input.charAt(i)))
  13.                         {
  14.                                 map.put(input.charAt(i),map.get(input.charAt(i))+1);
  15.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.                         else
  17.                         {
  18.                                 map.put(input.charAt(i), 1);
  19.                         }
  20.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.                 }
  22.                
  23.                 for(char temp:input.toCharArray()).1point3acres缃
  24.                 {
  25.                         if(map.get(temp)>=2)
  26.                         {
  27.                                 result = temp;
  28.                         }
  29.                 }. 鍥磋鎴戜滑@1point 3 acres
  30.                 .1point3acres缃
  31.                
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                
  33.                
  34.                 return result;. 1point 3acres 璁哄潧
  35.      }

  36. 3分钟写完的。。。
复制代码
回复 支持 反对

使用道具 举报

Yasuo 发表于 2016-2-27 05:01:32 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 04:13
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 1point 3acres 璁哄潧
想支持楼主,请点 ...

似乎第二个pass不用全扫一遍?直接把string从后往前扫,return第一个出现次数是twice的character就好了?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 05:09:28 | 显示全部楼层
Yasuo 发表于 2016-2-27 05:01
似乎第二个pass不用全扫一遍?直接把string从后往前扫,return第一个出现次数是twice的character就好了?

average running -time compexity都是o(n)。-google 1point3acres
你从后忘前扫,假如每次都是最前面2个char是结果,那么和最后2个char是结果,没有区别。. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-2-27 05:33:50 | 显示全部楼层
这个题可能可以考虑用ascii码做。先声明一个ref=int[128],全部放0,从后往前扫,每遇到一个char就把ref里的值改成1。如果遇到1就返回。这个方案虽然也是O(n) ,但是空间复杂度更小
回复 支持 反对

使用道具 举报

AlexPinhead 发表于 2016-2-27 06:30:05 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 04:13
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
想支持楼主,请点 ...

我想问下万一string里说会出现unicode的字符时候,array table还好用吗还是得老老实实上HashMap了?
或者说面试一般就玩玩ascii或者UTF-8这种,可以在一个字节内解决呢?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 06:48:29 | 显示全部楼层
AlexPinhead 发表于 2016-2-27 06:30. visit 1point3acres.com for more.
我想问下万一string里说会出现unicode的字符时候,array table还好用吗还是得老老实实上HashMap了?
或 ...

int[256]
应该可以handle unicode的字符的吧。
回复 支持 反对

使用道具 举报

AlexPinhead 发表于 2016-2-27 06:54:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 06:48
int[256]
应该可以handle unicode的字符的吧。

unicode不是一般16bit吗,请教下怎么用2^8来解决呢?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 06:58:27 | 显示全部楼层
AlexPinhead 发表于 2016-2-27 06:54
unicode不是一般16bit吗,请教下怎么用2^8来解决呢?
-google 1point3acres
不懂你说的啥意思-google 1point3acres
你原本意思是如果 char = '!' 或者‘#’ 这种,能不能array table?
回复 支持 反对

使用道具 举报

AlexPinhead 发表于 2016-2-27 09:06:27 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 06:58
不懂你说的啥意思
你原本意思是如果 char = '!' 或者‘#’ 这种,能不能array table?

我的意思是说如果string里有“Ё”或者“խ”这种怎么办,前者U+0401,后者U+056D,超出256了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-27 09:15:52 | 显示全部楼层
AlexPinhead 发表于 2016-2-27 09:06 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我的意思是说如果string里有“Ё”或者“խ”这种怎么办,前者U+0401,后者U+056D,超出256了

你想的好多啊。。。。
回复 支持 反对

使用道具 举报

warriorbrant 发表于 2016-2-27 12:04:09 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 09:15-google 1point3acres
你想的好多啊。。。。

在hashmap里放的时候不就可以知道了吗,不用第二个遍历,hashmap里放的时候一遇到2就记录到变量res里,下次再遇到更新一下,最后返回res

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

usa521 发表于 2016-2-27 12:24:33 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-27 06:58
不懂你说的啥意思
你原本意思是如果 char = '!' 或者‘#’ 这种,能不能array table?

你好 请问 ascii 和 unicode 这两2个 到底 int[128] int[256] 够不够用啊 ..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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