Hosting Host-UA for ukrainians!
zymnavoda | zanachka | house m.d.

Архів

Архів автора

Питання на співбесіді: зв’язані списки із петлями

Серпень 3rd, 2010 admin Прокоментувати
У цій частині розглядається загальне питання про зв’язані списки – як ми визначаємо, коли є цикл?

Зв’язані списки

Зв’язані списки одні із найбільш відомих структур даних і найбільш цікаві програмісти вивчають їх із самого початку. Але для повноти, давайте розглянемо їх коротко. Зв’язаний список являє собою послідовність вузлів. Кожен вузол містить фрагмент даних , а також посилання на наступний вузол в списку. Графічно це виглядає наступним чином linked list Питання на співбесіді: звязані списки із петлями

Зв’язаний список із петлею (циклом)

Можливо так, що вузол у зв’язаному списку може вказувати на попередній елемент у списку. Це погано з багатьох причин, не останньою з яких є те, що будь-який цикл, який перебирає всі вузли в списку через доступ до наступного вузлу ніколи не закінчиться. Таким чином, потрібно визначати, чи цикл має петлі. Ось ілюстрація того, як може виклядати список із петлею: loopy linked list Питання на співбесіді: звязані списки із петлями

Легке рішення

Просте рішення полягає в тому, щоб відслідковувати кожен вузол, який було пройдено до цього і перевірити , якщо поточний вузол є у цьому списку. Ось дуже простий зв’язаний список, реалізований на Ruby.
class Node
  attr_accessor :data, :next
  def initialize(data = nil)
    @data = data
    @next = nil
  end
end
Ось просте рішення для виявлення петлі використанням вищевказаних реалізації
def has_loop?(node)
  seen = []
  until node.next.nil? do
    return true if seen.include? node
    seen << node
    node = node.next
  end
  false
end
Це рішення є працездатним, але не дуже оптимальним. Воно має O(n2) складність по процесору та O(n) по пам’яті.

Черепаха і заєць

Краще рішення вимагає трохи математичного мислення. Якщо є цикл, то це означає, що будь-який ітератор, незалежно від того скільки кроків приходиться на одну ітерацію, повинен досягти вузол-”порушник”. Таким чином, якщо у нас є два ітератора, один з яких має довжину, яка є кратною іншій, вони коли небуть опиняться на одному й тому ж вузлі. Звичайне рішення полягає у створенні одного ітератора на один крок (“черепаха”), а другий – на 2 кроки (“заєць”). Це алгоритм виглядає наступним чином
def has_loop?(node)
  slow = node
  fast = node
  until slow.next.nil? or fast.next.nil? do
    slow = slow.next
    fast = fast.next.next
    return true if (slow == fast)
  end
  false
end

Додаткові питання

Вважаючи, що відповідь на поставлені вище питання, отримана правильно і швидко, інтерв’юер, ймовірно, почне задавати додаткові питання. Як виправити зв’язаний список, коли ви виявляєте цикл? Що, коли він містить декілька петель? Як визначити розмір петлі?
Я залишу вас замислитися над цими питаннями.

Оригінал: http://20bits.com/articles/interview-questions-loops-in-linked-lists/
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark

Регулярні вирази – це просто

Серпень 2nd, 2010 admin Прокоментувати
В цій замітці хочу поділитися про програму, яка значно спрощує розуміння і роботу регулярних виразів – Expresso До знайомства із цим продуктом, регулярні вирази давалися мені важко, хоча працювати доводилося і не часто. Але від часу початку роботи автоматизатором тестування, хочеш-не-хочеш, але рег. вирази потрібно розуміти. І на допомогу прийшла саме ця програма. Expresso 3.0
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark

Логічна задача про поле та встелення його паркетом

Серпень 2nd, 2010 admin Прокоментувати
На клітинчастому полі 8х8 вирізали по клітинці в протилежних кутах діагоналі. Чи можна встелити це поле паркетинами 2х1 клітинок. Відповідь довести. Відповідь : Ні. Доказ: Нехай поле буде шахове, з чорними і білими клітинами. Вирізано було 2 клітки однакового кольору ( на одній діагонілі всі клітини одного кольору). Як результат клітин одного з кольорів більше ніж клітин іншого кольору. Кожна паркетина 2х1 лягає на дві сусідні клітини, причому очевидно – це клітини різних кольорів. Відповідно в найкращому розкладі залишаться дві клітини одного кольору, на які неможливо буде укласти паркетини .
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark

Відповідь на задачу про султана і 100 візирів

Серпень 2nd, 2010 admin Прокоментувати
Публікую розв’язок до задачі про султана і 100 візирів. Може гарантовано вижити 99 візирів і 1 може вижити із імовірністю 1/3. Стратегія: позначимо кожен колір шапки цифрами: червоний – 0, синій – 1, жовтий – 2. Тепер самий останній візир (що бачить всі шапки, крім своєї) сумує “кольори” шапок мо модулю 3 (по аналогії із сумою по модулю 2: 2+1=0, 2+2=1). В результаті вийде цифра від 0 до 2. Цей візир говорить колір, що відповідає цій цифрі (цей колір може співпасти із його шапкою, тоді він виживе, в інших 2/3 випадках – помре). Наступний за ним візир рахує таку ж саму суму для всіх наступних, кого він бачить, віднімає від отриманого результату ту цифру-колір, яку назвав його попередник і говорить відповідний колір. Наступний візир рахує суму по модулю три для наступних і віднімає суму двох попередніх і т.д. Все :) Виживають гарантовано 99 візирів, а той, що першим говорив колір – із імовірністю 1/3. До речі, ця задача розширяється і на кількість кольорів, і на кількість візирів.
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark
Categories: Логічні задачі Tags:

