字节跳动社招hr面试,字节跳动社招面试流程

来自深圳字节跳动大佬熊熊熊帮忙内推的。
从简历投递到约面试一天，约的第二天面试。
开始，自我介绍，面试官看你的简历，差不多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(); }} 非递归实现二叉树中序遍历

这道题从思路上看很简单，就是利用一个栈，先将当前指针指向根结点，当前节点入栈，指针指向当前节点左侧子树，指针为空，指针指向栈弹出元素，打印指针元素值，指针指向当前节点右子树，循环

代码：

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; } }} 寻找两个排序数组第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)); } } }}

子类方法：

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]); }} 其他基础知识

Mysql，引擎，innoDB和MyIsam区别，索引，id。
Redis，基本数据结构，利用Redis实现分布式锁。

总结

总的来说以算法为主，可惜太紧张了没全答上来，惨烈的跪了，好好准备秋天继续面。平时要多动手多动脑，代码要落实到敲出来才算理解，不然就只是纸上谈兵，一动手就Bug百出。