📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 菡萏之默
跳转到指定楼层
上一主题 下一主题
收起左侧

FaceBook Onsite

🔗
22691482 2014-11-5 06:28:01 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
22691482 2014-11-5 06:29:00 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
hno3 2014-11-5 07:03:55 | 只看该作者
全局:
来学习下,trie一般怎么实现啊 可以直接调用?
回复

使用道具 举报

🔗
adiggo 2014-11-5 08:48:04 | 只看该作者
全局:
菡萏之默 发表于 2014-10-14 00:57
常规可能是hashmap,但是Pinterest 对这种题目希望用trie。 我觉得hashtable 和 trie 都可以吧。

感觉这个题用hashmap蛮好的。
回复

使用道具 举报

🔗
adiggo 2014-11-5 08:53:49 | 只看该作者
全局:
csgtc 发表于 2014-10-23 11:09
第三题是O(Kn),linear time但是基数很大。。 fb的on campus也有这题,正解是把每个词拆成两半,前一半reve ...

真样做,也是把所有的切开的词放进hashmap么, 另外如果length是odd, 那又得加一些条件判断了。
回复

使用道具 举报

🔗
jby1797 2014-11-5 09:13:52 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
moophis 2014-11-5 12:14:56 | 只看该作者
全局:
22691482 发表于 2014-11-5 06:28
你好, 关于思路把词分开还是有不懂的地方。

給出word1, word2, ... wordn

你理解错了,是word1和word2 concatenate以后的词自身是palindrome
回复

使用道具 举报

🔗
22691482 2014-11-5 13:41:47 | 只看该作者
全局:
moophis 发表于 2014-11-5 12:14
你理解错了,是word1和word2 concatenate以后的词自身是palindrome

对啊。。。 word1+word2 是回文的, 那么  word1 = reverse(word2)..  是哪一步理解错了呢?
回复

使用道具 举报

🔗
averillzheng 2014-11-6 01:41:57 | 只看该作者
全局:
22691482 发表于 2014-11-5 13:41
对啊。。。 word1+word2 是回文的, 那么  word1 = reverse(word2)..  是哪一步理解错了呢?

words 的长度不一样。
回复

使用道具 举报

