Temat: Łamigłówka

Po wprowadzeniu liczby pojawiać powinien się komunikat:
"Liczba zawiera:
s tysięcy
x setek
y dziesiątek
z jedności"

Prosił bym o podanie waszych propozycji rozwiązań oraz dyskusję merytoryczną na ich temat

Temat: Łamigłówka

A gdzie jest podpucha? :) Chodzi o optymalizację kodu? Zrozumienie polecenia

Tak, wiem, że pisało "po wprowadzeniu", ale chyba chodzi o algorytm, a nie sposób wprowadzania liczby? To ma chodzić w pętli i dla każdej nowo dodanej cyfry do liczby generować wyjście, czy wystarczy liczbę "rozłożyć na składowe"?

Poniżej kod dla dwóch przypadków - gdy autorowi chodzi o liczbę dziesiątek jako o cyfrę stojącą na pozycji dziesiątek w liczbie wejściowej i liczbę wszystkich dziesiątek w liczbie wejściowej.

static void Main(string[] args)

{

      long Wejscie = 8521;



      long Liczba = Wejscie;

      long Jednosci = 0;

      long Dziesiatek = 0;

      long Setek = 0;

      long Tysiecy = 0;



      Console.WriteLine("Liczba zawiera:");



      Tysiecy = Liczba / 1000;

      Liczba -= Tysiecy * 1000;



      Setek = Liczba / 100;

      Liczba -= Setek*100;



      Dziesiatek = Liczba / 10;

      Liczba -= Dziesiatek * 10;



      Jednosci= Liczba;



      Console.WriteLine("{0} tysięcy", Tysiecy);

      Console.WriteLine("{0} setek", Setek);

      Console.WriteLine("{0} dziesiatek", Dziesiatek);

      Console.WriteLine("{0} jednosci", Jednosci);



      Console.Write("\n----------------------\n");

      

      Liczba = Wejscie;

      Console.WriteLine("{0} tysięcy", Liczba / 1000);

      Console.WriteLine("{0} setek", Liczba / 100);

      Console.WriteLine("{0} dziesiatek", Liczba / 10);

      Console.WriteLine("{0} jednosci", Liczba);

      Console.ReadKey();

}

Adrian Olszewski edytował(a) ten post dnia 23.01.10 o godzinie 12:51

Temat: Łamigłówka

bardziej o przetestowanie tego czy tego typu zagadki mają odbiorcow

Temat: Łamigłówka

Czyli dałem ciała? :) Nadgorliwość gorsza od faszyzmu?
I gdzie jest ta zagadka? :> Bo poziom złożoności to mniej więcej - ile jest samogłosek w podanym wyrazie, ale pomyślałem, że a nuż dowiem się czegoś nowego :)Adrian Olszewski edytował(a) ten post dnia 23.01.10 o godzinie 12:56

Temat: Łamigłówka

chcesz trudniejsze zadanie?
zrób to samo ale bez dzieleniaPrzemysław R. edytował(a) ten post dnia 23.01.10 o godzinie 13:03

Temat: Łamigłówka

A mogę pomnożyć razy odwrotność? :)

Jeśli liczba ma mieć policzoną liczbę tysięcy, a nie np. dziesiątek tysięcy (i setek, etc.)

     

int Wejscie = 32;



string Liczba = Wejscie.ToString().PadLeft(4, '0');



Console.WriteLine("Liczba zawiera:");



Console.WriteLine("{0} tysięcy", Liczba[0]);

Console.WriteLine("{0} setek", Liczba[1]);

Console.WriteLine("{0} dziesiatek", Liczba[2]);

Console.WriteLine("{0} jednosci", Liczba[3]);



Console.ReadKey()

;

A numerycznie - zaraz pomyślę :)

Temat: Łamigłówka

ok
widzę że to za łatwe

to może w takim wypadku implementację Schematu Hornera

Temat: Łamigłówka

OK, widzę, że chodziło o żart, a nie o coś ciekawego :]

