[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1935|回复: 17
收起左侧

4/17 Google电面

[复制链接] |试试Instant~ |关注本帖
shou3301 发表于 2015-4-21 11:37:53 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类General 硕士 全职@Google - 猎头 - 技术电面  | Other | 在职跳槽

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

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

x
两个题:

1. 给两个date range,让返回这两个range有没有overlap。比较简单的比较,没有什么tricky的。
. more info on 1point3acres
2. 给一个SpecialArray,这个array只包含a-z26个字母。提供两种操作
SpecailArray.get(i)获得index为i的char
SpecialArray.swapA(i) 将‘a’swap到指定的index i,举例 bca, 假如我call SpecialArray.swapA(0), 就得到acb
攒rp. 牛人云集,一亩三分地

.1point3acres网

补充内容 (2015-4-21 12:12):
不好意思,竟然忘记写第二题的问题了。
问题是让你sort这个special array. visit 1point3acres for more.

补充内容 (2015-4-21 12:12):
不好意思,竟然忘记写第二题的问题了。
问题是让你sort这个special array

评分

5

查看全部评分

xujun 发表于 2015-4-21 11:53:21 | 显示全部楼层
第二题问题是什么
回复 支持 反对

使用道具 举报

cedar 发表于 2015-4-21 23:22:38 | 显示全部楼层
只包含26个字母是指Array长度是26 每个字母各出现一次呢 还是char的取值范围是a-z?
回复 支持 反对

使用道具 举报

lx223 发表于 2015-4-21 23:28:07 | 显示全部楼层
所以第二题是需要用inplace的算法咯?
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-22 00:46:14 | 显示全部楼层
cedar 发表于 2015-4-21 23:22
只包含26个字母是指Array长度是26 每个字母各出现一次呢 还是char的取值范围是a-z?

长度26,每个字母出现一次。
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-22 00:47:03 | 显示全部楼层
lx223 发表于 2015-4-21 23:28
所以第二题是需要用inplace的算法咯?

是的,因为没有提供方法可以让你直接写入这个special array,所以你只能swap
回复 支持 反对

使用道具 举报

yrcyq 发表于 2015-4-22 03:19:10 | 显示全部楼层
先找到a的位置, 把它放到第一个..然后写一个新的swap方法: a和小的换,a再和大的换,最后a再和小的换..然后用bubble sort排序.. From 1point 3acres bbs
这样 做对吗?. from: 1point3acres
回复 支持 反对

使用道具 举报

Guardians 发表于 2015-4-22 06:49:39 | 显示全部楼层
知道a最开始的location麽? 如果不知道先找a,.1point3acres网
找到后再跟现在index的字符换,
比如a的index是4, 那么就找到d(d可能在6)和d换
换完后再找f跟a swap, 依次类推?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-22 10:34:31 | 显示全部楼层
Guardians 发表于 2015-4-22 06:49
知道a最开始的location麽? 如果不知道先找a,
找到后再跟现在index的字符换,
比如a的index是4, 那么就找到 ...

我一开始的思路也是这样,但是发现假设a一开始就在0的位置,那就没法做了。后来经过思考,我的做法是,遍历,在某一个index i,我实际知道应该是哪个字母放在哪里,假设字母已经是对的了,我就继续,否则我就search那个应该在当前位置的字母在哪里,假设在j。现在的问题就是我怎么swap i和j的字母。做法就是我先swapA(i),那么a就在i了,然后我swapA(j),那么本来在j的字母现在就在i了,然后a在j。而本来在i的字母现在不知道在哪里,但是这个实际无所谓。我现在遍历整个数组,遍历过的我都可以确定相应的字母已经在对的地方了。最最后,我只要在swapA(0)我就把a放回到了正确的位置。
回复 支持 反对

使用道具 举报

Guardians 发表于 2015-4-22 10:55:30 | 显示全部楼层
shou3301 发表于 2015-4-22 10:34
我一开始的思路也是这样,但是发现假设a一开始就在0的位置,那就没法做了。后来经过思考,我的做法是,遍 ...

我打完自己写test的时候也发现这个问题了!嗯, 相当于把swapA换个方式写成了swap(i, j), 谢谢分享!!!
回复 支持 反对

使用道具 举报

小桶 发表于 2015-4-22 12:05:28 | 显示全部楼层
每次swap都保证使得一个字符交换到了最终位置,所以O(n)复杂度?
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-22 12:14:08 | 显示全部楼层
小桶 发表于 2015-4-22 12:05
每次swap都保证使得一个字符交换到了最终位置,所以O(n)复杂度?

取决于你search的复杂度。你可以很简单的维护一个hash存index,所以search可以O(1)完成,所以最终复杂度是O(n)
回复 支持 反对

使用道具 举报

ucichuck 发表于 2015-4-22 12:15:58 | 显示全部楼层
shou3301 发表于 2015-4-22 10:34
我一开始的思路也是这样,但是发现假设a一开始就在0的位置,那就没法做了。后来经过思考,我的做法是,遍 ...

其实你不需要每一次都找i的位置的。 这样时间复杂度太高了。 首先swapA(0) 这样保证A在0 index。然后 implement   swap(i,j) 这个function。  像你说的 假如 A = j, 先swapA(j), 然后 swapA(i), 然后再swapA(0)。
.1point3acres网
一个for loop 从1 到 end。 如果A != i, swap(i,A)。 然后继续查   A == i ? 相等 i++ 不等 继续swap(i,A) 一直到最后就能解决了。

我是按照你的思路想出来的,一开始真是不会。  感谢分享!!
回复 支持 反对

使用道具 举报

ucichuck 发表于 2015-4-22 12:18:02 | 显示全部楼层
ucichuck 发表于 2015-4-22 12:15
其实你不需要每一次都找i的位置的。 这样时间复杂度太高了。 首先swapA(0) 这样保证A在0 index。然后 imp ...
. visit 1point3acres for more.
晕 输入法有些问题。A [ i ]  都写成A了

更正下:

其实你不需要每一次都找i的位置的。 这样时间复杂度太高了。 首先swapA(0) 这样保证A在0 index。然后 implement   swap(i,j) 这个function。  像你说的 假如 A [ i ] = j, 先swapA(j), 然后 swapA(i), 然后再swapA(0)。. From 1point 3acres bbs
.留学论坛-一亩-三分地
一个for loop 从1 到 end。 如果A [ i ] != i, swap(i,A [ i ])。 然后继续查   A [ i ] == i ? 相等 i++ 不等 继续swap(i,A [ i ] ) 一直到最后就能解决了。

我是按照你的思路想出来的,一开始真是不会。  感谢分享!!
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-22 12:20:08 | 显示全部楼层
ucichuck 发表于 2015-4-22 12:18
晕 输入法有些问题。A [ i ]  都写成A了
-google 1point3acres
更正下:

哦,所以你的思路是我遍历的时候就把我当前的字母放到对的位置是吧?

恩,不明觉厉
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-22 12:26:59 | 显示全部楼层
其实a就相当于一个交换时的temp,swap(i,j)通过swapA(i)实现,只要把a交换到 i 再换到j,再换到原来的位置(原来的a先搜索数组找到),就实现ij互换了,然后就可以用任意一种排序方法了。不过楼主说长度就是26,每个字母一次,这个条件没用上。
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-4-23 01:55:55 | 显示全部楼层
gaohannk 发表于 2015-4-22 12:26
其实a就相当于一个交换时的temp,swap(i,j)通过swapA(i)实现,只要把a交换到 i 再换到j,再换到原来的位置 ...

.留学论坛-一亩-三分地还是用上了啊,因为用O(1)时间你就可以知道哪个字母应该在当前的index。有点类似于counting sort。
回复 支持 反对

使用道具 举报

泡妞被妞泡 发表于 2015-4-23 15:56:09 | 显示全部楼层
这样写对吗,好像get函数没用到,谢谢14楼的思路。
  1. public class sortSpecialArray {
  2.         private static class SpecialArray{. From 1point 3acres bbs
  3.                 char[] array = new char[26];
  4.                
  5.                 public char get(char[] array, int i) {
  6.                         return array[i];. 1point 3acres 论坛
  7.                 }
  8.                
  9.                 public static void swapA(char[] array, int i) {
  10.                         if (array[i] == 'a') {-google 1point3acres
  11.                                 return;. 一亩-三分-地,独家发布
  12.                         }. 留学申请论坛-一亩三分地
  13.                        
  14.                         int index = 0;-google 1point3acres
  15.                         while (index < array.length) {. 围观我们@1point 3 acres
  16.                                 if (array[index] == 'a') {. from: 1point3acres
  17.                                         break;. more info on 1point3acres
  18.                                 }
  19.                                 index++; 来源一亩.三分地论坛.
  20.                         }
  21.                         . visit 1point3acres for more.
  22.                         array[index] = array[i];
  23.                         array[i] = 'a';
  24.                 }. Waral 博客有更多文章,
  25.         }
  26.        
  27.         public void sort(char[] array) {
  28.                 for (int i = 0; i < array.length; i++) {
  29.                         if (array[i] == (char)(97 + i)) {
  30.                                 continue;
  31.                         } else {
  32.                                 SpecialArray.swapA(array, 0);
  33.                                 SpecialArray.swapA(array, i);
  34.                                 SpecialArray.swapA(array, (int)(array[i] - 97));
  35.                                 SpecialArray.swapA(array, 0);
  36.                                 i--;
  37.                         }
  38.                 }
    .1point3acres网
  39.         }
  40. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 16:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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