24 aprilie 2015

Probleme pentru interviu: Probabilitati, OOP, Recursivitate si Programare dinamica

cap. 7 - Math & probabilities                                                         

* exista doua feluri de a trage in poarta la fotbal: (1) ai o singura incercare sa dai gol; (2) din 3 incercari trebuie sa dai 2 goluri. Daca p este probabilitatea de a reusi un gol, pentru ce valori ale lui p ar trebui sa alegi varianta (1) sau (2)? incercarile sunt independente intre ele.

Sol.: (1) P(castig) = p orice ai face. Pentru (2), P(castig) = P(3 goluri) + P(2 din 3 goluri in oricare ordine) = p^3 + 3 * p^2 (1-p)  => ca (1) sa fie varianta aleasa, p<= 0.5 , altfel  varianta (2)


* implementati operatiile - , * , / pentru numere intregi folosind doar operatorul +

Sol.:    int multiply(int x, int y) {  int sum = 0;
             for (int i=0; i<y; i++) sum += x;
             return sum; }

  int negate (int a) { int neg = 0;
    int d = a < 0 ? 1 : -1; // semnul opus al lui a
    while (a != 0) {
      neg += d;
      a += d; }
    return a; }

  int minus (int a, int b) { return a + negate(b); }

  Impartire: (1) a, b > 0 =>  daca a > b => algoritmul cu scadere repetata
                                            daca a = b => 1
                                            daca a < b => 0
                   (2) a = 0  =>  0
                        b = 0  => eroare
                   (3) a si/sau b < 0  => negate(a) si/sau negate(b) si re-executie


* 3 furnici se afla pe laturi diferite ale unui triunghi. Fiecare furnica isi alege o directie si porneste in ea. Fiecare directie are probabilitate egala de alegere. Care este probabilitatea sa existe o coliziune?

Sol.: Fie d1, d2, d3 directiile care pot fi {in sensul acelor, trigonometric} .
daca d1 = d2 = d3 => P(meet) = 0
daca d1 = d2 != d3 sau oricare alta combinatie => coliziune
P (coliziune) = P (d1 = d2 != d3) + P (d1 != d2 = d3) + P (d1 = d2 != d3) = 1 - P (d1 = d2 = d3) 
Cum toate cele 4 combinatii sunt exhaustive si au sanse egale => sansa e 1/4 => P (coliziune) = 3/4


* algoritm pentru aflarea celui de-al k-lea numar a.i. singurii factori primi ii sunt 3, 5 sau 7
Exemplu, primele numere sunt: 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, .....

Sol.: Idee - "urmatorul" numar este un produs de puterile lui 3, 5 sau 7. Toate numerele generate se tin intr-un sir. Exista 3 pointeri pentru pozitia curenta (pt numerele 3, 5, 7) care denota puterea cu care e folosit nr respectiv ca factor. Exista un pointer global pt dimensiunea sirului final. La fiecare pas se alege cel mai mic numar din cele 3 generate si care este mai mare decat numarul cel mai recent generat. 

public class Ex75 {

    private int getNumber (int k) {
        ArrayList<Integer> numbers = new ArrayList();
        numbers.add(3); 
        numbers.add(5);
        numbers.add(7);
        
        if (k < 0) {
            System.err.println("Type k > 0");
            return -1;
        }
        else if (k <= 2) 
            return numbers.get(k);
        
        int p1 = 0, p2 = 0, p3 = 0; // current pointers
        int mainp = 2;  // pointer to index of the last element
        
        while (numbers.size() <= k) {
            int res1 = numbers.get(p1) * 3,
                    res2 = numbers.get(p2) * 5,
                    res3 = numbers.get(p3) * 7;
            
            if (res1 > numbers.get(mainp) && res1 <= res2 && res1 <= res3) {
                numbers.add(res1);
                p1++;
                mainp++;
                if (res2 == res1) p2++;
                if (res3 == res1) p3++;
            }
            else if (res2 > numbers.get(mainp) && res2 <= res1 && res2 <= res3) {
                numbers.add(res2);
                p2++;
                mainp++;
                if (res2 == res1) p1++;
                if (res2 == res3) p3++;
            }
            else if (res3>numbers.get(mainp) && res3 <= res1 && res3 <= res2) {
                numbers.add(res3);
                p3++;
                mainp++;
                if (res3 == res1) p1++;
                if (res3 == res2) p2++;
            }
            else {
                // update all pointers
                p1++; p2++; p3++;
            }
        }
        
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
        
        return numbers.get(numbers.size() - 1);
    }
    
