0
86147

15 задач на собеседовании для программиста

В этой статье я расскажу о задачах и вопросах, которые ждут программистов на собеседовании при приёме на работу.


Интервьюеры не отличаются оригинальностью, и один и тот же вопрос можно встретить на 3-5 разных собеседованиях.
Но даже опытные программисты, оказываясь в стрессовой ситуации, нередко теряются и не могут найти ответ на довольно простые вопросы. Поэтому предлагаю заранее потренироваться, проверить свои знания, а заодно и посмотреть на любимые вопросы интервьюеров. Не исключено, что именно на них Вам предстоит отвечать на следующем собеседовании.
Структуры данных и вопросы об алгоритмах – основная часть любого собеседования для программистов вне зависимости от их специализации

1. Как найти средний элемент в LinkedList за один проход?

Это один из самых популярных вопросов на собеседованиях. Его используют даже в телефонных интервью, чтобы быстро определить общий уровень знаний кандидата на роль программиста и оценить его способность быстро решать нестандартные задачи.

Все программисты знают, что средний элемент в LinkedList несложно найти, определив длину списка, последовательно пройдя все его узлы, пока не дойдёшь до NULL в первом проходе. А затем, пройдя половину из них во втором проходе. Когда же их просят решить эту задачу за один проход, многие теряются.

Большинство задач, поставленных на собеседовании, имеет довольно простое решение, и сидя в спокойной обстановке, Вы без особого труда найдёте его сами.

[spoiler title='Решение' style='default' collapse_link='true']

В этой задаче достаточно ввести два указателя. Первый будет увеличиваться при прохождении одного узла списка, второй - при прохождении 2 узлов. В момент, когда 2ой указатель дойдёт до конца списка (наткнётся на NULL), первый будет указывать на середину списка.
Успешно справились с этим вопросом? Получите следующий.

[/spoiler]

Исходный код решения

[spoiler title='Исходный код' style='default' collapse_link='true']

public class Central {	 	 
 	public static void main(String args[]) {	 	 
 		LinkedList linkedList = new LinkedList();	 	 
		LinkedList.Node head = linkedList.head();	 	 
		linkedList.add( new LinkedList.Node("1"));	 	 
		linkedList.add( new LinkedList.Node("2"));	 	 
		linkedList.add( new LinkedList.Node("3"));	 	 
		linkedList.add( new LinkedList.Node("4"));	 	 
		linkedList.add( new LinkedList.Node("5"));	 	 
		linkedList.add( new LinkedList.Node("6"));	 	 
		linkedList.add( new LinkedList.Node("7"));	 	 
		linkedList.add( new LinkedList.Node("8"));	 	 
		linkedList.add( new LinkedList.Node("9"));	 	 
		linkedList.add( new LinkedList.Node("10"));	 	 
 		LinkedList.Node current = head;	 	 
 		int length = 0;	 	 
 		LinkedList.Node middle = head;	 	 
 		while(current.next() != null){	 	 
 			length++;	 	 
 			if(length%2 ==0){	 	 
 				middle = middle.next();	 	 
 			}	 	 
 			current = current.next();	 	 
 		}	 	 
 		if(length%2 == 1){	 	 
 			middle = middle.next();	 	 
 		}	 	 
 		System.out.println("length of LinkedList: " + length);	 	 
 		System.out.println("middle element of LinkedList : " + middle);	 
	}	 	 
}	 	 
class LinkedList{	 	 
 	private Node head;	 	 
	private Node tail;	 	 
	public LinkedList(){	 	 
	this.head = new Node("head");	 	 
		tail = head;	 	 
	}	 	 
 	public Node head(){	 	 
 		return head;	 	 
 	}	 	 
 	public void add(Node node){	 	 
 		tail.next = node;	 	 
 		tail = node;	 	 
 	}	 	 
 	public static class Node{	 	 
 		private Node next;	 	 
 		private String data;	 	 
 		public Node(String data){	 	 
 			this.data = data;	 	 
		}	 	 
	 	public String data() {	 	 
			 return data;	 	 
		}	 	 
 		public void setData(String data) {	 	 
 			this.data = data;	 	 
 		}	 	 
 		public Node next() {	 	 
 			return next;	 	 
 		}	 	 
 		public void setNext(Node next) {	 	 
 			this.next = next;	 	 
 		}	 	 
 		public String toString(){	 	 
 			return this.data;	 	 
 		}	 	 
 	}	 	 
}

