sabato 30 giugno 2007

Norwich Union

Thank you for taking part in a telephone interview with us. We were very impressed by the large number of talented students, and congratulate you for the excellent academic achievement that qualified you to take part.

After a very difficult decision, we have decided to continue with candidates whose skills more closely match the positions available. So, although at this stage we cannot put you forward for the next round, we were very interested in your application and consider you an excellent candidate. We would therefore like to hold your resume in our active file, so that if a position suiting your skills becomes available, we will contact you immediately to assess your interest and employment status.

Thank you for your interest in Norwich Union.

Pigliano per il culo? Io dico di si'.

martedì 19 giugno 2007

Programmando in C

La scorsa settimana l'ho dedicata prevalentemente a correggere il paper e ripassare C.

Alla fine non e' cosi' male come linguaggio, non mi ricordavo piu' la potenza dei puntatori, ed un bel ripassone e' servito. Ne ho approfittato cosi' per creare un programma che mi risolvesse un giochino che sul cellulare, che mi sta facendo dannare dato che non riesco a trovarne la soluzione.

Il giochino si chiama Stone Bricks, ed e' presente sotto forma di gioco java sui Moto Razr V3. Il gioco e' abbastanza semplice: data una scacchiera a forma di croce, vengono disposte n pedine sulla scacchiera. Se una pedina e' adiacente ad un altra su un lato (verticale o orizzontale), mentre sull'altro lato e' presente una casella vuota, la pedina puo' essere mangiata da quella adiacente, che si posizionera' sulla casella vuota. Il gioco termina quando c'e' solo una pedina sulla scacchiera. Ci sono 5 configurazioni iniziali, la cui difficolta' varia in base al numero di pedine iniziali presenti. La scacchiera e' composta da 45 caselle, con blocchi di 3x3 messi a croce.

Io ho risolto le prime quattro, mentre non riesco a finire la quinta (rimango sempre con almeno 3 pedine sulla scacchiera, disposte in modo tale che non possono annullarsi a vicenda). Allora ho pensato di fare un programma per risolverlo.

Il programma C e' strutturato come segue: data una matrice 9x9, valorizzo le caselle della croce a "1" se e' presente una pedina, "0" altrimenti. Le caselle non facenti parte della croce hanno valore "-9". Una struttura dati ad albero tiene traccia delle mosse effettuate e da effettuare, utilizzando un algoritmo DFS ricorsivo per scoprire ed analizzare i nuovi nodi. Una struttura ad albero binario parallela poi e' usata per memorizzare le configurazioni della matrice gia' visitate, in modo tale da non ri-applicare la DFS su configurazioni gia' visitate (capita spesso che una stessa configurazione possa essere raggiunta partendo da passi diversi).

I problemi principali di questo programma sono due: l'esplosione di stati della DFS e la lentezza nel controllo di una configurazione gia' osservata. In particolare osservo gravi rallentamenti sull'ultimo livello, che riempie 44 delle 45 caselle disponibili.
Il primo problema non e' poi cosi' grave: la DFS non ha bisogno di memorizzare troppi nodi contemporaneamente, in quanto ogni volta sono allocati solo tutti i nodi padri, i relativi fratelli e il nodo stesso. Contando che avendo 44 pedine al massimo risolvero' il problema in 43 mosse (ma che generalmente ci si ferma a 5 pedine sulla scacchiera), e che mediamente ad ogni mossa ne ho a disposizione altre 5, i nodi allocati contemporaneamente sono 38*5.
Il secondo problema invece e' piu' noioso. Le configurazioni possibili sulla scacchiera sono 2^45: non posso andare in accesso diretto alla memoria con 2^45 combinazioni cosi' son stato costretto a costruire un albero binario, che per ogni casella della matrice avesse un puntatore a un nodo "1" o "0". Ogni volta che cosi' ho un nuovo passo mi trovo a scorrere tutto l'albero per vedere se e' gia' stato visitato o meno.

