Apa sing ditakoni ing wawancara: review algoritma, bagean 1

sugeng sonten sedaya! Macem-macem jinis algoritma digunakake ing proyek luwih kerep tinimbang sing sampeyan pikirake. Contone, kita kudu ngurutake sawetara data miturut paramèter tartamtu (kolom) supaya bisa navigasi tanpa gaweyan. Mulane, ora ana sing aneh yen sajrone wawancara kerja bisa ditakoni babagan siji utawa algoritma dhasar liyane, lan bisa uga diwenehi tugas kanggo ngetrapake nggunakake kode. Lan amarga sampeyan ana ing situs iki, aku bakal ngira manawa sampeyan nulis ing basa Jawa. Mulane, dina iki aku ngajak sampeyan kanggo familiarize dhewe karo sawetara algoritma dhasar lan conto tartamtu saka implementasine ing Jawa. Miturut sawetara maksudku:

1. Ringkesan algoritma ngurutake array:
   • jinis gelembung,
   • jinis pilihan,
   • urut-urutan sisipan,
   • Jenis cangkang,
   • urut cepet,
   • nggabung urut.
2. Algoritma rakus.
3. Algoritma Pathfinding:
   • crawling ing jero
   • nyusup amba.
4. Algoritma transportasi yaiku algoritma Dijkstra.

Inggih, tanpa ado maneh, ayo padha mudhun menyang bisnis.

1. Ringkesan algoritma ngurutake

Urut gelembung

Algoritma ngurutake iki dikenal utamane amarga kesederhanaan, nanging ing wektu sing padha nduweni kecepatan eksekusi sing paling murah. Contone, nimbang urutan gelembung kanggo nomer ing urutan munggah. Ayo bayangake rantai nomer sing diselehake kanthi acak, sing bakal ditindakake langkah-langkah ing ngisor iki, diwiwiti saka wiwitan rantai:

• mbandhingaké rong nomer;
• yen nomer ing sisih kiwa luwih gedhe, banjur ganti;
• mindhah siji posisi menyang tengen.

Sawise ngliwati kabeh rantai lan nindakake langkah kasebut, kita bakal nemokake manawa nomer paling gedhe ana ing pungkasan seri nomer. Sabanjure, pass sing padha ing sadawane ranté ditindakake, miturut langkah-langkah sing diterangake ing ndhuwur. Nanging wektu iki kita ora bakal kalebu unsur pungkasan saka dhaftar, awit iku paling gedhe lan wis ing Panggonan pungkasan, minangka ngirim. Maneh, kita bakal entuk unsur pungkasan ing pungkasan seri nomer kasebut. Dadi, rong nomer paling gedhe bakal ana ing papan kasebut. Lan maneh wacana ing sadawane ranté diwiwiti, ora kalebu unsur-unsur sing wis ana, nganti kabeh unsur ana ing urutan sing dibutuhake. Ayo katon ing implementasine saka bubble sort ing kode Jawa:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

Kaya sing sampeyan ngerteni, ora ana sing rumit ing kene, lan kabeh katon apik, yen ora siji "nanging" ... Urut gelembung alon banget, kanthi kerumitan wektu O(N²) , amarga kita wis nested. puteran. Eksternal liwat unsur ditindakake kaping N , sing internal uga kaping N , lan minangka asil, kita entuk iterasi N*N , N² . Sampeyan bisa sinau jinis ngurutake iki kanthi luwih rinci ing artikel iki .

Ngurutake miturut pilihan

