【氦图笔试和面试的笔试题】两个算法题1.双栈仿队列 .2布尔搜索(Boolean search is powerful in sourcing and recruiting.)

前言

其实都不算太难，但是没遇到过，所以做起来很懵……

1.双栈仿队列

请注意：请在11点30分前将代码保存为文本文件格式，以附件形式发回你的结果。如果未能准时收到你的答案，该场笔试可能作废。以下为题目详情——
There’s a Stark café opening in your school and you are invited to create an ordering system for the coffee shop. However you don’t have money to pay for a cloud computing instance so you must use the API they provide you to store the orders.

They have the following strange storage API:
storageNo1.push(orderNumber)
storageNo1.pop()

storageNo2.push(orderNumber)
storageNo2.pop()

In these APIs your order which comes in first are return last. For ex,

storageNo1.push(1);
storageNo1.push(2);
storageNo1.pop(); // returns 2;
storageNo1.pop(); // returns 1;

storageNo1 & storageNo2 are essentially the same. And you need to use the above data structure to create a ordering service in which orders comes first are returned first. For ex,
yourService.addOrder(1);
yourService.addOrder(2);
yourService.addOrder(3);
yourService.getOrder(); // outputs 1
yourService.getOrder(); // outputs 2
yourService.getOrder(); // outputs 3

看到的时候就是一脸懵逼，觉得很简单，但是又猜想不会这样吧？？？总之很……迷茫？

思路： 双栈仿队列，没什么可说的，就是两个栈倒来倒去呗……
具体来讲，就是，入队时，放到s1里，出队列时，先把s1里的全都pop出来，再push进s2里，直到栈底，再从s2 pop出来，再push回s1里。

代码:

class Storage_Stack:
    pipe = []
    def __init__(self):
        self.pipe = []
    def push(self,id):
        self.pipe.append(id)
        # print("入栈订单:",id)
    def pop(self):
        if len(self.pipe)>0:
            order=self.pipe.pop()
            # print("当前订单出栈:",order)
            return order
        else:
            # print("系统中无订单！")
            return '-1'
    def get_size(self):
        return len(self.pipe)


s1=Storage_Stack()
s2=Storage_Stack() # 双栈仿队列
print("输入订单id，输入-1返回订单，输入-2退出")
code=input()
while(code!='-2'):
    if (code=='-1'):
        order=s1.pop()
        while(order!='-1'):
            s2.push(order)
            order=s1.pop()
        print("弹出订单：",s2.pop())
        order=s2.pop()
        while(order!='-1'):
            s1.push(order)
            order=s2.pop()
    elif (int(code)>=0):
        s1.push(code)
        print("放入订单：",code)
    code = input()
print("退出系统,此时系统中剩余订单数:",s1.get_size())

演示效果，

双栈结构过程: 1,2表示了栈号

2. 布尔搜索

总之我是没听说过这个东西了……第一次写，开始用栈写的，遇到 [ 入栈，遇到 ] 出栈，大概知道要用递归，不过太紧张了，完全写不出来。
题目：

# 
# Your previous Plain Text content is preserved below:
# 
# 
# Boolean search is powerful in sourcing and recruiting.
# We will use machine learning prediction to provide relations among skills. Now we need a function to transfer those relations to a string with correct boolean format.
# 
# Example1:
# input: [["java", "python"], ["machine learning", "deep learning"]]
# output: ("java" OR "python") AND ("machine learning" OR "deep learning")
# 
# Example2:
# input: [[["java", "maven", "spring"], "python"], ["machine learning", "deep learning"]]
# output: (("java" OR "maven" OR "spring") AND "python") AND ("machine learning" OR "deep learning")

思路： 用栈肯定不太好，倒来倒去，入栈java出栈avaj ，面试官提示了要用递归，然而我没复习到那块，很久没写，很不熟练了。
这里注意，只有子节点内的列表需要用OR 连接，其他都用AND，而子节点都是那些列表内是Str的类型的节点，而且不能含有其他列表，实际上有点类似树那样的结构了。
例如下面的例子就是这样：python [[["java", "maven", "spring"], "python"], ["machine learning", "deep learning"]]

代码：

inp = [[["java", "maven", "spring"], "python"], ["machine learning", "deep learning"]]

def subString(sub_s):
    string=''
    i=0
    for s in sub_s: # 对每个列表求子结构
        if type(s).__name__!='str': # 非字符串类型，进行递归
            string+=subString(s)+' AND '
        else:
            string+="\""+s+"\""
            # 已经是子结构了，直接用OR连接
            if i <len(sub_s)-1:
                string+=' OR ' # 用len-1个or连接
            # print("sub_S:",s)
        i+=1
    return '('+string+')'
string=subString(inp)
s1=list(string)
s1[0]=''
s = ''.join(s1)
s= s.replace('AND )','')
print(s)