[/spoiler]

2. А если LinkedList зациклен?

[spoiler title='Решение' style='default' collapse_link='true']

Если в списке есть цикл, то в какой-то момент оба указателя будут показывать на один и тот же узел списка.

[/spoiler]

3. Этот вопрос может модифицироваться в «Как найти в LinkedList i-тый элемент с конца за один проход?»

Уже знаете ответ?

[spoiler title='Решение' style='default' collapse_link='true']
Можно использовать ту же схему решения. Первый указатель показывает на первый узел в связанном списке, второй на i-тый сначала. Когда второй указатель достигнет конца списка (дойдёт до NULL), первый будет указывать на i-тый элемент с конца.

[/spoiler]

4.Как определить дублированный элемент в массиве, в котором содержатся элементы типа int от 1 до 100, при условии, что в массиве дублируется только один элемент?

Это вообще задача на логику для средней школы. Многие программисты стремятся её решить длинным перебором/сравнением элементов, но есть куда более рациональный и эстетичный способ.

Догадались, какой?

[spoiler title='Решение' style='default' collapse_link='true']

  1. Считаем сумму всех чисел от 1 до 100 любым удобным для Вас методом.
  2. Считаем сумму элементов массива.
  3. Вычитаем первое из второго. Получаем… Правильно, получаем значение дублирующегося элемента.
  4. Если надо, находим номера искомых элементов в массиве.

[/spoiler]

5.Как изменить порядок элементов в строке на обратный без использования вспомогательных классов?

Один из самых популярных экспресс-вопросов. Есть несколько способов выполнения этого задания, но на собеседовании лучше выбрать самый простой. Не забывайте, что Ваш собеседник далеко не всегда может оценить преимущества длинного, но красивого решения.
Неплохо подойдёт что-то типа этого:

[spoiler title='Исходный код' style='default' collapse_link='true']

package Javatest.company;
public class Reverse {
    public static String reverseByArray(String s) {
        char[] a = s.toCharArray();
        char[] b = new char[a.length];
        for (int i = 0; i < a.length; i++) {
            b[(a.length - 1) - i] = a[i];
        }
        return new String(b);
    }
    public static void main(String[] args) {
        String string = "Java test";
        System.out.println(reverseByArray(string));
    }
}

[/spoiler]

6.Напишите программу для сортировки массива, использующую метод пузырька.

Вопросы по сортировке данных присутствуют почти на каждом собеседовании. Они позволяют нанимателю быстро оценить уровень умений кандидата и определить, соответствует ли этот уровень нужному.

Решить это можно так:

[spoiler title='Исходный код' style='default' collapse_link='true']

package Javatest.company;
import java.util.Arrays;
public class Bubble {
    public static void main(String args[]) {
        int[] unsorted = {32, 39,21, 45, 23, 3};
        bubbleSort(unsorted);
        int[] test = { 5, 3, 2, 1};
        bubbleSort(test);
    }
    public static void bubbleSort(int[] unsorted){
        System.out.println("unsorted array before sorting : " + Arrays.toString(unsorted));
        for(int i=0; i<unsorted.length -1; i++){
            for(int j= 1; j unsorted[j]){
                    int temp = unsorted[j];
                    unsorted[j] = unsorted[j-1];
                    unsorted[j-1] = temp;
                }
            }
            System.out.printf("unsorted array after %d pass %s: %n", i+1, Arrays.toString(unsorted));
        }
    }
}

