#牛客堂直播视频#常见面试题精讲（六）（9.16）
【本期题目】
题目一
有一个机器按自然数序列的方式吐出球(1 号球,2 号球,3 号球,......)，你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。设计一种选择方式，使得当机器吐出第N号球的时候(N>K)，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。举一个更具体的例子。有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10个球，并且1~100号中的每一个球被选中的概率都是10/100。然后继续吐球，当吐出1000个球时，袋子里有10个球，并且1~1000号中的每一个球被选中的概率都是10/1000。继续吐球，当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是10/i，即吐球的同时，已经吐出的球被选中的概率也动态地变化。
题目二
给定字符串str，其中绝对不含有字符’.’和’*’。再给定字符串exp，其中可以含有’.’或’*’，’*’字符不能是exp的首字符，并且任意两个’*’字符不相邻。exp中的’.’代表任何一个字符，exp中的’*’表示’*’的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配。
【举例】
str=“abc”，exp=“abc”。返回true。
str=“abc”，exp=“a.c”。exp中单个’.’可以代表任意字符，所以返回true。
str=“abcd”，exp=“.*”。exp中’*’的前一个字符是’.’，所以可表示任意数量的’.’字符，所以当exp是“....”时与“abcd”匹配，所以返回true。
str=“”，exp=“..*”。exp中’*’的前一个字符是’.’，可表示任意数量的’.’字符，但是”.*”之前还有一个’.’字符，该字符不受‘*’的影响，所以str起码得有一个字符才能被exp匹配。所以返回false。
题目三
给定字符串str1和str2，求str1的子串中含有str2所有字符的最小子串长度。
【举例】
str1="abcde”，str2="ac"。因为"abc"包含str2的所有字符，并且在满足这一条件的str1的所有子串中，”abc"是最短的，所以返回3。str1="12345”，str2="344"。最小包含子串不存在，返回0。
题目四
给定一个长度不小于2的数组 arr，实现一个函数调整arr，要么让所有的偶数下标都是偶数，要么让所有的奇数下标都是奇数。如果 arr 的长度为 N,函数要求时间复杂度为 O(N)，额外空间复杂度为 O(1)。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者，电子工业出版社7月底将出版发行，书籍涉及算法与数据结构编程题目240道以上，并且个人实现出最优解，大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30，直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客5群272820159