Miglioramenti
  • Ogni matrice che visito la registro 4 volte nell'albero, ovvero registro anche quella speculare da ogni lato. In questo modo aumento la probabilita' di trovare un nodo gia' visitato (e che non porta a soluzione).
  • Valutavo l'idea del backtracking, al posto della ricorsione. Dovrei implementare un sistema per salvare gli iteratori delle matrici ad ogni singolo step, nulla di complicato, ma non so quanto migliori il programma, in quando reputo che non sia li' il problema principale.
  • Dimezzare l'albero binario. Potrei portare l'albero binario a "soli" 13 nodi al posto di 45, ed allocare per gli ultimi 32 un array lungo 2^32.
Tutti questi miglioramenti comunque mi pare non abbassino la complessita' del problema, che rimane sempre alta.

E nel frattempo non ho ancora la soluzione...


sabato 16 giugno 2007

Bloomberg e il C

Lunedi' scorso ho avuto un colloquio a Londra presso gli uffici di Bloomberg.

Sede stupenda, piu' bella ancora di quella di Accenture. Peccato che mi abbiano segato.

Il colloquio e' durato due ore e' un quarto, precisamente dall'una fino alle tre e un quarto del pomeriggio. Il posto era un internship in R&D presso il loro laboratorio informatico, e sono arrivato al colloquio dopo aver superato la prima scrematura dei curriculum, quindi un test su Java della Brainbench.

Spendo due parole sul test, perche' mi sembrano doverose in caso che qualcuno debba affrontare queste prove. Il test consiste in 40 domande, 3 minuti massimo a domanda, non c'e' possibilita' di tornare sulle risposte precedenti e ci si puo' prendere una sola pausa di al massimo 30 minuti.
Le domande del test Java Fundamental consistevano nel capire il funzionamento di porzioni di codice (per esempio dire il valore di una variabile dopo un flusso computativo), oppure nella conoscenza e nell'uso di svariate librerie, in particolare quella dei Thread, dell'RMI e della AWT.
Il test non e' complicato: avendo la pagina delle API Java a disposizione su un'altra finestra, e il buon Google sempre pronto, credo che questo test voglia piu' che altro capire quanto tempo ci si metta a trovare una soluzione a domande non troppo difficili. Curioso comunque il fatto che, pur programmando da quattro anni in Java (sempre a livello scolastico ovviamente) e ritenendomi un discreto programmatore non fossi in grado di rispondere a quasi nessuna domanda senza andare su internet a controllare bene.
Nessuna domanda su algoritmi, complessita', logiche di codice distribuito.. insomma, solo mera programmazione Java.

A Bloomberg l'avevo specificato che conoscevo Java, mentre C l'avevo visto molto tempo fa (un annetto circa quattro anni fa e un esame). Immaginate il mio sconforto quando mi vedo i primi due esaminatori con un bell'esamino in C! A parte le domande di rito, del tipo "Cosa ti piace della programmazione, perche' vuoi lavorare per Bloomberg" che mi ero gia' preparato a casa, credevo che il colloquio vertesse sulla costruzione di algoritmi e di processi concorrenti, e perche' no un pizzico di economia. Mi ero infatti ben preparato su queste materie..

I primi due esaminatori mi mettono davanti un semplicissimo codice C, e mi chiedono il valore delle variabili finali. La difficolta' stava appunto nel ricordarsi i puntatori degli array e simili.. ma boh, li' con qualche problemuccio iniziale me la son ancora cavata. Il secondo codice (sempre in C) invece era un programma che stampava una data. Questo programma aveva un problema sulla seconda stampa, e bisognava capire quale fosse. Li' ho fatto molta fatica a capire che era un problema di allocazione della memoria nello stack.. e chi se la ricordava piu' la gestione della memoria in C!