Ale przy okazji - liczenie w pętli, skoro miało być bez dzielenia :]

int Liczba = 8541;



            if (Liczba >= 10000) return;



            int Tysiecy=0;

            int Setek=0;

            int Dziesiatek=0;

            int Jednosci=0;



            while (Liczba >=0)

            {

                Liczba -= 1000;

                if (Liczba >= 0)

                {

                    Tysiecy++;

                }

            }



            Liczba += 1000;



            while (Liczba >= 0)

            {

                Liczba -= 100;

                if (Liczba >= 0)

                {

                    Setek ++;

                }

            }

            Liczba += 100;



            while (Liczba >= 0)

            {

                Liczba -=10;

                if (Liczba >= 0)

                {

                    Dziesiatek++;

                }

            }

            Liczba +=10;



            while (Liczba >= 0)

            {

                Liczba--;

                if (Liczba >= 0)

                {

                    Jednosci++;

                }

            }



            Console.WriteLine("{0} tysięcy", Tysiecy);

            Console.WriteLine("{0} setek", Setek);

            Console.WriteLine("{0} dziesiatek", Dziesiatek);

            Console.WriteLine("{0} jednosci", Jednosci);

Adrian Olszewski edytował(a) ten post dnia 23.01.10 o godzinie 13:47

Temat: Łamigłówka

Myślę, że ciekawszym zadaniem byłoby rozwiązywanie zadań rekrutacyjnych Microsoftu, Google, itd.. ;)

Wystarczy podać schemat działania, a jeśli macie więcej czasu to implementację.

Na początek ta lista:

Write a method to combine two two sorted linked list into one in
sorted form with out using temporary Node.
void sort(Node* list1,Node* list2)

Write an algorithm to verify if a tree is a binary search tree.

Implement a counting semaphore using only binary mutexes

You have 8 balls. One of them is defective and weighs less than
others. You have a balance to measure balls against each other. In
2 weighings how do you find the defective one?

Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
making use of any floating point computations at all.

Given an array of characters which form a sentence of words, give
an efficient algorithm to reverse the order of the words (not
characters) in it.

Given an array t[100] which contains numbers between 1..99.
Return the duplicated value. Try both O(n) and O(n-square).

Jest tego wiele w sieci :-)

To może zacznę ja:

Write a method to combine two two sorted linked list into one in
sorted form with out using temporary Node.
void sort(Node* list1,Node* list2)

Mamy p1, p2 wskaźniki na początki tych list.
Sprawdzmy który jest większy: p1 czy p2.
L1 - początek jest większy, L2 - początek jest mniejszy.
L1 porównujemy z kolejnymi elementami L2 do momentu aż jeden z L2 będzie większy od L1, wtedy wkładamy element z L1 przed ten element z L2.
z kolejnymi elementami L1 robimy podobnie tyle, że iterujemy od momentu włożenia poprzedniego elementu.

Złożoność: O(n), gdzie n jest długością dłuższego ciągu / wariant pesymistyczny.

Write an algorithm to verify if a tree is a binary search tree.

Tworzymy kolejkę, p1 jest wskaźnikiem na korzeń drzewa.
Dodajemy korzeń do kolejki.
w kolejce wyrzucamy korzeń i sprawdzamy ile ma dzieci.
Jeśli wyrzucony element drzewa ma mniej lub równe 2 dzieci, dodajemy jego dzieci do kolejki w przeciwnym wypadku kończymy działanie algorytmu i wiemy, że drzewo nie jest binarne.
Robimy tak, aż skończą się elementy w kolejce.

edit: nie tylko sprawdzanie czy jest binarne ale czy BST! - zupełnie przeoczyłem to.
no więc do każdego kroku gdzie sprawdzamy ilość dzieci, sprawdzamy czy lewe dziecko jest mniejsze i prawe większe od danego elementu.

Złożoność: O(n)

