OPT 期间买房的利弊

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
[Google级团队]
实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 10871|回复: 67
收起左侧

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

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

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

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

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

x
输入是一个字符串数组,一个int数组,
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
. 1point3acres.com/bbs

打个比方,比如一个字符串数组是"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.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

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]];. 1point3acres.com/bbs
  8.                         swap(j,pos[j]);
  9.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.                 if (pos[j] == i) {. From 1point 3acres bbs
  11.                         cur[j] = temp;
  12.                         pos[j] = j;
    . 1point 3acres 璁哄潧
  13.                 }
  14.         }
  15. }
复制代码
回复 支持 4 反对 1

使用道具 举报

readman 发表于 2016-8-17 08:19:58 | 显示全部楼层
  1. public void convert(String[] strs, int[] ary){. 1point 3acres 璁哄潧
  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){. 1point3acres.com/bbs
  5.                 swap(str, j, map[j]);
  6.                 int temp = map[j];
  7.                 map[j] = j;
  8.                 j = temp;
  9.             }
  10.             map[j] = j;. visit 1point3acres.com for more.
  11.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.     }
  13.    
  14.     private void swap(String[] str, int i, int j) {
  15.         String temp = str[i];-google 1point3acres
  16.         str[i] = str[j];. 鍥磋鎴戜滑@1point 3 acres
  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]-google 1point3acres
            else:
                items[i] = items[index]
            repo = [i, temp]
        return items
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-17 08:03:31 | 显示全部楼层
太阳的爸爸 发表于 2016-8-17 08:02
. more info on 1point3acres.com不知道有没有正确理解楼主题意, 但是run了一下你的两个例子都是对的
def func(items, nums):. Waral 鍗氬鏈夋洿澶氭枃绔,
        re ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个不是o1 space把? 我不太认识这个语言..
回复 支持 反对

使用道具 举报

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

但如果从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
没有办法吗?那听大神这么说感觉我是被黑了. visit 1point3acres.com for more.
或者那个面试官自己也没想清楚就瞎JB问我

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

使用道具 举报

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

看起来是可行的,谢了!. from: 1point3acres.com/bbs
. 1point 3acres 璁哄潧
不过我不确定他心中是不是有一个想法或者有想法是否和这个一样。真的到面试谁知道那个面试官又会给加什么限制,我是一开始用了开数组的方法做,跟他讲了想法他才说这题要是只能用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++) {. 1point 3acres 璁哄潧
  3.         if (nums[i] > i) {. from: 1point3acres.com/bbs
  4.             swap(strs, i, nums[i]);. visit 1point3acres.com for more.
  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.         }. 1point 3acres 璁哄潧
  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;. 1point 3acres 璁哄潧
            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];.鏈枃鍘熷垱鑷1point3acres璁哄潧
            str[second] = temp;
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
    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);
            }
    }
}


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

使用道具 举报

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;
. 1point3acres.com/bbs
这个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, ...
. 鍥磋鎴戜滑@1point 3 acres
大神...我的呢
回复 支持 反对

使用道具 举报

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
大概思路是这样,比如lz举得第一个例子,从int数组的第0个开始,int[0] = 2, 那么 tmp = string[0], string ...

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-26 02:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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