Як почати проект автоматизації тестування (переклад)

Серпень 2nd, 2010 admin Прокоментувати

Тільки уявіть собі: ви інженер автоматизації тестування з 3+ роками досвіду. Ви знаєте кілька інструментів автоматизації тестування , і один з них ви знаєте краще за все. Ви також хочете зростати , і в один прекрасний день менеджер приходить до вас і говорить:  “Я знайшов хороший проект автоматизації тестування для вас. Ви будете лідером , ви будете мати свою власну команду, ви починаєте з нуля, і вам доведеться починати як можна швидше. Ви згодні?”
Ви , звичайно , погоджуєтеся! Але ви ніколи не починали проектів автоматизації тестування з самого початку. Отже, що робити в першу чергу?

Для того щоб допомогти у вирішенні цього завдання , ми створили наступну карту думок:

[Image]

Деякі пояснення:

1a. Отримати контакти тестувальників , які володіють та створили ручні тести для автоматизації, клієнта , який хотів би бачити автоматизацію ( або , може бути ініційований групою тестування , так що в будь-якому випадку отримаєте найбільш зацікавлену особу в автоматизації ) і розробників , які можуть допомогти у разі проблем із розпізнавання об’єктів.
1B. Зрозуміти мету тестового проекту автоматизації – для яких цілей і що буде критерієм успішності.
2. Оцінка програм, можливістть застосування засобу автоматизації до тестуємого додатку, взяти пару тестів і спробувати автоматизувати їх , щоб зрозуміти можливі труднощі / особливості .
3. Розрахувати роботи . На підставі цілі проекту з автоматизації і критерію оцінки результатів , зробити наступний крок і оцінити скільки часу необхідного для автоматизації тестування  і скільки людей потрібно (якщо це змінна величина , звичайно: )  . У статті “Як оцінити діяльність автоматизації тестування ви можете знайти додаткову інформацію щодо цього.
4a . Подумайте і створіть стратегію автоматизації тестування та керівні принципи , якими ваша команда буде користуватися пізніше.
4B . Розробити обґрунтування концепції для того, щоб показати всім, що ваша стратегія працює на прикладі.
З мого досвіду я знаю,  що  тижня-двох буде достатньо для гарного початку :) .

Для подальшого читання, я рекомендую статтю Сім кроків до успіху автоматизації тестування – Була опублікована перша більш ніж 10 років тому , але як і раніше корисні.

Оригінал: How to start test automation project

VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark

Побачила світ програма-настільний клієнт для сервісу перекладів Google Translate (gDesktop Translator)

Березень 19th, 2010 admin 1 коментар
Із радістю повідомляю, що з під мого пера вийшла програма-настільний клієнт для on-line перекладача від Google. Перш за все вона цікава двома можливостями: Вам більше не потрібно йти на сторінку Google  Translate для перекладу, крім цього, ви можете перекладати виділений текст у будь-якому вікні, що підтримує копіювання за допомогою комбінації клавіш  Ctrl+C. Основні можливості цієї програми такі:
  • переклад текстів із однієї мови на іншу;
  • автоматичне визначення мови тексту;
  • переклад виділеного фрагменту тексту за допомогою натиснення комбінації клавіш Ctrl+C+C
  • підтримка великої кількості мов;
  • програма згортається в системний лоток;
  • можливість роботи через проксі-сервер;
  • автозавантаження;
  • мова інтерфейсу користувача: англійська та українська;
Більш детально ознайомитися із цим продуктом можна тут. Там же ви зможете знайти посилання для завантаження, а також розташування початкових кодів програми. Буду радий відгукам та побажанням щодо роботи.

Знімки екрану

 gDesktop Translator   Google Translate Desktop Client
 gDesktop Translator   Google Translate Desktop Client
 gDesktop Translator   Google Translate Desktop Client
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: -1 (from 1 vote)
  • Share/Bookmark

Тестування власного додатку – з чого почати

Березень 11th, 2010 admin Прокоментувати
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark
Categories: HP Quick Test Professional Tags:

Куди рухатися далі після читання даного підручника?

Березень 11th, 2010 admin Прокоментувати
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark
Categories: HP Quick Test Professional Tags:

Запуск параметризованих тестів та аналіз результатів їх виконання

Березень 11th, 2010 admin Прокоментувати
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark
Categories: HP Quick Test Professional Tags:

Параметризація Дій

Березень 11th, 2010 admin Прокоментувати
VN:F [1.6.3_896]
Rating: 0.0/10 (0 votes cast)
VN:F [1.6.3_896]
Rating: 0 (from 0 votes)
  • Share/Bookmark
Categories: HP Quick Test Professional Tags:
Hosting Host-UA for ukrainians!
zymnavoda | zanachka | house m.d.