[/spoiler]

7. В чём разница между стеком (Stack) и очередью (Queue)?

[spoiler title='Решение' style='default' collapse_link='true']

Задавая такие вопросы, ваш собеседник, понятное дело, хочет услышать не заученное определение из учебника или получить ссылку из Википедии, а оценить ваше собственное понимание различия этих двух типов структур данных.
Стек и очередь похожи отсутствием свободного доступа ко всем элементам структуры данных. Главное же отличие заключается в том, что стек – это структура типа LIFO(Last In First Out), где свободный доступ возможен только к последнему добавленному элементу, а при его удалении методом «pop» к элементу, добавленному перед ним. Когда же в стек добавляется новый элемент, доступен становится только он.
Очередь относится к типу FIFO(First In First Out), то есть доступен в ней только первый добавленный элемент. В случае его удаления доступен второй и т.д.

[/spoiler]

8. Как найти продублированные элементы в массиве, если их больше одного?

[spoiler title='Решение' style='default' collapse_link='true']

Этот вопрос довольно часто на собеседовании слышат те, кто сумели быстро найти 1 дублирующийся элемент в массиве. Для решения этой задачи можно использовать HashMap. Как Вы, несомненно, знаете, HashMap хранит данные парами – ключ/значение, и создав нужное количество карточек, Вы легко найдёте все повторы и их номера.

[/spoiler]

9. В чём разница между двусвязным и односвязным списком?

Это один из классических вопросов для телефонного собеседования. Любой программист на него ответит, почти не задумываясь.

[spoiler title='Решение' style='default' collapse_link='true']
В обоих списках узлы связаны посредством указателей. Только в односвязном списке указатель от каждого узла ведёт исключительно к следующему, и переход возможен только к нему, то есть исключительно в одном направлении. А в двусвязном от каждого узла, кроме первого и последнего, есть возможность перейти как к следующему, так и к предыдущему узлу, то есть двигаться в обоих направлениях.

[/spoiler]

10. Напишите программу для вывода чисел Фибоначчи

Если вдруг кто-то не знает, числа Фибоначчи – это последовательность, где каждое следующее число после 1 является суммой двух ему предшествующих. То есть ряд чисел Фибоначчи выглядит так: 1,1, 2, 3, 5, 8, 13, 21…

Решить эту задачу можно так:

[spoiler title='Исходный код' style='default' collapse_link='true']

package javatest.company;
import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        System.out.println("Enter number upto which Fibonacci series to print: ");
        int number = new Scanner(System.in).nextInt();
        System.out.println("Fibonacci series upto " + number +" numbers : ");
        for(int i=1; i<=number; i++){
            System.out.print(fibonacci2(i) +" ");
        }
    }
    public static int fibonacci(int number){
        if(number == 1 || number == 2){
            return 1;
        }
        return fibonacci(number-1) + fibonacci(number -2); 
    }
    public static int fibonacci2(int number){
        if(number == 1 || number == 2){
            return 1;
        }
        int fibo1=1, fibo2=1, fibonacci=1;
        for(int i= 3; i<= number; i++){
            fibonacci = fibo1 + fibo2; 
            fibo1 = fibo2;
            fibo2 = fibonacci;
        }
        return fibonacci;
    }
}

[/spoiler]

11. Напишите программу, которая определит, является ли заданное число палиндромом, не используя сторонние библиотеки

Палиндром – это набор знаков (слово, число, фраза), в котором все знаки при прямом прочтении полностью совпадают со знаками при обратном прочтении.
То есть палиндромами являются числа 66, 13431, 789987 и т.д.

[spoiler title='Решение' style='default' collapse_link='true']

  1. Для определения значения каждого символа в числе можно использовать оператор /. Например: 66/10 вернёт 6.
  2. А для нахождения последнего символа в числе оператор %.
    66%10=6
    123%10=3
  3. Сравниваем полученные значения и делаем выводы.

