回复: 30
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Intern 面经 20150112

全局:

2015(1-3月) 码农类General 硕士 实习@google - 内推 - 技术电面  | | Other |

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x


本想有了match再发个总结帖,现在感觉怕是淹没在pool里了。

先分享一下时间点,2014.12.01 内推,很快有recuiter联系,但当时available的时间窗只有一月的
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

---

总体来讲题很简单,运气不错,换了难题还真未必能进host match。。

Hope for the best.

评分

参与人数 1大米 +3 收起 理由
mm豆 + 3 感谢分享!

查看全部评分


上一篇:2.18Amazon电面
下一篇:T家面试坐等跪
推荐
tinalxj12 2015-2-21 15:01:46 | 只看该作者
全局:
  1. public static void shuffle(String input){
  2.         List<Character> characters = new ArrayList<Character>();
  3.         for(char c:input.toCharArray()){
  4.             characters.add(c);
  5.         }
  6.         StringBuilder output = new StringBuilder(input.length());
  7.         while(characters.size()!=0){
  8.             int rand = (int)(Math.random()*characters.size());
  9.             
  10.             output.append(characters.remove(rand));
  11.         }
  12.         
  13.         
  14.         String res = output.toString();
  15.         for (int i=0; i<res.length()-1;i++) {
  16.                 if (res.charAt(i) ==res.charAt(i+1)) {
  17.                         System.out.println("not valid");
  18.                         break;
  19.                 }
  20.         }
  21.         System.out.println(res);
  22.     }
复制代码
回复

使用道具 举报

推荐
mm豆 2015-4-6 08:22:01 | 只看该作者
全局:
eval 发表于 2015-4-6 08:17
你的意思是“是否有多个valid的output?”吧?输出任意一个valid的答案即可。

比如这个解法,对于一种输入,对应着唯一一种输入。没有随机的过程。不知道lz怎么做的?
“先记录每个字符出现的次数,即该字符需要被填入生成字符串的次数
然后从第一位开始填空
然后每次从剩下的字母堆中选取剩余待填入次数最多、且与前一位字符不冲突的字符填入,这样可以确保剩余可填写的不同字符种类是最多的
如果没有其他不冲突的待填写字符就报错
最多是O(26n)或O(256n)
回复

使用道具 举报

推荐
mm豆 2015-4-10 01:43:21 | 只看该作者
全局:
will_ym 发表于 2015-4-8 01:59
就是按照正常的随机化 从最后一个开始随机选一个index然后判断是否符合要求,如果符合要求的话exchange。 ...

我明白你说的算法:
        Random rnd = new Random();
           for (int i=size - 1; i>= 1; i--)
                swap(arr, i, rnd.nextInt(i-1));
这样随机交换之后不会出现相同字母变成邻居的情况么?
回复

使用道具 举报

🔗
houqingniao 2015-2-19 14:57:54 | 只看该作者
全局:
子矩阵是啥问题?咋dp?
回复

使用道具 举报

🔗
Linzertorte 2015-2-19 15:16:53 | 只看该作者
全局:
houqingniao 发表于 2015-2-19 14:57
子矩阵是啥问题?咋dp?

其实就是部分和。容斥原理啥的。

评分

参与人数 1大米 +3 收起 理由
eval + 3 对对,就是这个意思

查看全部评分

回复

使用道具 举报

🔗
will_ym 2015-2-20 04:29:54 | 只看该作者
全局:
请教一下第二题怎么解的?
回复

使用道具 举报

🔗
 楼主| eval 2015-2-20 11:12:12 | 只看该作者
全局:
will_ym 发表于 2015-2-20 04:29
请教一下第二题怎么解的?

hint:是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。
回复

使用道具 举报

🔗
will_ym 2015-2-21 01:33:52 | 只看该作者
全局:
eval 发表于 2015-2-20 11:12
hint:是否能shuffle成valid的字符串可以由每个字符出现的次数的关系确定。

搞定了,但是是O(n squre). 你当时做得是O(n) 么?
回复

使用道具 举报

🔗
sonicgu 2015-2-21 01:49:26 | 只看该作者
全局:
子矩阵的题可以用容斥,也可以维护一个一维的数组
回复

使用道具 举报

🔗
中庸人90 2015-2-23 06:09:24 | 只看该作者
全局:

这个感觉不太对呢,会产生相同的char相邻的情况吧
回复

使用道具 举报

🔗
中庸人90 2015-2-23 06:11:32 | 只看该作者
全局:
will_ym 发表于 2015-2-21 01:33
搞定了,但是是O(n squre). 你当时做得是O(n) 么?

先统计每个char的个数,如果有count > (size+1)/2, 那就是invalid的。然后剩下的就不会了。。求问怎么做的?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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