Oltre a queste due domande iniziali, il resto penso sia andato bene: mi e' stato chiesto di scrivere un programmino per calcolare il fattoriale, e si e' discusso sui vantaggi e gli svantaggi delle funzioni ricorsive. Quindi mi son stati proposti due test logici:
  • un treno sta arrivando presso una galleria, in cui all'interno c'e' un uomo. L'uomo si trova ad 1/4 dall'uscita della galleria da dove sta arrivando il treno. Sia che l'uomo corra verso quell'uscita (andando quindi verso il treno, e percorrendo 1/4 di galleria) sia che l'uomo corra verso l'altra uscita (andando nella stessa direzione del treno, e percorrendo 3/4 di galleria), l'uomo si salva al pelo. Dire qual'e' il rapporto tra la velocita' del treno e dell'uomo.
  • su un foglio e' disegnata una croce, la cui verticale e' composta da 3 coppie di quadretti bianchi, e l'orizzontale e' composta da 4 quattro quadretti bianchi (due sono in comune con la verticale). Riempire le otto caselle con i primi 8 numeri naturali, in modo tale che in nessuna casella adiacente (anche quelle diagonali sono da considerarsi adiacenti) contengano due numeri che sono successivi tra loro.
Dopo questi due test, e' arrivato il secondo esaminatore. Questo era piu' interessato agli algoritmi, e mi ha chiesto di pensare (ed implementare) un codice che, dato un array di numeri, ricavasse il primo numero univoco nell'array. Con lui si e' parlato di complessita' di algoritmi, quindi mi ha proposto un'altro quiz logico:
  • tre carcerati hanno la possibilita' di uscire dalla prigione, indovinando il colore del proprio cappello. Se sbagliano vengono giustiziati, se non lo sanno rimangono in cella. Il guardiano benda uno dei tre carcerati, e dispone i cappelli sulle loro teste. I cappelli a disposizione del guardiano sono 5, 3 bianchi e 2 neri. Ogni carcerato non puo' vedere il proprio cappello ma solo quello dei colleghi (ovviamente quello bendato non vede nulla). Alla fine i due carcerati non bendati rispondono che non sanno qual'e' il loro cappello, mentre quello bendato dice di saperlo. Perche'?
Questo e' come si e' svolto il colloquio: mi e' stata poi alla fine fatta vedere come funziona il Bloomberg Terminal, quindi ho fatto un piccolo tour all'interno degli uffici.. quindi due giorni dopo mi han scaricato.

Dopo tutto questo ho sbagliato aereoporto al ritorno (al posto di andare a Luton son finito a Stansted) e cosi' son tornato a casa che era la mezza.

Presumbilmente volevano una persona che conoscesse bene C, o che lo conoscesse meglio di me in quel momento: pazienza.. ora sono quattro giorni che sto programmando C tutto il giorno e la notte, la prossima volta non mi fregheranno piu'. Anche perche' la preparazione che ho fatto per Bloomberg sta volta mi e' molto piaciuta, e sono soddisfatto comunque delle risposte che ho dato sui test logici e sugli algoritmi.

A breve tocca IBM.. ho passato la revisione del curriculum, ora devo fare un test attitudinale: chi sa che sia la volta buona!

PS: I codici che ho postato potrebbero non essere esattamente quelli che mi hanno proposto a Bloomberg. Sono abbastanza simili, ma non identici.

Ho finito gli esami!

Ho finito gli esami della specialistica in Metodologie e Sistemi Informatici! Chiudo con un 30 la mia carriera nell'universita' (italiana?), media 27.69, voto di presentazione alla tesi 101.72 (102). C'e' quindi il rischio che esca con 110, paura! Di seguito tutti i voti conseguiti nei relativi esami:

