一亩三分地论坛

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

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

发个G家电面面经,攒个人品

[复制链接] |试试Instant~ |关注本帖
williamwjs 发表于 2015-11-3 13:07:03 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Failfresh grad应届毕业生

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

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

x
哎,面跪了,不过确实发现还有很多需要继续准备的,来年再战吧!

发经历攒个人品:

“AB string” is a string with only letter “a” and letter “b”, e.g. “bbab”. You can flip any letter from “a” to “b” or vice versa. Given a AB string, find out the minimum number of flips you need to convert it to an ascending order.

For example: for “baa”, you can flip it to:
1/ aaa, which requires 1 flips
2/ bbb, which requires 2 flips
3/ aab, which requires 2 flip.


Follow up是如果string是 "ABC string"的话,该怎么实现?


补充内容 (2015-11-3 22:21):
LZ不太会,一起讨论讨论吧

评分

2

查看全部评分

本帖被以下淘专辑推荐:

AndyLiu0429 发表于 2015-11-3 23:58:06 | 显示全部楼层
  1. public static int minFlip(String word) {
  2.         int endA = 0, endB = 0;

  3.         for (char c : word.toCharArray()) {

  4.             int ta = endA, tb = endB;
  5.             int costA = c == 'a' ? 0 : 1;
  6.             endA = ta + costA;
  7.             endB = Math.min(ta, tb) + (1 - costA);
  8.         }

  9.         return Math.min(endA, endB);
  10.     }
复制代码
  1. public static int minFlip2(String word) {
  2.         char[] chars = {'a', 'b', 'c'};
  3.         int[] dp = new int[chars.length]; // generalize to k character

  4.         for (char c : word.toCharArray()) {
  5.             for (int j = dp.length - 1; j >= 0; j--) {
  6.                 dp[j] += c == chars[j] ? 0 : 1;
  7.                 for (int m = 0; m < j; m++) {. 1point3acres.com/bbs
  8.                     dp[j] = Math.min(dp[j], dp[m] + (c == chars[m] ? 0 : 1));
  9.                 }
  10.             }
  11.         }

  12.         return min(dp);
  13.     }
复制代码
回复 支持 3 反对 0

使用道具 举报

小柯西 发表于 2015-11-4 07:05:09 | 显示全部楼层
wip727 发表于 2015-11-4 06:42. From 1point 3acres bbs
一个计数器a[]记录的是序列里b出现的个数,也就是直接把所有b翻成a的解. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
另一个b[]记录的是什么呢? 求大 ...

a[]记录的是,使得 i 位置为 'a' 并且 0...i-1为non-descending,最少需要flip的次数。
b[]记录的也是相同的东西。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
对于某个位置 i, 有以下两种情况:
1. ab == 'a'。. 鍥磋鎴戜滑@1point 3 acres
这个时候我们可以选择,flip或者不flip。. visit 1point3acres.com for more.
如果不flip,并且要使得ab[0..i] valid,那ab[i-1]只能是'a',要让ab[i-1]是'a'的最小代价是a[i-1].
所以a = a[i-1]。
如果我们选择flip, 则ab[i-1]可以是'a'或'b',所以b = min(a[i-1], b[i-1]) + 1。
2. ab == 'b'。.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果不flip,ab[i-1]可以等于'a'或者'b',我们只要选择二者最小的就好,所以b = min(a[i-1], b[i-1])。
如果flip, ab[i-1]只能是"a",所以a = a[i-1] + 1。

评分

3

查看全部评分

回复 支持 2 反对 0

使用道具 举报

maomaoxiong 发表于 2015-11-3 14:26:52 | 显示全部楼层
DP来做吧。N[i] = min(Na[i], Nb[i]);
Na[i] -- string以a为结尾的变换次数,Nb[i] -- string以b为结尾的变换次数。
讨论:
if s[i] == 'a',  Na[i] = Na[i-1], Nb[i] = Nb[i-1]+1;
if s[i] == 'b',  Na[i] = Na[i-1] + 1; Nb[i] = Nb[i-1];

follow up 同理吧。
回复 支持 2 反对 0

使用道具 举报

ljh304 发表于 2015-11-3 19:42:17 | 显示全部楼层
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。
. Waral 鍗氬鏈夋洿澶氭枃绔,讨论 ...