Algoritma iki padha karo urutan gelembung, nanging kerjane luwih cepet. Maneh, minangka conto, ayo njupuk seri nomer sing arep kita atur ing urutan munggah. Inti saka algoritma punika sequentially liwat kabeh nomer lan pilih unsur paling cilik, kang njupuk lan ngganti panggonan karo unsur kiwa (0 unsur). Ing kene kita entuk kahanan sing padha karo urutan gelembung, nanging ing kasus iki unsur sing diurutake bakal dadi sing paling cilik. Mulane, pass sabanjure liwat unsur bakal diwiwiti karo unsur ing indeks 1. Maneh, pass iki bakal bola nganti kabeh unsur diurutake. Implementasine ing Jawa:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Algoritma iki luwih unggul tinimbang ngurutake gelembung, amarga ing kene jumlah permutasi sing dibutuhake dikurangi saka O(N²) dadi O(N): kita ora nyurung siji unsur ing kabeh dhaptar, nanging jumlah perbandingan tetep O (N²). ) . Kanggo sing pengin sinau luwih lengkap babagan algoritma iki, aku nyaranake materi iki .

Urut selipan

Sapisan maneh, minangka conto, ayo njupuk seri nomer sing arep kita atur ing urutan munggah. Algoritma iki kalebu nempatake panandha, ing sisih kiwa unsur-unsur kasebut bakal diurutake ing antarane. Ing saben langkah algoritma, salah sawijining unsur bakal dipilih lan diselehake ing posisi sing dikarepake ing urutan sing wis diurutake. Dadi bagean sing diurutake bakal terus berkembang nganti kabeh unsur wis katon. Sampeyan bisa uga takon: ing ngendi aku bisa entuk bagean saka unsur sing wis diurut lan sawise sampeyan kudu menehi tandha? Nanging susunan unsur pisanan wis diurutake, ta? Ayo ndeleng implementasine ing Jawa:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Jinis ngurutake iki luwih unggul tinimbang sing diterangake ing ndhuwur, amarga sanajan kasunyatane wektu mlaku padha - O(N²) , algoritma iki kerjane kaping pindho luwih cepet tinimbang ngurutake gelembung lan rada luwih cepet tinimbang ngurutake pilihan. Waca liyane kene .

Urut cangkang

Urut iki, miturut sifate, minangka jinis sisipan sing diowahi. Apa sing dakkandhakake? Ayo budhal. A langkah dipilih, lan ana akeh pendekatan kanggo pilihan iki. Kita ora bakal nerangake masalah iki kanthi rinci. Ayo dibagi dadi setengah lan entuk nomer tartamtu - iki bakal dadi langkah kita. Dadi, yen kita duwe 9 unsur ing array, langkah kita bakal dadi 9/2 = 4.5 . Kita mbuwang bagean pecahan lan entuk 4 , amarga indeks array mung integer. Kanthi langkah iki kita bakal nggawe sambungan kanggo grup kita. Yen unsur duwe indeks 0, mula indeks unsur sabanjure ing klompoke yaiku 0+4 , yaiku 4 . Unsur katelu bakal duwe indeks 4+4 , sing kaping papat duwe indeks 8+4 , lan liya-liyane. Kanggo klompok kapindho, unsur pisanan bakal dadi 1,5,9…. Ing klompok katelu lan kaping papat, kabeh bakal padha. Akibaté, saka larik nomer {6,3,8,8,6,9,4,11,1} entuk papat klompok: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Padha tetep panggonan ing array umum, nanging kanggo kita padha ditandhani minangka anggota saka grup padha: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Salajengipun wonten ing grup menika wonten urut-urutan sisipan , sasampunipun kelompok kasebut kadosta: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Ing array umum, sel sing dikuwasani dening klompok, bakal tetep padha, nanging urutan ing jerone bakal owah, miturut urutan klompok ing ndhuwur: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Rarangkén rada runtut ta? Langkah sabanjure bakal dibagi 2: 4/2 = 2 Kita duwe rong klompok: I - {1,4,6,8,6} II - {3,8,9,11} B array umum: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Kita ngliwati loro klompok nggunakake algoritma ngurutake sisipan lan entuk larik: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Saiki array kita meh diurutake. Pengulangan pungkasan algoritma tetep: kita dibagi langkah kanthi 2: 2/2 = 1. Kita entuk klompok, kabeh array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Miturut kang kita tindakake liwat insertion sort algorithm lan njaluk: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Ayo ndeleng carane kita bisa nampilake sorting iki ing kode Jawa:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