Do boju Panowie! :)Karim Agha edytował(a) ten post dnia 24.01.10 o godzinie 15:06

Temat: Łamigłówka

You have 8 balls. One of them is defective and weighs less than
others. You have a balance to measure balls against each other. In
2 weighings how do you find the defective one?

Fajnie mieć 8 kulek :).
Pierwsze ważenie to po 3 kulki na każdej z szalek.
=> Jeśli są równe to ważymy pozostałe 2 kulki i znajdujemy lżejszą.
=> Jeśli nie to bierzemy 3 kulki lżejsze i dwie z nich ważymy. Jeśli równe to pozostała 3cia jest lżejsza. Jeśli są różne to waga nam wskaże lżejszą.

Temat: Łamigłówka

Given an array t[100] which contains numbers between 1..99.
Return the duplicated value. Try both O(n) and O(n-square)

Dla O(n) wybieram sposób oparty o naturalną cechę idealnej hashmapy - pod danym kluczem powinien znajdować się tylko jeden, różny od pozostałych obiekt (w sensie wartości f. haszującej wykonanej na obiektach). W tym przypadku do uzyskania indeksu wystarczają liczby z zakresu 0..99, a zatem zawartość badanej tablicy.

Kolejnymi liczbami z badanej tabeli indeksuję hm. i inkrementuję wartość wskazanych komórek haszmapy. Jeśli dla danej liczby okaże się, że wartość zaindeksowanej nią komórki haszmapy > 1, wypisuję tę liczbę. Złożoność - O(n) dla przejścia tablicy, O(1) dla znalezienia w HM (o ile funkcja h. jest idealna na podanej dziedzinie - u mnie jest), zatem łącznie O(n).

Wada: tworzę dodatkową strukturę danych. Tutaj danych jest mało, ale gdyby było bardzo dużo...

// Generowanie danych w tablicy

            int[] Tab = new int[100];

            System.Random Rnd = new System.Random();



            for (int i = 0; i < 99; i++)

            {

                //Tab[i] = i+1;



                Tab[i] = Rnd.Next(1, 99);

            }

            //Tab[99] = Rnd.Next(1, 99);



            // Utworzenie i przygotowanie haszmapy (wszystkie komórki = 0)

            int[] HM = new int[100];





            // Kontrola duplikatów

                for (int i = 0; i < 100; i++)

                {

                    HM[ Tab[i] ]++;



                    if(HM[ Tab[i] ] > 1)

                    {

                        Console.WriteLine("Duplicated: {0}", Tab[i]);

                    }



                }

            Console.ReadKey();

Dla O(n2) mogę brać każdą z wartości tablicy i przeglądać kolejne komórki w poszukiwaniu duplikatu - 2 zagnieżdżone pętle. Mogę także posortować wartości (O(nlogn), pesym. O(n2)), a następnie zrobić przegląd liniowy (O(n)), co razem daje O(n2). Nie potrzebuję jednak dodatkowej struktury pamięci.Adrian Olszewski edytował(a) ten post dnia 24.01.10 o godzinie 14:44

Temat: Łamigłówka

O! :)

http://www.careercup.com/page?pid=microsoft-interview-... tu jest jeszcze więcej. Może z tej listy zaczniemy przerabiać?

_____________________________________________________
There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing.


Given a binary tree
struct node{
struct node* leftChild;
struct node* rightChild;
struct node* nextRight;
}
populate the nextRight pointers in each node.
(_to akurat jest podoble do tego co w poprzednim poście rozwiązałem_.)

Given a set of coordinates (x_i, y_i), i ranges from 1 to n, the coordinate values are integers, write a function 'bool isCenterInteger(int points[][])' which returns true if at least one of the midpoints of the line joining the points is an integer.

sort an array of 0's and 1's in a most efficient way.

given a matrix (assume it is a bitmap), print all cells that are on
__________________________________________________________

To ja zrobię to:

given a matrix (assume it is a bitmap), print all cells that are on

