美国卖车经历分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2085|回复: 14
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
williamwjs 发表于 2015-11-3 13:07:03 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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.
. from: 1point3acres
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"的话,该怎么实现?.本文原创自1point3acres论坛
. 1point3acres

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

评分

参与人数 2大米 +28 收起 理由
samson1215 + 3 感谢分享!
wrj5518 + 25

查看全部评分


上一篇:LiveRamp OA -1102
下一篇:自己总结的Zenefits 家面经

本帖被以下淘专辑推荐:

我的人缘0
AndyLiu0429 发表于 2015-11-3 23:58:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
  1. public static int minFlip(String word) {
  2.         int endA = 0, endB = 0;
  3. . from: 1point3acres
  4.         for (char c : word.toCharArray()) {
  5. . visit 1point3acres for more.
  6.             int ta = endA, tb = endB;. 围观我们@1point 3 acres
  7.             int costA = c == 'a' ? 0 : 1;
  8.             endA = ta + costA;. more info on 1point3acres
  9.             endB = Math.min(ta, tb) + (1 - costA);
  10.         }-google 1point3acres

  11.         return Math.min(endA, endB);
  12.     }
复制代码
  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++) {
  8.                     dp[j] = Math.min(dp[j], dp[m] + (c == chars[m] ? 0 : 1));
    . 牛人云集,一亩三分地
  9.                 }.1point3acres网
  10.             }
  11.         }

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

使用道具 举报

我的人缘0
小柯西 发表于 2015-11-4 07:05:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wip727 发表于 2015-11-4 06:42
一个计数器a[]记录的是序列里b出现的个数,也就是直接把所有b翻成a的解
另一个b[]记录的是什么呢? 求大 ...
. Waral 博客有更多文章,
a[]记录的是,使得 i 位置为 'a' 并且 0...i-1为non-descending,最少需要flip的次数。
b[]记录的也是相同的东西。

对于某个位置 i, 有以下两种情况:. more info on 1point3acres
1. ab == 'a'。
这个时候我们可以选择,flip或者不flip。
如果不flip,并且要使得ab[0..i] valid,那ab[i-1]只能是'a',要让ab[i-1]是'a'的最小代价是a[i-1]. 来源一亩.三分地论坛.
所以a = a[i-1]。. 1point 3acres 论坛
如果我们选择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大米 +5 收起 理由
cwjade + 3 回答的很好!
csmargaret + 1 回答的很好!
wip727 + 1 思路好赞! 谢谢这么清晰的解答

查看全部评分

回复 支持 2 反对 0

使用道具 举报

我的人缘0
maomaoxiong 发表于 2015-11-3 14:26:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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];. from: 1point3acres

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

使用道具 举报

我的人缘0
ljh304 发表于 2015-11-3 19:42:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。. more info on 1point3acres
讨论 ...

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]);-google 1point3acres

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

使用道具 举报

我的人缘0
kayv 发表于 2015-11-3 22:35:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
好像没那么麻烦吧,对于AB string, min( count[a], count[b] ) 不就行了?
回复 支持 0 反对 2

使用道具 举报

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

补充内容 (2015-11-3 22:15):
这样原题是O(N)time O(N) space,然后follow up的话同理,相当于原来要找一个分割线,现在要找两个,所以有N^2种情况,貌似是O(N^2) O(N)

补充内容 (2015-11-3 22:19):
啊,罪过,宝贝忆彼岸 同学已经发过了...之前没看.. sorry! 奇怪这贴居然没有说删除功能....
回复 支持 1 反对 0

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-11-3 14:48:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。
讨论 ...

我是这样想的,两个 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分别是什么呢?
Mobile Apps Category (English)728x90
回复 支持 1 反对 0

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-11-3 13:34:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问follow up的思路呀!!!
回复 支持 反对

使用道具 举报

我的人缘0
eko910817 发表于 2015-11-3 14:50:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maomaoxiong 发表于 2015-11-2 22:26
DP来做吧。N = min(Na, Nb);. Waral 博客有更多文章,
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。 来源一亩.三分地论坛.
讨论 ...

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

使用道具 举报

我的人缘0
marthew777 发表于 2015-11-3 15:03:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我们用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. more info on 1point3acres
eg: "ab"=0 -> "aba"=1 -> "abaa"=1
. visit 1point3acres for more.
补充内容 (2015-11-3 15:13):
错误了!

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

使用道具 举报

我的人缘0
DJ963 发表于 2015-11-4 00:52:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maomaoxiong 发表于 2015-11-3 14:26
DP来做吧。N = min(Na, Nb);
Na -- string以a为结尾的变换次数,Nb -- string以b为结尾的变换次数。. From 1point 3acres bbs
讨论 ...

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

使用道具 举报

我的人缘0
epochou 发表于 2015-11-4 04:19:18 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
k 指 规定的input 从'a' -> 'a' + k
(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];.1point3acres网
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = n;
                int c = s.charAt(i - 1) - 'a';
                for (int p = 0; p <= j; p++) {
                    int prev = dp[i - 1][p];
                    if (j != c) {. more info on 1point3acres
                        prev++;
                    }
                    dp[i][j] = Math.min(dp[i][j], prev);
                }
            }. 留学申请论坛-一亩三分地
        }
        int min = n;
        for (int num : dp[n]) {
            min = Math.min(min, num);
        }
        return min;
    }
回复 支持 反对

使用道具 举报

我的人缘0
小柯西 发表于 2015-11-4 05:03:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
def flip(ab):
        a = [0] * len(ab).本文原创自1point3acres论坛
        b = [0] * len(ab)

        if ab[0] == 'a': b[0] = 1
        else: a[0] = 1

        for i in range(1, len(ab)):
                if ab[i] == 'a':-google 1point3acres
                        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.. From 1point 3acres bbs
其实可以简化到O(1) space..因为注意到,对于位置i,其最优解只与i-1的两个最优解有关。
回复 支持 反对

使用道具 举报

我的人缘0
wip727 发表于 2015-11-4 06:42:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
小柯西 发表于 2015-11-4 05:03
def flip(ab):
        a = [0] * len(ab)
        b = [0] * len(ab)
. from: 1point3acres
一个计数器a[]记录的是序列里b出现的个数,也就是直接把所有b翻成a的解
另一个b[]记录的是什么呢? 求大概赐教下思路。。。。谢谢


回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-21 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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