Saiki, efektifitas ngurutake Shell ora bener-bener dibuktekake, amarga asil beda-beda ing macem-macem kahanan. Perkiraan sing dipikolehi saka eksperimen mulai saka O(N ^3/2 ) nganti O(N ^7/6 ) .

Urut cepet

Iki minangka salah sawijining algoritma sing paling populer, lan mulane kudu menehi perhatian khusus. Inti saka algoritma iki yaiku unsur pivot dipilih saka dhaptar unsur-utamane unsur apa wae sing kudu diurutake nilai sing isih ana. Nilai kurang saka ing sisih kiwa, nilai luwih gedhe tinimbang ing sisih tengen. Sabanjure, sisih tengen lan kiwa uga dipilih dening unsur sing ndhukung lan kedadeyan sing padha: nilai diurutake relatif marang unsur kasebut, banjur unsur sing ndhukung dipilih saka bagean sing diasilake - lan sateruse nganti diurutake. baris. Algoritma iki ing Jawa ditindakake kanthi nggunakake rekursi:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0)// condition выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем middle
           recursionFastSort(array, i, max);
   }
}

Tanpa mangu-mangu, algoritma quicksort dianggep paling populer, amarga ing umume kahanan mlaku luwih cepet tinimbang liyane, ing wektu O(N*logN) .

Gabung urut

Pengurutan iki uga populer. Iki nuduhake salah sawijining jinis algoritma sing makarya kanthi prinsip "dibagi lan digdaya": ing wong-wong mau, kita mbagi tugas dadi bagean paling tithik ( urut cepet uga minangka wakil saka algoritma kasebut ). Dadi, apa inti saka algoritma iki?

dibagi:

Susunan dipérang dadi rong bagéan sing ukurané kira-kira padha, saben rong bagéan iki dipérang dadi loro manèh, lan saterusé nganti tetep dadi bagéan sing paling cilik sing ora bisa dibagi. Bagean sing paling ora bisa dibagi yaiku nalika saben larik duwe siji unsur, tegese larik kasebut kanthi otomatis dianggep diurutake.

nelukake:

Iki ngendi proses diwiwiti sing menehi jeneng kanggo algoritma - gabung . Kanggo nindakake iki, njupuk loro susunan urutan asil lan gabungke dadi siji. Ing kasus iki, sing paling cilik saka unsur pisanan saka loro susunan ditulis kanggo larik asil, lan operasi iki bola nganti ora ana unsur liyane ing loro susunan. Yaiku, yen kita duwe rong larik minimal {6} lan {4} , nilai-nilai kasebut bakal dibandhingake lan asile bakal ditulis: {4,6} . Yen ana array sing diurutake {4,6} lan {2,8} , mula nilai 4 lan 2 bakal dibandhingake , sing 2 bakal ditulis menyang array sing diasilake. Sawise iki, 4 lan 8 bakal dibandhingake , 4 bakal ditulis, lan ing pungkasan 6 lan 8 bakal dibandhingake . Patut, 6 bakal ditulis, lan mung sawise - 8. Akibaté, kita bakal entuk array sing diasilake: {2,4,6,8} . Kepiye carane iki katon ing kode Jawa? Kanggo ngolah algoritma iki, luwih trep kanggo nggunakake rekursi:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

Kaya ing urutan cepet, kita mindhah cara rekursif menyang penengah supaya pangguna ora perlu repot nyetel argumen standar tambahan, nanging mung bisa nemtokake array sing kudu diurutake. Amarga algoritma iki mirip karo penghapusan sing luwih cepet, kacepetan eksekusi padha - O(N*logN) .

2. Algoritma rakus