🔗
averillzheng 2014-11-6 03:27:20 | 只看该作者
全局:
palindrome pair, 贴一个我写的很撮的程序:
抛砖引玉:求指点。
  1. import java.util.HashMap;
  2. import java.util.List;
  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. public class PalindromePairs {
  9.         public static List<String> palinPair(String[] arr) {
  10.                 List<String> palin = new ArrayList<String>();
  11.                 if(arr == null || arr.length == 1)        return palin;
  12.                 TreeNodeInTrie root = buildTree(arr);                               
  13.                 for(String s : arr) {
  14.                         String rev = (new StringBuffer(s)).reverse().toString();
  15.                         TreeNodeInTrie curr = root;
  16.                         StringBuffer sb = new StringBuffer();
  17.                         int i = 0;
  18.                         boolean cont = true;
  19.                         Set<String> finished = new HashSet<String>();
  20.                         finished.add(s);
  21.                         for(; i < rev.length(); ++i) {
  22.                                 if(curr.isWord && isPalindrome(s, i, rev.length() - 1)) {
  23.                                         if(finished.add(sb.toString()))
  24.                                                 palin.add(sb.toString() + ":"+s);
  25.                                 }
  26.                                
  27.                                 if(curr.child != null && curr.child.containsKey(rev.charAt(i))) {
  28.                                         curr = curr.child.get(rev.charAt(i));
  29.                                         sb.append(rev.charAt(i));
  30.                                 }else{
  31.                                         cont = false;
  32.                                         break;
  33.                                 }
  34.                         }
  35.                         if(cont) {
  36.                                 if(i < rev.length()){ //curr is a leaf of the trie tree
  37.                                         if(isPalindrome(rev, i, rev.length() - 1)) {
  38.                                                 if(finished.add(sb.toString()))
  39.                                                         palin.add(sb.toString() + ":"+s);
  40.                                         }
  41.                                 }else{ //curr is not a leaf of the trie tree
  42.                                         if(curr.isWord) {
  43.                                                 if(finished.add(sb.toString()))
  44.                                                         palin.add(sb.toString() + ":"+s);
  45.                                         }                                       
  46.                                         if(curr.child != null){
  47.                                                 List<String> rem = new ArrayList<String>();
  48.                                                 dfs(curr, rem, new StringBuffer());
  49.                                                 for(String s1: rem) {
  50.                                                         if(isPalindrome(s1,0, s1.length() - 1)) {
  51.                                                                 if(finished.add(sb.toString() + s1))
  52.                                                                         palin.add(sb.toString()+s1+":"+ s);
  53.                                                         }
  54.                                                 }
  55.                                         }       
  56.                                 }
  57.                         }
  58.                 }
  59.                
  60.                 return palin;
  61.         }
  62.        
  63.         private static void dfs(TreeNodeInTrie curr, List<String> rem, StringBuffer sb){
  64.                 if(curr.child == null) {                       
  65.                         return;
  66.                 }               
  67.                 Iterator<Character> its = curr.child.keySet().iterator();
  68.                 while(its.hasNext()){
  69.                         char ch= its.next();
  70.                         sb.append(ch);
  71.                         if(curr.child.get(ch).isWord)         rem.add(new String(sb));
  72.                         dfs(curr.child.get(ch), rem, sb);                       
  73.                         sb.deleteCharAt(sb.length() - 1);
  74.                 }               
  75.         }
  76.        
  77.        
  78.         private static boolean isPalindrome(String s, int i, int j) {
  79.                 if(i >= j)        return true;
  80.                 while(i < j) {
  81.                         if(s.charAt(i) != s.charAt(j))                return false;
  82.                         ++i;
  83.                         --j;
  84.                 }
  85.                 return true;
  86.         }
  87.        
  88.         private static TreeNodeInTrie buildTree(String[] arr){
  89.                 TreeNodeInTrie root = new TreeNodeInTrie(' ', false);
  90.                 for(String s : arr) {
  91.                         int len = s.length();
  92.                         TreeNodeInTrie curr = root;
  93.                         for(int i = 0; i < len; ++i) {
  94.                                 if(curr.child == null){         //child is empty, create child and a new TreeNodeInTrie
  95.                                         Map<Character, TreeNodeInTrie> child = new HashMap<Character, TreeNodeInTrie>();                                       
  96.                                         curr.child = child;
  97.                                 }
  98.                                
  99.                                 if(curr.child.containsKey(s.charAt(i))) {        //if the TreeNodeInTrie exists;
  100.                                         if(i == len - 1)                curr.child.get(s.charAt(i)).isWord = true;
  101.                                 }else{                 //if the TreeNodeInTrie does not exists
  102.                                         curr.child.put(s.charAt(i), new TreeNodeInTrie(s.charAt(i), i == len - 1));
  103.                                 }                       
  104.                                 curr = curr.child.get(s.charAt(i));          // recursively
  105.                         }
  106.                 }
  107.                 return root;
  108.         }
  109.        
  110.        
  111.         public static void main(String[] args) {
  112.                 String[] arr = new String[] {"a", "aa", "aaa"};
  113.                 System.out.println(palinPair(arr));
  114.                 String[] arr1 = new String[] {"shit", "tihsa"};
  115.                 System.out.println(palinPair(arr1));
  116.         }
  117. }
  118. class TreeNodeInTrie {
  119.         char c;
  120.         Map<Character, TreeNodeInTrie> child;
  121.         boolean isWord;
  122.         TreeNodeInTrie(char c, boolean isWord){
  123.                 this.c = c;
  124.                 this.isWord = isWord;
  125.         }
  126. }
复制代码

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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