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.
public class UnorderedArrayMaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;
public UnorderedArrayMaxPQ(int capacity) {
pq = (Key[]) new Comparable[capacity];
N = 0; }}Copy the codeOperation 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
// Insert the element at the end of the array
public void insert(Key item) { pq[N++] = item; }
// Remove (and return) the largest item
public Key delMax(a) {
int max = 0;
for (int i = 1; i < N; i++)
if (less(max, i)) max = i;
swap(max, N-1);
return pq[--N];
}
// Is the queue empty?
public boolean isEmpty(a)
{ return N == 0; }
Copy the codeOrdered arrays implement priority queues
Priority queue class
public class OrderedArrayMaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;
public OrderedArrayMaxPQ(int capacity) {
pq = (Key[]) (new Comparable[capacity]);
N = 0; }}Copy the codeOperation 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.
// Inserts elements into an array of sorted positions
public voidInsert (Key item) {int i = N-1;
// As long as the new element is less than pq [I], move it to the right
while (i >= 0 && less(item, pq[i])) {
pq[i+1] = pq[i];
i--;
}
pq[i+1] = item;
N++;
}
// Remove (and return) the largest item
publicKey delMax () {return pq [-N]; }
// Is the queue empty?
public booleanIsEmpty () {return N == 0; }
Copy the codeUnordered linked lists implement priority queues
Implementation of linked list nodes
private class Node
{
Key item;
Node next;
}
Copy the codeOperation 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.
public boolean isEmpty(a)
{ return N==0; }public void Insert(Key v)
{
Node Item=new Node();
Item.item=v;
Item.next=first;
first=Item;
N++;
}
public Key delMax(a)
{
Node Item=new Node();
Item.next=first;
Node maxItem=first;
Node maxItemPrev=Item;
while(Item.next.next! =null)
{
if(less(maxItem.item,Item.next.next.item))
{
maxItem=Item.next.next;
maxItemPrev=Item.next;
}
Item=Item.next;
}
Key max=maxItem.item;
maxItemPrev.next=maxItem.next;
if(first==maxItem) first=maxItem.next;
maxItem=null;
N--;
return max;
}
Copy the codeThe complete code
public class UnOrderedListMaxPQ<Key extends Comparable<Key>>
{
private class Node
{
Key item;
Node next;
}
// Unordered lists implement priority queue heaps
private Node first;
private int N=0;
public boolean isEmpty(a)
{ return N==0; }public int size(a)
{ returnN; }public void Insert(Key v)
{
Node Item=new Node();
Item.item=v;
Item.next=first;
first=Item;
N++;
}
public Key delMax(a)
{
Node Item=new Node();
Item.next=first;
Node maxItem=first;
Node maxItemPrev=Item;
while(Item.next.next! =null)
{
if(less(maxItem.item,Item.next.next.item))
{
maxItem=Item.next.next;
maxItemPrev=Item.next;
}
Item=Item.next;
}
Key max=maxItem.item;
maxItemPrev.next=maxItem.next;
if(first==maxItem) first=maxItem.next;
maxItem=null;
N--;
return max;
}
public static void main(String[] args)
{
E2d4d3v3 pq=new E2d4d3v3();
pq.Insert(1);
pq.Insert(3);
StdOut.println(pq.delMax());
pq.Insert(2); StdOut.println(pq.delMax()); StdOut.println(pq.delMax()); }}}Copy the codeOrdered linked lists implement priority queues
Implementation of linked list nodes
private class Node
{
Key item;
Node next;
}
Copy the codeOperation 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.
public boolean isEmpty(a)
{ return N==0; }public int size(a)
{ returnN; }public void Insert(Key v)
{
Node newItem=new Node();
newItem.item=v;
Node Item=new Node();
Item.next=first;
while(Item.next! =null && less(newItem.item,Item.next.item))
Item=Item.next;
newItem.next=Item.next;
Item.next=newItem;
// Add a new node to node 0 or change first when the new node is the maximum
if(first==null || first==newItem.next) first=newItem;
N++;
}
public Key delMax(a)
{
Node maxItem=first;
first=first.next;
Key max=maxItem.item;
N--;
return max;
}
Copy the codeThe complete code
public class OrderedListMaxPQ<Key extends Comparable<Key>>
{
private class Node
{
Key item;
Node next;
}
// Ordered lists implement a priority queue heap, with first storing the largest element
private Node first;
private int N=0;
public boolean isEmpty(a)
{ return N==0; }public int size(a)
{ returnN; }public void Insert(Key v)
{
Node newItem=new Node();
newItem.item=v;
Node Item=new Node();
Item.next=first;
while(Item.next! =null && less(newItem.item,Item.next.item))
Item=Item.next;
newItem.next=Item.next;
Item.next=newItem;
// Add a new node to node 0 or change first when the new node is the maximum
if(first==null || first==newItem.next) first=newItem;
N++;
}
public Key delMax(a)
{
Node maxItem=first;
first=first.next;
Key max=maxItem.item;
N--;
return max;
}
public static void main(String[] args)
{
OrderedListMaxPQ pq=new OrderedListMaxPQ();
pq.Insert(1);
pq.Insert(3);
StdOut.println(pq.delMax());
pq.Insert(2); StdOut.println(pq.delMax()); StdOut.println(pq.delMax()); }}Copy the codeconclusion
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!
The article continues to be updated, can be searched for “Cloud, Ao Child” in wechat to read, reply [information] [interview] [resume] prepared by the first line of large factory interview materials and resume template, at the same time my GitHub github.com/1170300826/… There is an Internet interview guide for a large factory.