小米2018秋招服务端工程师主观题合集

stack和heap都是常见的数据结构。现在我希望你设计一个容器，同时拥有stack和heap的特性，即该容器至少包含这四个接口：

   (1) size：容器中元素的个数。

   (2) push：向该容器中加入一个元素。

   (3) stack_pop：从该容器中取出一个元素，且取出顺序与push顺序相反。

   (4) heap_pop：从该容器中取出一个元素，且该元素是容器中值最大的。

   一旦某个元素从容器中pop出去（无论是stack_pop还是heap_pop），该元素就不在容器中了，即一个元素只能被pop一次。

   下面为样例，第一列是操作，第二列是操作完成后容器中的元素集合：

       push(1)           {1}

       push(3)           {1,3}

       push(2)           {1,3,2}

       heap_pop()->3     {1,2}

       stack_pop()->2    {1}

       stack_pop()->1    {}

   请设计该容器，定义所需的数据结构，实现以上四个接口（用你熟悉的语言或者伪码），并给出各个方法的计算复杂度和整个容器的空间复杂度。

给定文本text和待匹配字符串pattern，二者皆只包含小写字母，并且不为空。

   1). 在text中找出匹配pattern的最短字符串，匹配指按序包含pattern中的所有字母，但不要求pattern连续。

       输出为第一个最短匹配字符串的起始位置和长度。

       如text为abaacxbcbbbbacc，pattern为cbc，则输出的起始位置为4（下标从0开始），长度为4。

       请给出算法思想和复杂度。

   2). 在text中找出匹配pattern的最短字符串，匹配指包含pattern中的所有字母，既不要求连续，也不要求有序，也不考虑重复。

       输出为第一个最短匹配字符串的起始位置和长度。

       如text为abaacxbcbbbbacc，pattern为cbc，则输出的起始位置为6（下标从0开始），长度为2。

       请给出算法思想和复杂度。