bb 电面跪经

说一个刚刚面完的bb电面，感觉是个亚裔女的声音，先简单介绍了一下实习情况和一个项目，接着就马上开始做题，第一题是count unique of pairs of two s

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主用的dp，刚开始写的有重复的长度为2 的dp，后来加长长度为1的结果， 但是没有去重；时间本来就超了；估计是挂了

loserloser 发表于 2017-10-28 05:25
能给个用hashmap的完整解法吗

public static int find(int target, int[] nums) {
                if (nums == null || nums.length == 0) {
                        return 0;
                }
                Set<Integer> set = new HashSet<>();
                Map<Integer, Integer> map = new HashMap<>();
                boolean sameNum = false;
                for (int i: nums) {
                        if (set.contains(target - i)) {
                                if (i * 2 == target) {
                                        sameNum = true;
                                }
                                if (!map.containsKey(i)) {
                                        map.put(i, target - i);
                                        map.put(target -  i, i);
                                }
                        }
                        set.add(i);
                }
                return sameNum? (map.size() + 1) / 2: map.size() / 2;
        }

1. public static int countSubstrings(String s) {
   
2.         if (s.isEmpty()) return 0;
   
3.         // because we won't cover the last letter
   
4.         Set<String> set = new HashSet<>();
   
5.         for (int i = 0; i < s.length() - 1; i++) {
   
6.             checkByPos(s, i, i, set);
   
7.             checkByPos(s, i, i + 1, set);
   
8.         }
   
9.         if (!set.contains(s.substring(s.length() - 1))) {
   
10.          set.add(s.substring(s.length() - 1));
    
11.         }
    
12.         return set.size();
    
13.     }
    
14.    
    
15.     private static void checkByPos(String s, int i, int j, Set<String> set) {
    
16.         while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
    
17.             if (set.contains(s.substring(i, j + 1))) {
    
18.              i--;
    
19.                 j++;
    
20.                 continue;
    
21.             }
    
22.             else {
    
23.              set.add(s.substring(i, j + 1));
    
24.              i--;
    
25.                 j++;
    
26.             }
    
27.         }
    
28.     }

复制代码

其实不用dp反而简单多了

FF-Ti 发表于 2017-10-28 05:37
public static int find(int target, int[] nums) {
                if (nums == null || nums.length == 0) {
                        re ...

这是我写的

    private static int findPairs(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();

        for (int num : nums) {
            if (set.contains(target - num)) {
                if (!res.contains(num) && !res.contains(target - num)) {
                    res.add(num);
                }
            } else {
                set.add(num);
            }
        }
        return res.size();
    }

用hashmap的话，先用set保存数，然后把两个数分别当成2对key value pair存进map里，然后最后取map.size() / 2. 这样行吗.
比如target = 4， 碰到（1，3），就把（1，3）（3， 1）存进map里。如果碰到2，2这种情况，就把（2，2）存进去，但是设一个boolean值表示最后算结果的时候要加一个数再除2.

FF-Ti 发表于 2017-10-28 05:16
用hashmap的话，先用set保存数，然后把两个数分别当成2对key value pair存进map里，然后最后取map.size() / ...

要想做肯定可以，就是麻烦多了，有duplicate的感觉还是直接sort再跳过就好

第三题是twitter oa 我是这么做的
public static int countSubstrings(String s) {
            HashSet<String> set = new HashSet<>();
        for(int i = 0;i<s.length();i++){
            helper(s, i, i, set);
            helper(s,i,i+1, set);
        }
        return set.size();
    }
    public static void helper(String s, int left, int right, HashSet<String> set){
        while(left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                set.add(s.substring(left, right + 1));
            left--;
            right++;
        }
    }

FF-Ti 发表于 2017-10-28 05:20
第三题是twitter oa 我是这么做的
public static int countSubstrings(String s) {
            HashSet set = n ...

跟我后来想的一样的，当时太紧张了

loserloser 发表于 2017-10-28 05:18
要想做肯定可以，就是麻烦多了，有duplicate的感觉还是直接sort再跳过就好

一个nlogn 和o（1），一个是o（n） 和o（n）。看面试官想要哪种把

做了三道题应该问题不大

talentednew 发表于 2017-10-28 05:22
做了三道题应该问题不大

第三题写出思路了，没给出完全正确答案，而且写复杂了，但是她的意思是让用dp?

FF-Ti 发表于 2017-10-28 05:21
一个nlogn 和o（1），一个是o（n） 和o（n）。看面试官想要哪种把

能给个用hashmap的完整解法吗