一亩三分地论坛

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

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

报个google面经顺便问一下怎么做

  [复制链接] |试试Instant~ |关注本帖
ariesxiao 发表于 2016-8-17 06:48:11 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other其他

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

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

x
输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间

打个比方,比如一个字符串数组是"cat", "rabbit","dog", "mouse",int数组给的2,0,3,1,意思是string数组第0个词是cat,它本来的位置是在哪呢,我们要看int数组,int数组的0在index 1上,所以说cat之前应该是1号位的,同理rabbit在string数组的1号位,而index数组3号位的值是1,说明rabbit这个词之前应该在3号位上的,依次类推,所以变换前的字符串数组应该是 dog, cat, mouse, rabbit. Waral 鍗氬鏈夋洿澶氭枃绔,

再打个比方,如果输入是Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat, mouse, rabbit

再打个比方,如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4,输出会是dog, cat ,moutse, rabbit, lion, tiger

这个题感觉从变换前的数组求变换后的数组很好做,假设string数组是S,int数组是A, 直接一位一位循环遍历,当A[i] != i 时候把A[i] 与 A[A[i]]以及S[i] 与S[A[i]]一直调换就可以了

但这个题是要从变换后的数组求变换前的数组,做了半天也没做出个好的解法,估计跪了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

readman 发表于 2016-8-17 08:19:58 | 显示全部楼层
  1. public void convert(String[] strs, int[] ary){. 1point3acres.com/bbs
  2.         int n = ary.length;
  3.         for (int i = 0; i < n; i++) {
  4.             strs[i] += "#"+strs[ary[i]];. from: 1point3acres.com/bbs
  5.         }
  6.         for (int i = 0; i < n; i++){
  7.             strs[i] = strs[i].split("#")[1];. visit 1point3acres.com for more.
  8.         }
  9.     }
复制代码

补充内容 (2016-8-17 08:20):
反向mapping还不让我建数组, 我真的只能hack这题了
回复 支持 3 反对 1

使用道具 举报

raychien 发表于 2016-9-26 17:20:19 | 显示全部楼层
Space O(1), Time O(n)
  1. void findPrev(vector<int> &pos, vector<string> &cur) {.1point3acres缃
  2.         for (int i = 0; i < pos.size(); ++i) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.                 if (i == pos[i]) continue;
  4.                 string temp = cur[i];
  5.                 int j = i;
  6.                 while (pos[j] != j && pos[j] != i) {
  7.                         cur[j] = cur[pos[j]];
  8.                         swap(j,pos[j]);
  9.                 }
  10.                 if (pos[j] == i) {
  11.                         cur[j] = temp;
  12.                         pos[j] = j;
  13.                 }
  14.         }
  15. }
复制代码
回复 支持 2 反对 1

使用道具 举报

pawprinter 发表于 2016-8-17 13:07:31 | 显示全部楼层
大概思路是这样,比如lz举得第一个例子,从int数组的第0个开始,int[0] = 2, 那么 tmp = string[0], string[0] = string[2], 然后看int[int[0]]也就是int[2],  int[2] = 3, 那么string[2] = string[3], 以此类推,再看int[3], int[3] = 1, 那么string[3] = string[1], 最后看int[1], int[1] = 0, 那么string[1] = tmp. 完毕
回复 支持 2 反对 0

使用道具 举报