To jest zajebiście podchwytliwe pytanie.

mamy tablicę bmp[k][j]:
tablica jest uporządkowana w taki sposób w pamięci:

bmp[k1] - [j1][j2][j3][j4]...[jn]

bmp[k2] - [j1][j2][j3][j4]...[jn]

.

.

.

bmp[kn] - [j1][j2][j3][j4]...[jn]

I teraz zależy od tego co uznamy za X a co za Y - k czy j.
Różnica w prędkości działania sięga do 30x. Już wyjaśniam:

W przypadku tablic, alokowana pamięć w jednej tablicy jednowymiarowej, jest ciągła - czyli przeskok z jednego obszaru pamięci do drugiego jest bardzo szybko - przesuwamy adres o jeden.

Przechodzenie pomiędzy różnymi poziomami w wielowiamarowych tablicach jest już wolniejsze ponieważ o ile "j0..jn" są ciągłym obszarem pamięci o tyle k1j1.. knj1" nie są i zmieny adresu są wolniejsze.

Dlatego powinniśmy brać k jako Y i j jako X.

bmp[y][x]

for(int i = 0; i < y_count; i++)

  for(int j = 0; j < x_count; j++)

     bmp[i][j] // zrob cos

http://msdn.microsoft.com/en-us/magazine/cc850829.aspx
tutaj jest to dobrze opisane.Karim Agha edytował(a) ten post dnia 24.01.10 o godzinie 15:40

Temat: Łamigłówka

Given an array t[100] which contains numbers between 1..99.
Return the duplicated value. Try both O(n) and O(n-square).

Przecież to się da prościej niż przez wyszukiwanie powtórzeń ;)

Skoro mamy tablicę 100 elementów, i 99 różnych, całkowitych wartości z przedziału (1;99), to oznacza, że w 99 elementach tablicy będzie te 99 wartości, a 100-tny element będzie zawierał dokładnie jedno powtórzenie.

A więc zrobiłbym tak: obliczyłbym sumę wszystkich elementów tablicy. Następnie, korzystając ze znanego faktu, że suma kolejnych liczb naturalnych od 1 do n wynosi n*(n+1)/2, czyli w tym wypadku 99*100/2 = 4950, odjąłbym od wcześniej obliczonej sumy 100 elementów to 4950 i wyszłoby, co się powtarza. Nie?

Temat: Łamigłówka

sort an array of 0's and 1's in a most efficient way.

Ja to bym zrobił tak:
biorę dwa indeksy, jeden idzie od początku tablicy, drugi od końca. W pętli, w każdym jej obrocie, będę pierwszy zwiększał o 1, a drugi jednocześnie zmniejszał o 1 - aż się "spotkają".
I teraz w każdym obrocie pętli, sprawdzałbym relację pomiędzy elementami tablicy wskazywanymi przez te indeksy, i jeśli byłaby "zła", zamieniałbym wartości tych elementów miejscami.
Może być?Piotr G. edytował(a) ten post dnia 25.01.10 o godzinie 15:36

Temat: Łamigłówka

Piotr G.:

Given an array t[100] which contains numbers between 1..99.
Return the duplicated value. Try both O(n) and O(n-square).

Przecież to się da prościej niż przez wyszukiwanie powtórzeń ;)

Skoro mamy tablicę 100 elementów, i 99 różnych, całkowitych wartości z przedziału (1;99), to oznacza, że w 99 elementach tablicy będzie te 99 wartości, a 100-tny element będzie zawierał dokładnie jedno powtórzenie.

A więc zrobiłbym tak: obliczyłbym sumę wszystkich elementów tablicy. Następnie, korzystając ze znanego faktu, że suma kolejnych liczb naturalnych od 1 do n wynosi n*(n+1)/2, czyli w tym wypadku 99*100/2 = 4950, odjąłbym od wcześniej obliczonej sumy 100 elementów to 4950 i wyszłoby, co się powtarza. Nie?

