一亩三分地论坛

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

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

facebook 电面

[复制链接] |试试Instant~ |关注本帖
andy198423 发表于 2014-10-29 23:31:52 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Fail

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

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

x
一道很简单的题,结果自己脑抽,绕进去了
string 有多少palindrome substring。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
exp: 'aba' 返回4 , 'abba' 返回6

评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
干.什么 发表于 2015-3-25 07:13:32 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
干.什么 发表于 2015-3-25 07:12
public static int partition(String s) {
        int count = 0;
        // single char is palin ...

哎呀忘记格式啦!
  1.     public static int partition(String s) {
  2.         int count = 0;
  3.         // single char is palindrome
  4.         for (int i = 0; i < s.length(); i++) count++;. 鍥磋鎴戜滑@1point 3 acres
  5.         for (int i = 1; i < s.length(); i++) {. 鍥磋鎴戜滑@1point 3 acres
  6.             // even position
  7.             for (int l = i - 1, r = i; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {. from: 1point3acres.com/bbs
  8.                 count++;
  9.             }
  10.             // odd
  11.             for (int l = i - 1, r = i + 1; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
  12.                 count++;
  13.             }
  14.         }
  15.         return count;
  16.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

francisyang 发表于 2014-10-30 03:08:05 | 显示全部楼层
关注一亩三分地微博:
Warald
这个题我以前自己做过,不过只有O(n^2)的方法,不过代码很少,想法也比较直接。:check所有的连续substring 是否是palindrome ,  存进hashmap,最后输出map的key的数量。. visit 1point3acres.com for more.
代码就不贴了。
回复 支持 0 反对 1

使用道具 举报

e5399014 发表于 2014-10-31 01:49:14 | 显示全部楼层
根据输入输出,是不需要检查重复的, 'abba' 返回6。 所以用dp来做,代码如下:
public class Solution{

public int palindrome(String s) {
    if (s.length()==0) return 0;. from: 1point3acres.com/bbs
    if (s.length()==1) return 1;

    int num=0;
    //initialize the table
    int[][] table= new int[s.length()][s.length()];
    for (int i=0; i<s.length(); i++) {
        table[i][i]=1;
        num+=1;
    }
    for (int i=0; i<s.length()-1; i++) {
        if (s.charAt(i)==s.charAt(i+1)){
            table[i][i+1]=1;
            num+=1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }else{
            table[i][i+1]=0;
        }

    }

    // looping

    for (int len=3; len<=s.length(); len++) {
        for (int i=0; i<=s.length()-len; i++) {
            if (s.charAt(i)==s.charAt(i+len-1) && table[i+1][i+len-2]==1){
                table[i][i+len-1]=1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                num+=1;
            }else{
                table[i][i+len-1]=0;  
            }
        }
    }
. 1point 3acres 璁哄潧
    return num;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

}

}

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

byrlhb 发表于 2014-10-30 00:13:40 | 显示全部楼层
谢楼主分享,继续加油了!
回复 支持 反对

使用道具 举报

rengokantai 发表于 2014-10-30 00:25:32 | 显示全部楼层
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家的面试题lc里的不少。
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-30 00:36:29 | 显示全部楼层
rengokantai 发表于 2014-10-30 00:25
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家 ...

跟leetcode还是不一样的
回复 支持 反对

使用道具 举报

 楼主| andy198423 发表于 2014-10-30 01:00:23 | 显示全部楼层
rengokantai 发表于 2014-10-30 00:25
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家 ...

这个不是原题,我开始也觉得像原题,所以一边扯一边找,然后自己就乱了
其实还不如直接自己分析,自己解,题也不难
所以我觉得大家还是别太依赖原题,思路最重要
回复 支持 反对

使用道具 举报

frozenplay 发表于 2014-10-30 23:33:37 | 显示全部楼层
francisyang 发表于 2014-10-30 03:08
这个题我以前自己做过,不过只有O(n^2)的方法,不过代码很少,想法也比较直接。:check所有的连续substring ...

lc原题不是可以dp优化么,因为一个长的String是palindrome,那就暗示start+1, end-1也是. more info on 1point3acres.com
最变态的是一种Manacher's algorithm,不过面试应该写不出来
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2014-10-30 23:48:04 | 显示全部楼层
恩,感觉和ON回文方法类似,这题应该还是ON的最优解吧,只是判重的话多个hashtable罢了
回复 支持 反对

使用道具 举报

Neal_kks 发表于 2014-11-24 17:31:44 | 显示全部楼层
我一开始理解错题目了,居然YY成跟子序列差不多的那种情况,感觉好复杂。。原题还是挺好写的,贴一下我的c++代码,大家看看有没有bug。
  1. #include <iostream>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2. #include <string>
  3. using namespace std;

  4. const int MAX = 1002;

  5. int dp[MAX][MAX];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6. . more info on 1point3acres.com
  7. void solve(string &s){
  8.     int len = s.length();
  9.     for(int i=0;i<len;++i){
  10.         for(int j=0;j<len;++j){
  11.             dp[i][j] = i>=j?1:0;
  12.         }
  13.     }
  14.     int res = len;
  15.     for(int k=2;k<=len;++k){
  16.         for(int i=0;i<len;++i){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.             int j = i+k-1;
  18.             if(j>=len)  break;
  19.             if(s[i] == s[j] && dp[i+1][j-1] == 1){
  20.                 dp[i][j] = 1;
  21.                 ++res;
  22.             }
  23.             
  24.         }
  25.     }
  26.     printf("%d\n", res);.1point3acres缃
  27. }.1point3acres缃

  28. int main(){
  29.     string s;
  30.     while(cin>>s){. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.         solve(s);
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.     }
  33. }. 1point 3acres 璁哄潧
复制代码
回复 支持 反对

使用道具 举报

GLambda 发表于 2014-11-24 18:58:42 | 显示全部楼层
直接枚举对称中点O(n),然后枚举长度O(n),计数就行,也是O(n^2)的。
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2014-11-24 22:20:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

njuprincerain 发表于 2014-11-24 22:48:08 | 显示全部楼层
最近也有同学被问这题, 要求o(1)空间复杂度
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-11-25 00:27:38 | 显示全部楼层
njuprincerain 发表于 2014-11-24 22:48
最近也有同学被问这题, 要求o(1)空间复杂度
. 1point3acres.com/bbs
O(1)空间就是楼上说的枚举吧?不用DP的那种O(N^2)的算法
回复 支持 反对

使用道具 举报

njuprincerain 发表于 2014-11-25 00:30:38 | 显示全部楼层
是的, 因为用了dp然后悲剧
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-11-25 08:11:51 | 显示全部楼层
这道题你用DP还不如不用,使用DP的话是严格O(n^2)的复杂度,而使用枚举的话严格复杂度是O(nk),其中k是最长回文的回文半径。这样可以达到O(1)空间
回复 支持 反对

使用道具 举报

lilihao2014 发表于 2014-11-26 02:36:20 | 显示全部楼层
为什么aba是4,abba是6????能枚举一下吗
回复 支持 反对

使用道具 举报

dragonmigo 发表于 2014-11-26 04:23:10 | 显示全部楼层
lilihao2014 发表于 2014-11-26 02:36. From 1point 3acres bbs
为什么aba是4,abba是6????能枚举一下吗

aba:
{a, b, a, aba}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

abba:
{a, b, b, a, bb, abba}

每一个single character 也是一个 palindrome string
回复 支持 反对

使用道具 举报

lilihao2014 发表于 2014-11-26 23:13:35 | 显示全部楼层
. 鍥磋鎴戜滑@1point 3 acres
懂了懂了!O(∩_∩)O谢谢
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-18 07:36:08 | 显示全部楼层
这叫做DP么?。。。. visit 1point3acres.com for more.
很直接的思想做一下。这个题目的变形题https://leetcode.com/problems/longest-palindromic-substring/. Waral 鍗氬鏈夋洿澶氭枃绔,
设定一个boolean[j]代表i~j是否是一个回文。最后数一下boolean数组里面的true的个数就ok了。
快速的方法是 如果我们已经知道 i-1, j-1是一个回文,并s.charAt(i) == s.charAt(j)的话 那么i j 就是一个回文了。. Waral 鍗氬鏈夋洿澶氭枃绔,
举个栗子,abba, 已经处理了bb了,存在了flag[1][2], 那么flag[0][3] = flag[1][2] && ('a' == 'a') = true;
所以第一步初始化1和相邻位置
然后枚举长度,依次递推。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-4-30 19:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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