Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

technical screening > algorithms & data structures > Flashcards

algorithms & data structures Flashcards

1
Q

Какие структуры данных бывают

A

Базовые структуры данных являются фундаментальными элементами программирования.

  1. Maccив Array
    Массив - это упорядоченная коллекция элементов, доступ к которым осуществляется по индексу.

  2. Связанный список (Linked List)
    Связанный список - это структура данных, состоящая из узлов, каждый из которых содержит данные и ссылку на следующий узел.
  3. Стек (Stack)
    Стек - это структура данных, в которой элементы добавляются и удаляются только с одного конца (вершины).

  4. Очередь (Queue)
    Очередь - это структура данных, в которой элементы добавляются в конец и удаляются с начала (первыми пришли - первыми ушли).
  5. Дерево (Tree):
    Дерево - это иерархическая структура данных, состоящая из узлов, где каждый узел имеет родительский узел и ноль или более дочерних узлов.
  6. Хэш-таблица (Hash Table):
    Хэш-таблица - это структура данных, которая использует хэш-функцию для преобразования ключей в индексы таблицы, где значения хранятся.
    Реализуется на JavaScript используя встроенный объект Map.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Реализация структуры данных Array

A 
const myArray = [1, 2, 3, 4, 5];
console.log(myArray[2]); // Вывод: 3
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Реализация структуры данных Linked List

A 
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(data) {
    const newNode = new Node(data);

    if (this.head === null) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

const myList = new LinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Реализация структуры данных Stack

A 
class Stack {
  constructor() {
    this.stack = [];
  }

  push(item) {
    this.stack.push(item);
  }

  pop() {
    return this.stack.pop();
  }
}

const myStack = new Stack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
console.log(myStack.pop()); // Вывод: 3
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Реализация структуры данных Queue

A 
class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(item) {
    this.queue.push(item);
  }

  dequeue() {
    return this.queue.shift();
  }
}

const myQueue = new Queue();
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
console.log(myQueue.dequeue()); // Вывод: 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Реализация структуры данных Tree

A

```
class TreeNode {
constructor(data) {
this.data = data;
this.children = [];
}

addChild(node) {
this.children.push(node);
}
}

const rootNode = new TreeNode(‘A’);
const childNode1 = new TreeNode(‘B’);
const childNode2 = new TreeNode(‘C’);

rootNode.addChild(childNode1);
rootNode.addChild(childNode2);
~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Реализация структуры данных Hash Table

A

```
const myHashTable = new Map();
myHashTable.set(‘key1’, ‘value1’);
myHashTable.set(‘key2’, ‘value2’);
myHashTable.set(‘key3’, ‘value3’);
console.log(myHashTable.get(‘key2’)); // Вывод: value2
~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Какие базовые алгоритмы сортировки вы знаете?

A
  • Сортировка пузырьком Bubble Sort
  • Сортировка перемешиванием (шейкерная сортировка)
  • Сортировка расческой
  • Сортировка вставками
  • Сортировка выбором Selection Sort
  • Быстрая сортировка Quick Sort
  • Сортировка слиянием Merge Sort
  • Пирамидальная сортировка
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Какие алгоритмы поиска вы знаете?

A
  1. Linear Search Линейный поиск
  2. Binary Search Бинарный поиск
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Расскажите алгоритм Bubble Sort
с примером реализации

A
  • Этот алгоритм проходит по списку несколько раз, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке.
  • Процесс продолжается до тех пор, пока весь список не будет отсортирован.
  • Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской


Худшее время O(n2)
Среднее время O(n2)
Лучшее время O(n)
Затраты памяти O(1)

Реализация

```
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Меняем элементы местами
}
}
}
return arr;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = bubbleSort(unsortedArray);
console.log(sortedArray); // Вывод: [11, 12, 22, 25, 34, 64, 90]

~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Расскажите алгоритм Сортировки Вставками с примером реализации

A

При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.


Худшее время O(n2) для сравнений и перестановок
Среднее время O(n2) для сравнений и перестановок
Лучшее время O(n) для сравнений O(1) для перестановок
Затраты памяти O(n) основной, O(1) дополнительный

Реализация

const copyArr = arr;
  for (let i = 0; i < copyArr.length - 1; i += 1) {
    let j = i + 1;
    while (j !== 0 && copyArr[j - 1] > copyArr[j]) {
      const position = copyArr[j];
      copyArr[j] = copyArr[j - 1];
      copyArr[j - 1] = position;
      j -= 1;
    }
  }

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Расскажите алгоритм Selection Sort (сортировка выбором) с примером реализации

A
  • В этом алгоритме на каждом шаге находится наименьший элемент в оставшейся части списка и меняется местами с элементом на текущей позиции.
  • Процесс продолжается до тех пор, пока список не будет отсортирован.


Худшее время O(n2)
Среднее время O(n2)
Лучшее время O(n2)
Затраты памяти O(n) основной O(1) вспомогательной

```
function selectionSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // Меняем элементы местами
}
return arr;
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // Вывод: [11, 12, 22, 25, 34, 64, 90]
~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Расскажите алгоритм Quick Sort с примером реализации