Mogłem nie usuwać pierwszej części wypowiedzi, że GDYBYM wiedział, że są tam WSZYSTKIE liczby z przedziału 1..99 (nie mylić z "wszystkie wartości należą do tego przedziału"), to skorzystałbym z wzoru sumacyjnego :) Akurat to zadanie często się powtarza, zwłaszcza dla liczb posortowanych, gdzie wystarczy badać sumy 1+99, 2+98 etc :)

Ale ja zrobiłem na ogólny przypadek, gdy mogą tam być liczby z zakresu 1..99 (uwaga - brak słowa wszystkie) :) I tak właśnie to zrozumiałem: np. {1,1,1,1,97, 97, 99,99, 44,55,22,11....} - dlatego zrobiłem przypadek ogólny :) Można rzec - w pełni świadomie.

Co prawda jest napisane "duplicated value" a nie "values", co sugeruje jedną powtórkę, czyli 98 pozostałych musi być unikalnych, ale może chodzić o zwrócenie jeden powtórki z n. Mnie na czymś takim złapano kiedyś na jednym teście i od tej pory mam paranoję :) Możliwe, że chodziło jednak o najzwyklejszy ciąg {1,2,....97,98,REP.}Adrian Olszewski edytował(a) ten post dnia 25.01.10 o godzinie 16:06

Temat: Łamigłówka

Ooops - masz rację ;) Nie ma ani słowa o tym, że wykorzystane jest wszystkie 99 wartości. Zwracam honor ;) Zasugerowałem się tym: "Return the duplicated value." - wyraźnie piszą, żeby zwrócić tą wartość (a nie wartości!), która się powtarza.
Ale rzeczywiście z tego wcale nie wynika, że powtórzenie ma być dokładnie jedno - wynika tylko to, że mamy znaleźć dokładnie jedno powtórzenie, a nie wszystkie.

Twoja metoda z dodatkową tablicą (wektorem) "obecności" jest rzeczywiście uniwersalna - zmieniłbym tylko jedno: zamiast tablicy int dałbym tablicę bool (bo nie obchodzi nas de facto ilośc powtórzeń danej wartości tylko fakt, że się powtarza). A jeśli miałbym (musiałbym) pozostać przy tablicy int to zamiast inkrementować jej element i sprawdzać, czy jest > 1 najpierw bym sprawdził, czy jest > 0 i albo wyświetlił, że już było, albo dopiero bym zainkrementował. Zawsze jedna inkrementacja mniej, nie?Piotr G. edytował(a) ten post dnia 25.01.10 o godzinie 16:33

Temat: Łamigłówka

Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
making use of any floating point computations at all.

Z tego wynika, że:
1. okrąg ma środek w punkcie (0,0)
2. x, y i r muszą być całkowite (bo inaczej musimy stosować floating pointy)

Kto pisał kiedyś grafikę w assemblerze, wie, o co biega ;)
Korzystając z tego, że po przekształceniu: y**2 = r**2 - x**2, zrobiłbym to tak:

bool DrawCircle(int r)
{
if (r = 0)
return false; // nie ma co rysować

int r2 = r * r; // żeby nie liczyć w pętli

for (int x = 0, y = r; x <= r; x++)
{
int r2_minus_x2 = r2 - x * x;
while (y * y > r2_minus_x2) y--;
if (y < 0)
break;
plot(x, y);
plot(-x, y);
plot(x, -y);
plot(-x, -y);
}
return true;
}

Okrąg będzie co prawda nieco mniejszy (wszystkie punkty będą leżały na okręgu lub w jego wnętrzu), ale będzie. Można byłoby jeszcze dodać trochę "szumu", np. dla parzystych x dodawać 1 do y, żeby co drugi punkt wyszedł poza okręgiem, ale to już kosmetyka.Piotr G. edytował(a) ten post dnia 25.01.10 o godzinie 16:35

Temat: Łamigłówka

Paweł Łukasik:

