搜狗2019秋招客户端工程师编程题合集（第二场）

一群探险家被困古巴比伦迷宫 ，经过努力，探险家破译出了密码。原来通关需要先打开前方的M个机关的任意一个或多个为打开状态，然后关闭所有机关才能安全通过。探险家还发现了一种带有凸起的圆盘，圆盘可以用来同时反转若干个机关的状态（打开状态反转为关闭状态，关闭状态反转为打开状态，这若干个机关必须同时反转）。为了速记，探险家们用十六进制数字表示一个圆盘。如圆盘能同时控制第3、4、5个开关，圆盘就记为1C（11100）。每次操作一个圆盘，比特位为1的位置的机关同时被反转；而且每个圆盘使用一次后就会碎掉。目前探险家收集到了N个圆盘，问现在探险家可以顺利走出迷宫么？

若探险家手里有0、1、2、3、5五个圆盘，M=7，由于存在1 xor 2 xor 3 = 0， 因此结果是yes；
若探险家手里有0、1、2、2、5五个圆盘，M=7，由于存在2 xor 2 = 0， 因此结果是yes；
若探险家手里有0、1、3、5、9五个圆盘，M=7，由于不存组合使得 xor = 0， 因此结果是no。

输入描述： 包含多组数据，第一行是数据组数。

每组数据中首行为M N，M为机关个数，M <= 360(大部分情况下小于40)，N为圆盘个数,
N<=50000；其余为N行圆盘的16进制ID，可以保证每行输入小于2^M输入样例： 2 2 3 0 2 2 5 2 4 1C 输出描述： 每组一行输出，满足条件输出yes，反之输出no输出样例 yes no

判断一个数字串是否匹配一个表达式，具体如下：
1）表达式m：一定不为空，只能由数字和“*”构成，其中的“*”表示匹配一个或多个“它前面所有非”*“的数字的和值除以10的余数”；“*”如果在最前面或其前面都是“*”，则只可以是任意一个数字。
2）数字串s：可能为空，只能由数字构成，不能包含其它字符。
3）是否匹配：匹配要求覆盖整个数字串s，而不是某一部分匹配。

解题要求：不能将m转写成标准正则表达式来解题，需要自己编程实现匹配算法。

注意，对应objc语言，系统里的@autoreleasepool {} 需要改写成如下形式

#import <Foundation/Foundation.h>
//strcmp
//NSString:
//- (NSArray<NSString *> *)componentsSeparatedByCharactersInSet:(NSCharacterSet *)separator
//- (unichar)characterAtIndex:(NSUInteger)index
//- (NSString *)substringWithRange:(NSRange)range

int main(int argc, const char * argv[]) {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]
    //...
    //add your code
    //...
    [pool drain]
    return 0
}

输入描述： 见输入样例，其中最后一行的0表示结束输入输入样例： 3 1* 11111 **1 121 **1 1221 0 输出描述： YES:匹配

NO:不匹配输出样例 YES YES NO

试判断一个消息队列是否可能死锁。
消息队列的缓冲区长度为L单位，读操作为每次从缓冲区读取R单位，写操作为每次写入缓冲区W单位。
消息队列会持续进行读写操作。具体为写操作会在缓冲区还剩余大于等于W单位空间时保持进行，当缓冲区内空间小于W时，写操作停止，等待读操作进行；类似的，读操作会在缓冲区可读内容大于等于R时保持进行，当可读内容小于R时，读操作停止，等待写操作进行。读写都是原子操作。
若读写操作均无法进行，定义此时状态为死锁。
给定L,R,W，问消息队列是否可能进入死锁状态，若能，输出YES，否则输出NO 输入描述： 第1行输入N(N<=10)表示数据组数。
从第2行到第N+1行，每行三个整数L,R,W。输入样例： 2 5 2 3 5 3 4 输出描述： 输出N行，每行输出'YES'或'NO'输出样例 NO YES