    public static void main(String[] args) {
        Ex75 exercise = new Ex75();
        // print the first 30 numbers with this property
        exercise.getNumber(30);
    }  
}


cap 8. OOP                                                                                                      

La acest capitol, raspunsurile tin de imaginatia fiecaruia, neexistand solutie unica. De fapt, rezolvarile sunt mai mult descriptive decat algoritmice, si anume modelarea unor clase cu anumite proprietati si care sa conlucreze bine.

Se au in vedere urmatoarele design patterns:
* singleton - o clasa care poate avea o singura instanta, accesul la instanta avand loc in cadrul aplicatiei
ex.   public class Restaurant {
          private static inst = null;
          public static Restaurant getInstance () {
            if (inst == null) { inst = new Restaurant (); }
            return inst; 
         }
       }
* factory method - existenta unei interfete pentru crearea unei instante a clasei, in care se decide carei subclase ii va apartine instanta

Exemple de intrebari (fara rezolvare):
* proiectarea unui lot de parcare folosind OOP 
* implementarea unui puzzle
* sistem de fisiere, etc.


cap. 9 - Recursivitate si Programare dinamica
In acest capitol, diferenta intre recursivitate si DP este ca DP are un plus de memorie care mai taie din intensitatea computationala a recursivitatii (vezi divide et impera) . Majoritatea programelor se pot rescrie din recursivitate in DP cu adaugarea unui caching.

* exista o scara care are N trepte. Un copil poate urca 1, 2 sau 3 trepte odata. In cate feluri posibile poate el sa ajunga in varful scarii?

#define MAX 100
// recursion: bottom-up - de la 0 trepte urcate pana ajunge la N
int ways = 0;

void runup1 (int n, int current) {
if (n <= current) {
if (n == current) ways++; // valid path completed
return;
}
runup1(n, current+1);
runup1(n, current+2);
runup1(n, current+3);
}

// dp: top-down - de sus in jos
int runup2 (int n, int map[MAX]) {
if (n<0) return 0; // invalid path
if (n==0)  return 1; // valid path completed
if (map[n] > -1) {
return map[n]; 
// nr. of ways you can run up to that point was already computed and cached
}
// else - compute and cache it
map[n] = runup2(n-1, map) + runup2(n-2, map) + runup2(n-3, map); /* cache nr. of ways you can  
reach height n as: nr. of ways you can reach via 1 step ahead + ..2 steps + ..3 steps ahead */
return map[n];
}

int main() {
int map [MAX],i;
for (i=0; i<MAX; i++) map[i] = -1;
printf("He ran in %d ways\n" ,runup2(4, map));
return 0;
}


* intr-un sir, indexul "magic" este nr. i pentru care  A[i] = i . Dandu-se un sir sortat de intregi distincte, scrieti o metoda pentru a afla un index magic in A . 

Sol.: ceva asemanator cu cautarea binara 

int magicIndex ( int myArray, int start, int stop ) {
  int mid = (start + stop) / 2; 
  if (stop < start) return -1;
  if (myArray [mid] == mid ) return mid;   /* index magic */
  if (myArray[mid] < mid ) {
    // partea stanga este exclusa, este prea inapoi, iar numerele sunt distincte, diferenta nu va fi acoperita
    magicIndex (myArray, mid+1, stop);
  }
  else {
    magicIndex ( start , mid-1 );
  }
}


* sa se afle toate submultimile unei multimi (pt. o multime cu n elemente exista 2^n submultimi)

Sol.:  pp A = {a1, a2, a3, ... , an } , atunci submultimile ce includ elemente cu nr. de ordine cel mult k sunt:
         k = 0 => {}
         k = 1 => {} , { a1 }
         k = 2 => {} , { a1 } , { a2 } ,  { a1, a2 } = P(2)
         k = 3 => P(2) + { a3 } + { a1, a3 } + { a2, a3 } + { a1, a2, a3 }
                   =  P(2) + clonele lui P(2) adaugand a3 la ele
         ...
         k = n  => P(n-1) + clonele lui P(n-1) adaugand an la ele

