回国之前,写点东西和H1B了断。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

锦晖律师事务所
12月16日
H1B讲座通知
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1079|回复: 4
收起左侧

[其他] 这道题不用KMP怎么才能做到O(N)

[复制链接] |试试Instant~
我的人缘0
reddatecookies 发表于 2017-11-1 00:22:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩

2017(7-9月)-[]CS本科+3个月-1年 - 内推| 码农类General其他@其他

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

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

x
Given a list of keywords and a list of search words, return a list of indices that indicate the beginning of sequences of adjacent keywords.
-baidu 1point3acres
Examples:

Search list: ['hello', 'hi', 'welcome', 'greetings', 'hi', 'greetings', 'hey', 'hello']
Keywords: ['hi', 'hey', 'greetings']
Output: [4]

Search list: ['i', 'saw', 'susie', 'sitting', 'in', 'a', 'shoe', 'shine', 'shop', 'where', 'she', 'sits', 'she', 'shines', 'and', 'where', 'she', 'shines', 'she', 'sits']
Keywords: ['she', 'sits', 'shines']
Output: [11, 17]

Search list: ['peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', 'peppers', 'a', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper',’ 'picked', 'if', 'peter', 'piper', 'picked', 'a', 'peck', 'of', 'pickled', 'peppers', 'wheres', 'the', 'peck', 'of', 'pickled', 'peppers', 'peter', 'piper', 'picked']
Keywords: ['peter', 'picked', 'piper']
Output: [0, 13, 17, 31]
. From 1point 3acres bbs

上一篇:明天就11月了还没面试
下一篇:亚麻实习no longer基本确定是简历拒了
我的人缘0
cai_lw 发表于 2017-11-1 01:22:32 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  90% (201)
 
 
9% (20)  踩
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的出现次数,当所有keyword的出现次数都为1时输出对应index
每slide一格至多有两个keyword的出现次数会变化,故维护这个记录和判断是否输出index都可以在O(1)内完成,总复杂度为O(N)
回复

使用道具 举报

我的人缘0
LukeDong 发表于 2017-11-1 00:44:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (66)
 
 
2% (2)  踩
N 是什么? 以及 Search List, Keyword 的长度 都影响到复杂度吧。
以及。。indices that indicate the beginning of sequences of adjacent keywords 指的是找到所有的不重复子序列开始的 index 在满足这个子序列的单词全部是 key word 下 这个意思嘛?
回复

使用道具 举报

我的人缘0
 楼主| reddatecookies 发表于 2017-11-1 12:06:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
多谢楼上指点。写了写代码如下:. From 1point 3acres bbs

import java.util.*;

public class SolutionTwo {
    public List<Integer> findIndices(List<String> search, List<String> keys) {

        if (search == null || search.size() == 0 || keys == null || keys.size() == 0). From 1point 3acres bbs
            return Collections.emptyList(); // empty keys as invalid (assumption)

        List<Integer> res = new ArrayList<>();

        Map<String, Integer> target = new HashMap<>();


        for (String word : keys) {
            int cnt = target.getOrDefault(word, 0);
            target.put(word, cnt + 1);
        }

        int m = search.size(), n = keys.size();
        if (m < n) return res;

        Map<String, Integer> window = new HashMap<>();

        int i = 0;
        while (i < m) {
            // constructing initial window
            while (i < n && i < m) {
                System.out.println(String.format("Inner: i=%d, window=%s", i, window));. check 1point3acres for more.
                int cnt = window.getOrDefault(search.get(i), 0);
                window.put(search.get(i), cnt + 1);-baidu 1point3acres
                i++;
            }

            System.out.println(String.format("Outer: i=%d, window=%s", i, window));


            // chk should be done b4 any sliding. 1point3acres
            if (Objects.equals(window, target)) {
                res.add(i - n);
            }


            // window sliding
            String toRemove = search.get(i - n);
            decrementWithCleaning(window, toRemove);

            String toAdd = search.get(i);
            window.put(toAdd, window.getOrDefault(toAdd, 0) + 1);
. 1point3acres

            i++;
        }

        return res;
    }

    private void decrementWithCleaning(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            int cnt = map.getOrDefault(key, 0);. From 1point 3acres bbs
            if (cnt <= 1) {
                map.remove(key);
            } else {
                map.put(key, cnt - 1);
            }
        }
    }

    public static void main(String[] args) {
        SolutionTwo solution = new SolutionTwo();

        String[] searchArray = {"hello", "hi", "welcome", "greetings", "hi", "greetings", "hey", "hello"};
        List<String> searchList = Arrays.asList(searchArray);-baidu 1point3acres


        String[] keyArray = {"hi", "hey", "greetings"};
        List<String> keyList = Arrays.asList(keyArray);

        List<Integer> res = solution.findIndices(searchList, keyList);
        System.out.println("result is " + res);
    }
. 1point3acres
}
回复

使用道具 举报

我的人缘0
 楼主| reddatecookies 发表于 2017-11-1 21:35:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
cai_lw 发表于 2017-11-1 01:22
这比字符串匹配trivial得多啊,跟KMP没什么关系
用一个sliding window扫一遍,记录window内各个keyword的 ...

如何有效比较两个map的内容?map.equals居然是O(N)
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-11 06:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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