After the National Day, my friends in a small circle of wechat group posted a picture, which is the code of bytedance’s interview questions spread on the Internet. They thought about it in their spare time and found that it was not difficult. They were all considerations of basic mathematical knowledge. Go ahead!

Of course, I can’t finish coding any two questions in 40 minutes. I only know the general idea of solving the questions. The only thing I can be sure of is that I can finish coding the second question in 20 minutes within the specified time of the interview.

 

Subject to a

 

The basic knowledge is the plane rectangular coordinate system of junior high school.

  1. Calculate the total perimeter;
  2. The coordinate before and after each side length is calculated and encapsulated, and the fourth step is to use;
  3. According to K segment value, the average segment length is calculated.
  4. Then cycle K times and calculate the coordinates of the equinoxes according to the average length.

Without further ado, on the code:

Start by defining the Point class for coordinates

class Point { float x; float y; public Point() { } public Point(float x, float y) { this.x = x; this.y = y; } public Point(Point point) { this(point.x, point.y); } @override public String toString() {return "Point, x: "+ x +" y: "+ y; }}Copy the code

N Edge wrapper class for edges

class Line { Point begin; Point end; float length; public Line() { } public Line(Point begin, Point end, float length) { this.begin = begin; this.end = end; this.length = length; }}Copy the code

Now the class that implements the calculation

In the first version of this code, the calculation of coordinate points was not accurate when the square and even were divided equally. Tonight, I looked at the code and thought about it for 10 minutes. I made some changes and there is no such bug for the time being. Other bugs, look forward to finding together, and then fix it!

Public class Polygon {/** * count length ** @return */ private static float lineLength(Point A, Point b) {float length; If (a.x = = b.x) {/ / vertical line length = math.h abs (a.y - b.y); } else { length = Math.abs(a.x - b.x); } return length; } @return */ private static float totalSideLength(Point[] points, Line[] lines) {float side = 0; for (int i = 1; i < points.length; i++) { Point prev = points[i - 1]; Point point = points[i]; float length = lineLength(prev, point); side += length; lines[i - 1] = new Line(prev, point, length); if (i == points.length - 1) { length = lineLength(point, points[0]); side += length; lines[i] = new Line(point, points[0], length); } } return side; } public static Point[] division(Point[] points, int divisionNum) { Point[] divisionPoint = new Point[divisionNum]; Line[] lines = new Line[points.length]; float side = totalSideLength(points, lines); Float divisionLength = side/divisionNum; float divisionLength = side/divisionNum; int lineIndex = -1; float sumLength = 0; for (int i = 0; i < divisionNum; I ++) {if (I == 0) {divisionPoint[I] = new Point(points[0]); continue; } divisionPoint[i] = new Point(); float lineLength = divisionLength * i; while (true) { Line line; if (sumLength < lineLength) { lineIndex++; line = lines[lineIndex]; sumLength += line.length; } else line = lines[lineIndex]; if (sumLength >= lineLength) { float temp = sumLength - lineLength; If (line.begin. X == line.end. X) {// Begin and end are vertical divisionPoint[I]. X = line.begin. if (line.end.y > line.begin.y) divisionPoint[i].y = line.end.y - temp; else divisionPoint[i].y = line.end.y + temp; } else {// begin and end divisionPoint[I]. Y = line.end. Y; if (line.end.x > line.begin.x) divisionPoint[i].x = line.end.x - temp; else divisionPoint[i].x = line.end.x + temp; } break; } } } return divisionPoint; } private static void print(Point[] points) { for (int i = 0; i < points.length; I++) {System. Out. Println (" first "+ (I + 1) +", such as x: "+ points [I] x + + points", y: "[I] y); } } public static void main(String[] args) { Point[] points = new Point[] { new Point(0, 0), new Point(0, 1), new Point(1, 1), new Point(1, 0) }; Point[] divPoints = division(points, 8); print(divPoints); }}Copy the code

Topic 2

 

Answer:

The sum of the corresponding digits never adds up to more than 18, so we start by calculating the sum of the corresponding digits, and then iterate over and over again to find numbers greater than 9 and carry toward the higher digits.

This one is simpler, just looking at the detail that the positive integer addition of the units digit is never greater than 18.

The code:

public class LinkAddition { static class NumNode { public int num; public NumNode next; public NumNode() { } public NumNode(int num) { this.num = num; }; public NumNode(int num, NumNode next) { this(num); this.next = next; } } private static int length(NumNode num) { int length = 0; NumNode temp = num; while (temp ! = null) { length++; temp = temp.next; } return length; } private static NumNode calc(NumNode a, NumNode b, int aLength, int bLength) { NumNode aNode = a; NumNode bNode = b; NumNode result = new NumNode(); NumNode resultNode = result; Int aStartIndex = alength-blength; for (int i = 0; i < aLength; i++) { if (i >= aStartIndex) { resultNode.num = aNode.num + bNode.num; bNode = bNode.next; } else resultNode.num = aNode.num; aNode = aNode.next; if (aNode ! = null) { resultNode.next = new NumNode(); resultNode = resultNode.next; } } return result; } public static NumNode addition(NumNode a, NumNode b) { NumNode result = null; Int aLength = length(a); int bLength = length(b); if (aLength > bLength) { result = calc(a, b, aLength, bLength); } else { result = calc(b, a, bLength, aLength); } boolean isGreater9 = true; while (isGreater9) { isGreater9 = false; NumNode node = result; while (node ! If (node.num > 9) {isGreater9 = true; break; } node = node.next; } // No entries greater than 9 need to be carried if (! isGreater9) break; node = result; Result = new NumNode(1, node); if (node.num > 9) {result = new NumNode(1, node); node.num = node.num - 10; } while (node.next ! = null) { if (node.next.num > 9) { node.num += 1; node.next.num = node.next.num - 10; } node = node.next; } } return result; } private static void print(NumNode num) { NumNode node = num; while (node ! = null) { System.out.print(node.num); node = node.next; } } public static void main(String[] args) { NumNode a = new NumNode(9); a.next = new NumNode(9, new NumNode(9)); NumNode b = new NumNode(9); // b.next = new NumNode(9, new NumNode(9)); NumNode result = addition(a, b); print(result); }}Copy the code

The title three

 

The first version OF this I wrote, only fit the class example, and then I immediately overturned the class, and finally sat down and thought about the class for 10 minutes, and parsed this as a two-dimensional array.

First find the highest point, and then take the highest point as a dimension, do the cycle calculation of water, or on the code:

public class Water {
 public static int waterNum(int[] steps) { int waterNum = 0; int max = steps[0]; for (int i = 1; i < steps.length; i++) { if (max < steps[i]) max = steps[i]; } for (int i = 0; i < max; i++) { int num = 0, index = 0; for (int n = 0; n < steps.length; n++) { if (steps[n] - i > 0) { if (num > 0) { waterNum += n - index - 1; } num = steps[n] - i; index = n; } } } return waterNum; } public static void main(String[] args) { int[] steps = new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 3, 0, 1 }; int water = waterNum(steps); System.out.println(water); }}
Copy the code

Conclusion:

In fact, the knowledge points themselves are not difficult, are usually used to see how to convert into code.

The first question is how to calculate the length of the side in the rectangular coordinate system, and then calculate the corresponding coordinate according to the equal length of the first side next to each other.

The second problem is to investigate the maximum number of positive integer addition on each digit, as long as you understand this point, after adding each digit, and then unified carry processing can be done.

The third problem is the least amount of code, my way of thinking is a two-digit array, is not difficult.