【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1706|回复: 17
收起左侧

4/17 Google电面

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

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

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

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

x
两个题:. visit 1point3acres.com for more.

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

2. 给一个SpecialArray,这个array只包含a-z26个字母。提供两种操作
SpecailArray.get(i)获得index为i的char.鏈枃鍘熷垱鑷1point3acres璁哄潧
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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二题问题是什么
回复 支持 反对

使用道具 举报

cedar 发表于 2015-4-21 23:22:38 | 显示全部楼层
关注一亩三分地微博:
Warald
只包含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
回复 支持 反对

使用道具 举报

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,. 鍥磋鎴戜滑@1point 3 acres
找到后再跟现在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)。. 鍥磋鎴戜滑@1point 3 acres

一个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 ...

晕 输入法有些问题。A [ i ]  都写成A了

更正下: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. Waral 鍗氬鏈夋洿澶氭枃绔,
其实你不需要每一次都找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了

更正下:

哦,所以你的思路是我遍历的时候就把我当前的字母放到对的位置是吧?. From 1point 3acres bbs

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

使用道具 举报

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{
  3.                 char[] array = new char[26];
  4.                
  5.                 public char get(char[] array, int i) {
  6.                         return array[i];
  7.                 }
  8.                
  9.                 public static void swapA(char[] array, int i) {
  10.                         if (array[i] == 'a') {
  11.                                 return;
  12.                         }
  13.                         . visit 1point3acres.com for more.
  14.                         int index = 0;
  15.                         while (index < array.length) {
  16.                                 if (array[index] == 'a') {
  17.                                         break;
  18.                                 }
  19.                                 index++;
  20.                         }
  21.                        
  22.                         array[index] = array[i];
  23.                         array[i] = 'a';
  24.                 }
  25.         }
  26.        
  27.         public void sort(char[] array) {
    .1point3acres缃
  28.                 for (int i = 0; i < array.length; i++) {
  29.                         if (array[i] == (char)(97 + i)) {
  30.                                 continue;. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.                         } else {. 1point3acres.com/bbs
  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.                 }
  39.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  40. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-22 23:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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