Nb需要考虑Na哦,可以试试baab。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
正确的应该是:
if s == 'a',  Na = Na[i-1]; Nb = min(Nb[i-1]+1, Na[i-1]+1);
if s == 'b',  Na = Na[i-1] + 1; Nb = min(Nb[i-1], Na[i-1]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

时间O(n),空间O(1)。
回复 支持 2 反对 0

使用道具 举报

kayv 发表于 2015-11-3 22:35:14 | 显示全部楼层
好像没那么麻烦吧,对于AB string, min( count[a], count[b] ) 不就行了?. 1point 3acres 璁哄潧
回复 支持 0 反对 2

使用道具 举报

dong882205 发表于 2015-11-3 22:08:36 | 显示全部楼层
额大神轻喷,我是naive地这样想:不论是怎样的输入,结果一定是: i 个 a + (n-i) 个b, i 可以是从0 一直到 n.
如果已经确定i是多少,那么只要把i左边的都变成a,即:数有多少个b; 同理,数右边有多少个a.
那么如何确定i? 就是使得 左边b的个数+右边a个数最小的那个i。
所以只需要 先从左向右扫一遍,得出到这里为止有多少个b, 同理再从右向左扫一遍,得出到这里为止有多少个a, 最后再扫一遍,得到a+b的最小值的i,就是那个位置。.1point3acres缃

补充内容 (2015-11-3 22:15):. more info on 1point3acres.com
这样原题是O(N)time O(N) space,然后follow up的话同理,相当于原来要找一个分割线,现在要找两个,所以有N^2种情况,貌似是O(N^2) O(N)
. From 1point 3acres bbs
补充内容 (2015-11-3 22:19):
啊,罪过,宝贝忆彼岸 同学已经发过了...之前没看.. sorry! 奇怪这贴居然没有说删除功能....
回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-11-3 14:48:47 | 显示全部楼层
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。. From 1point 3acres bbs
讨论 ...

我是这样想的,两个 int array,resA[]和resB[],resA[ i ]表示从0到i都换成a所需要flip的次数,resB[ i ]表示从i到length-1都换成b所需要flip的次数,然后再同时遍历一遍resA和resB,找到resA[ i ] + resB[ i+1]最小的值就是答案。
你的思路我没怎么看懂呀,请问当输入为aaabbb时,你的Na和Nb分别是什么呢?
回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-11-3 13:34:53 | 显示全部楼层
求问follow up的思路呀!!!
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-3 14:50:01 | 显示全部楼层
maomaoxiong 发表于 2015-11-2 22:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。
讨论 ...

厉害,求问怎样得出这个思路的
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-3 15:03:05 | 显示全部楼层
我们用index从1开始,
DP[1] = 0;
DP[2] = str[1]<=str[2]? 0:1;
DP[3] = DP[2] + str[2]<=str[3]? 0:1;
DP = DP[i-1] + str[i-1]<=str? 0:1;

eg: "bb"=0 -> "bba"=1 -> "bbab"=1
eg: "ab"=0 -> "abb"=0 -> "abba"=1
eg: "ab"=0 -> "aba"=1 -> "abab"=1. 1point 3acres 璁哄潧
eg: "ab"=0 -> "aba"=1 -> "abaa"=1

补充内容 (2015-11-3 15:13):
错误了!

补充内容 (2015-11-3 16:06):
无法generalize到ABC String ..反例:abcab -> 1 但应该是2
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-11-4 00:52:44 | 显示全部楼层
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。
讨论 ...

如果输入的已经是 ascending order的话 例如“abb” 最小的flip是0,那这个算法能解决吗
回复 支持 反对

使用道具 举报

epochou 发表于 2015-11-4 04:19:18 | 显示全部楼层
k 指 规定的input 从'a' -> 'a' + k. From 1point 3acres bbs
(1) k = 2, ab
(2) k = 3, abc

public int minimumFlips(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n + 1][k];
        for (int i = 1; i <= s.length(); i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            for (int j = 0; j < k; j++) {. visit 1point3acres.com for more.
                dp[i][j] = n;
                int c = s.charAt(i - 1) - 'a';. From 1point 3acres bbs
                for (int p = 0; p <= j; p++) {.1point3acres缃
                    int prev = dp[i - 1][p];
                    if (j != c) {
                        prev++;
                    }
                    dp[i][j] = Math.min(dp[i][j], prev);. From 1point 3acres bbs
                }
            }
        }
        int min = n;
        for (int num : dp[n]) {. visit 1point3acres.com for more.
            min = Math.min(min, num);
        }
        return min;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-4 05:03:31 | 显示全部楼层
def flip(ab):
        a = [0] * len(ab)
        b = [0] * len(ab). Waral 鍗氬鏈夋洿澶氭枃绔,

        if ab[0] == 'a': b[0] = 1. more info on 1point3acres.com
        else: a[0] = 1

        for i in range(1, len(ab)):
                if ab[i] == 'a':
                        a[i] = a[i-1]
                        b[i] = min(b[i-1], a[i-1]) + 1.鐣欏璁哄潧-涓浜-涓夊垎鍦
                else:
                        b[i] = min(b[i-1], a[i-1])
                        a[i] = a[i-1] + 1.1point3acres缃


        return min(a[-1], b[-1])

O(n) space O(n) time.
其实可以简化到O(1) space..因为注意到,对于位置i,其最优解只与i-1的两个最优解有关。
回复 支持 反对

使用道具 举报

wip727 发表于 2015-11-4 06:42:49 | 显示全部楼层
小柯西 发表于 2015-11-4 05:03
def flip(ab):.鐣欏璁哄潧-涓浜-涓夊垎鍦
        a = [0] * len(ab)
        b = [0] * len(ab)

一个计数器a[]记录的是序列里b出现的个数,也就是直接把所有b翻成a的解
另一个b[]记录的是什么呢? 求大概赐教下思路。。。。谢谢
. visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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