San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5962|回复: 30
收起左侧

facebook 电面

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

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

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

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

x
一道很简单的题,结果自己脑抽,绕进去了
string 有多少palindrome substring。
exp: 'aba' 返回4 , 'abba' 返回6

评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
干.什么 发表于 2015-3-25 07:13:32 | 显示全部楼层
干.什么 发表于 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++;. 牛人云集,一亩三分地
  5.         for (int i = 1; i < s.length(); i++) {. 1point3acres
  6.             // even position. from: 1point3acres
  7.             for (int l = i - 1, r = i; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
  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.         }. Waral 博客有更多文章,
  15.         return count;
  16.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

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

public int palindrome(String s) {
    if (s.length()==0) return 0;
    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;
        }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;
                num+=1;
            }else{
                table[i][i+len-1]=0;  
            }
        }
    }

    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。他家 ...

这个不是原题,我开始也觉得像原题,所以一边扯一边找,然后自己就乱了. Waral 博客有更多文章,
其实还不如直接自己分析,自己解,题也不难. Waral 博客有更多文章,
所以我觉得大家还是别太依赖原题,思路最重要
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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也是.本文原创自1point3acres论坛
最变态的是一种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];

  6. void solve(string &s){
  7.     int len = s.length();
  8.     for(int i=0;i<len;++i){
  9.         for(int j=0;j<len;++j){
    . Waral 博客有更多文章,
  10.             dp[i][j] = i>=j?1:0;
  11.         }. From 1point 3acres bbs
  12.     }. 1point3acres
  13.     int res = len;
  14.     for(int k=2;k<=len;++k){
  15.         for(int i=0;i<len;++i){
  16.             int j = i+k-1;
  17.             if(j>=len)  break;
  18.             if(s[i] == s[j] && dp[i+1][j-1] == 1){
  19.                 dp[i][j] = 1;
  20.                 ++res;
  21.             }
  22.             
  23.         }
  24.     }
  25.     printf("%d\n", res);
    . 一亩-三分-地,独家发布
  26. }

  27. int main(){. from: 1point3acres
  28.     string s;. Waral 博客有更多文章,
  29.     while(cin>>s){
  30.         solve(s);.本文原创自1point3acres论坛
  31.     }
  32. }. 1point3acres
复制代码
回复 支持 反对

使用道具 举报

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)空间复杂度
. more info on 1point3acres
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. visit 1point3acres for more.
为什么aba是4,abba是6????能枚举一下吗

aba:
{a, b, a, aba}

abba:.1point3acres网
{a, b, b, a, bb, abba}

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

使用道具 举报

lilihao2014 发表于 2014-11-26 23:13:35 | 显示全部楼层

懂了懂了!O(∩_∩)O谢谢
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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