#牛客堂直播视频#常见面试题精讲(二)(2015.6.3)
【本期题目】
1 拼接所有字符串产生字典顺序最小的大字符串
2 从5随机到7随机及其扩展
(1)题目
给定一个等概率随机产生1~5的随机函数rand1To5如下:
public int rand1To5() {
return (int) (Math.random() * 5) + 1;
}
除此之外不能使用任何额外的随机机制,请用rand1To5实现等概率随机产生1~7的随机函数rand1To7。
(2)补充题目
给定一个以p概率产生0,以1-p概率产生1的随机函数rand01p如下:
public int rand01p() {
// you can change p as you like
double p = 0.83;
return Math.random() < p ? 0 : 1;
}
除此之外不能使用任何额外的随机机制,请用rand01p实现等概率随机产生1~6的随机函数rand1To6。
(3)进阶题目
给定一个等概率随机产生1~M的随机函数rand1ToM如下:
public int rand1ToM(int m) {
return (int) (Math.random() * m) + 1;
}
除此之外不能使用任何额外的随机机制。有两个输入参数分别为m和n,请用rand1ToM(m)实现等概率随机产生1~n的随机函数rand1ToN。
3给定一个无序数组arr,求出需要排序的最短子数组长度。
例如:
arr = [1,5,3,4,2,6,7]
返回4,因为只有[5,3,4,2]需要排序。
4 最大的leftMax与rightMax之差的绝对值
给定一个长度为N(N>1)的整型数组arr,可以划分成左右两个部分,左部分arr[0..K],右部分arr[K+1..N-1],K可以取值的范围是[0,N-2]。求这么多划分方案中,左部分中的最大值减去右部分最大值的绝对值,最大是多少?
例如[2,7,3,1,1],当左部分为[2,7],右部分为[3,1,1]时,左部分中的最大值减去右部分最大值的绝对值为4。当左部分为[2,7,3],右部分为[1,1]时,左部分中的最大值减去右部分最大值的绝对值为6。还有很多划分方案,但最终返回6。
5 现在有一种新的二叉树节点类型如下:
public class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } }
该结构比普通二叉树节点结构多了一条指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确的指向自己的父节点,头节点的parent指向null。只给一个在二叉树中的某个节点node,请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中,node的下一个节点叫做node的后继节点。
例如,下图的二叉树:
__________6__________
/ \
___3___ ___9___
/ \ / \
1__ 4__ __8 10
\ \ /
2 5 7
中序遍历的结果为:1,2,3,4,5,6,7,8,9,10
所以节点1的后继为节点2,节点2的后继为节点3,…,节点10的后继为null
注:下面回帖给出了源代码供参考。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30,直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客5群272820159