May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

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

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

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

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

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

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

再打个比方,如果输入是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;. From 1point 3acres bbs
  4.                 string temp = cur[i];. visit 1point3acres.com for more.
  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.         }. From 1point 3acres bbs
  6.         for (int i = 0; i < n; i++){
  7.             strs[i] = strs[i].split("#")[1];
  8.         }. 1point3acres.com/bbs
  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){. From 1point 3acres bbs
  5.                 swap(str, j, map[j]);
  6.                 int temp = map[j];
  7.                 map[j] = j;
  8.                 j = temp;
  9.             }
  10.             map[j] = j;. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         }.1point3acres缃
  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].鏈枃鍘熷垱鑷1point3acres璁哄潧
        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. 1point 3acres 璁哄潧
不知道有没有正确理解楼主题意, 但是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. From 1point 3acres bbs
从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 | 显示全部楼层
ariesxiao 发表于 2016-8-17 08:14
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴不是O1 SPACE

不是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) {
  4.             swap(strs, i, nums[i]);
  5.         } else if (nums[i] < i) {
  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.   }

  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) {.1point3acres缃
            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];. 鍥磋鎴戜滑@1point 3 acres
            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);
            }
    }
}


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

使用道具 举报

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) {.1point3acres缃
            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. 鍥磋鎴戜滑@1point 3 acres
大神...我的呢
.鏈枃鍘熷垱鑷1point3acres璁哄潧
并非大神。。。如果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, ...
.1point3acres缃
但我觉得输出就是 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 下一条

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

custom counter

GMT+8, 2017-5-23 20:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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