Even before fall 2020, Internet companies are already looking for new talent, and they’re starting their fall hiring process in advance. A recent reader shared his experience with me yesterday after attending byteDance’s early selection session.
During the entire interview process, ByteDance will have at least three rounds of technical interviews, and each round will be tested on algorithms. For example, in the interview of this reader, the interviewer asked him to write the implementation algorithm of priority queue and explain his ideas. He answered four implementations: unordered array, ordered array, unordered linked list and the implementation of ordered linked list. At that time, the interviewer praised him for his thorough explanation, but the result was too short. Today, I’m going to talk about priority queues based on readers’ interview experiences.
Priority queue
Priority queues, like stacks and queues, are collections of elements. In the delete operation, the stack is a first-in-last-out data structure, removing the most recently added element; A normal queue is a first-in, first-out data structure in which elements are appended at the end of the queue and removed from the queue head. In priority queues, elements are assigned priority. When an element is accessed, the element with the highest priority is deleted first. Priority queues have the characteristics of first in (largest out).
The main operations on the priority queue are insert, delMax (delete the maximum value), and isEmpty (determine if it isEmpty).
Priority queues have many applications, such as:
- A * search algorithm in AI
- Use Huffman encoding for data compression
- Event-driven Simulation
Unordered arrays implement priority queues
Priority queue class
Construct a maximum priority queue in which the element with the maximum value has the highest priority. Key must extend the Comparable interface. This is because we are comparing between elements in the priority queue, not between priority queue objects.
Priority queue class: Key[] Pq is an array of generic type, and N is the number of elements in the array.
Operation function
Insert () : Inserts elements into the end of an array
DelMax () : All elements need to be scanned each time the maximum number of elements is found. The trick to removing the largest element is to swap the largest element with the last element in the array and then remove it.
IsEmpty () : checks whether the queue isEmpty
Ordered arrays implement priority queues
Priority queue class
Operation function
Insert () : Inserts elements into an array of sorted positions, maintaining the sorted array.
DelMax () : The Max element will always be at the end, remove it.
IsEmpty () : checks whether the queue isEmpty.
Unordered linked lists implement priority queues
Implementation of linked list nodes
Operation function
Insert () : Inserts elements into the linked list using the header method.
DelMax () : Finds the maximum number of elements in the linked list each time, and then deletes it.
IsEmpty () : checks whether the list isEmpty.
The complete code
Ordered linked lists implement priority queues
Implementation of linked list nodes
Operation function
Insert () : Inserts elements into the list, preserving the order of the list.
DelMax () : The largest element of the list is always at the head of the list. Each time the largest element of the list is deleted, the element in the head of the list is deleted.
IsEmpty () : checks whether the list isEmpty.
The complete code
conclusion
Let’s have fun, let’s have fun, let’s not joke about the interview! While poking fun at Bytedance’s “every job interview algorithm”, why do companies use so many algorithms? In fact, the core is to see whether the candidate is smart enough, many companies recruit engineers essential condition is smart.
The implementation of the priority queue itself is not difficult, but there are very few candidates like readers who tell all four implementations of the priority queue. The reader successfully passed one, the next interview is still continuing, wish this reader can get byte offer smoothly!
Next is xiaobian through some big factory friends to their internal Java interview questions, information is rare, but also nearly a year of real interview questions;
There are: Ant Financial, Pinduoduo, Ali Cloud, Baidu, Vipshop, Ctrip, Fengchao Technology, Letxin, Isoftstone, OPPO, Yinsheng Payment, Ping an of China and other primary, intermediate, advanced Java interview questions set, with super detailed answers, I hope to help you.
Xiaobian web disk also through the accumulation of these years, the Java e-book is also shared with you, about 10G of resources
230 high-end resume templates collected for many years are also presented to you
