To count the total pairs of numbers which have a difference of K

Опубликовал admin 23 Январь 2014 в рубрике Задачи для интервью. Комментарии: Комментарии отключены
Given N numbers , [N<=10^5] we need to count the total pairs of numbers which have a difference of K. [K>0 and K<10^9].
Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.
Sample Input:
5 2
1 5 3 4 2
Sample Output:
3
Explanation:
The possible pairs are (5,3), (4,2) and (3,1).

Задача коммивояжера

Опубликовал admin 11 Январь 2014 в рубрике Алгоритмы. Комментарии: Комментарии отключены

Как известно задача коммивояжера является np-полной. Существуют несколько эвристических методов комбинаторного поиска, которые позволяют найти хорошее решение за приемлемое время. Одним из самых эффективных и простых в реализации является метод имитации отжига (simulated anealing). Данный метод основан на принципе, который лежит в основе одноименного процесса обработки металла. Хорошее описание алгоритма имитации отжига с примером кода приводится здесь.

Heavy and Light Balls Puzzle

Опубликовал admin 9 Январь 2014 в рубрике Логические задачи. Комментарии: Комментарии отключены

Очень простая задачка, но за пять минут может и не получиться решить.

You have 2 ball of each A,B,C colors and each color have 1 light and 1 heavy ball.  All light balls  are of same weight same goes for heavy. Find out weight type of each ball in minimum chances. You can use a two sided balance system (not the electronic one).

Что появилось нового и интересного в Visual Studio 2013

Опубликовал admin 30 Декабрь 2013 в рубрике Заметки программиста. Комментарии: Комментарии отключены
Помимо мелких и незначительных фишек в Visual Studio 2013 появилось несколько очень удобных фич, которых реально не хватало:
  1. Map mode. Теперь вместо скролбара для прокрутки кода справа можно активировать в опциях новый мега скрол с возможность проматывать код и одновременно видеть в попапе его содержимое.
  2. Доступ к буферу через Ctrl+Shift+V. Вот этого реально не хватало. Бывало такое, что скопировал кусок кода и понимаешь, что вот еще одну строчку тоже надо копирнуть? Теперь без проблем можно нажимать Ctrl+C еще раз. При вставке Ctrl+V вставляет содержимое активного буфера, а при нажатии Ctrl+Shift+V вставляет то, что было скопировано перед этим.
  3. Просмотр реализации функции в попапе Alt+F12. Теперь можно посмотреть реализацию функции, не переходя в другое окно, нажимаем Alt+F12 и вуаля! Всплывающий попап со скролом показывает всю подноготную исследуемого метода.
  4. В окне Autos можно смотреть, что возвращает текущий метод. Последнее по списку, но не последнее по полезности нововведение. Все наверняка сталкивались с такой ситуацией, когда отлаживаешь метод, который возвращает какое-то значение без сохранения ее в локальную переменную, что делает несколько затруднительным посмотреть его в отладчике. Теперь же в окне Autos можно совершенно спокойно просматривать, что возвращает метод. Например, у вас есть код return 12 + 34, и когда вы доходите до закрывающей фигурной скобки метода, в окне Autos отображается заветный результат 46.

Задача на алгоритм поиска в ширину на графе

Опубликовал admin 30 Декабрь 2013 в рубрике Алгоритмы. Комментарии: Комментарии отключены

What would be the best way to arrange a given sequence of number such that sum of any two adjacent number is a prime number. For e.g : 7,6,5,2,1,4,3 is a valid one sequence for arranging 1..7

Bitwise Stuff

Опубликовал admin 27 Декабрь 2013 в рубрике Алгоритмы. Комментарии: Комментарии отключены

1. Пусть N — такое число, что 0xff = 0xc0 + N. Напишите представление числа N в десятичной системе счисления.

2. You are given a number having only one “1″ its binary representation,. You have to find position of it?

3. Find if a number is of power of 2

4. Given an array of integers, write an algorithm that will check if the sum of any two is zero

Головоломка с выключателями

Опубликовал admin 26 Декабрь 2013 в рубрике Логические задачи. Комментарии: Комментарии отключены

Еще одна логическая задачка. Так же есть две полностью изолированные комнаты. В одной комнате на столе стоят 3 лампы, во второй – 3 выключателя. Каждый выключатель может включать одну лампу. Надо определить какой выключатель за какую лампу отвечает.

Экспериментатор только один – это Вы. Толькоодна попытка: сначала вы должны войти в комнату с выключателями. Затем вы должны войти в комнату с лампочками и определить какой выключатель за какую лампу отвечает. Никакими инструментами и измерительной техникой пользоваться нельзя.

Задачи с собеседований

Опубликовал admin 24 Декабрь 2013 в рубрике Логические задачи. Комментарии: Комментарии отключены

1. Перед вами прямоугольный стол и неограниченное количество монет достоинством 25 центов. Вы и ваш противник по очереди кладёте монеты на стол(каждый по одной), полностью плашмя (нельзя ставить на другие монеты или ребром), выигрывает тот после чьего хода у противника нет возможности положить монету на стол.

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

2. Имеется два одинаковых яйца неизвестной птицы и стоэтажное здание.  Требуется узнать прочность скорлупы, проверив с какого минимального этажа яйцо разобьется. Как проверить это за минимальное количество попыток?

Сортировка большого файла

Опубликовал admin 24 Декабрь 2013 в рубрике Алгоритмы. Комментарии: Комментарии отключены

Задание

Пусть у нас на диске есть файл размером 4 гигабайта. Файл содержит беззнаковые целочисленные значения, разделенные пробелом. Нужно отсортировать этот файл. То есть программа  должна  сгенерировать ещё один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство  на жёстком диске.

Решение

Сортируем алгоритмом слияния за время O(nlog(n)). Если было бы нельзя использовать дополнительную память на жестком диске, то сортировали бы хипом. Однако, в этом случае алгоритм сортировки работал бы медленнее, так как сортировка хипом не предполагает одновременной сортировки нескольких участков массива на отдельных ядрах процессора. С другой стороны сортировка слиянием это вполне позволяет.

Задача про людоеда и гномов

Опубликовал admin 23 Декабрь 2013 в рубрике Логические задачи. Комментарии: Комментарии отключены

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

«На следующее утро – сказал он, я построю вас в колонну и в случайном порядке надену на вас шапки двух цветов (красный и синий). Начиная с последнего в колонне, я буду спрашивать, какого цвета его шапка. Того, кто назовет цвет своей шапки правильно – отпущу, тех кто назовет неправильный цвет – того съем. Вы будете видеть всех тех, кто стоит впереди и слышать ответы тех, кто сзади. Но цвет своей шапки никто не видит. Говорить можно только одно слово – «красный» или «синий», иначе съем всех сразу».

Соотношение красных и синих шапок гномы не могут знать. Никакие дополнительные сигналы подавать нельзя (интонацией, паузами в ответах и т.п.).
Тем не менее, за ночь гномы придумали порядок ответов, который при этих условиях гарантировал выживание всех, кроме одного из них (у этого одного, тем не менее, тоже оставался шанс выжить).

Вопрос: какой способ придумали гномы?