hoppke@gmail.com


Ćwiczenie programistyczne

Wpis na 0. poziomie, wysłany 13 stycznia 2010 o 22:32:45

W trakcie rozglądania się za nową, ciekawą pracą otrzymałem do rozwiązania dość nietypowe (jak na procesy rekrutacyjne) zadanie. Rozwiązywanie go było dość ciekawe, więc pomyślałem, że się podzielę:

LTP (Left-Truncatable Prime) to liczba pierwsza , która

  • nie zawiera cyfry 0
  • pozostaje liczbą pierwszą po odcięciu dowolnej ciągłej sekwencji cyfr z lewej strony.

Wprowadzenie:
5167 to LTP, gdyż 5167, 167, 67 i 7 są liczbami pierwszymi; 2179 nie jest LTP, bo co prawda 2179, 179 i 79 są liczbami pierwszymi, ale 9 już nie. W przedziale do 1 000 000 000 znajduje się 2166 LTP.

Napisz program, który:

  1. przyjmuje pojedynczą liczbę n (1 ≤ n ≤ 2166) jako parametr CLI
  2. oblicza n-tą liczbę LTP
  3. wypisuje wartość tej liczby na standardowe wyjście

Na przykład:

  1. podanie 10 powinno wypisać 47
  2. podanie 100 powinno wypisać 5167
  3. podanie 1000 powinno wypisać 8391283

Twoje rozwiązanie powinno mieć na uwadze wydajność (choć nie tylko ten aspekt wymaga uwagi). Twój program powinien być w stanie zwrócić odpowiedź w przeciągu 500ms na standardowym PC.

Oprócz tego oryginalne zadanie sugerowało, że rozwiązanie powinno być jakości "produkcyjnej", a stworzenie go nie powinno zająć więcej niż 1h, ale możemy to sobie darować.

Mnie najbardziej interesuje: jakie, droga braci techniczna, masz pomysły na algorytm, i ile czasu/MB pamięci potrzebują wasze rozwiązania? Zaznaczam, że program ma liczby obliczać, więc rozwiązanie typu "ściągam listę LTP z internetu, zapisuję w pliku, a program to tylko wczytuje" jest niekoszerne (taki był mój pierwszy pomysł :)

A, usłyszałem też, że nawet programiści z wieloletnim doświadczeniem potrafią mieć problemy z rozwiązaniem tego zadania/zapewnieniem odpowiedniej wydajności.

52 komentarze | Ogólne Techblog |

Eee BOX, cz. 2

Wpis na 0. poziomie, wysłany 30 października 2008 o 23:14:29

Właśnie instaluję Ubuntu.

Miałem małą zagwozdkę, bo Eee BOX nie ma napędu CD, a nasz zewnętrzny CD podczepiany przez USB właśnie wyzionął ducha (płyt nie widzi). Próbowałem z Ubuntu 8.04.1 -- i przez unetbootin + karta SD, i przez UPX ciągnący dane z serwera tftp postawionego na moim desktopie z Vistą.

Nada. Nic. Bez skutku. LiveCD Ubuntu 8.04.1, mimo iż teoretycznie powinno działać (z poprawką na kartę graficzną, której nie rozpoznaje poprawnie i trzeba przestawić na sterownik Vesa), zawiodło mnie fatalnie -- jakimś cudem sterownik ethernetu nie wypuszczał pakietów choćby do rutera. Jest to sprzeczne z "success stories" jakie znalazłem w sieci, bo ewidentnie ludziom jakoś 8.04.1 działało z Eee BOX-em (model B202, czyli taki sam jak mój). Jednym słowem wczorajszy wieczór zakończył się porażką.

Ale dzisiaj skorzystałem z oficjalnej premiery 8.10 i ściągnąłem sobie http://releases.ubuntu.com/releases/8.10/ubuntu-8.10-rc-mobile-i386.img (Ubuntu powinno popracować nad promowaniem alternatywnych sposobów instalacji...). Jest to obraz, który należy wrzucić bezpośrednio ("cat img > /dev/pendrive") na jakiś nośniczek USB i użyć jak LiveCD. Można to wykonać i pod Windowsem -- ja użyłem dd.exe dla win32 i przygotowałem bootowalną kartę SD.

