推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

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

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

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

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

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

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

. 1point3acres.com/bbs再打个比方,如果输入是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

查看全部评分

本帖被以下淘专辑推荐:

raychien 发表于 2016-9-26 17:20:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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]];. visit 1point3acres.com for more.
  8.                         swap(j,pos[j]);
  9.                 }
  10.                 if (pos[j] == i) {
  11.                         cur[j] = temp;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                         pos[j] = j; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.                 }
  14.         }
  15. }
复制代码
回复 支持 3 反对 1

使用道具 举报

readman 发表于 2016-8-17 08:19:58 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. public void convert(String[] strs, int[] ary){
  2.         int n = ary.length;
  3.         for (int i = 0; i < n; i++) {
  4.             strs[i] += "#"+strs[ary[i]];
  5.         }
  6.         for (int i = 0; i < n; i++){
  7.             strs[i] = strs[i].split("#")[1];
  8.         }
  9.     }
复制代码

补充内容 (2016-8-17 08:20):
反向mapping还不让我建数组, 我真的只能hack这题了
回复 支持 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]);
  6.                 int temp = map[j];
  7.                 map[j] = j;
  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:
                items[i] = items[index]
            repo = [i, temp]
        return items
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 08:03:31 | 显示全部楼层
太阳的爸爸 发表于 2016-8-17 08:02
不知道有没有正确理解楼主题意, 但是run了一下你的两个例子都是对的. 1point3acres.com/bbs
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. 鍥磋鎴戜滑@1point 3 acres
为什么感觉倒回去跟正着来一样呢 @.@ 都是把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

但如果从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...符合你的要求...你看这样行不行

看起来是可行的,谢了!. 1point3acres.com/bbs

不过我不确定他心中是不是有一个想法或者有想法是否和这个一样。真的到面试谁知道那个面试官又会给加什么限制,我是一开始用了开数组的方法做,跟他讲了想法他才说这题要是只能用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) {. 1point 3acres 璁哄潧
  4.             swap(strs, i, nums[i]);
  5.         } else if (nums[i] < i) {
  6.              //Find target position after swap operations. visit 1point3acres.com for more.
  7.              int index = nums[i];
  8.              while (index < i) {. 1point 3acres 璁哄潧
  9.                  index = nums[index];
  10.              }
    . From 1point 3acres bbs
  11.              swap(strs, i, index);
  12.         }
  13.     }
  14.   }

  15.   private void swap(String[] strs, int i, int j) {
  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..鐣欏璁哄潧-涓浜-涓夊垎鍦

回复 支持 反对

使用道具 举报

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 {-google 1point3acres
                            swap(str, i, next);
                            swap(idx, i, next);
                    }
            }. 1point 3acres 璁哄潧
    }
   
    private static void swap(String[] str, int first, int second) {. From 1point 3acres bbs
            String temp = str[first];
            str[first] = str[second];-google 1point3acres
            str[second] = temp;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
    private static void swap(int[] str, int first, int second) {.1point3acres缃
            int temp = str[first];-google 1point3acres
            str[first] = str[second];
            str[second] = temp;
    }. more info on 1point3acres.com
   
    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);. more info on 1point3acres.com
            }
    }
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 鍥磋鎴戜滑@1point 3 acres
写了个解法,有人能看看对嘛
回复 支持 反对

使用道具 举报

zzw_511 发表于 2016-8-17 11:21:01 | 显示全部楼层
william_gong 发表于 2016-8-17 10:43.1point3acres缃
public class test2 {
    public static void exchange(String[] str, int[] idx) {
            int i = 0;
. 鍥磋鎴戜滑@1point 3 acres
这个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. 1point3acres.com/bbs
这个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.1point3acres缃
这个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
大概思路是这样,比如lz举得第一个例子,从int数组的第0个开始,int[0] = 2, 那么 tmp = string[0], string ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 13:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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