Josh 发表于 2016-8-18 00:24:14 | 显示全部楼层
Java 版本的code.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. public void reverseMapping(String[] str, int[] map) {
  2.         for(int i=0; i<map.length; i++){-google 1point3acres
  3.             int j = i;
  4.             while(map[j] != i){
  5.                 swap(str, j, map[j]);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  6.                 int temp = map[j];
  7.                 map[j] = j;. 鍥磋鎴戜滑@1point 3 acres
  8.                 j = temp;
  9.             }
  10.             map[j] = j;
  11.         }
  12.     }
  13.    
  14.     private void swap(String[] str, int i, int j) {
  15.         String temp = str[i];
  16.         str[i] = str[j];
  17.         str[j] = temp;
  18.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

taobingxue 发表于 2016-8-17 07:04:08 | 显示全部楼层
为什么感觉倒回去跟正着来一样呢 @.@ 都是把index数组置换回0~n-1?
回复 支持 反对

使用道具 举报

太阳的爸爸 发表于 2016-8-17 08:02:34 | 显示全部楼层
不知道有没有正确理解楼主题意, 但是run了一下你的两个例子都是对的
def func(items, nums):
        repo = [-1, None]
        for i in range(len(nums)):
            index = nums[i]
            temp = items[i]
            if index == repo[0]:
                items[i] = repo[1]
            else:-google 1point3acres
                items[i] = items[index]
            repo = [i, temp]. From 1point 3acres bbs
        return items
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 08:03:31 | 显示全部楼层
太阳的爸爸 发表于 2016-8-17 08:02
不知道有没有正确理解楼主题意, 但是run了一下你的两个例子都是对的
def func(items, nums):
.鐣欏璁哄潧-涓浜-涓夊垎鍦        re ...

这个不是o1 space把? 我不太认识这个语言..
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-8-17 08:14:30 | 显示全部楼层
太阳的爸爸 发表于 2016-8-17 08:02
不知道有没有正确理解楼主题意, 但是run了一下你的两个例子都是对的
def func(items, nums):
        re ...

不是O1 SPACE
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-8-17 08:15:49 | 显示全部楼层
taobingxue 发表于 2016-8-17 07:04
为什么感觉倒回去跟正着来一样呢 @.@ 都是把index数组置换回0~n-1?

.鐣欏璁哄潧-涓浜-涓夊垎鍦不对啊,比如例子
Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat, mouse, rabbit
从dog, cat, mouse, rabbit 按2013置换可以得到Cat mouse dog rabbit
.鏈枃鍘熷垱鑷1point3acres璁哄潧
但如果从Cat mouse dog rabbit 按2013置换,得到的是mouse dog cat rabibit..不是需要的dog, cat, mouse, rabbit
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-8-17 08:16:11 | 显示全部楼层

不是O1 SPACE就非常好做了,方法很多
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-8-17 08:23:34 | 显示全部楼层
readman 发表于 2016-8-17 08:19
补充内容 (2016-8-17 08:20):
反向mapping还不让我建数组, 我真的只能hack这题了

没有办法吗?那听大神这么说感觉我是被黑了.鐣欏璁哄潧-涓浜-涓夊垎鍦
或者那个面试官自己也没想清楚就瞎JB问我
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 08:29:42 | 显示全部楼层
ariesxiao 发表于 2016-8-17 08:23. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没有办法吗?那听大神这么说感觉我是被黑了
或者那个面试官自己也没想清楚就瞎JB问我

我上面的code能work...符合你的要求...你看这样行不行
回复 支持 反对

使用道具 举报

 楼主| ariesxiao 发表于 2016-8-17 08:35:26 | 显示全部楼层
readman 发表于 2016-8-17 08:29
我上面的code能work...符合你的要求...你看这样行不行

看起来是可行的,谢了!

不过我不确定他心中是不是有一个想法或者有想法是否和这个一样。真的到面试谁知道那个面试官又会给加什么限制,我是一开始用了开数组的方法做,跟他讲了想法他才说这题要是只能用O(1)空间要怎么做。。。感觉就是和他想的不一样,他不想让你从这条路走,所以不断给你加限制条件
回复 支持 反对

使用道具 举报

zzw_511 发表于 2016-8-17 08:55:06 | 显示全部楼层
  1.   public void reorder(String[] strs, int[] nums) {
  2.     for (int i = 0; i < nums.length; i++) {
  3.         if (nums[i] > i) {. From 1point 3acres bbs
  4.             swap(strs, i, nums[i]);. 1point 3acres 璁哄潧
  5.         } else if (nums[i] < i) {-google 1point3acres
  6.              //Find target position after swap operations. from: 1point3acres.com/bbs
  7.              int index = nums[i];
  8.              while (index < i) {
  9.                  index = nums[index];
  10.              }
  11.              swap(strs, i, index);
  12.         }
  13.     }
  14.   }. From 1point 3acres bbs
  15. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.   private void swap(String[] strs, int i, int j) {
  17.     String tmp = strs[i];
  18.     strs[i] = strs[j];. 1point 3acres 璁哄潧
  19.     strs[j] = tmp;
  20.   }
复制代码
有点union-find 题目的赶脚。我不确定running time 是 O(n), 但是我觉得可以根据union find类型的题目一样进行优化。思路:从左到右处理nums array, 假设当前index为i。我们的invariant:string array中在i 左边的元素都是处理好了的。由于我们的invariant,如果nums < i, 那么我们寻找的那个string曾经被我们swap过,而且最终的position肯定在i的右边或者就等于i. 我们根据nums找到该string最终的position(此处可优化), 然后进行swap.. visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

william_gong 发表于 2016-8-17 10:43:56 | 显示全部楼层
public class test2 {
    public static void exchange(String[] str, int[] idx) {
            int i = 0;
            while (i < idx.length) {
                    int next = idx[i];
                    if (next == i) {
                            i++;
                    } else {
                            swap(str, i, next);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                            swap(idx, i, next);
                    }
.1point3acres缃            }
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
   
    private static void swap(String[] str, int first, int second) {
            String temp = str[first];
            str[first] = str[second];
            str[second] = temp;. more info on 1point3acres.com
    }
   
    private static void swap(int[] str, int first, int second) {
            int temp = str[first];
            str[first] = str[second];
            str[second] = temp;
    }
   
    public static void main(String[] agrs) {
            String[] test = {"a", "b", "c", "d"};
            int[] num = {3,1,2,0};
            exchange(test, num);
            for (String i : test) {
                    System.out.println(i);
            }
    }
}
. 鍥磋鎴戜滑@1point 3 acres

写了个解法,有人能看看对嘛
回复 支持 反对

使用道具 举报

zzw_511 发表于 2016-8-17 11:21:01 | 显示全部楼层
william_gong 发表于 2016-8-17 10:43
public class test2 {
    public static void exchange(String[] str, int[] idx) {
            int i = 0;

这个test case貌似过不了额。"如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4,输出会是dog, cat ,mouse, rabbit, lion, tiger"。 你的输出的是: mouse, dog, Cat, rabbit, lion, tiger
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 11:21:40 | 显示全部楼层
zzw_511 发表于 2016-8-17 11:21. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个test case貌似过不了额。"如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4,输出会是dog, ...

大神...我的呢
回复 支持 反对

使用道具 举报

zzw_511 发表于 2016-8-17 11:26:40 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
并非大神。。。如果string里面有'#'咋办?比如input 是 "Cat", "###mouse", "##dog", "##rabbit", "tiger", "lion"
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-8-17 11:28:14 | 显示全部楼层
zzw_511 发表于 2016-8-17 11:21
这个test case貌似过不了额。"如果输入是Cat mouse dog rabbit, tiger, lion和2,0,1,3,5,4,输出会是dog, ...

但我觉得输出就是 mouse, dog,etc啊。。
莫非我理解错题意了。。我再看看
回复 支持 反对

使用道具 举报

say543 发表于 2016-8-17 13:48:07 | 显示全部楼层
output 数组也不能用吗? 算在space complexity 里面吗?
回复 支持 反对

使用道具 举报

Josh 发表于 2016-8-17 14:31:29 | 显示全部楼层
pawprinter 发表于 2016-8-17 13:07. from: 1point3acres.com/bbs
大概思路是这样,比如lz举得第一个例子,从int数组的第0个开始,int[0] = 2, 那么 tmp = string[0], string ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
大神,太机智了!这个做法应该是对的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 09:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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