Eee BOX bezproblemowo wystartował z karty, pokazał bardzo estetyczny pulpit w 1600x1200 (natywna monitora podpiętego akurat przez DVI). Co ciekawe nie jest to raczej typowy Gnome (pionowy taskbar itp.), ale to pewnie dlatego, że ten obraz instalacyjny jest przeznaczony dla urządzeń mobilnych, netbooków.

Dysk standardowo posiadał 4 partycje, z czego 2 ukryte. Jedna z ukrytych nazywa się "Rescue", więc pewnie leży na niej coś ważnego. Druga zawiera bógwieco, podejrzewam, że może mieć coś wspólnego z Express Gate albo jakąś kopią systemu. Zbadam później. W każdym bądź razie partycje są pozakładane tak, że cfdisk marudzi o błędach w tablicy partycji i trzeba sięgać po zwykłego fdiska w razie czego. Miłe za to jest to, że dysk ma wydzieloną pustą partycję "Data" o wielkości 100GB, więc jest gdzie posadzić Linuksa bez dotykania pozostałych partycji.

Instalacja przeszła gładko. Nie wiedziałem gdzie wpakować bootloader by nie uszkodzić Express Gate (to taki minimalny Linux wbudowany jakoś w urządzenie, posiada graficzną przeglądarkę podejrzanie przypominającą Firefoksa w jakimś trybie kiosku, Skype, Pidgina, Photo Managera i parę innych programów do obsługi sieci/wifi, ale pozbawioną za to łatwego dostępu do CLI (BUUUUU!!!). Więc bootloader wylądował w bootsektorze partycji na której kazałem umieścić Ubuntu.

Oczywiście po restarcie automatycznie wstał WindowsXP. Jeszcze raz uruchomiłem Ubuntu z karty SD i fdiskiem ustawiłem flagę "bootable" na partycji Ubuntu. Po restarcie zobaczyłem czarny ekran biosu z komunikatem o uszkodzonej tablicy partycji.

W panice sprawdziłem, czy Express Gate nadal działa -- działa. No dobra, to przestawię bootable z powrotem na partycję WinXP i zaryzykuję umieszczenie bootloadera w MBR... zobaczymy co z tego wyjdzie!

Update

Uruchomiłem jeszcze raz LiveSD, uruchomiłem okienko terminala. Przestawiłem aktywną partycję w poprzedni stan. Podmontowałem partycję z ubuntu i wrzuciłem bootloadera do MBR:

sudo su
mount /dev/sda5 /mnt
cd /mnt
mount -o bind /dev dev
mount -o bind /proc proc
chroot . /bin/sh
grub
root (hd0,4)
setup (hd0)
quit
exit
umount proc
umount dev
cd ..
umount mnt

Zrestartowałem maszynkę, pojawił się Grub, wybrałem Ubuntu, wystartowało. Synaptic właśnie aktualizuje jakąś setkę pakietów. Jak na razie idzie nieźle.

4 komentarze | Ogólne Techblog |

Eee BOX

Wpis na 0. poziomie, wysłany 29 października 2008 o 19:37:32

Dzisiaj nasze gospodarstwo domowe wzbogaciło się o kolejną zabawkę. Tym razem jest to maciupki Asus Eee Box (nie mylić z Eee PC), model czarny, z dyskiem 160GB o ile się nie mylę i WinXP na pokładzie. W chwili obecnej nie ma ich jeszcze zbyt wiele w naszej części globu, ale moim zdaniem to komputerki warte uwagi.

Właśnie jestem na etapie rozpakowywania, więc pełniejszą relację z wrażeń zdam gdy już go oswoję i posadzę na nim jakieś Ubuntu. Instalować będę pewnie musiał z karty SD... no nic, się zobaczy :)

5 komentarzy | Ogólne Techblog |