一亩三分地论坛

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

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

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

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

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

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

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

x
输入是一个字符串数组,一个int数组,输入的字符串数组是另外一个字符串数组通过int数组变换得到的,int数组的值代表的是原来这位置上的字符串经过变换后的坐标,然后输出是求变换之前的字符串数组,要求用线性时间,o(1)额外空间
. 1point 3acres 璁哄潧
打个比方,比如一个字符串数组是"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

再打个比方,如果输入是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]]一直调换就可以了
-google 1point3acres
但这个题是要从变换后的数组求变换前的数组,做了半天也没做出个好的解法,估计跪了
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

3

查看全部评分

本帖被以下淘专辑推荐:

raychien 发表于 2016-9-26 17:20:19 | 显示全部楼层
Space O(1), Time O(n)
  1. void findPrev(vector<int> &pos, vector<string> &cur) {
  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.         }. 1point 3acres 璁哄潧
  15. }
复制代码
回复 支持 3 反对 1

使用道具 举报

readman 发表于 2016-8-17 08:19:58 | 显示全部楼层
  1. public void convert(String[] strs, int[] ary){-google 1point3acres
  2.         int n = ary.length;
  3.         for (int i = 0; i < n; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.             strs[i] += "#"+strs[ary[i]];
  5.         }. more info on 1point3acres.com
  6.         for (int i = 0; i < n; i++){
  7.             strs[i] = strs[i].split("#")[1];
  8.         }
  9.     }
复制代码

补充内容 (2016-8-17 08:20):
反向mapping还不让我建数组, 我真的只能hack这题了
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 3 反对 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
  1. public void reverseMapping(String[] str, int[] map) {
  2.         for(int i=0; i<map.length; i++){
  3.             int j = i;
  4.             while(map[j] != i){
  5.                 swap(str, j, map[j]);. 鍥磋鎴戜滑@1point 3 acres
  6.                 int temp = map[j];
  7.                 map[j] = j;
  8.                 j = temp;
  9.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.             map[j] = j;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. from: 1point3acres.com/bbs
  18.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

taobingxue 发表于 2016-8-17 07:04:08 | 显示全部楼层
为什么感觉倒回去跟正着来一样呢 @.@ 都是把index数组置换回0~n-1?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

太阳的爸爸 发表于 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]. Waral 鍗氬鏈夋洿澶氭枃绔,
            else:
                items[i] = items[index]
            repo = [i, temp]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        return items
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 08:03:31 | 显示全部楼层
太阳的爸爸 发表于 2016-8-17 08:02.鏈枃鍘熷垱鑷1point3acres璁哄潧
不知道有没有正确理解楼主题意, 但是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):
. more info on 1point3acres.com        re ...
. more info on 1point3acres.com
不是O1 SPACE
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

不对啊,比如例子.1point3acres缃
Cat mouse dog rabbit和2,0,1,3,输出也会是dog, cat, mouse, rabbit
从dog, cat, mouse, rabbit 按2013置换可以得到Cat mouse dog rabbit

但如果从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这题了

没有办法吗?那听大神这么说感觉我是被黑了. from: 1point3acres.com/bbs
或者那个面试官自己也没想清楚就瞎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: 1point3acres.com/bbs
  4.             swap(strs, i, nums[i]);-google 1point3acres
  5.         } else if (nums[i] < i) {
  6.              //Find target position after swap operations
  7.              int index = nums[i];
  8.              while (index < i) {
  9.                  index = nums[index];
  10.              }
  11.              swap(strs, i, index);
  12.         }
  13.     }
  14.   }

  15.   private void swap(String[] strs, int i, int j) {. visit 1point3acres.com for more.
  16.     String tmp = strs[i];
  17.     strs[i] = strs[j];
  18.     strs[j] = tmp;
  19.   }
复制代码
有点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.

求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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);
                    }
            }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
   
    private static void swap(String[] str, int first, int second) {
            String temp = str[first];
            str[first] = str[second];
            str[second] = temp;
    }
   
    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);
            }
    }. visit 1point3acres.com for more.
}


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

使用道具 举报

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 | 显示全部楼层
readman 发表于 2016-8-17 11:21. 1point3acres.com/bbs
大神...我的呢

并非大神。。。如果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.鏈枃鍘熷垱鑷1point3acres璁哄潧
大概思路是这样,比如lz举得第一个例子,从int数组的第0个开始,int[0] = 2, 那么 tmp = string[0], string ...

大神,太机智了!这个做法应该是对的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-24 05:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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