Можно пойти другим путём и развернуть число, используя рекурсию.

Например, так:

package com.Javatest;
public class Palindrome {
    public static int recursion(int n) {
        if (n < 10) {
            return n;
        }
        else {
            System.out.print(n % 10 + " ");
            return recursion(n / 10);
        }
    }
    public static void main(String[] args) {
        System.out.println(recursion(123)); 
    }
}

[/spoiler]

А после этого дописать этот код так, чтобы он сравнивал полученные цифры.

12. Напишите программу, которая проверит, является ли заданное слово палиндромом

Задача, в принципе, аналогичная предыдущей, но с существенным отличием - использовать операторы / и % не получится.
Используем рекурсию и получим простое и красивое решение:

[spoiler title='Исходный код' style='default' collapse_link='true']

package Javatest.com;
public class Palword {
    public static String recursion(String s) {
        if (s.length() == 1) {
            return "YES";
        } else {
            if (s.substring(0, 1).equals(s.substring(s.length() - 1, s.length()))) {
                if (s.length() == 2) {
                    return "YES";
                }
                return recursion(s.substring(1, s.length() - 1));
            } else {
                return "NO";
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(recursion("ABBA")); 
    }
}

[/spoiler]

13. Что такое бинарное дерево поиска?

[spoiler title='Решение' style='default' collapse_link='true']

Бинарное, или двоичное дерево поиска – это структура данных, каждый узел в которой может иметь от 1 до 2 подузлов (детей) или не иметь их вовсе.

Расположение данных в бинарном дереве имеет ряд ограничений:

  1. Как и во всех деревьях, любой узел бинарного дерева не может иметь более одного родителя.
  2. Данные в дереве распределяются в зависимости от их значений. Если значение подузла (ребёнка) меньше, чем значение узла (родителя), этот подузел становиться левым или ребёнком левого подузла, если левый подузел уже существует. Соответственно, если значение подузла больше значения узла, то он становится правым или ребёнком правого.

Применяются бинарные деревья в реализации ассоциативных массивов и множеств, например TreeMap или TreeSet, в некоторых алгоритмах вычислительной геометрии.

[/spoiler]

14. Напишите программу для реализации структуры данных Stack.

Этот вопрос позволяет Вам продемонстрировать свои навыки владения стандартными методами (push и pop) для работы с этой структурой данных. При выполнении этой задачи Вам нужно будет использовать массив или связный список для хранения элементов.
Написать можно, например, программу стандартного калькулятора.

15. Как развернуть LinkedList, используя рекурсию и итерацию?

Ещё один пример очень популярного вопроса. Есть много способов изменения порядка элементов в связанном списке. В следующей статье я рассчитываю подробно осветить их все.
Ждите! Или пишите свои варианты этой программы, не заглядывая в «авторскую версию»!
for java interview

В заключение

Не забывайте, что решая ту или иную задачу на собеседовании, желательно разъяснять каждый логический шаг интервьюеру. На стартовом собеседовании оценивают не только скорость и правильность решения поставленных задач, но и логику мышления в целом.
Именно поэтому иногда даже неполное решение сложной задачи позволит интервьюеру оценить ваши знания как достаточные для вакантной должности.
Даже если Вы опытный программист с десятками реализованных проектов портфолио, не поленитесь перед собеседованием повторить теорию. Ведь ответ «ну это работает где-то так… и вообще, за последние 3 года я ни разу не пользовался этой структурой данных» вряд ли устроит интервьюера.
Часть материалов переведена из этого источника.

Креатива Вам и удачи на собеседовании!

Другие статьи по теме

Подборка материалов и видеокурсов по Java

6 книг по Java для программистов любого уровня

МЕРОПРИЯТИЯ

05 декабря Санкт-Петербург Бесплатно
05 декабря Москва Бесплатно
04 декабря Москва Бесплатно
28 ноября Онлайн 48000 RUB

Комментарии 0

BUG