字节跳动2019年春季社招面试内容
【摘要】 来自深圳字节跳动大佬熊熊熊帮忙内推的。 从简历投递到约面试一天，约的第二天面试。 开始，自我介绍，面试官看你的简历，差不多5分钟左右，随便说就行，避免尴尬。 开始刷算法题：
给定两个链表和第三个链表，找规律然后进行算法实现。
其实就是实现加法，有进位，而且需要考虑链表长度不一样的情况。
例子： List1 ： 1 -》 3 -〉5 List2：2 -》4 -〉2 ...
来自深圳字节跳动大佬熊熊熊帮忙内推的。
从简历投递到约面试一天，约的第二天面试。
开始，自我介绍，面试官看你的简历，差不多5分钟左右，随便说就行，避免尴尬。
开始刷算法题：
给定两个链表和第三个链表，找规律然后进行算法实现。
其实就是实现加法，有进位，而且需要考虑链表长度不一样的情况。
例子：
List1 ： 1 -》 3 -〉5
List2：2 -》4 -〉2
List3：3 -》 7 -〉 7
例子2：
List1：1 -》3 -〉 9
List2：。 2 -》 3
List3：1 -》 6 -〉2
思路：
将两个链表进行翻转，翻转后从头开始进行相加，直到某个链表到了头，相加过程中维护一个进位符号。最后再将相加的结果进行翻转即可。
代码：
package interview;
import leetcode.leetcodeaa.base.ListNode;
public class SumOfArrayList { public static void main(String[] args) { SumOfArrayList sum = new SumOfArrayList(); ListNode root = new ListNode(1); ListNode node1 = new ListNode(2); ListNode node2 = new ListNode(3); ListNode node3 = new ListNode(4); root.next = node1; node1.next = node2; node2.next = node3; node3.next = null; ListNode root2 = new ListNode(8); ListNode node4 = new ListNode(5); ListNode node5 = new ListNode(6); root2.next = node4; node4.next = node5; node5.next = null; sum.printList(root); sum.printList(root2); ListNode add1 = sum.sumOfArrayList(root2, root); sum.printList(add1); } private ListNode sumOfArrayList(ListNode root1, ListNode root2) { ListNode rNode1 = reverseList(root1); ListNode rNode2 = reverseList(root2); ListNode resNode = sumList(rNode1, rNode2); return reverseList(resNode); } private ListNode reverseList(ListNode root) { if (null == root) { return null; } ListNode preNode; ListNode curNode; ListNode nextNode; preNode = root; curNode = root.next; preNode.next = null; while(null != curNode) { nextNode = curNode.next; curNode.next = preNode; preNode = curNode; curNode = nextNode; } return preNode; } private ListNode sumList(ListNode root1, ListNode root2) { int add = 0; ListNode res = new ListNode(0); ListNode out = res; while(root1 != null && root2 != null) { ListNode nextNode = new ListNode(0); nextNode.val = (root1.val + root2.val + add) % 10; add = (root1.val + root2.val) / 10; root1 = root1.next; root2 = root2.next; res.next = nextNode; res = nextNode; } while(root1 != null){ ListNode nextNode = new ListNode(0); nextNode.val = root1.val + add; add = 0; root1 = root1.next; res.next = nextNode; res = nextNode; } while(root2 != null){ ListNode nextNode = new ListNode(0); nextNode.val = root2.val + add; add = 0; root2 = root2.next; res.next = nextNode; res = nextNode; } return out.next; } private void printList(ListNode root) { while (null != root) { System.out.print(root.val + " -> "); root = root.next; } System.out.println(); }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
非递归实现二叉树中序遍历
这道题从思路上看很简单，就是利用一个栈，先将当前指针指向根结点，当前节点入栈，指针指向当前节点左侧子树，指针为空，指针指向栈弹出元素，打印指针元素值，指针指向当前节点右子树，循环
代码：
package interview;
import java.util.Stack;
public class LDRnonrecursion { public void LDR(leetcode.base.TreeNode root) { if (null == root) return; Stack<leetcode.base.TreeNode> stack = new Stack<>(); while(root!= null || !stack.isEmpty()) { while(root != null) { stack.push(root); root = root.left; } root = stack.peek(); stack.pop(); System.out.println(root.val); root = root.right; } }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
寻找两个排序数组第K小的数字
这道题一开始是想到通过两个指针分别指向两个数组头部，然后比较每个指针下一位的大小，决定哪个继续向前移动。-这样实现时间复杂度很高
后来想到了其实可以用二分，区分以下的情况：
假设短数组shortArr，长度为lenS;
长数组为longArr，长度为lenL。
- 如果k<lenS，那么短数组取k个数，长数组取k个数，这两段数组的上中位数就是整体第k小的数；
- 如果k>lenL，对于longArr中前k-lenS-1个数，不能满足，因为即使他们比shortArr中的所有数都大，也无法达到第k个数。longArr中的第k-lenS个数，如果他比shortArr中的所有数都大，那么它就是第k小的数，否则，它也不是。对于shortArr中的前k-lenL-1个数，也是这样的。如果shortArr[k-lenL-1]和longArr[k-lenS-1]都不是第k小的数，那么shortArr[k-lenL … lenS-1]和longArr[k-lenS … lenL-1]的上中位数就是整体第k小的数。（因为前一段长度k-lenL，和k-lenS，中位数长度就是（(lenS-(k-lenS) + (lenL - (k-lenL) )/ 2，也就是lenS+lenL-k，和前面的长度相加就等于k
- 如果lenS<k<lenL，对于longArr前k-lenS-1个数，都不能满足要求，如果longArr中第k-lenS个数比shortArr中所有数都大，那么longArr[k-lenS]就是第k小的数。否则，对于longArr第k个数以后的数，也无法满足，那么shortArr[0 … lenS-1]和longArr[k-lenS … lenL-1]的上中位数就是所求的值。
也就衍生出了另一道题，求两个相同长度数组的上中位数。
同样使用二分法，取两个数组中间值比较，若中间值相同，则返回这个值，
否则中位数应当在中间值大的那个数组左侧，和中间值小的那个数组右侧。
代码：
package search;
import java.util.Arrays;
public class getKthInTwoSortedArray { public static void main(String[] args) { int[] arr1 = new int[]{3, 4}; int[] arr2 = new int[]{5, 6}; System.out.println(getKth(arr1, arr2,2)); System.out.println(getKth(arr1, arr2,3)); int[] arr3 = new int[]{1, 2, 3, 4, 5}; int[] arr4 = new int[]{4, 8}; System.out.println(getKth(arr3, arr4,2)); System.out.println(getKth(arr3, arr4,3)); System.out.println(getKth(arr3, arr4,6)); } private static int getKth(int[] arr1, int[] arr2, int k) { if (null == arr1 || arr1.length == 0) { return arr2[k]; } if (null == arr2 || arr2.length == 0) { return arr1[k]; } // init int[] shortArr; int[] longArr; if (arr1.length < arr2.length) { shortArr = arr1; longArr = arr2; } else { shortArr = arr2; longArr = arr1; } int lenS = shortArr.length; int lenL = longArr.length; // calc if (k <= lenS) { return getUpMid.getUpMidValue(Arrays.copyOfRange(shortArr, 0, k), Arrays.copyOfRange(longArr, 0 , k)); } else if (k > lenL) { if (longArr[k - lenS - 1] > shortArr[lenS-1]) { return longArr[k - lenS - 1]; } else if (shortArr[k - lenL - 1] > longArr[lenL-1]) { return shortArr[k - lenL - 1]; } else { return getUpMid.getUpMidValue(Arrays.copyOfRange(shortArr, k-lenL, lenS), Arrays.copyOfRange(longArr, k-lenS , lenL)); } } else { if (longArr[k - lenS - 1] > shortArr[lenS-1]) { return longArr[k - lenS - 1]; } else { return getUpMid.getUpMidValue(Arrays.copyOfRange(shortArr, 0, lenS), Arrays.copyOfRange(longArr, k-lenS , k)); } } }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
子类方法：
package search;
public class getUpMid { public static void main(String[] arg) { int[] arr1 = new int[]{3, 4}; int[] arr2 = new int[]{5, 6}; System.out.print(getUpMidValue(arr1, arr2)); } public static int getUpMidValue (int[] arr1, int[] arr2) { int left1 = 0; int right1 = arr1.length - 1; int left2 = left1; int right2 = right1; int mid1, mid2; while (left1 < right1) { mid1 = (left1 + right1) / 2; mid2 = (left2 + right2) / 2; int offset = (right1 - left1 + 1) & 1 ^ 1; if (arr1[mid1] == arr2[mid2]) { return arr1[mid1]; } else if (arr1[mid1] > arr2[mid2]) { right1 = mid1; left2 = mid2 + offset; } else { right2 = mid2; left1 = mid1 + offset; } } return Math.min(arr1[left1], arr2[left2]); }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
其他基础知识
Mysql，引擎，innoDB和MyIsam区别，索引，id。
Redis，基本数据结构，利用Redis实现分布式锁。
总结
总的来说以算法为主，可惜太紧张了没全答上来，惨烈的跪了，好好准备秋天继续面。平时要多动手多动脑，代码要落实到敲出来才算理解，不然就只是纸上谈兵，一动手就Bug百出。
文章来源: zclhit.blog.csdn.net，作者：zclhit_，版权归原作者所有，如需转载，请联系作者。
原文链接：zclhit.blog.csdn.net/article/details/89286024
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）