// pseudocod
void generate (int index, list<int> initialList) {
  if (index == 0)  return new emptyList;
  else {
    int currentElem = initialList.get(index);
    int prevLists = generate(index - 1, initialList);
    list <list <int>> newLists = init ();
    copy (newLists , prevLists);
    for ( mylist : prevLists ) {
      newLists.add ( mylist.add(currentElem));
    }
    return newLists;
}


* avem un numar infinit de monezi de 25 bani, 10 bani, 5 bani si 1 ban. In cate feluri de poate reprezenta suma de N bani?

Sol.:  am inlocuit banii cu centi.
# change(100) = change(100) using 0 quarters + 0 dimes
#   = change(100) using 0 quarters + 1 dime 
#   = change(100) using 0 quarters + 2 dimes
#   = ....
#   = change(100) using 0 quarters + 10 dimes -> SOLUTION!
#   = etc
# AND SO ON

# solutia considera monezi de la cele mai mari la cele mai mici

# n = amount of money
# denom = the largest coin available
# coin set is {25, 10, 5, 1} cents
# 25 = quarter, 10 = dime, 5 = nickel, 1 = penny
def change (n, denom):
next_denom = 0
if denom == 25:
next_denom = 10
elif denom == 10:
next_denom = 5
elif denom == 5:
next_denom = 1
elif denom == 1:
# there is no less denomination
# means a single way to pay the rest,
# using pennies
return 1
ways = 0
i = 0
while i * denom <= n:
# assume i*denom was used with the current denomination, 
# in how many ways we can give the rest using next denom?
ways += change (n-i*denom, next_denom)
i += 1
# all combinations with our current denom were used so far
return ways

# how many ways you can make this amount using
# coins less or equal than 25
print change(26, 25)


* avem o stiva cu N cutii, cu dimensiunile respective wi, hi, di. Cutiile nu se pot roti, dar se pot pune una deasupra alteia daca cutia de deasupra e mai mica decat cea de dedesubt in privinta tuturor celor 3 dimensiuni. Scrieti o metoda prin care se poate construi cea mai inalta stiva posibila, inaltime = suma inaltimilor tuturor cutiilor.

Sol.:    
createStack (boxes, bottom) {
  int max_height = 0;  List<Box> maxStack = null;
  for (int i = 0; i< boxes.length; i++ ) {
    if (boxes[i].canBeAbove (bottom)) {
      // TODO: ignora cutiile deja considerate, aflate sub bottom
      List<Box> new_stack = createStack (boxes, boxes[i]);
      new_height = getHeight(new_stack);
      if (new_height > max_height ) {
        max_stack = new_stack;
        max_height = new_height;
     } 
   }
  }
  if (max_stack == null) { max_stack = new ArrayList<Box> (); }
  if (bottom != null) { max_stack.add (0, bottom); {
  return max_stack;
}

Imbunatatire: cache,  un HashMap <Box, List<Box>> , unde cheia reprezinta cutia de la fund iar valoarea este cea mai buna stiva gasita pentru acest fund. 

20 aprilie 2015

Princeton Compilers design (SML) --- lista de teme rezolvate

Enunturile sunt prezentate pe pagina COS 320, prof. Andrew Appel (Princeton) dar si in folderul dropbox aferent _ENUNT_.html.

Rezolvarile, dupa cum urmeaza:
(2) Alpha convert 
(3) Type checking
(4) Lexical analyzer 
(5) Parser
(6) Simple MIPS code for solving Fibonacci
(7), (8), (9), (10) aici :
(7) Assembler code generation for Fun  - codegen.sml
(8) Liveness analysis - interference graph - liveness.sml - nu este 100% corect
(9) Graph coloring & register allocation - color.sml
(10) Spills / Putting it together  - regalloc.sml , mips.sml

Pentru compilare si rulare, stergeti toate extensiile .txt puse doar pentru pre-vizualizare in dropbox. 
> sml
Compilare: 
> CM.make "sources.cm";
Rulare (variaza, dupa caz):
> Test.run();
> RunLex.runlex "test.fun";      (* a #4 *)
> Compile.compile "test.fun";   (* a #5  si restul*)

Nota: sunt rezolvari personale care nu sunt ferite de bug-uri sau alte defecte, insa marele lor merit este ca au reusit ca limbajele de asamblare sa nu-mi mai para ca un fel de cutie neagra..

06 aprilie 2015

MIPS/SPIM - idei principale






sbrk = heap allocation for pointers or dynamic data, where $a0 is size of the allocation


> sudo apt-get install spim
> spim
(spim) load "loop.s"
(spim) run
(spim) reinitialize
(spim) quit

# altele aici


Finally - MIPS set instruction: