近期论坛无法登录的解决方案


一亩三分地论坛

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

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

FaceBook Onsite

[复制链接] |试试Instant~ |关注本帖
菡萏之默 发表于 2014-10-13 00:33:57 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Other

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

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

x
跑去脸谱家面试。搜集不少题目现在列下
1:print all path from root to leaf
2:  power set
3:  given a list of words, find palindom pairs.鐣欏璁哄潧-涓浜-涓夊垎鍦
4:  implement
还有一些简单题估计人家随便找的,祝好运。.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

6

查看全部评分

在希望的田野上 发表于 2015-2-8 07:48:58 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
cosym 发表于 2015-1-20 02:17
这题怎么去掉重复的结果呢?

.鏈枃鍘熷垱鑷1point3acres璁哄潧在 abc, cba 的情况下,有重复是因为枚举一个 word 的回文划分时,从左到右和右到左都考虑 empty string as a padlindrome, 所以如果只考虑一个 empty 回文,就不会有重复了
如 abc, cba
1. 枚举 abc, left->right {empty, abc}, {a, bc}, 发现只有{empty, abc}这种划分,能找到 reverse(abc)=cba 在字典里,顾找到一对 abccba; righ->left (不再考虑empty as palindrome){ab, c}, 没找到 reverse(ab)=ba 在字典中,done
2. 枚举 cba, left->right {empty, cba}, {c, ba}, 发现 reverse(cba)=abc 在字典中,于是找到一对:cbaabc; right->left,同上,无 reverse(cb)=bc 存在字典
所以最终结果是2对,{abc,cba} {cba,abc} 无重复
回复 支持 2 反对 0

使用道具 举报

averillzheng 发表于 2014-11-6 03:27:20 | 显示全部楼层
关注一亩三分地微博:
Warald
palindrome pair, 贴一个我写的很撮的程序:.1point3acres缃
抛砖引玉:求指点。
  1. import java.util.HashMap;
  2. import java.util.List;. Waral 鍗氬鏈夋洿澶氭枃绔,
  3. import java.util.ArrayList;
  4. import java.util.Map;
  5. import java.util.Iterator;
  6. import java.util.Set;
  7. import java.util.HashSet;
  8. . 鍥磋鎴戜滑@1point 3 acres
  9. public class PalindromePairs { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.         public static List<String> palinPair(String[] arr) {
  11.                 List<String> palin = new ArrayList<String>();
  12.                 if(arr == null || arr.length == 1)        return palin;
  13.                 TreeNodeInTrie root = buildTree(arr);                               
  14.                 for(String s : arr) {
  15.                         String rev = (new StringBuffer(s)).reverse().toString();
  16.                         TreeNodeInTrie curr = root;
  17.                         StringBuffer sb = new StringBuffer();
  18.                         int i = 0;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                         boolean cont = true;
  20.                         Set<String> finished = new HashSet<String>();
  21.                         finished.add(s);
  22.                         for(; i < rev.length(); ++i) {
  23.                                 if(curr.isWord && isPalindrome(s, i, rev.length() - 1)) {. more info on 1point3acres.com
  24.                                         if(finished.add(sb.toString()))
  25.                                                 palin.add(sb.toString() + ":"+s);
  26.                                 }
  27.                                
  28.                                 if(curr.child != null && curr.child.containsKey(rev.charAt(i))) {
  29.                                         curr = curr.child.get(rev.charAt(i));
  30.                                         sb.append(rev.charAt(i));
  31.                                 }else{
  32.                                         cont = false;
  33.                                         break;
  34.                                 }
  35.                         }
  36.                         if(cont) {
  37.                                 if(i < rev.length()){ //curr is a leaf of the trie tree
  38.                                         if(isPalindrome(rev, i, rev.length() - 1)) {
  39.                                                 if(finished.add(sb.toString()))
  40.                                                         palin.add(sb.toString() + ":"+s);
  41.                                         }
  42.                                 }else{ //curr is not a leaf of the trie tree
  43.                                         if(curr.isWord) {
  44.                                                 if(finished.add(sb.toString()))
  45.                                                         palin.add(sb.toString() + ":"+s);
  46.                                         }                                       
  47.                                         if(curr.child != null){
  48.                                                 List<String> rem = new ArrayList<String>();
  49.                                                 dfs(curr, rem, new StringBuffer());
  50.                                                 for(String s1: rem) {
  51.                                                         if(isPalindrome(s1,0, s1.length() - 1)) {
  52.                                                                 if(finished.add(sb.toString() + s1))
  53.                                                                         palin.add(sb.toString()+s1+":"+ s);
  54.                                                         }. from: 1point3acres.com/bbs
  55.                                                 }
  56.                                         }       
  57.                                 }
  58.                         }
  59.                 }
  60.                
  61.                 return palin;
  62.         }
  63.        
  64.         private static void dfs(TreeNodeInTrie curr, List<String> rem, StringBuffer sb){. From 1point 3acres bbs
  65.                 if(curr.child == null) {                       
  66.                         return;. 1point 3acres 璁哄潧
  67.                 }               
  68.                 Iterator<Character> its = curr.child.keySet().iterator();
  69.                 while(its.hasNext()){
  70.                         char ch= its.next();
  71.                         sb.append(ch);
  72.                         if(curr.child.get(ch).isWord)         rem.add(new String(sb));
  73.                         dfs(curr.child.get(ch), rem, sb);                        . more info on 1point3acres.com
  74.                         sb.deleteCharAt(sb.length() - 1);
  75.                 }               
    . visit 1point3acres.com for more.
  76.         }. visit 1point3acres.com for more.
  77.        
  78.         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  79.         private static boolean isPalindrome(String s, int i, int j) {
  80.                 if(i >= j)        return true;
  81.                 while(i < j) {
  82.                         if(s.charAt(i) != s.charAt(j))                return false;. 1point3acres.com/bbs
  83.                         ++i;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  84.                         --j;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  85.                 }
  86.                 return true;
  87.         }
  88.        
  89.         private static TreeNodeInTrie buildTree(String[] arr){
  90.                 TreeNodeInTrie root = new TreeNodeInTrie(' ', false);
  91.                 for(String s : arr) {
  92.                         int len = s.length();
  93.                         TreeNodeInTrie curr = root;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  94.                         for(int i = 0; i < len; ++i) {
  95.                                 if(curr.child == null){         //child is empty, create child and a new TreeNodeInTrie
  96.                                         Map<Character, TreeNodeInTrie> child = new HashMap<Character, TreeNodeInTrie>();                                       
  97.                                         curr.child = child;
  98.                                 }
  99.                                
  100.                                 if(curr.child.containsKey(s.charAt(i))) {        //if the TreeNodeInTrie exists;
  101.                                         if(i == len - 1)                curr.child.get(s.charAt(i)).isWord = true;
  102.                                 }else{                 //if the TreeNodeInTrie does not exists
  103.                                         curr.child.put(s.charAt(i), new TreeNodeInTrie(s.charAt(i), i == len - 1)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  104.                                 }                        . From 1point 3acres bbs
  105.                                 curr = curr.child.get(s.charAt(i));          // recursively
  106.                         }
  107.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  108.                 return root;
  109.         }
  110.        
  111.        
  112.         public static void main(String[] args) {-google 1point3acres
  113.                 String[] arr = new String[] {"a", "aa", "aaa"};. visit 1point3acres.com for more.
  114.                 System.out.println(palinPair(arr));. from: 1point3acres.com/bbs
  115.                 String[] arr1 = new String[] {"shit", "tihsa"};
  116.                 System.out.println(palinPair(arr1));
  117.         }
  118. }
  119. class TreeNodeInTrie {. 1point3acres.com/bbs
  120.         char c;
  121.         Map<Character, TreeNodeInTrie> child;-google 1point3acres
  122.         boolean isWord; . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  123.         TreeNodeInTrie(char c, boolean isWord){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  124.                 this.c = c;
  125.                 this.isWord = isWord;
  126.         }
  127. }
复制代码

补充内容 (2014-11-6 03:28):
给的两个例子跑出来的结果是:
[aa:a, aaa:a, a:aa, aaa:aa, a:aaa, aa:aaa]
[tihsa:shit]
回复 支持 1 反对 0

使用道具 举报

moophis 发表于 2014-10-15 09:09:16 | 显示全部楼层
第三题可以把每个word劈成两半,如果一半自身是palindrome并且另一半的reverse过来的词在字典里存在,就找到了一个这样pair,找出所有这样的可能性就行了。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

jason51122 发表于 2014-10-23 10:53:55 | 显示全部楼层
楼主能麻烦解释下什么是palindrome pairs吗 谢谢了
回复 支持 1 反对 0

使用道具 举报

shinichish 发表于 2014-10-13 00:42:15 | 显示全部楼层
第二题是快速幂吗?第四题实现啥?
回复 支持 反对

使用道具 举报

 楼主| 菡萏之默 发表于 2014-10-13 00:57:24 | 显示全部楼层
不知道为啥写不上,implement BufferedReader
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-13 01:03:11 | 显示全部楼层
菡萏之默 发表于 2014-10-12 11:57
不知道为啥写不上,implement BufferedReader
. visit 1point3acres.com for more.
要实现啥功能? 这个bufferedreader.
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2014-10-13 03:35:29 | 显示全部楼层
请问没有设计题吗lz?
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-10-13 06:36:55 | 显示全部楼层
菡萏之默 发表于 2014-10-13 00:57. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不知道为啥写不上,implement BufferedReader

BufferedReader。。。?我Google下
回复 支持 反对

使用道具 举报

linuxcoder 发表于 2014-10-13 10:23:22 | 显示全部楼层
问一下楼主一共几轮呀
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-10-13 14:10:02 | 显示全部楼层
问一下楼主第三题是需要用Trie吗?
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-10-13 14:10:37 | 显示全部楼层
北美农民 发表于 2014-10-13 01:03
要实现啥功能? 这个bufferedreader.

同关注这个BufferedReader
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-10-13 14:18:34 | 显示全部楼层
lhh_NJU 发表于 2014-10-13 14:10.鏈枃鍘熷垱鑷1point3acres璁哄潧
问一下楼主第三题是需要用Trie吗?

.1point3acres缃第三题应该是经典的anagrams吧 cc150好像有 lc上一定有 常规解法是用hashmap来做
回复 支持 反对

使用道具 举报

 楼主| 菡萏之默 发表于 2014-10-14 00:57:40 | 显示全部楼层
常规可能是hashmap,但是Pinterest 对这种题目希望用trie。 我觉得hashtable 和 trie 都可以吧。
回复 支持 反对

使用道具 举报

达达主义 发表于 2014-10-14 14:18:42 | 显示全部楼层
请问power set 是不是 leetcode里面的subset
回复 支持 反对

使用道具 举报

geng77 发表于 2014-10-15 10:30:40 | 显示全部楼层
收下了,楼主好运
回复 支持 反对

使用道具 举报

geng77 发表于 2014-10-15 10:30:47 | 显示全部楼层
收下了,楼主好运
回复 支持 反对

使用道具 举报

michaelsoeng 发表于 2014-10-16 05:41:43 | 显示全部楼层
buffredreader 从什么方向怎么实现啊?
楼主可以说详细一点吗。谢谢。
回复 支持 反对

使用道具 举报

09832700d 发表于 2014-10-22 05:10:36 | 显示全部楼层
用Trie要怎么判断?root到path和path到root一样得pair?不太好找吧
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-10-23 10:46:51 | 显示全部楼层
moophis 发表于 2014-10-15 09:09
第三题可以把每个word劈成两半,如果一半自身是palindrome并且另一半的reverse过来的词在字典里存在,就找 ...

能麻烦详细说一下这个题目吗 我题目还是不太理解 Thanks
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-30 00:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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