EsameProfessoreVotoData
Reti IISirovich2701/03/06
Sistemi Informativi IIGiolito2608/03/06
Programmazione Concorrente DistMargaria3031/03/06
Algoritmi IIZacchi2721/04/06
Metodi NumericiGiordano2630/05/06
SimulazioneBalbo2807/06/06
Paradigmi di ProgrammazioneCoppo2727/06/06
Gestione Sistemi e Reti IISereno2726/07/06
SemanticaDezani2831/07/06
Laboratorio Servizi WebArdissono30L28/08/06
Architetture IIGunetti2804/09/06
Fondamenti ComunicazioneLucenteforte2528/09/06
Specifiche Proc ConcorrentiDonatelli3016/01/07
EconomiaPironti3023/04/07
Ricerca OperativaLocatelli2418/06/07
Organizzazione d'ImpresaPironti3010/06/07

martedì 12 giugno 2007

Highlands

L'altra settimana sono stato sulle Highlands con i miei.

Paesaggi magnifici, non ho assolutamente parole per descriverli, quindi vi rimando al link con le foto che c'e' sulla destra. Anzi, ora sto creando la mappa del viaggio su My Maps di Google.. vediamo come viene! Riesco anche a likare qualche foto alla mappa: stupendo!

Potete seguire il giro su questa mappa.

Domenica (rosso):
Ritiriamo la macchina all'Avis, passiamo al b&b dei miei per raccogliere tutte le valigie e successivamente a casa mia per prendermi lo zainetto. La giornata promette bene, un bel sole, e faccio pranzo con una pizzetta da Domino.
Si parte da Edinburgh, direzione Fort Williams. Nei pressi di Stirling inizia a diventare nuvolo, e qualche miglio dopo inizia a piovere. Porca zozza.. piove anche tanto!
Passiam sotto il Ben Nevis, ma si vede nulla dato che ci son le nuvole basse. I paesaggi sembrano lunari: nessuna vegetazione, distese di nulla a perdita d'occhio.. mai vista una cosa simile!
Fort Williams non mi pare una gran cosa: forse anche perche' il tempo e' brutto, non c'e' proprio nulla da vedere. Proseguiamo cosi' per Fort Augustus, dove decidiamo di fermarci la notte. Troviamo un simpatico b&b, e dopo una lauta cena a nanna. Io ero stanco morto che eran due notti che non dormivo causa discoteca - levatacce!

Lunedi' (blu):
Facciam un giro del Loch Ness (non potevamo non vederlo, dai!) e ci dirigiamo verso Skye. Quest'isola e' veramente stupenda! Insenature bellissime, una natura davvero spettacolare. La giornata e' anche assolata, uno spettacolo puro.
Visitiamo il museo della vita dell'isola, che non si fa ricordare: oggetti e utensili che ho identici in campagna. Anche il castello di Dunvegan non e' bellissimo, solo i giardini si salvano. Si dorme a Dunvegan, presso un b&b di un simpatico signore.

Martedi' (verde):
Si fanno tante miglia: si esce da Skye, e ci si addentra nella Scozia. Prima Inverness, poi Huntly e il suo castello (o quello che ne rimane), quindi Dufftown, la cittina del whisky. Visitiamo la distilleria della Glenfiddich, e devo dire che ne e' valsa la pena. Ovviamente ho dovuto poi portarmente a casa una bottiglia :P
Si scende fino a Ballanter, dove ci fermiamo a dormire. A cena trovo un ragazzo italiano che fa il cameriere da 12 giorni, in quel paese dimenticato da dio: c'e' qualcuno che sta peggio di me!

Mercoledi' (giallo):
Passiamo dal castello di Balmoral, ma pare non ne valga la pena entrar dentro, cosi' ci dirigiamo verso il castello di Glamis, molto bello questo. Si scende quindi a Dundee, che boh, gia' solo dalla macchina dice poco.. proseguiamo per St Andrews, che invece trovo davvero stupenda. Penso che meglio di Edinburgh qua ci sia solo St Andrews: la cattedrale, il castello sul mare: fantastica!

Insomma, il giro della Scozia e' stato spettacolare per i paesaggi, un po' meno per i castelli, che francamente credevo di trovarne di piu' e in miglior stato. Ne vale comunque la pena per me farsi sto bel giretto, in particolare per l'isola di Skye.