Чегой-то тихо стало на форуме, скучно... Предлагаю вашему вниманию еще несколько задачек задававшихся в свое время на собеседованиях в Интеле, IBM, и т.д. Может будут полезны будущим соискателям, а те кто сами проводят собеседования могут взять их на вооружение.

Сразу предупреждаю, что задачи не на знание языка/умение программировать, а на создание эффективных алгоритмов решения - писать код в них обычно не нужно. Ну и, разумеется, решения ко всем задачам можно найти в и-нете, если кто сам не осилит.

Задача 1:

Вы получаете указатель на первый элемент связанного списка (linked list). Задача определить является ли этот список линейным (т.е. конечным) или начиная с какого-то элемента замыкается сам на себя (т.е. бесконечным).

Бонус 1: решение укладывается в следущие параметры:
время работы: О(L+M), где L - длина всего списка, а M - длина закольцованного участа
использование памяти: О(1)

Бонус 2: указать на каком элементе происходит зацикливание и длинну замкнутого отрезка

Желающие протестировать свой алгоритм могут использовать следущую функцию для создания листа:

class ListItem {
	public $value;
	public $nextItem;
	
	public function __construct($v,$n = null){
		$this->value    = $v;
		$this->nextItem = $n;
	}
}

// функция возвращает первый элемент списка
// $maxLen задает максимальный размер листа (минимум - 10)
// в $answers будут уложены правильные ответы
function createList($maxLen = 10000, &$answers)
{
	$len  = mt_rand(10,$maxLen);
	$loop = mt_rand(1,$maxLen);
	$item = $tmp = new ListItem($len);
	
	for($i=$len-1; $i>0; $i--){
		$tmp = new ListItem($i,$tmp);

		if ($i == $loop)
			$item->nextItem = $tmp;
	}
	
	$answers = array(
		  'total_length' => $len       // всего элементов в листе
		, 'loop_length'  => max($len - $loop + 1,0)  // длина "кольца" (если его нет, то 0)
		, 'loop_start'   => ($loop > $len) ? 0 : $loop  // $value элемента где происходит зацикливание (если список линейный, то 0)
	);
	
	return $tmp;
}

Дерзайте !


Другие задачи:
Задача 2
Задача 3