一亩三分地论坛

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

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

4/17 Google电面

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

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

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

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

x
两个题:

1. 给两个date range,让返回这两个range有没有overlap。比较简单的比较,没有什么tricky的。

2. 给一个SpecialArray,这个array只包含a-z26个字母。提供两种操作. more info on 1point3acres.com
SpecailArray.get(i)获得index为i的char
SpecialArray.swapA(i) 将‘a’swap到指定的index i,举例 bca, 假如我call SpecialArray.swapA(0), 就得到acb.鐣欏璁哄潧-涓浜-涓夊垎鍦
攒rp



补充内容 (2015-4-21 12:12):
不好意思,竟然忘记写第二题的问题了。
问题是让你sort这个special array
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (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: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| 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的位置,那就没法做了。后来经过思考,我的做法是,遍 ...
. 鍥磋鎴戜滑@1point 3 acres
其实你不需要每一次都找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) 一直到最后就能解决了。
. 鍥磋鎴戜滑@1point 3 acres
我是按照你的思路想出来的,一开始真是不会。  感谢分享!!
回复 支持 反对

使用道具 举报

ucichuck 发表于 2015-4-22 12:18:02 | 显示全部楼层
ucichuck 发表于 2015-4-22 12:15
其实你不需要每一次都找i的位置的。 这样时间复杂度太高了。 首先swapA(0) 这样保证A在0 index。然后 imp ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
晕 输入法有些问题。A [ i ]  都写成A了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

更正下:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实你不需要每一次都找i的位置的。 这样时间复杂度太高了。 首先swapA(0) 这样保证A在0 index。然后 implement   swap(i,j) 这个function。  像你说的 假如 A [ i ] = j, 先swapA(j), 然后 swapA(i), 然后再swapA(0)。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一个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了

更正下:

哦,所以你的思路是我遍历的时候就把我当前的字母放到对的位置是吧? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. visit 1point3acres.com for more.
恩,不明觉厉
回复 支持 反对

使用道具 举报

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 {-google 1point3acres
  2.         private static class SpecialArray{. 鍥磋鎴戜滑@1point 3 acres
  3.                 char[] array = new char[26];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.                
  5.                 public char get(char[] array, int i) {
  6.                         return array[i];. visit 1point3acres.com for more.
  7.                 }
  8.                
  9.                 public static void swapA(char[] array, int i) {
  10.                         if (array[i] == 'a') {
  11.                                 return;
  12.                         }. From 1point 3acres bbs
  13.                        
  14.                         int index = 0;
  15.                         while (index < array.length) {
  16.                                 if (array[index] == 'a') {
  17.                                         break;
  18.                                 }
  19.                                 index++;
  20.                         }-google 1point3acres
  21.                        
  22.                         array[index] = array[i];
  23.                         array[i] = 'a';
  24.                 }
  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);. 1point3acres.com/bbs
  33.                                 SpecialArray.swapA(array, i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                                 SpecialArray.swapA(array, (int)(array[i] - 97));
  35.                                 SpecialArray.swapA(array, 0);
  36.                                 i--;
  37.                         }
  38.                 }.1point3acres缃
  39.         }
  40. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 07:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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