分享一道狗家onsite题目

Job Hunting Interview
, , , , ,
1

给一个string,用\n分隔，给定index，返回该index在第几行

Follow up：
给一个string,用\n分隔，给多个index，分别返回该index在第几行

1 Like
2 
def findLine_iterate(article, keyword):
    lines = article.split('\n')

    for idx,line in enumerate(lines, 1):
        idxof = line.indexOf(keyword)
        if idxof != -1:
            return idx
    return -1
3

解释一下思路？

4

其实可以binary search 的

5

我只写了第一部分的简单思路,binary search 是如何实现的呢?

至于indexOf部分的话,就可以用KMP等算法了.

6

这个有点过了吧

7

这个应该很容易想到，而且应该是正解，你再想想

8

你是指遍历行的时候用 binary search 吗? 没有顺序的行排列用 binary search 有优势吗?

9

举个例子，每一行的ending index 分别是 10, 23, 45, 80
你搜index 50 的话，不就是binary search这个数组么