You have 8 balls. One of them is defective and weighs less than
others. You have a balance to measure balls against each other. In
2 weighings how do you find the defective one?

Fajnie mieć 8 kulek :).
Pierwsze ważenie to po 3 kulki na każdej z szalek.
=> Jeśli są równe to ważymy pozostałe 2 kulki i znajdujemy lżejszą.
=> Jeśli nie to bierzemy 3 kulki lżejsze i dwie z nich ważymy. Jeśli równe to pozostała 3cia jest lżejsza. Jeśli są różne to waga nam wskaże lżejszą.

To rzeczywiście chyba jedyny algorytm.Piotr G. edytował(a) ten post dnia 25.01.10 o godzinie 16:44

Temat: Łamigłówka

Piotr G.:

Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
making use of any floating point computations at all.

Z tego wynika, że:
1. okrąg ma środek w punkcie (0,0)
2. x, y i r muszą być całkowite (bo inaczej musimy stosować floating pointy)

Kto pisał kiedyś grafikę w assemblerze, wie, o co biega ;)
Korzystając z tego, że po przekształceniu: y**2 = r**2 - x**2, zrobiłbym to tak:

bool DrawCircle(int r)
{
if (r = 0)
return false; // nie ma co rysować

int r2 = r * r; // żeby nie liczyć w pętli

for (int x = 0, y = r; x <= r; x++)

> {

int r2_minus_x2 = r2 - x * x;
while (y * y > r2_minus_x2) y--;
if (y < 0)

> break;

plot(x, y);
plot(-x, y);
plot(x, -y);
plot(-x, -y);
}
return true;
}

Okrąg będzie co prawda nieco mniejszy (wszystkie punkty będą leżały na okręgu lub w jego wnętrzu), ale będzie. Można byłoby jeszcze dodać trochę "szumu", np. dla parzystych x dodawać 1 do y, żeby co drugi punkt wyszedł poza okręgiem, ale to już kosmetyka.Piotr G. edytował(a) ten post dnia 25.01.10 o godzinie 16:35

Hehe, można jeszcze to uprościć, bo skoro punkt (x,y) należy do okręgu, to (y,x) też należy (przy założeniu, że okrąg ma środek w punkcie (0,0)).
Otrzymamy więc o połowę "krótszą" pętlę:

bool DrawCircle(int r)
{
if (r = 0)
return false; // nie ma co rysować

int r2 = r * r; // żeby nie liczyć w pętli

for (int x = 0, y = r; x <= y; x++)
{
int r2_minus_x2 = r2 - x * x;

while (y * y > r2_minus_x2) y--;

if (y < x)
break;

plot(x, y);
plot(-x, y);
plot(x, -y);
plot(-x, -y);

plot(y, x);
plot(-y, x);
plot(y, -x);
plot(-y, -x);
}

return true;
}

Temat: Łamigłówka

OO widzę, że Panowie się wzięli za te testy. W trosce o to, żeby zabawa nie skończyła się z powodu braku pytań to tutaj jest kojenia porcja:

- binary tree, nodes, each node has an ID
- root node of the tree

structure node
{
int id;
node * left;
node *right;
}

- problem: given node id 1, and node id 2, determine the
lowest common ancestor of these 2 nodes

- input:
id1, id2, root

- out: node id of this ancestor node

______________________

Amazon.com has hired you to design their system in .NET.
List 10 business requirements and then draw me a design to meet the requirements.
Don't just put UI, BL, DL, DB either. "I will be back in 45 minutes > (note: guy comes back in 15 minutes later)." Explain your requirements list to me. Explain your design diagram to me. Why did you do it that way?

(to akurat jak komuś się chce pisać esseye :-))
_______________________

You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above.

_______________________

Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.

(to już było ale w innej formie)
_______________________

Give a one-line C expression to test whether a number is a power of 2. No loops allowed.

_______________________

Give a very good method to count the number of ones in a 32 bit number. (caution: looping through testing each bit is not a solution)