Превъзходно интервю за разработка на софтуер: Изчерпателното ръководство през 2023 г
Предговор
По време на тези странни икономически времена имах приятели и колеги да губят работата си и трябваше да започнат интервюта отново. Все още си спомням колко трудно беше да запаметявам, практикувам и овладявам много информация, която никога не знаех преди и (повечето) никога не използвах след това. Така че какво си струва тук е моето ръководство за интервюто за софтуера….или измамен лист, наистина не съм сигурен. Примерите и отговорите са дадени на Java и Javascript, но могат лесно да се преобразуват в който език предпочитате.
Основи:
Разбиране на основите на компютърните науки и разработката на софтуер, като типове данни (напр. цяло число, плаваща единица, низ, булево, char, double, long, short), контролен поток (напр. оператори if-else, цикли, switch-case, троичен оператор) и основни концепции за програмиране (напр. функции, класове, променливи, обхват, управление на паметта).
- Типове данни: Типовете данни определят типа данни, които една променлива може да съдържа. Например, целочислена променлива може да съдържа цяло число, докато низова променлива може да съдържа текст. Разбирането на различните типове данни и тяхното използване е важно за писане на ефективен и правилен код. Те включват, но не се ограничават до int, float, double, short, long, char, string, boolean и др.
- Контролен поток: Контролният поток се отнася до реда, в който се изпълняват инструкциите в програмата. Изявления за контрол на потока, като оператори if-else, цикли, switch-case и троични оператори ви позволяват да контролирате потока на изпълнение въз основа на определени условия.
- Променливи: Променливата е наименувано място в паметта, където програмистът може да съхранява данни. Разбирането как да декларирате, инициализирате и манипулирате променливи е фундаментално за програмирането, включително концепции като обхват и управление на паметта.
Структури на данни:
Прегледайте общи структури от данни като масиви, свързани списъци, стекове, опашки, дървета (двоично дърво, AVL дърво, B-дърво, B+ дърво), хеш-таблици, купчини и графики. Разберете тяхната времева и пространствена сложност и практикувайте внедряването им в код.
Масиви: Масивът е колекция от елементи от един и същи тип данни, които се съхраняват в съседни места в паметта. Те имат постоянна времева сложност за основни операции като вмъкване, изтриване и достъп до елемент чрез неговия индекс.
Java:
int[] arr = new int[5];
arr[0] = 2;
arr[1] = 4;
arr[2] = 6;
arr[3] = 8;
arr[4] = 10;
// Accessing an element at index 2
System.out.println("Element at index 2: " + arr[2]);
// Inserting a new element at index 3
arr[3] = 9;
// Deleting an element at index 4
arr[4] = 0;
В този пример създаваме масив от цели числа с 5 елемента. След това инициализираме масива със стойности 2, 4, 6, 8 и 10. Можем да осъществим достъп до елемент с конкретен индекс, използвайки синтаксиса на масива arr[index]. Можем също да вмъкнем нов елемент в конкретен индекс, като му присвоим стойност и да изтрием елемент, като присвоим стойност 0.
Javascript:
let myArray = [1, 2, 3, 4, 5]; // Access an element by its index console.log(myArray[2]); // Output: 3 // Insert an element at the end of the array myArray.push(6); console.log(myArray); // Output: [1, 2, 3, 4, 5, 6] // Insert an element at a specific index myArray.splice(2, 0, 8); console.log(myArray); // Output: [1, 2, 8, 3, 4, 5, 6] // Delete an element at a specific index myArray.splice(2, 1); console.log(myArray); // Output: [1, 2, 3, 4, 5, 6]
console.log(myArray[2]) ще изведе 3, защото масивите в javascript са индексирани с 0
myArray.push(6) ще добави 6 към края на масива
myArray.splice(2, 0, 8) ще вмъкне 8 в индекс 2 и 0 елемента ще бъдат изтрити
myArray.splice(2, 1) ще изтрие 1 елемент при индекс 2
Моля, обърнете внимание, че масивите в JavaScript имат постоянна времева сложност за основни операции като достъп до елемент чрез неговия индекс, операции за вмъкване и изтриване.
Свързани списъци: Свързаният списък е структура от данни, която се състои от поредица от възли, всеки от които съдържа препратка към следващия възел в списъка. Те са полезни за динамично разпределение на паметта и имат линейна времева сложност за основни операции като вмъкване, изтриване и преминаване.
Java:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Insert a new node at the beginning of the list
public void push(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// Insert a new node after a given node
public void insertAfter(Node prevNode, int data) {
if (prevNode == null) {
System.out.println("Previous node cannot be null");
return;
}
Node newNode = new Node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
// Delete a node with a given key
public void delete(int key) {
Node temp = head, prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
if (temp == null) {
return;
}
prev.next = temp.next;
}
// Traverse the list
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
}
В този пример класът Node представлява единичен възел в свързания списък, съдържащ цяло число и препратка към следващия възел. Класът LinkedList използва главен възел, за да представи началото на списъка, и съдържа методи за вмъкване, изтриване и обхождане на списъка. Методът push() добавя нов възел в началото на списъка, методът insertAfter() добавя нов възел след даден възел, методът delete() изтрива възел с даден ключ, а методът printList() преминава списъка и отпечатва данните на всеки възел.
Методът push е O(1), тъй като актуализира само главата на списъка
Методът insertAfter е O(1), тъй като актуализира само следващия указател на един възел
Методът за изтриване е O(n), тъй като трябва да премине през списъка, за да намери възела с дадения ключ
Методът printList е O(n), тъй като трябва да премине през целия списък, за да отпечата всички възли
Можете също да добавите повече функционалност към свързания списък като размер, обръщане, сливане и т.н.
Javascript
public Node merge(LinkedList list1, LinkedList list2) {
Node dummy = new Node(0);
Node tail = dummy;
Node l1 = list1.head;
Node l2 = list2.head;
while (l1 != null && l2 != null) {
if (l1.data <= l2.data) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 == null) ? l2 : l1;
return dummy.next;
}
Този метод merge() приема два LinkedList обекта като параметри и връща главата на обединения списък. Той използва фиктивен възел, за да следи текущата опашка на обединения списък, и два указателя за преминаване през всеки от входните списъци. Цикълът while сравнява данните на текущите възли във всеки списък и добавя възела с по-малка стойност към обединения списък. След като един от входните списъци бъде изчерпан, останалите възли от другия списък се добавят към обединения списък. Времевата сложност на този метод е O(n), където n е общият брой възли в двата списъка.
Javascript:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Insert a new node at the beginning of the list
push(data) {
let newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
// Insert a new node after a given node
insertAfter(prevNode, data) {
if (prevNode === null) {
console.log("Previous node cannot be null");
return;
}
let newNode = new Node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
// Delete a node with a given key
delete(key) {
let temp = this.head, prev = null;
if (temp !== null && temp.data === key) {
this.head = temp.next;
return;
}
while (temp !== null && temp.data !== key) {
prev = temp;
temp = temp.next;
}
if (temp === null) {
return;
}
prev.next = temp.next;
}
// Traverse the list
printList() {
let temp = this.head;
while (temp !== null) {
console.log(temp.data);
temp = temp.next;
}
}
merge(list1, list2) {
let dummy = new Node(0);
let tail = dummy;
let l1 = list1.head;
let l2 = list2.head;
while (l1 !== null && l2 !== null) {
if (l1.data <= l2.data) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 === null) ? l2 : l1;
return dummy.next;
}
}
Този код дефинира клас Node, който има свойство данни и свойство next. Класът LinkedList използва свойство head за представяне на началото на списъка и съдържа методи за вмъкване, изтриване и обхождане на списъка, както и сливане на два списъка.
Моля, имайте предвид, че в JavaScript console.log се използва вместо System.out.print и също операторите за сравнение са различни в JS (===, !==)
Стекове: Стекът е структура от данни последен влязъл, първи излязъл (LIFO), където елементите се добавят и премахват от върха на стека. Те имат постоянна времева сложност за основни операции като натискане, изскачане и надникване.
import java.util.ArrayList;
public class Stack<T> {
private ArrayList<T> list = new ArrayList<T>();
public void push(T item) {
list.add(item);
}
public T pop() {
if (list.size() == 0) {
return null;
}
return list.remove(list.size() - 1);
}
public T peek() {
if (list.size() == 0) {
return null;
}
return list.get(list.size() - 1);
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.size() == 0;
}
}
- Методът
push(item)е O(1), тъй като актуализира само горната част на стека. - Методът
pop()е O(1), тъй като има достъп само до върха на стека. - Методът
peek()е O(1), тъй като има достъп само до върха на стека. - Методът
size()е O(1), тъй като има достъп само до размера на стека. - Методът
isEmpty()е O(1), тъй като проверява само дали размерът на стека е нула.
Важно е да се отбележи, че времевата сложност на основните операции на стека е O(1), ако се прилага с помощта на ArrayList, тъй като използва постоянна времева сложност на метода за добавяне и премахване на ArrayList. Въпреки това, ако стекът е имплементиран с помощта на LinkedList, времевата сложност ще бъде O(n), тъй като средната времева сложност на метода за добавяне и премахване е O(n)
В Javascript:
class Stack {
constructor() {
this.items = [];
this.count = 0;
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if (this.isEmpty()) return "Underflow";
this.count--;
return this.items.pop();
}
peek() {
if (this.isEmpty()) return "No elements in Stack";
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
clear() {
this.items = [];
this.count = 0;
}
}
Опашки: Опашката е структура от данни „първи влязъл, първи излязъл“ (FIFO), където елементите се добавят отзад и се премахват отпред. Те имат постоянна времева сложност за основни операции като поставяне в опашка, изваждане от опашка и надникване.
class Queue {
private int[] items;
private int front;
private int rear;
private int count;
public Queue(int capacity) {
items = new int[capacity];
}
public void enqueue(int item) {
if (count == items.length)
throw new IllegalStateException();
items[rear] = item;
rear = (rear + 1) % items.length;
count++;
}
public int dequeue() {
if (count == 0)
throw new IllegalStateException();
int item = items[front];
items[front] = 0;
front = (front + 1) % items.length;
count--;
return item;
}
public int peek() {
if (count == 0)
throw new IllegalStateException();
return items[front];
}
public boolean isEmpty() {
return count == 0;
}
public int size() {
return count;
}
}
Тази реализация използва масив и два указателя (преден и заден), за да следи предната и задната част на опашката. Методът enqueue добавя елемент в задната част на опашката чрез актуализиране на задния показалец и добавяне на елемента към масива. Методът за премахване на опашката премахва елемент от началото на опашката чрез актуализиране на предния указател и премахване на елемента от масива. Методът peek връща елемента в началото на опашката, без да го премахва, като връща елемента в предния показалец. Методът isEmpty връща true, ако опашката е празна, и false в противен случай. Методът size връща броя на елементите в опашката
Всички основни операции като поставяне в опашка, изваждане от опашка и надникване имат постоянна времева сложност O(1).
Струва си да се спомене, че в тази реализация опашката се реализира с помощта на кръгъл масив, това е за предотвратяване на препълване, когато масивът е пълен, когато последният елемент бъде изваден от опашката, предният показалец ще сочи отново към началото на масива, по този начин масивът може да се използва отново, без да се създава нов.
Освен това тази реализация използва mod оператора %, за да гарантира, че предният и задният указател винаги остават в границите на масива, ако задният указател надхвърли края на масива, той отново се увива в началото на масива.
Също така си струва да се отбележи, че когато даден елемент е изваден от опашката, аз задавам стойността му на нула, това е за предотвратяване на лутане, което е, когато даден обект вече не е необходим, но все още се държи в паметта.
Можете също така да приложите Queue, като използвате свързан списък в Java, тази реализация няма да има проблема с препълването, но ще има малко по-голяма пространствена сложност, тъй като изисква допълнителна памет за съхраняване на указателите.
Javascript:
class Queue {
constructor() {
this.items = [];
this.count = 0;
this.lowestCount = 0;
}
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
dequeue() {
if (this.isEmpty()) return "Underflow";
let result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
peek() {
if (this.isEmpty()) return "No elements in Queue";
return this.items[this.lowestCount];
}
isEmpty() {
return this.count - this.lowestCount === 0;
}
size() {
return this.count - this.lowestCount;
}
}
- Дървета: Дървото е йерархична структура от данни, която се състои от възли, като всеки възел има стойност и препратка към своите деца. Те са полезни за много различни видове проблеми като търсене и сортиране и имат линейна времева сложност за основни операции като вмъкване, изтриване и преминаване.
- Различните видове дървета включват:
- Двоично дърво: Двоичното дърво е дървовидна структура от данни, в която всеки възел има най-много две деца, които се наричат ляво дете и дясно дете.
- AVL дърво: AVL дърво е самобалансиращо се двоично дърво за търсене, където разликата между височините на левите и десните поддървета не може да бъде повече от една за всички възли.
- B-Tree: B-Tree е самобалансираща се дървовидна структура от данни, която поддържа данните сортирани и позволява търсения, последователен достъп, вмъквания и изтривания в логаритмично време.
- B+ дърво: B+ дърво е продължение на B-дърво. В дървото B+ всички данни се съхраняват само в листови възли, а не във вътрешни възли, а листовите възли са свързани помежду си, за да образуват единично свързан списък.
- Trie: Trie е дървовидна структура от данни, която се използва за ефективно извличане на ключ в голям набор от данни от низове.
Често срещан тип дърво, което често се използва за търсене и сортиране, е двоично дърво за търсене. Ето примерна реализация в Java и JavaScript за двоично дърво за търсене, заедно със сложността на времето за основните операции.
Java:
class Node {
int key;
Node left, right;
public Node(int key) {
this.key = key;
left = right = null;
}
}
class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
Node search(Node root, int key) {
if (root == null || root.key == key)
return root;
if (root.key > key)
return search(root.left, key);
return search(root.right, key);
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.inorder();
}
}
Javascript:
class Node {
constructor(key) {
this.key = key;
this.left = this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(key) {
this.root = this._insertRec(this.root, key);
}
_insertRec(root, key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = this._insertRec(root.left, key);
else if (key > root.key)
root.right = this._insertRec(root.right, key);
return root;
}
inorder() {
this._inorderRec(this.root);
}
_inorderRec(root) {
if (root != null) {
this._inorderRec(root.left);
console.log(root.key);
this._inorderRec(root.right);
}
}
search(key) {
return this._search(this.root, key);
}
_search(root, key) {
if (root == null || root.key == key)
return root;
if (root.key > key)
return this._search(root.left, key);
return this._search(root.right, key);
}
}
let tree = new BinarySearchTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.inorder();
console.log(tree.search(40));
За операцията по вмъкване времевата сложност е O(h), където h е височината на дървото, в най-лошия случай може да бъде O(n). За операцията inorder времевата сложност е O(n), тъй като тя посещава всички възли в дървото. За операцията за търсене времевата сложност е O(h), където h е височината на дървото, в най-лошия случай може да бъде O(n).
- Хеш таблици: Хеш таблицата е структура от данни, която съпоставя ключове със стойности. Те имат постоянна времева сложност за основни операции като вмъкване, изтриване и търсене.
Java
import java.util.HashMap;
public class HashTableExample {
public static void main(String[] args) {
// Initialize HashMap
HashMap<Integer, String> hashTable = new HashMap<>();
// Insert key-value pairs
hashTable.put(1, "Value 1");
hashTable.put(2, "Value 2");
hashTable.put(3, "Value 3");
// Search for a value using a key
String value = hashTable.get(2);
System.out.println("Value for key 2: " + value);
// Delete a key-value pair
hashTable.remove(3);
}
}
Javascript
let hashTable = new Map();
// Insert key-value pairs
hashTable.set(1, "Value 1");
hashTable.set(2, "Value 2");
hashTable.set(3, "Value 3");
// Search for a value using a key
let value = hashTable.get(2);
console.log("Value for key 2: " + value);
// Delete a key-value pair
hashTable.delete(3);
- Както в Java, така и в JavaScript, HashMap или Map се използва за реализиране на хеш таблица.
- Методът
put()илиset()се използва за вмъкване на двойки ключ-стойност в хеш-таблицата. - Методът
get()се използва за търсене на стойност с помощта на ключ. - Методът
remove()илиdelete()се използва за изтриване на двойка ключ-стойност от хеш-таблицата.
Хеш таблиците имат постоянна времева сложност за основни операции като вмъкване, изтриване и търсене.
Времевата сложност е средно O(1) за тези операции, като се приеме, че хеш функцията разпределя ключовете равномерно между кофите. Въпреки това, в най-лошия сценарий, времевата сложност може да бъде O(n), ако хеш функцията причинява голям брой сблъсъци, което води до дълга верига от ключове в една кофа.
Забележка: HashMap в Java не е безопасен за нишки и не се препоръчва за многонишкови приложения. Можете да използвате ConcurrentHashMap за безопасна за нишки версия.
- Купчини: Купчината е специален вид дървовидна структура от данни, която отговаря на свойството купчина. Свойството heap гарантира, че ключът на основния възел е или по-голям или равен на ключовете на неговите деца в max-heap, или по-малък или равен на ключовете на своите деца в min-heap. Те имат логаритмична времева сложност за основни операции като вмъкване, изтриване и извличане на max/min елемент.
- Има два вида купчини:
- Max-Heap: В max-heap ключът на основния възел е по-голям или равен на ключовете на неговите деца.
- Min-Heap: В min-heap ключът на основния възел е по-малък или равен на ключовете на неговите деца.
- Купчините могат да бъдат реализирани с помощта на масиви или свързани списъци.
- Купчините са полезни в много алгоритми като сортиране, обхождане на графики и алгоритми за най-кратък път като алгоритъма на Дейкстра.
Java:
import java.util.PriorityQueue;
public class MaxHeapExample {
public static void main(String[] args) {
// Initialize a max heap using a PriorityQueue
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// Insert elements into the heap
maxHeap.add(3);
maxHeap.add(2);
maxHeap.add(1);
// Get the maximum element
int max = maxHeap.peek();
System.out.println("Maximum element: " + max);
// Remove the maximum element
maxHeap.poll();
}
}
В Java максималната купчина се реализира с помощта на PriorityQueue с персонализиран компаратор, който сравнява елементите в обратен ред.
Javascript:
class MaxHeap {
constructor() {
this.heap = [];
}
// Insert an element into the heap
insert(val) {
this.heap.push(val);
this.siftUp();
}
// Get the maximum element
getMax() {
return this.heap[0];
}
// Remove the maximum element
removeMax() {
let max = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown();
return max;
}
// Move the last element up the heap until it's in the correct position
siftUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] > this.heap[parentIndex]) {
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
} else {
break;
}
}
}
// Move the first element down the heap until it's in the correct position
siftDown() {
let index = 0;
while (index < this.heap.length) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let largestChildIndex = index;
if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largestChildIndex]) {
largestChildIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largestChildIndex]) {
largestChildIndex = rightChildIndex;
}
if (largestChildIndex !== index) {
[this.heap[index], this.heap[largestChildIndex]] = [this.heap[largestChildIndex], this.heap[index]];
index = largestChildIndex;
} else {
break;
}
}
}
}
let maxHeap = new MaxHeap();
maxHeap.insert(3);
maxHeap.insert(2);
maxHeap.insert(1);
console.log("Maximum element: " + maxHeap.getMax());
maxHeap.removeMax();
В JavaScript максималната купчина се реализира с помощта на масив и персонализирани методи за вмъкване, премахване и поддържане на свойството на купчината.
За операцията по вмъкване времевата сложност е O(log n), тъй като трябва да пресеем вмъкнатия елемент до правилната му позиция.
За операцията по премахване времевата сложност също е O(log n), тъй като трябва да отсеем първия елемент до правилната му позиция след премахването му.
За операцията getMax времевата сложност е O(1), тъй като просто трябва да върнем първия елемент от масива, който е максималният елемент.
Кодът на min heap е подобен, като основната разлика е, че сравнителят за PriorityQueue в Java ще бъде (a, b) -› a — b, а методите siftUp и siftDown в JavaScript ще бъдат модифицирани, за да сравняват стойностите във възходящ ред ред вместо в низходящ ред.
За Min heap,
- За операцията по вмъкване времевата сложност е O(log n), тъй като трябва да пресеем вмъкнатия елемент до правилната му позиция.
- За операцията по премахване времевата сложност също е O(log n), тъй като трябва да отсеем първия елемент до правилната му позиция след премахването му.
- За операцията getMin времевата сложност е O(1), тъй като просто трябва да върнем първия елемент от масива, който е минималният елемент.
Важно е да се отбележи, че действителната времева сложност на тези операции зависи от имплементацията и не е гарантирано да бъде O(log n) в най-лошия случай, като например изкривена купчина.
- Графики: Графиката е нелинейна структура от данни, която се състои от набор от върхове и ръбове. Те са полезни за проблеми, които включват връзки между обекти. Те имат времева сложност от O(V+E) за основни операции като добавяне и премахване на връх и ръб и преминаване през графиката (DFS и BFS). Запознайте се с различни видове графики като насочени и ненасочени, претеглени и непретеглени, циклични и ациклични.
- Различните видове графики включват:
- Насочена графика: Насочената графа е графика, в която ръбовете имат посока и са представени със стрелки.
- Неориентирана графика: Неориентираната графика е графика, в която ръбовете нямат посока и са представени от линии.
- Претеглена графика: Претеглена графика е графика, в която ръбовете имат тегла или стойности, свързани с тях.
- Непретеглена графика: Непретеглена графика е графика, в която ръбовете нямат тегла или стойности, свързани с тях.
- Циклична графика: Цикличната графика е графика, която съдържа поне един цикъл.
- Ациклична графика: Ациклична графика е графика, която не съдържа цикли.
Често срещан тип графика, която често се използва за представяне на мрежи от реалния свят, е ненасочена, претеглена графика. Ето примерна реализация в Java и JavaScript за ненасочена, претеглена графика, заедно със сложността на времето за основните операции.
Java:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class WeightedGraph {
// HashMap to store the edges of the graph
private HashMap<Integer, List<Edge>> edges;
public WeightedGraph() {
this.edges = new HashMap<>();
}
// Edge class to represent an edge in the graph
private static class Edge {
int neighbor;
int weight;
public Edge(int neighbor, int weight) {
this.neighbor = neighbor;
this.weight = weight;
}
}
// Add an edge to the graph
public void addEdge(int source, int destination, int weight) {
if (!edges.containsKey(source)) {
edges.put(source, new ArrayList<>());
}
edges.get(source).add(new Edge(destination, weight));
if (!edges.containsKey(destination)) {
edges.put(destination, new ArrayList<>());
}
edges.get(destination).add(new Edge(source, weight));
}
// Get all the neighbors of a vertex
public List<Edge> getNeighbors(int vertex) {
return edges.get(vertex);
}
}
JavaScript:
class WeightedGraph {
constructor() {
this.edges = new Map();
}
// Add an edge to the graph
addEdge(source, destination, weight) {
if (!this.edges.has(source)) {
this.edges.set(source, []);
}
this.edges.get(source).push({ neighbor: destination, weight });
if (!this.edges.has(destination)) {
this.edges.set(destination, []);
}
this.edges.get(destination).push({ neighbor: source, weight });
}
// Get all the neighbors of a vertex
getNeighbors(vertex) {
return this.edges.get(vertex);
}
// Get the weight of an edge
getWeight(source, destination){
let neighbors = this.edges.get(source);
for(let neighbor of neighbors){
if(neighbor.neighbor === destination){
return neighbor.weight;
}
}
return -1;
}
// remove an edge
removeEdge(source, destination){
let neighbors = this.edges.get(source);
for(let i = 0; i < neighbors.length; i++){
if(neighbors[i].neighbor === destination){
neighbors.splice(i,1);
break;
}
}
neighbors = this.edges.get(destination);
for(let i = 0; i < neighbors.length; i++){
if(neighbors[i].neighbor === source){
neighbors.splice(i,1);
break;
}
}
}
}
- Времевата сложност на добавяне на ребро към графиката е O(1), тъй като използваме HashMap (Java) или Map (JavaScript) за съхраняване на ребра.
- Времевата сложност за получаване на съседите на връх също е O(1), тъй като ние използваме HashMap (Java) или Map (JavaScript) за съхраняване на ръбовете.
- Времевата сложност за получаване на теглото на ребро е O(n), защото в най-лошия случай трябва да преминем през всички съседи на върха.
- Времевата сложност на премахването на ребро е O(n), защото в най-лошия случай трябва да преминем през всички съседи на върха.
Важно е да се отбележи, че това е проста реализация на претеглена, неориентирана графика и има други начини за реализация на графика, като например използване на матрица на съседство или списък на съседство. Времевите сложности могат да се променят в зависимост от избраната структура на данните.
Основната разлика между този код и версията на Java е, че в Javascript използваме обект Map за съхраняване на ръбовете вместо HashMap. И двете са подобни, но начинът, по който се изпълняват е различен.
Алгоритми (задачи: липсващи примерни проблеми):
Преглед на често срещани алгоритми като сортиране (напр. бързо сортиране, сортиране чрез сливане, сортиране чрез вмъкване, сортиране с балон, сортиране по избор, сортиране в купчина), търсене (напр. линейно търсене, двоично търсене, хеш-таблица) и обхождане (напр. първо в ширина) търсене, първо търсене в дълбочина).
Алгоритми за сортиране: Алгоритмите за сортиране се използват за подреждане на даден набор от елементи в определен ред. Различните типове алгоритми за сортиране включват:
Бързо сортиране: Бързото сортиране е алгоритъм „разделяй и владей“, който избира „основен“ елемент от масива и разделя другите елементи на два подмасива, според това дали са по-малки или по-големи от въртящия се. Той има средна времева сложност на случая O(N log N)
Пример в Java:
public class QuickSort {
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}
private static void quickSort(int[] array, int left, int right) {
if (left < right) {
int pivotIndex = partition(array, left, right);
quickSort(array, left, pivotIndex - 1);
quickSort(array, pivotIndex + 1, right);
}
}
private static int partition(int[] array, int left, int right) {
int pivot = array[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, right);
return i + 1;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
В Javascript:
function quickSort(array, left, right) {
let pivot, partitionIndex;
if (left < right) {
pivot = right;
partitionIndex = partition(array, pivot, left, right);
// sort left and right
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
return array;
}
function partition(array, pivot, left, right) {
let pivotValue = array[pivot],
partitionIndex = left;
for (let i = left; i < right; i++) {
if (array[i] < pivotValue) {
swap(array, i, partitionIndex);
partitionIndex++;
}
}
swap(array, right, partitionIndex);
return partitionIndex;
}
function swap(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
Основната идея зад бързото сортиране е да се раздели масивът по такъв начин, че всички елементи, по-малки от опорната точка, да са преди всички елементи, по-големи от опорната точка. Основната точка обикновено е последният елемент на масива, но може да бъде всеки елемент. Използваме два указателя, един започващ отляво и един започващ отдясно, за да разделим масива. Ако намерим елемент отляво, който е по-голям от опорната точка, и елемент отдясно, който е по-малък от опорната точка, ние ги разменяме. След като указателите се срещнат, разменяме опорната точка с елемента в индекса на дяла и го връщаме. След това сортираме рекурсивно левия и десния дял на масива.
Времева сложност:
- Средната времева сложност на алгоритъма за бързо сортиране е O(n log n)
- Най-лошият случай на времева сложност на алгоритъма за бързо сортиране е O(n²)
Сортиране с обединяване: Сортирането с сливане е алгоритъм за разделяне и владеене, който разделя входния масив на две половини, извиква себе си за двете половини и след това обединява двете сортирани половини. Има времева сложност от O(N log N)
public class MergeSort {
public static void mergeSort(int[] array) {
mergeSort(array, 0, array.length - 1);
}
private static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
merge(array, left, middle, right);
}
}
private static void merge(int[] array, int left, int middle, int right) {
int leftSize = middle - left + 1;
int rightSize = right - middle;
int[] leftArray = new int[leftSize];
int[] rightArray = new int[rightSize];
for (int i = 0; i < leftSize; i++) {
leftArray[i] = array[left + i];
}
for (int i = 0; i < rightSize; i++) {
rightArray[i] = array[middle + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
while (i < leftSize) {
array[k] = leftArray[i];
i++;
k++;
}
while (j < rightSize) {
array[k] = rightArray[j];
j++;
k++;
}
}
}
Основната идея зад сортирането чрез сливане е да разделите масива на две половини, да сортирате всяка половина и след това да обедините отново двете сортирани половини. Функцията за сливане приема три индекса, най-левия индекс, средния индекс и най-десния индекс на частта от масива, която трябва да се обедини. След това създава два масива от дадената част от масива и ги обединява обратно по сортиран начин.
В Javascript:
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [],
leftIndex = 0,
rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length){
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
Алгоритъмът за сортиране чрез сливане в javascript използва същата основна логика като сортирането чрез сливане в java. Започва с разделяне на входния масив на две половини рекурсивно, след което сортира и слива двете половини отново заедно.
Времева сложност:
- Средната и най-лошата времева сложност на алгоритъма за сортиране чрез сливане е O(n log n)
Сортиране чрез вмъкване: Сортирането чрез вмъкване е прост алгоритъм за сортиране, който изгражда крайния сортиран масив (или списък) един по един елемент. Има времева сложност O(n^2)
Пример в Java:
public class InsertionSort {
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
В Javascript:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
Основната идея зад сортирането чрез вмъкване е да се премине през масива и за всеки елемент да се намери правилната му позиция, като се сравни с елементите, които идват преди него. След това вмъква елемента в правилната му позиция, като измества по-големите елементи надясно.
Времева сложност:
- Средната и най-лошата времева сложност на алгоритъма за сортиране на вмъкване е O(n²)
Сортиране с мехурчета: Сортирането с балончета е прост алгоритъм за сортиране, който многократно преминава през списъка за сортиране, сравнява всяка двойка съседни елементи и ги разменя, ако са в грешен ред. има времева сложност O(n^2)
В Java:
public class BubbleSort {
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}
В Javascript:
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Идеята зад балонното сортиране е многократно да се разменят съседни елементи, ако са в грешен ред. Алгоритъмът многократно преминава през масива, сравнява съседни елементи и ги разменя, ако са в грешен ред.
Времева сложност:
- Средната и най-лошата времева сложност на алгоритъма за балонно сортиране е O(n²)
Сортиране при избор: Сортирането при избор е прост алгоритъм за сортиране, който разделя входния списък на две части: сортираната част в левия край и несортираната част в десния край. Многократно избира най-малкия елемент от несортираната част и го премества в края на сортираната част. Има времева сложност O(n^2)
Пример в java:
public class SelectionSort {
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
}
В Javascript:
function selectionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
let temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
Горното многократно намира минималния елемент от несортираната част и го разменя с първия елемент на несортираната част. Той многократно намира минималния елемент от несортираната част и го разменя с първия елемент от несортираната част.
Времева сложност:
- Средната и най-лошата времева сложност на алгоритъма за сортиране на селекцията е O(n²)
Сортиране на купчина: Сортирането на купчина е базиран на сравнение алгоритъм за сортиране, който изгражда купчина от масива и след това многократно извлича максималния елемент от купчината и го поставя в края на сортирания масив. Има времева сложност от O(N log N)
Пример в java:
public class HeapSort {
public static void heapSort(int[] array) {
int n = array.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}
public static void heapify(int[] array, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && array[left] > array[largest]) {
largest = left;
}
if (right < n && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
heapify(array, n, largest);
}
}
}
В Javascript:
function heapSort(arr) {
let n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i >= 0; i--) {
let temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
Heap sort е алгоритъм за сортиране, базиран на сравнение. Heapsort може да се разглежда като подобрено сортиране на селекция: подобно на този алгоритъм, той разделя своя вход на сортиран и несортиран регион и итеративно свива несортирания регион, като извлича най-големия елемент и го премества в сортирания регион. Подобрението се състои в използването на структура от данни в купчина, а не в линейно времево търсене за намиране на максимума.
Времева сложност:
- Средната и най-лошата времева сложност на сортирането на купчина е O(n log n). Това е така, защото операцията heapify отнема O(log n) време и се изпълнява n пъти, което води до O(n log n) времева сложност.
Важно е да разберете конкретните случаи на употреба и предимствата на всеки алгоритъм за сортиране, както и тяхната времева и пространствена сложност. Също така е важно да практикувате прилагането им и да разберете кога да използвате всеки от тях въз основа на конкретния проблем и ограничения.
Алгоритми за търсене: Алгоритмите за търсене се използват за намиране на конкретен елемент или група от елементи от даден набор от елементи. Различните типове алгоритми за търсене включват:
Двоично търсене: Двоичното търсене е алгоритъм за търсене, който намира позицията на целева стойност в рамките на сортиран масив. Има времева сложност O(log n).
Пример в java:
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
В javascript:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Двоичното търсене е алгоритъм за търсене, който намира позицията на целева стойност в рамките на сортиран масив. Той многократно разделя интервала на търсене наполовина. Това е най-ефективният начин за търсене в голям сортиран масив.
Времева сложност:
- Средната и най-лошата времева сложност на двоичното търсене е O(log n). Това е така, защото с всяка итерация пространството за търсене се разделя наполовина, което води до log n итерации.
Линейно търсене: Линейното търсене е прост алгоритъм за търсене, който проверява всеки елемент от масив един по един, докато се намери целевата стойност. Има времева сложност O(n).
Пример в java:
public class LinearSearch {
public static int linearSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i;
}
}
return -1;
}
}
В Javascript:
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
Линейното търсене е прост алгоритъм за търсене, който проверява всеки елемент от масив един по един, докато се намери целевата стойност.
Времева сложност:
- Средната и най-лошата времева сложност на линейното търсене е O(n). Това е така, защото в най-лошия случай алгоритъмът трябва да премине през всички елементи в масива, за да намери целевата стойност.
Първоначално търсене в дълбочина (DFS): Първоначално търсене в дълбочина е алгоритъм за преминаване или търсене на дървовидни или графични структури от данни. Започва от корена на дървото (или някакъв произволен възел на графика, понякога наричан „ключ за търсене“) и изследва, доколкото е възможно, всеки клон, преди да се върне назад. Той има времева сложност O(V+E), където V е броят на върховете, а E е броят на ръбовете.
Пример в java:
class DFS {
private boolean[] visited;
public void dfs(Graph g, int v) {
visited[v] = true;
for (int w : g.adj(v)) {
if (!visited[w]) {
dfs(g, w);
}
}
}
}
В Javascript:
class DFS {
dfs(graph, v) {
let visited = new Array(graph.length).fill(false);
this._dfs(graph, v, visited);
}
_dfs(graph, v, visited) {
visited[v] = true;
for (let w of graph[v]) {
if (!visited[w]) {
this._dfs(graph, w, visited);
}
}
}
}
Първото търсене в дълбочина е алгоритъм за обхождане или търсене на дървовидни или графични структури от данни. Започва от корена на дървото (или някакъв произволен възел на графика, понякога наричан „ключ за търсене“) и изследва, доколкото е възможно, всеки клон, преди да се върне назад.
Времева сложност:
- Средната и най-лошата времева сложност на DFS е O(V+E), където V е броят на върховете, а E е броят на ръбовете. Това е така, защото в най-лошия случай алгоритъмът посещава всички върхове и ръбове в графиката.
Търсене в ширина (BFS): Търсене в ширина е алгоритъм за обхождане или търсене в дървовидни или графични структури от данни. Започва от корена на дървото (или някакъв произволен възел на графика) и първо изследва съседните възли, преди да премине към съседите на следващото ниво. Той има времева сложност O(V+E), където V е броят на върховете, а E е броят на ръбовете.
Пример в java:
class BFS {
public void bfs(Graph g, int v) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[g.V()];
queue.add(v);
visited[v] = true;
while (!queue.isEmpty()) {
int w = queue.poll();
for (int x : g.adj(w)) {
if (!visited[x]) {
queue.add(x);
visited[x] = true;
}
}
}
}
}
В Javascript:
class BFS {
bfs(graph, v) {
let queue = [];
let visited = new Array(graph.length).fill(false);
queue.push(v);
visited[v] = true;
while (queue.length) {
let w = queue.shift();
for (let x of graph[w]) {
if (!visited[x]) {
queue.push(x);
visited[x] = true;
}
}
}
}
}
Търсенето в ширина е алгоритъм за преминаване или търсене в дървовидни или графични структури от данни. Започва от корена на дървото (или някакъв произволен възел на графика) и първо изследва съседните възли, преди да премине към съседите на следващото ниво.
Времева сложност:
- Средната и най-лошата времева сложност на BFS е O(V+E), където V е броят на върховете, а E е броят на ръбовете. Това е така, защото в най-лошия случай алгоритъмът посещава всички върхове и ръбове в графиката. Важно е да се отбележи, че горните примери са основни реализации на алгоритмите и има различни начини за подобряване на производителността и оптимизиране на кода.
Дизайн на системата:
- Разберете основите на системния дизайн, включително разпределени системи, балансиране на натоварването и мащабируемост.
- Практикувайте проектиране на системи за различни сценарии и можете да обсъждате компромиси и взети решения.
- Разпределени системи: Разберете концепциите за разделяне, репликация и съгласуваност в разпределените системи. Запознайте се с популярни разпределени системни архитектури като архитектура на микроуслуги, архитектура, управлявана от събития, архитектура клиент-сървър и др. Разберете значението на консенсусните протоколи като Paxos, RAFT и GRPC.
- Балансиране на натоварването: Разберете различните типове балансьори на натоварването, като кръгов режим, най-малко връзки, IP хеширане и базирано на DNS балансиране на натоварването. Разберете кога да използвате всеки тип и включените компромиси.
- Мащабируемост: Разберете концепции като хоризонтално мащабиране, вертикално мащабиране и шардинг. Разберете как да проектирате системи, които могат да се справят с нарастващи количества натоварване и трафик. Запознайте се с популярни технологии за постигане на мащабируемост като балансиращи натоварването, опашки за съобщения и кеширане.
Освен това е важно да се разбере концепцията за „евентуална последователност“ в разпределените системи и различните модели на последователност, като силна последователност и слаба последователност. Запознайте се с техники за работа с мрежови дялове, като кворуми и избор на лидер.
По отношение на балансирането на натоварването също е важно да се разберат принципите на откриване на услуги и регистрация на услуги и как балансиращите на натоварването могат да използват тези техники за динамично откриване и насочване към налични услуги. Запознайте се с популярни инструменти за откриване и регистрация на услуги като Zookeeper, Consul и др.
Мащабируемостта може да бъде постигната и чрез внедряване на ефективни системи за съхранение и извличане на данни, като бази данни NoSQL и разпределени файлови системи. Разберете компромисите между последователност и наличност в разпределени бази данни и се запознайте с популярни NoSQL бази данни като MongoDB, Cassandra и Riak.
Също така е важно да разберете концепцията за автоматично мащабиране и как може да се използва за автоматично регулиране на броя на изпълняваните екземпляри на услуга въз основа на промените в търсенето. Разберете различните типове автоматично мащабиране, като хоризонтално автоматично мащабиране и вертикално автоматично мащабиране, и се запознайте с популярни инструменти за автоматично мащабиране като AWS Auto Scaling и Kubernetes.
Освен това е важно да се разберат принципите на контейнеризацията и как може да се използва за постигане на мащабируемост и надеждност чрез опаковане и внедряване на софтуер в изолирани среди. Запознайте се с популярните технологии за контейнеризация като Docker и Kubernetes.
Като цяло, за да се разберат напълно и проектират системи за мащабируемост, от съществено значение е да имате добро разбиране на основната инфраструктура и различните технологии и инструменти, които могат да се използват за постигане на скалируемост. Практикуването на проектиране на системи и обсъждането на компромиси и решения, взети с други, може значително да подобри разбирането и способността ви да проектирате мащабируеми системи.
Кодиране и решаване на проблеми:
- Упражнявайте се в писане на чист, ефективен код и решаване на проблеми с кодирането на уебсайтове като LeetCode и HackerRank. Използвайте някои от примерните проблеми, дадени в тази статия, за да преминете към въпроси със средна и висока трудност на тези уебсайтове.
Масиви
Ето пример за проблем, който може да бъде разрешен с помощта на масив:
Даден е масив от цели числа, намерете първото липсващо положително цяло число в диапазона от 1 до n+1.
В Java:
public static int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (num > 0) {
set.add(num);
}
}
for (int i = 1; i <= nums.length + 1; i++) {
if (!set.contains(i)) {
return i;
}
}
return 1;
}
В Javascript:
function firstMissingPositive(nums) {
let set = new Set();
for (let num of nums) {
if (num > 0) {
set.add(num);
}
}
for (let i = 1; i <= nums.length + 1; i++) {
if (!set.has(i)) {
return i;
}
}
return 1;
}
Това решение използва HashSet за съхраняване на положителните цели числа във входния масив. След това преминава през диапазона от 1 до n+1 и проверява дали текущото число е в набора. Ако не е, връща това число като първото липсващо положително цяло число. Ако всички числа са намерени в набора, той връща 1 като липсващото положително цяло число.
Това решение има времева сложност O(n), тъй като итерираме през масива веднъж, а методът съдържа() на HashSet има средна времева сложност O(1). Сложността на пространството е O(n), защото съхраняваме n елемента в HashSet.
Ето един възможен начин за решаване на този проблем с помощта на масив в линейно време и постоянно пространство:
Решение в Java:
public static int firstMissingPositive(int[] nums, int n) {
// mark negative numbers and numbers greater than n as -1
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = -1;
}
}
// mark the index of positive numbers as negative
for (int i = 0; i < n; i++) {
int index = Math.abs(nums[i]) - 1;
if (index < n && nums[index] > 0) {
nums[index] = -nums[index];
}
}
// find the first index with positive value
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
// if all indices are negative, return n + 1
return n + 1;
}
Функцията първо маркира отрицателни числа и числа, по-големи от n, като -1. След това маркира индекса на положителните числа като отрицателен, след това намира първия индекс с положителна стойност и го връща+1 като първото липсващо положително цяло число. Ако всички индекси са отрицателни, функцията връща n + 1.
Тази функция има времева сложност O(n), защото обхожда масива два пъти и пространствена сложност O(1), защото използва само постоянно количество допълнително пространство за съхраняване на няколко променливи.
Тук се използва масив за решаване на проблема, тъй като проблемът изисква промяна на стойността на елемента на масива, а основните операции на масива като индексиране и итерация са O(1) в Java, което го прави подходяща структура от данни за решаване на проблема.
Ето го в Javascript:
function firstMissingPositive(nums) {
let n = nums.length;
for (let i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = -1;
}
}
for (let i = 0; i < n; i++) {
let index = Math.abs(nums[i]) - 1;
if (index < n && nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (let i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
Работи по същия начин като версията на Java, първо маркира отрицателни числа и числа, по-големи от n като -1, след това маркира индекса на положителните числа като отрицателен и намира първия индекс с положителна стойност и го връща
Упражнявайте повече проблеми с масиви! https://leetcode.com/tag/array/
Свързани списъци
Свързан списък може да се използва за различни проблеми, един често срещан пример би бил прилагането на кеш.
Кешът е малка и бърза памет, която съхранява наскоро достъпни данни, така че бъдещите заявки да могат да се обслужват по-бързо. Свързан списък може да се използва за внедряване на най-малко използван кеш (LRU), където най-малко използваните елементи се премахват, когато кешът достигне максималния си размер.
Ето един възможен начин за внедряване на основен LRU кеш с помощта на единично свързан списък и HashMap в Java:
import java.util.HashMap;
public class LRUCache<K, V> {
private int maxSize;
private HashMap<K, Node<K, V>> map = new HashMap<>();
private Node<K, V> head;
private Node<K, V> tail;
public LRUCache(int maxSize) {
this.maxSize = maxSize;
}
public void put(K key, V value) {
Node<K, V> node = new Node<>(key, value);
if (map.containsKey(key)) {
remove(map.get(key));
} else if (map.size() == maxSize) {
remove(tail);
}
addToHead(node);
map.put(key, node);
}
public V get(K key) {
if (!map.containsKey(key)) {
return null;
}
Node<K, V> node = map.get(key);
remove(node);
addToHead(node);
return node.value;
}
private void addToHead(Node<K, V> node) {
node.next = head;
if (head != null) {
head.prev = node;
}
head = node;
if (tail == null) {
tail = node;
}
}
private void remove(Node<K, V> node) {
map.remove(node.key);
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (node == head) {
head = node.next;
}
if (node == tail) {
tail = node.prev;
}
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
Това внедряване използва HashMap за бързо търсене на възлите в свързания списък по ключ и двойно свързан списък за ефективно преместване на възли в началото на списъка, когато са достъпни (за да ги направи най-скоро използваните) и премахване на най-малко наскоро използвани възли, когато кешът е пълен.
Времевата сложност на основните операции като get и put е средно O(1), което е ключово предимство на използването на HashMap, а пространствената сложност е O(n), където n е броят на елементите в кеша. Времевата сложност за основни операции като поставяне и получаване е средно O(1), което е ключово предимство на използването на HashMap, а пространствената сложност е O(n), където n е броят на елементите в кеша.
Струва си да се отбележи, че в метода put, когато ключ вече съществува в кеша, ние премахваме стария възел и добавяме новия в началото на списъка. В метода get, когато ключът бъде намерен в кеша, ние премахваме възела и го добавяме отново към началото на списъка, това помага да се поддържа редът на най-скоро използваните елементи.
Освен това, когато кешът достигне максималния си размер, ние премахваме последния възел в свързания списък (най-малко използвания възел), използвайки метода за премахване, който е O(1), тъй като имаме препратка към последния възел.
Това е само един пример за това как може да се използва свързан списък, но свързаните списъци могат да се използват и при други проблеми, като поддържане на списък с операции за отмяна/възвръщане, внедряване на проста база данни и много други случаи на употреба.
Решение в Javascript:
class LRUCache {
constructor(maxSize) {
this.maxSize = maxSize;
this.map = new Map();
this.head = null;
this.tail = null;
}
put(key, value) {
if (this.map.has(key)) {
this.remove(this.map.get(key));
} else if (this.map.size === this.maxSize) {
this.remove(this.tail);
}
const node = { key, value };
this.addToHead(node);
this.map.set(key, node);
}
get(key) {
if (!this.map.has(key)) {
return null;
}
const node = this.map.get(key);
this.remove(node);
this.addToHead(node);
return node.value;
}
addToHead(node) {
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node;
}
}
remove(node) {
this.map.delete(node.key);
if (node.prev) {
node.prev.next = node.next;
}
if (node.next) {
node.next.prev = node.prev;
}
if (node === this.head) {
this.head = node.next;
}
if (node === this.tail) {
this.tail = node.prev;
}
}
}
Това внедряване използва JavaScript карта за бързо търсене на възлите в свързания списък по ключ и единично свързан списък за ефективно преместване на възли в началото на списъка, когато се осъществи достъп до тях (за да ги направи най-скоро използваните) и премахване на най-малко използваните възли, когато кешът е пълен.
Времевата сложност на основните операции като get и put е средно O(1), което е ключово предимство на използването на Map, а пространствената сложност е O(n), където n е броят на елементите в кеша.
Струва си да се отбележи, че в метода put, когато ключ вече съществува в кеша, ние премахваме стария възел и добавяме новия в началото на списъка. В метода get, когато ключът бъде намерен в кеша, ние премахваме възела и го добавяме отново към началото на списъка, това помага да се поддържа редът на най-скоро използваните елементи.
Освен това, когато кешът достигне максималния си размер, ние премахваме последния възел в свързания списък (най-малко използвания възел), използвайки метода за премахване, който е O(1), тъй като имаме препратка към последния възел.
Това е само един пример за това как може да се използва свързан списък за внедряване на LRU кеш, но има и други начини за прилагането му, например използване на двойно свързан списък, масив или дори комбинация от структури от данни.
Още проблеми със свързания списък! https://leetcode.com/tag/linked-list/
Стек
Стекътможе да бъде полезен при различни проблеми, но един често срещан пример е при анализиране на изрази и валидиране на съвпадението на скобите.
Например, разгледайте следните изрази:
(1 + 2) * 3(1 + 2(1 + 2)) * 3
Първият израз е добре оформен, тъй като скобите са правилно съпоставени. Вторият и третият израз не са добре оформени, тъй като има отворена или затворена скоба, която няма съответстващ аналог.
Ето един възможен начин да проверите дали даден израз е добре формиран с помощта на стек:
public static boolean isValidExpression(String expr) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < expr.length(); i++) {
char c = expr.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
Функцията итерира всеки знак в израза, ако е отворена скоба, тя го избутва в стека, ако е затворена скоба, проверява дали стекът е празен или не, ако не е празен, изважда елемент. В края на итерацията, ако стекът е празен, това означава, че е валиден израз, в противен случай не е.
Тази функция ще върне true за първия пример, false за втория пример и false за третия пример.
И ето го в Javascript:
function isValidExpression(expression) {
const stack = new Stack();
for (let i = 0; i < expression.length; i++) {
let char = expression[i];
if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else if (char === ')' || char === ']' || char === '}') {
if (stack.isEmpty()) {
return false;
}
let top = stack.pop();
if ((char === ')' && top !== '(') ||
(char === ']' && top !== '[') ||
(char === '}' && top !== '{')) {
return false;
}
}
}
return stack.isEmpty();
}
Времевата сложност на тази функция е O(n), тъй като тя преминава през целия израз веднъж, а пространствената сложност също е O(n), тъй като в най-лошия случай избутва всички скоби в стека.
Още стекови въпроси! https://leetcode.com/tag/stack/
Опашки
Дадена е 2D решетка от цели числа, като всяка стойност представлява височината на клетка и списък с инструкции за робот за навигация в мрежата. Роботът може да се движи само нагоре, надолу, наляво или надясно и може да се движи само до клетка с височина, по-малка или равна на текущата клетка. Роботът започва от горния ляв ъгъл на мрежата и трябва да стигне до долния десен ъгъл.
Един от начините за решаване на този проблем би бил да се използва алгоритъм за търсене в ширина (BFS) с опашка. Алгоритъмът BFS изследва мрежата, като посещава всички клетки, които са достъпни от началната клетка в широк ред, т.е. посещава всички клетки на дадено ниво, преди да премине към следващото ниво.
Java:
public boolean navigate(int[][] grid, int[] start, int[] end) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == end[0] && curr[1] == end[1]) {
return true;
}
for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] <= grid[curr[0]][curr[1]] && !visited[x][y]) {
queue.offer(new int[] {x, y});
visited[x][y] = true;
}
}
}
return false;
}
В Javascript:
public boolean navigate(int[][] grid, int[] start, int[] end) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == end[0] && curr[1] == end[1]) {
return true;
}
for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] <= grid[curr[0]][curr[1]] && !visited[x][y]) {
queue.offer(new int[] {x, y});
visited[x][y] = true;
}
}
}
return false;
}
Тази функция приема 2D решетка от цели числа, начална точка, представена от масив с дължина 2, и крайна точка, представена от масив с дължина 2. Тя използва опашка, за да следи клетките, които ще бъдат посетени следващите, и a 2D булев масив за проследяване на посетените клетки. Той също така използва масив от посоки, за да провери клетките в четирите кардинални посоки.
В тази реализация използваме опашка за съхраняване на клетките, които трябва да бъдат посетени следващите, и набор за проследяване на посетените клетки. Ние също така използваме масив от упътвания, за да проверим всички възможни ходове от текущата клетка. Започваме с добавяне на началната клетка към опашката и посетения набор. След това използваме цикъл while, за да продължим да обикаляме мрежата, докато опашката се изпразни или се достигне крайната клетка. За всяка итерация вземаме първата клетка от опашката, проверяваме дали това е крайната клетка и ако не е, проверяваме всички възможни ходове от тази клетка. Ако дадено преместване е валидно (т.е. в границите на мрежата и към клетка с височина по-малка или равна на текущата клетка), ние го добавяме към опашката и посетения набор. Ако бъде достигната крайната клетка, връщаме true, в противен случай връщаме false.
Времевата сложност на това решение е O(n * m), където n е броят на редовете в мрежата, а m е броят на колоните в мрежата. Това е така, защото за всяка клетка в мрежата алгоритъмът проверява всички съседни клетки, за да намери следващата най-добра клетка, към която да се придвижи. Сложността на пространството също е O(n * m), тъй като използва опашка за съхраняване на клетките, които трябва да бъдат посетени, и 2D мрежа за съхраняване на височината на всяка клетка.
Още въпроси на опашка! https://leetcode.com/tag/queue/
Дърво
Примерен проблем за интервю с дърво би бил:
При дадено двоично дърво, върнете обхождането на реда на нива на стойностите на възлите му. (т.е. отляво надясно, ниво по ниво).
Например: Дадено е двоично дърво [3,9,20, null, null,15,7],
3
/
9 20
/
15 7
връща неговото преминаване на реда на ниво като:
[ [3], [9,20], [15,7] ]
Решение в java:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
currentLevel.add(currentNode.val);
if (currentNode.left != null) {
queue.add(currentNode.left);
}
if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
result.add(currentLevel);
}
return result;
}
}
Решение в javascript:
const levelOrder = (root) => {
if (!root) return [];
let queue = [root], result = [], level;
while (queue.length) {
level = queue.length;
let currentLevel = [];
for (let i = 0; i < level; i++) {
let currentNode = queue.shift();
currentLevel.push(currentNode.val);
if (currentNode.left) queue.push(currentNode.left);
if (currentNode.right) queue.push(currentNode.right);
}
result.push(currentLevel);
}
return result;
}
В това решение използваме опашка, за да преминем през дървото по начин BFS. Започваме с добавяне на основния възел към опашката и докато опашката не е празна, вземаме размера на опашката, който представлява броя на възлите на текущото ниво. След това преминаваме през нивото, премахваме възела от опашката, добавяме го към текущия списък с нива и добавяме неговите деца към опашката, ако съществуват. Повтаряме този процес, докато опашката се изпразни.
Това решение използва опашка за преминаване през дървото по начин на търсене в ширина, което означава, че изследва всички възли на едно и също ниво, преди да премине към следващото ниво. Това ни позволява да получим обхождането на реда на нивата на дървото.
Времевата и пространствената сложност на този алгоритъм е O(n), където n е броят на възлите в дървото.
Друг!
Дадено е двоично дърво и целева стойност, определете най-близката стойност в дървото до целевата стойност.
Един от начините за решаване на този проблем е да преминете през дървото в ред и да сравните всяка стойност с целевата стойност, като следите най-близката стойност, намерена досега.
Ето примерна реализация в Java:
public class ClosestValue {
public static int closestValue(TreeNode root, int target) {
int closest = root.val;
while (root != null) {
if (Math.abs(root.val - target) < Math.abs(closest - target)) {
closest = root.val;
}
if (root.val < target) {
root = root.right;
} else if (root.val > target) {
root = root.left;
} else {
break;
}
}
return closest;
}
}
В JavaScript:
function closestValue(root, target) {
let closest = root.val;
while (root) {
if (Math.abs(root.val - target) < Math.abs(closest - target)) {
closest = root.val;
}
if (root.val < target) {
root = root.right;
} else if (root.val > target) {
root = root.left;
} else {
break;
}
}
return closest;
}
Решението на този проблем включва преминаване през BST и сравняване на стойността на текущия възел с целевата стойност. Ако стойността на текущия възел е равна на целевата стойност, тогава можем да върнем тази стойност като най-близката стойност. Ако стойността на текущия възел е по-малка от целевата стойност, отиваме в дясното поддърво и ако стойността на текущия възел е по-голяма от целевата стойност, отиваме в лявото поддърво. Този процес продължава, докато се намери най-близката стойност. Времевата сложност на тази операция е O(h), където h е височината на дървото, а пространствената сложност е O(1), тъй като не използваме допълнителна памет, различна от рекурсивния стек.
Времевата сложност на решението е O(h), където h е височината на дървото, в най-лошия случай може да бъде O(n). Пространствената сложност на решението е O(1), тъй като ние използваме само променлива, за да следим най-близката стойност, намерена досега.
Още проблеми с дърветата! https://leetcode.com/tag/tree/
Хеш таблици
Един често срещан проблем с интервюто, който може да бъде решен с хеш-таблица, е проблемът „две суми“.
Даден е масив от цели числа и целева стойност, определете дали има две цели числа в масива, които се събират до целевата стойност.
Един от начините за решаване на този проблем е да се използва хеш-таблица за съхраняване на елементите в масива като ключове и техните индекси като стойности. След това за всеки елемент в масива проверете дали целевата стойност минус текущия елемент е в хеш-таблицата. Ако е така, тогава има двойка цели числа, които се събират до целевата стойност.
Ето примерна реализация в Java:
import java.util.HashMap;
public class TwoSum {
public static int[] findTwoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashTable = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (hashTable.containsKey(complement)) {
return new int[] { hashTable.get(complement), i };
}
hashTable.put(nums[i], i);
}
return new int[] {-1,-1};
}
}
В Javascript:
function findTwoSum(nums, target) {
let hashTable = new Map();
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (hashTable.has(complement)) {
return [hashTable.get(complement), i];
}
hashTable.set(nums[i], i);
}
return [-1,-1];
}
Времевата сложност на решението е O(n), тъй като итерираме през масива веднъж и за всеки елемент извършваме операция с постоянно време (поставяне или получаване) на хеш-таблицата.
Пространствената сложност на решението е O(n), тъй като съхраняваме всички n елемента в хеш-таблицата.
И двете решения са много сходни, основната разлика е, че в javascript използваме обект Map вместо HashMap, както в Java, но основната идея зад решението е същата, използването на хеш таблица за съхраняване на елементите
Още проблеми с хеш-таблицата! https://leetcode.com/tag/hash-table/
Купища
Един класически проблем, който може да бъде решен с помощта на min-heap, е проблемът „Намерете k-тия най-малък елемент в несортиран масив“.
Даден е несортиран масив от n елемента и цяло число k, намерете k-тия най-малък елемент в масива.
Един от начините за решаване на този проблем е използването на min-heap. Основната идея е първо да вмъкнете първите k елемента от масива в min heap. След това за всеки оставащ елемент в масива го сравнете с минималния елемент в купчината. Ако текущият елемент е по-малък от минималния елемент, премахнете минималния елемент от купчината и вмъкнете текущия елемент. След като всички елементи са обработени, минималният елемент в купчината е k-тият най-малък елемент в масива.
Ето примерна реализация в Java:
import java.util.PriorityQueue;
public class KthSmallest {
public static int findKthSmallest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// insert the first k elements into the heap
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
// for each remaining element in the array
for (int i = k; i < nums.length; i++) {
// if the current element is smaller than the minimum element in the heap
if (nums[i] < minHeap.peek()) {
// remove the minimum element from the heap
minHeap.poll();
// insert the current element into the heap
minHeap.add(nums[i]);
}
}
// the minimum element in the heap is the kth smallest element in the array
return minHeap.peek();
}
}
В Javascript:
function findKthSmallest(nums, k) {
let minHeap = new MinHeap();
// insert the first k elements into the heap
for (let i = 0; i < k; i++) {
minHeap.insert(nums[i]);
}
// for each remaining element in the array
for (let i = k; i < nums.length; i++) {
// if the current element is smaller than the minimum element in the heap
if (nums[i] < minHeap.getMin()) {
// remove the minimum element from the heap
minHeap.removeMin();
// insert the current element into the heap
minHeap.insert(nums[i]);
}
}
// the minimum element in the heap is the kth smallest element in the array
return minHeap.getMin();
}
Времева сложност:
- Операциите за вмъкване и премахване в min heap имат времева сложност от O(log k)
- Времевата сложност на итерация през масива е O(n)
- Следователно общата времева сложност на това решение е O(n log k)
Пространствената сложност на това решение е O(k), тъй като трябва да съхраним k елемента в min heap
Този проблем може да бъде решен и с максимална купчина чрез обръщане на реда на елементите и намиране на k-тия най-голям елемент в масива.
Още проблеми с купчина! https://leetcode.com/tag/heap/
Графики
При дадена претеглена графа, начален връх и целеви връх, намерете най-краткия път от началния връх до целевия връх.
Един от начините за решаване на този проблем е да се използва алгоритъмът за най-краткия път на Дейкстра, който е добре известен алгоритъм за намиране на най-краткия път в претеглена графика. Основната идея на алгоритъма е да следи най-късото разстояние от началния връх до всеки връх в графиката и да актуализира най-късото разстояние, ако бъде намерен по-къс път.
Ето примерна реализация в Java:
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Dijkstra {
public static Map<Integer, Integer> shortestPath(WeightedGraph graph, int start) {
Map<Integer, Integer> distances = new HashMap<>();
PriorityQueue<Vertex> queue = new PriorityQueue<>();
queue.add(new Vertex(start, 0));
while (!queue.isEmpty()) {
Vertex vertex = queue.poll();
if (distances.containsKey(vertex.id)) {
continue;
}
distances.put(vertex.id, vertex.distance);
for (WeightedGraph.Edge edge : graph.getNeighbors(vertex.id)) {
if (!distances.containsKey(edge.neighbor)) {
queue.add(new Vertex(edge.neighbor, vertex.distance + edge.weight));
}
}
}
return distances;
}
private static class Vertex implements Comparable<Vertex> {
int id;
int distance;
public Vertex(int id, int distance) {
this.id = id;
this.distance = distance;
}
@Override
public int compareTo(Vertex other) {
return Integer.compare(this.distance, other.distance);
}
}
}
В тази реализация използвах класа WeightedGraph, който предоставих по-рано, за да съхраня ръбовете на графиката и приоритетна опашка за ефективно намиране на върха с най-малко разстояние. Алгоритъмът започва с инициализиране на карта за съхраняване на най-късото разстояние от началния връх до всеки връх в графиката и след това добавяне на началния връх към опашката с приоритети. След това алгоритъмът многократно извлича върха с най-малкото разстояние от приоритетната опашка, актуализира разстоянието на неговите съседи, ако бъде намерен по-къс път, и добавя своите съседи към приоритетната опашка.
Времева сложност:
- Времевата сложност на алгоритъма за най-краткия път на Дейкстра, използващ класа
WeightedGraph, е O(E + V log V), където E е броят на ръбовете, а V е броят на върховете. Това е така, защото използваме приоритетна опашка, за да намерим ефективно върха с най-малкото разстояние, което отнема O(log V) време за всяка операция за извличане на минути и извършваме тази операция V пъти. Освен това итерираме всички ръбове веднъж, което отнема O(E) време.
В Javascript:
class Dijkstra {
static shortestPath(graph, start) {
let distances = new Map();
let heap = new MinHeap((a,b) => a[1] - b[1]);
heap.push([start, 0]);
while (heap.size() > 0) {
let [vertex, distance] = heap.pop();
if (distances.has(vertex)) {
continue;
}
distances.set(vertex, distance);
for (let {neighbor, weight} of graph.getNeighbors(vertex)) {
if (!distances.has(neighbor)) {
heap.push([neighbor, distance + weight]);
}
}
}
return distances;
}
}
Времевата сложност на алгоритъма за най-краткия път на Dijkstra, използващ класа WeightedGraph и min heap в JavaScript, е O(E + V log V), където E е броят на ръбовете, а V е броят на върховете. Това е така, защото използваме min heap, за да намерим ефективно върха с най-малкото разстояние, което отнема O(log V) време за всяка операция за извлечение-min и извършваме тази операция V пъти. Освен това итерираме всички ръбове веднъж, което отнема O(E) време.
Езикови съвети и трикове
Този раздел ще се съсредоточи върху някои съвети за тези, които не се чувстват добре с Java или Javascript
Съвети за Java:
Java Streams: Java 8 представи Stream API, който позволява операции във функционален стил върху колекции от елементи. Потоците предоставят по-ефективен и четим начин за извършване на операции като филтриране, картографиране и намаляване. Ето пример за използване на API на Stream за филтриране на списък от цели числа и поставяне на квадрат на всеки елемент
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> squares = numbers.stream()
.filter(n -> n % 2 == 0)
.map(n -> n * n)
.collect(Collectors.toList());
Това е по-добро от традиционния подход for-loop, тъй като е по-четлив и може да се възползва от многоядрените архитектури за подобрена производителност.
Java Optional: Java въведе класа Optional в Java 8, който се използва за представяне на незадължителна стойност. Това може да се използва за предотвратяване на изключения с нулев указател. Ето пример за използване на Optional за безопасен достъп до елемент в списък
List<Integer> numbers = Arrays.asList(1, 2, 3);
Optional<Integer> result = numbers.stream()
.filter(n -> n > 2)
.findFirst();
Това е по-добро от традиционните нулеви проверки, тъй като прави кода по-четлив и елиминира необходимостта от множество нулеви проверки.
Java Lambda Expressions: Java 8 въведе ламбда изрази, които позволяват кратък код във функционален стил. Ето пример за използване на ламбда израз за сортиране на списък от цели числа:
List<Integer> numbers = Arrays.asList(3, 2, 1); numbers.sort((a, b) -> a - b);
Това е по-четливо и по-ефективно от използването на традиционни анонимни вътрешни класове.
Java Generics: Java въведе генерични кодове в Java 5, което позволява колекции с безопасен тип и подобрена повторна употреба на кода. Ето пример за използване на общ клас за създаване на стек от цели числа
public class Stack<T> {
private List<T> items;
public Stack() {
items = new ArrayList<>();
}
public void push(T item) {
items.add(item);
}
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return items.remove(items.size() - 1);
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return items.get(items.size() - 1);
}
public boolean isEmpty() {
return items.isEmpty();
}
}
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.pop(); // 2
Това е по-безопасно за типа и ефикасно от използването на негенерични класове като традиционния клас Stack.
CompletableFuture: Java 8 въведе класа CompletableFuture, който позволява лесното създаване и съставяне на асинхронни задачи. Ето пример за използване на CompletableFuture за извличане на данни от два различни URL адреса паралелно и след това комбиниране на резултатите
CompletableFuture<String> fetchData1 = CompletableFuture.supplyAsync(() -> fetch("https://example.com/data1"));
CompletableFuture<String> fetchData2 = CompletableFuture.supplyAsync(() -> fetch("https://example.com/data2"));
CompletableFuture<String> combinedData = fetchData1.thenCombine(fetchData2, (data1, data2) -> data1 + data2);
Това е по-ефективно и управляемо от използването на традиционни функции за обратно извикване или нишки.
Обработка на анотации: Java позволява използването на анотации, които могат да се използват за добавяне на метаданни към вашия код. Обработката на анотации позволява обработката на анотации по време на компилиране, което може да се използва за генериране на код или изпълнение на други задачи.
Да предположим, че имаме приложение, което се занимава със служители и искаме да проследим датата на създаване за всеки служител. Можем да създадем анотация, наречена @TrackCreation, която ще използваме, за да маркираме класовете, които искаме да проследяваме.
Ето пример за анотацията @TrackCreation:
@Retention(RetentionPolicy.SOURCE)
@Target(ElementType.TYPE)
public @interface TrackCreation {
}
Тази анотация ще се запази само на ниво източник и може да се прилага към класове.
Ето пример за използване на анотацията в клас:
@TrackCreation
public class Employee {
// class implementation
}
Сега ще създадем процесор за анотации, който ще обработва анотацията @TrackCreation и ще генерира необходимия код за проследяване на датата на създаване. Ето пример за изпълнение на процесора за анотация:
@SupportedAnnotationTypes("com.example.annotations.TrackCreation")
public class TrackCreationProcessor extends AbstractProcessor {
@Override
public boolean process(Set<? extends TypeElement> annotations, RoundEnvironment roundEnv) {
for (TypeElement annotation : annotations) {
for (Element element : roundEnv.getElementsAnnotatedWith(annotation)) {
// Get the class name
TypeElement classElement = (TypeElement) element;
String className = classElement.getSimpleName().toString();
// Create the field
FieldSpec field = FieldSpec.builder(Date.class, "creationDate")
.addModifiers(Modifier.PRIVATE)
.build();
// Create the constructor
MethodSpec constructor = MethodSpec.constructorBuilder()
.addModifiers(Modifier.PUBLIC).addStatement("this.$N = new Date()", "creationDate").build();
// Add the field and constructor to the class
TypeSpec updatedClass = TypeSpec.classBuilder(className).addModifiers(Modifier.PUBLIC).addField(field).addMethod(constructor).build();
// Write the updated class to a file
JavaFile javaFile = JavaFile.builder("com.example", updatedClass).build();
try {
javaFile.writeTo(processingEnv.getFiler());
} catch (IOException e) {
e.printStackTrace();
}
}
}
return true;
}
}
Този процесор ще обработва класовете, които са анотирани с `@TrackCreation` и ще добавя частно поле `creationDate` от тип `Date` и конструктор, който го инициализира с текущата дата към класа.
Този пример демонстрира как обработката на анотации може да се използва за генериране на код и добавяне на функционалност към вашите класове, без да се налага ръчно да пишете кода. Това може да бъде полезно, когато работите с големи кодови бази или когато искате да автоматизирате повтарящи се задачи.
Съвети за Javascript:
Деструктуриране на JavaScript:Деструктурирането на JavaScript ви позволява да извличате стойности от масиви или обекти и да ги присвоявате на променливи. Ето пример за деструктуриране на масив
let numbers = [1, 2, 3]; let [a, b, c] = numbers; console.log(a); // 1 console.log(b); // 2 console.log(c); // 3
Оператор за разпространение на JavaScript: JavaScript въведе оператора за разпространение в ES6, който ви позволява да разпространявате елементите на масив или обект в нов масив или обект. Ето пример за използване на оператора spread за свързване на масиви
let numbers1 = [1, 2, 3]; let numbers2 = [4, 5, 6]; let numbers3 = [...numbers1, ...numbers] console.log(numbers3); //[1, 2, 3, 4, 5, 6]
JavaScript Async/Await: JavaScript въведе синтаксиса async/await в ES2017, което позволява по-четлив и управляем асинхронен код. Ето пример за използване на async/await за изчакване за разрешаване на обещание
async function getData() {
let result = await fetch('https://example.com/data');
let data = await result.json();
console.log(data);
}
Това е по-разбираемо и управляемо от използването на традиционни функции за обратно извикване или верижно обещание.
JavaScript Map: Вграденият в JavaScript метод за карта ви позволява да създадете нов масив с резултатите от извикване на предоставена функция за всеки елемент в извикващия масив. Ето пример за използване на map за удвояване на стойностите на масив:
let numbers = [1, 2, 3, 4, 5]; let doubleNumbers = numbers.map(number => number * 2); console.log(doubleNumbers); // [2, 4, 6, 8, 10]
Филтър на JavaScript: Вграденият филтърен метод на JavaScript ви позволява да създадете нов масив с всички елементи, които преминават теста, реализиран от предоставената функция. Ето пример за използване на филтър за включване само на четни числа в масив:
let numbers = [1, 2, 3, 4, 5]; let evenNumbers = numbers.filter(number => number % 2 === 0); console.log(evenNumbers); // [2, 4]
Също така е важно да се запознаете със специфичните технологии и езици за програмиране, които са подходящи за позицията, за която кандидатствате, както и всички специфични за индустрията знания, които може да са необходими. Не забравяйте, че най-добрият начин да се подготвите е чрез практика и опит в реалния свят.