Algoritma rakus minangka pendekatan sing njupuk keputusan sing optimal sacara lokal ing saben tahapan lan nganggep yen solusi pungkasan uga bakal optimal. Solusi "optimal" yaiku sing menehi keuntungan sing paling jelas lan langsung ing langkah / tahap tartamtu. Kanggo nimbang algoritma iki, kita bakal milih masalah sing cukup umum - babagan tas ransel. Ayo padha pura-pura yen sampeyan maling. Sampeyan nyuwil menyang toko ing wayah wengi karo tas ransel, lan ing ngarep sampeyan ana sawetara barang sing bisa nyolong. Nanging ing wektu sing padha, kapasitas tas ransel diwatesi - ora luwih saka 30 unit konvensional. Ing wektu sing padha, sampeyan pengin nggawa sakumpulan barang kanthi nilai maksimal sing pas karo tas ransel. Kepiye sampeyan mutusake apa sing bakal dilebokake? Dadi, algoritma rakus kanggo masalah knapsack kasusun saka langkah-langkah ing ngisor iki (kita nganggep kabeh obyek pas karo knapsack):

1. Pilih barang sing paling larang saka sing durung kena.
2. Yen pas karo tas ransel, lebokake ing kono; yen ora, skip.
3. Apa sampeyan wis ngurutake kabeh item? Yen ora, kita bali menyang titik 1, yen ya, kita mlayu saka toko, amarga tujuan kita ing kene wis rampung.

Ayo dideleng iki, nanging ing Jawa. Iki bakal katon kaya kelas Item:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

Ora ana sing khusus ing kene: telung kolom - jeneng , bobot , biaya - kanggo nemtokake karakteristik barang kasebut. Uga, sampeyan bisa ndeleng, antarmuka Comparable diterapake ing kene supaya kita bisa ngurutake Barang miturut rega. Sabanjure kita ndeleng kelas ransel kita - Tas :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight minangka kapasitas tas ransel kita, sing disetel nalika nggawe obyek;
• item - obyek ing tas ransel;
• currentWeight , currentCost - bobot saiki lan biaya kabeh barang ing tas ransel, sing kita tambah nalika nambah item anyar ing metode addItem .

Bener, ayo menyang kelas, ing ngendi kabeh tumindak:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

Pisanan, kita nggawe dhaptar unsur lan ngurutake. Nggawe obyek tas kanthi kapasitas 30 unit. Sabanjure, kita ngirim unsur lan obyek tas menyang cara fillBackpack , kang, nyatane, tas ransel diisi nggunakake algoritma rakus:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Kabeh iku arang banget prasaja: kita miwiti kanggo mbukak liwat dhaptar item diurutake miturut biaya lan sijine ing tas, yen kapasitas ngidini. Yen ora ngidini, unsur bakal dilewati lan wacana liwat unsur isih bakal terus nganti pungkasan dhaftar. Kanthi mlaku utama, kita entuk output ing ngisor iki menyang konsol: Bener, iki minangka conto algoritma rakus: ing saben langkah solusi optimal lokal dipilih, lan ing pungkasan sampeyan entuk solusi sing optimal sacara global. Ing kasus kita, pilihan sing paling apik yaiku barang sing paling larang. Nanging iki solusi sing paling apik? Apa sampeyan ora mikir kita bisa modernisasi solusi kita supaya bisa nglengkapi tas ransel kanthi biaya total sing luwih dhuwur? Ayo dipikirake carane iki bisa ditindakake:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

Kene kita ngetung rasio bobot-rega kanggo saben item. Dadi kanggo ngomong, pinten biaya siji unit saka item tartamtu? Lan kanthi nilai kasebut, kita ngurutake barang lan ditambahake menyang tas. Ayo mlaku:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Kita entuk output menyang konsol: Luwih apik, ta? Algoritma rakus nggawe pilihan sing optimal sacara lokal ing saben langkah kanthi pangarep-arep yen solusi pungkasan uga optimal. Iki ora mesthi dibenerake, nanging kanggo akeh masalah, algoritma rakus nyedhiyakake optimal. Kerumitan wektu algoritma iki yaiku O(N) , sing apik banget, ta? Inggih, kanthi mangkono, bagean pisanan saka artikel iki wis rampung. Yen sampeyan kasengsem ing tutugan artikel iki, sing bakal ngomong babagan grafik lan algoritma sing ana gandhengane, sampeyan bisa nemokake ing kene .