A

Алгоритм:

  1. Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
  2. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
  3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

Худшее время O(n2)
Среднее время O(n log n)
Лучшее время O(n)
Затраты памяти O(n)

Реализация

const quickSort = (arr) => {
  // Условие остановки, выхода из рекурсии, возвращем массив с 1 элементом
  if (arr.length < 2) return arr;
  // Выбираем опорный элемент
  let pivot = arr[0];
  // Определяем массивы для тех, что меньше и больше опорного
  const left = [];
  const right = [];

  // Проходим циклом по всем элементам из массива и разносим их в массивы созданные ранее согласно условию, больше опорного - в правый, меньше - в левый  
  for (let i = 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // Рекурсивно повторяем процесс для новых двух массивов, текущий опорный элемент - кладем как первый в правый массив.
  return quickSort(left).concat(pivot, quickSort(right));
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Расскажите алгоритм Merge Sort с примером реализации

A

Алгоритм:

Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.


Худшее время O(n log n)
Среднее время O(n log n)
Лучшее время O(n log n)
Затраты памяти O(n) вспомогательной

Реализация

const merge = (arrFirst, arrSecond) => {
    const arrSort = [];
    let i = j = 0;
    // сравниваем два массива, поочередно сдвигая указатели
    while (i < arrFirst.length && j < arrSecond.length) {
        arrSort.push(
            (arrFirst[i] < arrSecond[j]) ?
                arrFirst[i++] : arrSecond[j++]
        );
    }
    // обрабатываем последний элемент при разной длине массивов
    // и возвращаем один отсортированный массив
    return [
        ...arrSort,
        ...arrFirst.slice(i),
        ...arrSecond.slice(j)
    ];
};

const mergeSort = arr => {
    // Проверяем корректность переданных данных
    if (!arr || !arr.length) {
        return null;
    }
    //Если массив содержит один элемент просто возвращаем его
    if (arr.length <= 1) {
        return arr;
    }
    // Находим середину массива и делим его на два
    const middle = Math.floor(arr.length / 2);
    const arrLeft = arr.slice(0, middle);
    const arrRight = arr.slice(middle);
    // Для новых массивов снова вызываем сортировку,
    // сливаем их и возвращаем снова единый массив
    return merge(mergeSort(arrLeft), mergeSort(arrRight));;
};
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Расскажите алгоритм Linear Search с примером реализации

A
  • В этом алгоритме каждый элемент списка последовательно сравнивается с искомым значением.
  • Если элемент найден, возвращается его индекс; в противном случае возвращается -1.

Пример на JavaScript:

function linearSearch(arr, target) {

const len = arr.length;
     for (let i = 0; i < len; i++) {
       if (arr[i] === target) {
         return i;
       }
     }
     return -1;
   }
   
const array = [12, 45, 67, 23, 9];
const targetValue = 23;
const index = linearSearch(array, targetValue);
console.log(index); // Вывод: 3
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Расскажите алгоритм Binary Search с примером реализации

A
  • В этом алгоритме предполагается, что список отсортирован.
  • Он находит средний элемент списка и сравнивает его с искомым значением.
  • Если значения совпадают, возвращается индекс; если искомое значение меньше, поиск продолжается в левой половине списка; если оно больше, поиск продолжается в правой половине списка.
  • Процесс повторяется до тех пор, пока значение не будет найдено или список не будет исчерпан.

Пример на JavaScript:

function binarySearch(arr, target) {

  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
     const mid = Math.floor((low + high) / 2);
     if (arr[mid] === target) {
       return mid;
     } else if (arr[mid] < target) {
       low = mid + 1;
     } else {
       high = mid - 1;
     }
   }
   return -1;
}
   
const sortedArray = [11, 12, 22, 25, 34, 64, 90];
const targetValue = 25;
const index = binarySearch(sortedArray, targetValue);
console.log(index); // Вывод: 3
17
Q
A

technical screening (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions