This article has been accepted by Github github.com/silently952…
Wechat official account: Beta learning Java
preface
In the Http protocol in the last interview, the interviewer is originally wanted to Http asked about, want to continue to ask me some of the problems related to JAVA, I suddenly feel my throat uncomfortable coughs a few times, (at the time of this sensitive) have deterred the interviewer, the interviewer said after the mask is the interview first temporarily here, talk to you next time; Two weeks later I got another call from HR;
HR: Have you recovered from your cold? The last interview went well. When would you be free to come to our company for a second interview?
Me: Always ready
When I arrived at the office, I was taken to the small dark room to wait for the interviewer. What I didn’t expect was a beautiful little sister.
Me: Sweet little sister, you are the interviewer of this time? (I am secretly pleased)
Beautiful interviewer: Yes, the interviewer who interviewed you last time has gone to a meeting, and I have come to talk with you for this interview
Interviewer: see you so can talk, let me help you open a stomach first, talk about dichotomy search
Me :(appetizing ah, this little sister is so kind)
Me: Binary lookup is to find a value in an ordered array, return the index in the array if it exists, otherwise return -1; The algorithm maintains two variables lo(minimum) and Hi (maximum). Each search is compared with the middle value (mid). If it is equal to, mid is returned; if it is greater than, the right half of the array is queried; if it is less than, the left half is queried. Binary lookup is fast because half of the values are excluded from each query.
No BB, show you the code
Public class BinarySearch {/** * BinarySearch * @param key * @param arr * @return Public static int search(int key, int[] arr) {int lo = 0, hi = arr. Length -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (key > arr[mid]) { lo = mid + 1; } else if (key < arr[mid]) { hi = mid - 1; } else { return mid; } } return -1; }}Copy the codeFor a list of n elements, binary search takes at most log2n (the first 2 is the base) times to determine whether the element exists. So the time of binary search is zeroO(log n)
Interviewer: Tell me how to implement stacks using arrays.
Me: Little sister, the characteristics of the stack is last in first out, using array and linked list can realize the function of the stack, first look at the definition of the stack:
public interface Stack<T> extends Iterable { void push(T item); // Add element T pop() to the stack; // Pop Boolean isEmpty() from the stack; int size(); Return the number of elements}Copy the codeIt is possible that the stack will iterate over all elements when used, so inherit Iterable and implement the complete stack code using arrays:
public class FixCapacityArrayStack<T> implements Stack<T> { private T[] arr; private int size; public FixCapacityArrayStack(int capacity) { this.arr = (T[]) new Object[capacity]; } @override public void push(T item) {this.arr[size++] = item; } @Override public T pop() { return this.arr[--size]; } @Override public boolean isEmpty() { return size == 0; } @Override public int size() { return this.size; } @Override public Iterator<T> iterator() { return new Iterator<T>() { int index; @Override public boolean hasNext() { return index < size; } @Override public T next() { return arr[index++]; }}; }}Copy the codeInterviewer: The stack you just implemented is constant volume. How do you dynamically adjust the stack size
Me :(I knew you were going to ask this question, but didn’t say dynamic resizing; After years of interview experience, the most harmonious interview process is to push and block the interviewer, at the beginning of the best solution, how to reflect the interviewer’s sense of superiority?
I: To achieve dynamic resizing, first need to provide a resize method, expand the array to the specified size and copy the original data into the new array;
private void resize(int newCapacity) {
Object[] tmp = new Object[newCapacity];
for (int index = 0; index < size; index++) {
tmp[index] = arr[index];
}
this.arr = (T[]) tmp;
}
Copy the codeIt is necessary to check whether the current size has reached the maximum capacity of the array in the push method. If so, expand the array by 2 times
@Override
public void push(T item) {
if (this.arr.length == size) {
this.resize(2 * this.arr.length);
}
this.arr[size++] = item;
}
Copy the codeIn the POP method, you need to check if the current size is a quarter of the size of the array, and if so, you need to reduce the size of the data by half
@Override public T pop() { T item = this.arr[--size]; this.arr[size] = null; If (size > 0 && size == this.arr. Length / 4) {this.resize(this.arr. Length / 2); if (size > 0 && size == this.arr. } return item; }Copy the codeInterviewer: You mentioned linked lists. How do you implement stacks using linked lists
Me :(this is the result of you push me block, and the interaction of the little sister is very harmonious)
Me: To use a linked list, you need to define a Node first. A one-way linked list contains a value and a reference to the next Node
public class Node<T> {
private T item;
private Node next;
}
Copy the codeThe stack implemented by linked list is relatively simple compared with the array implementation and does not need to consider the problem of expansion.
public class LinkedListStack<T> implements Stack<T> { private Node<T> first; private int size; @override public void push(T item) {this.first = new Node<>(item, first); size++; } @override public T pop() {T item = first.getitem (); size--; first = first.getNext(); return item; } @Override public boolean isEmpty() { return first == null; } @Override public int size() { return this.size; } @Override public Iterator<T> iterator() { return new Iterator<T>() { private Node<T> current = first; @Override public boolean hasNext() { return current ! = null; } @Override public T next() { T item = current.getItem(); current = current.getNext(); return item; }}; }}Copy the codeInterviewer: How do YOU implement fifO queues using linked lists
Me: Similar to the stack implementation process, the queue needs to be defined first
public interface Queue<T> extends Iterable { void enqueue(T item); T dequeue(); Int size(); boolean isEmpty(); }Copy the codeImplementing queues with linked lists requires maintaining two variables: first and last; First is the head of the queue, last is the tail of the queue; Enqueue adds elements to the tail node when enqueued and dequeue removes elements from the head node when enqueued.
public class LinkedListQueue<T> implements Queue<T> { private Node<T> first; private Node<T> last; private int size; @Override public void enqueue(T item) { Node<T> node = new Node<>(item, null); if (isEmpty()) { first = node; } else {last.setNext(node);} else {last.setnext (node); } last = node; size++; } @Override public T dequeue() { T item = first.getItem(); first = first.getNext(); If (isEmpty()) {// set last to null when the queue isEmpty. } size--; return item; } @Override public int size() { return this.size; } @Override public boolean isEmpty() { return first == null; Override public Iterator<T> Iterator () {return new Iterator<T>() {private Node<T> current = first; @Override public boolean hasNext() { return current ! = null; } @Override public T next() { T item = current.getItem(); current = current.getNext(); return item; }}; }}Copy the codeInterviewer: Your stomach is ready. Let’s talk a little bit about algorithms. You design an algorithm to evaluate an arithmetic representation, such as:(1 + (2 + 3) * (4 * 5))
Me :(last night stayed up to see the algorithm is not in vain hard ah, just saw this solution.
Me :(scratching his head), this problem is a bit troublesome, I need to think about it for a while. (It seems that I did not prepare in advance, which is improvisation)
Me: Define two stacks, one for operators and one for users to store operands; The specific operation process is as follows:
- Ignore the left parenthesis
- When it hits a number, it pushes it onto the operand stack
- It hits a symbol and pushes it onto the symbol stack
- When a close parenthesis is encountered, an operator pops up, pops up the required operand, and pushes the result of the calculation onto the operand stack again
public static int calculate(String expression) {
Stack<String> operate = new LinkedListStack<>();
Stack<Integer> numbers = new LinkedListStack<>();
String[] split = expression.split(" ");
for (String str : split) {
if ("(".equals(str)) {
} else if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
operate.push(str);
} else if (")".equals(str)) {
String op = operate.pop();
int resut = 0;
if ("+".equals(op)) {
resut = numbers.pop() + numbers.pop();
} else if ("-".equals(op)) {
resut = numbers.pop() - numbers.pop();
} else if ("*".equals(op)) {
resut = numbers.pop() * numbers.pop();
} else if ("/".equals(op)) {
resut = numbers.pop() / numbers.pop();
}
numbers.push(resut);
} else {
numbers.push(Integer.valueOf(str));
}
}
return numbers.pop();
}
Copy the codeInterviewer: An array of int numbers with three numbers that add up to zero. Design an algorithm to help me figure out how many groups of numbers there are
Me: This is easy, look at the code:
public static int count1(int[] arr) {
int length = arr.length;
int count = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
for (int k = j + 1; k < length; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
count++;
}
}
}
}
return count;
}
Copy the codeInterviewer: If the array has 1 million ints, how long will your algorithm run
Me :(yes, the time complexity of this algorithm is O(n³), which is extremely inefficient when encountering large data volume)
(After a quick brain thought)
Me: There is something wrong with this algorithm. I was careless and didn’t take into account the large amount of data. Using this algorithm will waste little sister’s youth, so JUST now I thought, to improve this algorithm;
So let’s simplify 3-sum to 2-sum.
In 2-sum, one number a[I] is added to another number to equal 0; There are two ways:
The first is a two-layer loop similar to the 3-sum implementation, with O(n²) time.
The second way: just need to find whether the array has -a[I], the search algorithm uses binary search method
public static int count2(int[] arr) { Arrays.sort(arr); Int length = arr. Length; int count = 0; for (int i = 0; i < length; i++) { if (BinarySearch.search(-arr[i], arr) > i) { count++; } } return count; }Copy the codeThe time complexity of binary search method is O(log n), the algorithm to implement 2-sum has an extra layer of loop, so the time complexity is O(nlog n).
Use a similar method for 3-sum.
public static int count3(int[] arr) {
Arrays.sort(arr);
int length = arr.length;
int count = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (BinarySearch.search(-arr[i]-arr[j], arr) > j) {
count++;
}
}
}
return count;
}
Copy the codeMe: Sis, this algorithm is O(n ^ 2 log n). I’m doing my best. It’s as fast as I can. (The interviewer smiles.)
Interviewer: If you are a developer of wechat, I give you two users randomly, how to judge whether these two users are connected. What is connectivity? A is A friend of B, and B is A friend of C, so A and C are connected
Me :(the little sister’s questions are getting harder and harder)
Me: Beautiful interviewer, my brain is burning badly today, may I lie down and have a rest? (In fact, I didn’t think of a good solution, stalling tactics)
Interviewer: Ok, take a 10-minute break.
The interview is unfinished, to be continued
Finally (pay attention, don’t get lost)
There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.
Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏
All source code has been put into github repository github.com/silently952…
Reference books: Algorithms fourth edition
IDEA plug-ins commonly used by programmers: github.com/silently952…
Fully open source Taoke project: github.com/silently952…