楼主: low910411
跳转到指定楼层
上一主题 下一主题
收起左侧

G家onsite 8/8

🔗
taobingxue 2016-8-20 04:25:13 | 只看该作者
全局:
lovelysier613 发表于 2016-8-20 03:28
感觉时间和空间复杂度都是一样的?还是我没有理解sliding windows。能不能给个详细点儿的过程?

我就mark一下,我也觉得sliding windows复杂度是一样的 @.@?
难道sliding windows不是像扫描线一样移动嘛 还是每一块都要暴力一下的?

默默觉得,N非常大,可以把每个单词当字符,然后做后缀数组……的样子?

评分

参与人数 1大米 +3 收起 理由
frank11118 + 3 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
frank11118 2016-8-20 08:19:36 | 只看该作者
全局:
taobingxue 发表于 2016-8-20 04:25
我就mark一下,我也觉得sliding windows复杂度是一样的 @.@?
难道sliding windows不是像扫描线一样移动 ...

感覺複雜度是 O(mn), n: number of words, m from input

請問是正確的嗎?
回复

使用道具 举报

🔗
taobingxue 2016-8-20 10:00:39 | 只看该作者
全局:
frank11118 发表于 2016-8-20 08:19
感覺複雜度是 O(mn), n: number of words, m from input

請問是正確的嗎?

还要乘上一个hash的复杂度?
自己写hash一般是字符串长度,std::map的find的复杂度是log(size of map)
回复

使用道具 举报

🔗
larry_cn 2016-8-20 21:20:15 | 只看该作者
全局:
楼主 第二题 如果是 [1, 2, 3], [1, 2], [1, 3]
是要 可以一起 嘛 还是 要分开
回复

使用道具 举报

🔗
frank11118 2016-8-21 06:48:36 | 只看该作者
全局:
taobingxue 发表于 2016-8-20 10:00
还要乘上一个hash的复杂度?
自己写hash一般是字符串长度,std::map的find的复杂度是log(size of map)

因為要把所有小於等於 m 的 substring 找出來,所以 O(m*n)
還是我算錯了?
回复

使用道具 举报

🔗
 楼主| low910411 2016-8-21 10:18:38 | 只看该作者
全局:
larry_cn 发表于 2016-8-20 21:20
楼主 第二题 如果是 [1, 2, 3], [1, 2], [1, 3]
是要 可以一起 嘛 还是 要分开

可以的。因为(1,2)被包含于(1,2,3),(1,3)被包含于(1,2,3)
回复

使用道具 举报

🔗
a08805436 2016-8-22 14:52:08 | 只看该作者
全局:
  1. </blockquote></div>4.1  n-gram, 貌似只能暴力做<p></p><div>
  2. </div><div><div class="blockcode"><blockquote>import java.util.*;
  3. import java.util.Map.Entry;

  4. public class Solution {
  5.     public static Map<String, Integer> ngrams(int n, String str) {
  6.         Map<String, Integer> ngrams = new HashMap<>();
  7.         String[] words = str.split(" ");
  8.         for (int i = 0; i < words.length - n + 1; i++) {
  9.             String res = concat(words, i, i + n);
  10.             if (!ngrams.containsKey(res)) {
  11.                 ngrams.put(res, 1);
  12.             } else {
  13.                 ngrams.put(res, ngrams.get(res) + 1);
  14.             }
  15.         }
  16.         return ngrams;
  17.     }

  18.     public static String concat(String[] words, int start, int end) {
  19.         StringBuilder sb = new StringBuilder();
  20.         for (int i = start; i < end; i++)
  21.             sb.append((i > start ? " " : "") + words[i]);
  22.         return sb.toString();
  23.     }


  24.     public static void main(String[] args) {
  25.         for (int n = 1; n <= 3; n++) {
  26.             for (Entry e : ngrams(n, "happy new year new year").entrySet()) {
  27.                 System.out.print((String) e.getKey() + " ");
  28.                 System.out.println((Integer) e.getValue());
  29.             }
  30.             System.out.println();
  31.         }
  32.     }
  33. }
复制代码
回复

使用道具 举报

🔗
larry_cn 2016-8-22 21:05:37 | 只看该作者
全局:
frank11118 发表于 2016-8-21 06:48
因為要把所有小於等於 m 的 substring 找出來,所以 O(m*n)
還是我算錯了?

不知道 要 怎么 找出来 小于等于n的 substring 出来
感觉 那会是 m * n * n    (n from gram numbers)

虽然 上面 说 后缀数组 的 额不懂,,,
不过 感觉 可以 联想到 用trie,
对 input 从后往前上 scan 对于 在n 内 从前往后 按 trie 走
这样 应该是 m * n
回复

使用道具 举报

🔗
南慕伦 2016-8-24 12:06:56 | 只看该作者
全局:
chenzhan171 发表于 2016-8-19 04:42
我觉得第二题和第4题可以改进下,
#2, UnionFind好一些
#4.2  A^A  = 0, A^0 = A, 两次for循环可以Sp ...

4.2 你这何必要用这个方法做,反而复杂了。
比较到第一个不同返回长的那个就好了,如果不一样的不是最后一个那这根本不用遍历完整个字符串。
你异或必须遍历完所有字符串。没必要啊。
回复

使用道具 举报

🔗
chenzhan171 2016-8-24 15:04:33 | 只看该作者
全局:
南慕伦 发表于 2016-8-24 12:06
4.2 你这何必要用这个方法做,反而复杂了。
比较到第一个不同返回长的那个就好了,如果不一样的不是最后 ...

两个字符串顺序是不一样的。
回复

使用道具 举报

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

本版积分规则

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