(Algorithm) Find and arrange combination of teams as pairs

Question: We have 4 teams and 3 gamedays. Write the algorithm that each team plays another team every gameday, and by the end of 3 game days, each team should have played one game with every other team.

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: rockeblaze

ANSWER

Consider teams as 1, 2, 3, and 4.

Store them into integer array.(ex. a[4])

Each day our teams will play different teams.

T1-T2 and T3-T4

T2-T4 and T1-T3

T1-T4 and T2-T3

As you see, we made our matching in three days. But focus that how we do it.

We did it by selecting them as pairs!

We just did combination in mathematics of 4 and 2.

But how we write these combinations in real world?

Answer is simple. While we are writing possible pairs, we check if we wrote this pair before. So, we should do this checking in programming world too.

We can calculate combination of 4 and 2 as 6. It means we have 6 possible pairs. So let's create two dimentional array to hold pairs that we created, so then, we can check if following pairs will be written are suitable. (ex. b[6][2])

Actually we chose next "neighbor" for each number. What I mean is:

1 2 3 4

we choose 1 and 2

1 - 2

Then we jumped into next: 3

1 - 3

Then finally jump to last: 4

1 - 4

Pass to second team: 2

2 - 3

2 - 3

And  third(which is last for algorithm):

3 - 4

Can you get the algorithm? We choose pairs like that, then arrange them so no team will play more than one match on same day.

You can use following pseudocode to choose pairs:

DEFINE and INITIALIZE i to 0.
DEFINE integer j.
DEFINE and INITIALIZE m to 0. //Last index of empty row of column b.
WHILE i is less than ((size of array a) - 1)
ASSIGN (i+1) to j
WHILE j is less than size of array a
STORE a[i] into b[m][0]
STORE a[j] into b[m][1]
INCREASE m by 1
INCREASE j by 1
END WHILE
INCREASE i by 1
END WHILE

After you find the pairs, just you have to do is print them on the screen so no team will play more than one match on same day. You can easily do it by checking array b's first rows.

(Algorithm) How to count frequencies of all elements of array

Question: How can we count frequencies of all elements of array?

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions
Question owner: HimanshuP

ANSWER

Let's give an example of array: a[9] = {5, 3, 7, 3, 3, 1, 6, 5, 7}

In real World, we recognize elements that we "already" count, and so we don't count them again. So, in computer world, we "remember" those already counted elements, too.

I will do this work with two dimensional array. Let's initialize two dimentional dynamic integer array b[1][1]. Then follow steps below:

Read element of array and store it into "k".

Check if this element is already stored into first column of array.(b[a][0] == k)

If it is not, then start to count this element from its location.

Else, skip this element. Because it was already counted.

Let's write pseudocode of this algorithm. End of this code we have two dimentional array which holds in second row that how many times does number repeat:

WHILE i is less than size of array a
SET flag to 0.
STORE a[i] into holder.
DEFINE and INITIALIZE counter m to 0.
WHILE m is less than number of rows of array b
IF b[m][0] is equal to holder.
SET flag to 1.
            END IF
            INCREASE m by 1
END WHILE
IF flag does not equal 1
INCREASE number of rows of array b by 1.
STORE holder into b[m][0].
DEFINE and INITIALIZE counter j to 1.
IF (i+1) is less than size of array a.
ASSIGN (i+1) to h.
WHILE h is less than size of a.
IF a[h] equals holder
INCREASE j by 1
END IF
                        INCREASE h by 1
END WHILE
END IF
STORE j into b[m][1]
END IF
INCREASE i by 1.
END WHILE

(Algorithm) How many Fibonacci numbers exist less than a given number?

Question: How many Fibonacci numbers exist less than a given number 'n'?

Ex. n = 4

{0, 1, 1, 2, 3}

5 numbers

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: Rahul Sharma

ANSWER

First of all, we should understand how Fibonacci numbers occur. (In modern usage) they start with 0 and 1. After this two numbers, they continue as sum of previous numbers. Let's see:

0, 1,...

0 + 1 = 1

0, 1, 1,...

1 + 1 = 2

0, 1, 1, 2,...

2 + 1 = 3

0, 1, 1, 2, 3,...

3 + 2 = 5

0, 1, 1, 2, 3, 5,...

I think you can continue easily from this point. From this series, we understand that we should start with two variable; (ex. x and y) and we should have counter to count, and n to number will be checked.

x = 0, y = 1, n = input, counter = 0

They are our first entries. And they build our previous numbers by using each other!

If (n > 0), we print x and increase counter by 1. If (n>1) we print y and increase counter by 1. For following numbers we can use for loop, because we have only condition to check and regularity. First we swap x and y. Because our y will be our x for next step. Then we assign (x + y) to y, then check if y is less than n. According to this, we increase counter and print y or break the loop.

(ENG) Algorithm to convert integers each other with minimum number of operations

Question: Convert integer m to integer n with minimum number of operations(m < n). Operations allowed are (-1) and (*2) Eg. 4 and 6.

-1 -> 4 - 1 = 3

*2 -> 3 * 2 = 6

2 operations.

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: Rahul Sharma

ANSWER

Thank you Emre Sermutlu for your feedbacks about the question.

Let's give one more example: 7 and 10

(-1) (-1) and (*2)

One more example: 6 and 10

(-1) and (*2)

We can see that if (m >= n%2), we use (-1) up to (m = n%2), then (*2)

If (m<n%2),...Let's try to see:

ex 1: 3 and 10

(*2) (-1) (5 is half of 10 this can be key!) and (*2)

ex 2: 4 and 10

(-1) we get 3!!!(2.5 =3 is half of 5) Then continue with same way (*2) (-1) and (*2)

ex 3: 1 and 10

(*2) (*2) (-1) we get 3!!!(2.5 =3 is half of 5) Then continue with the same way again!

Why did we try to get 3 every time? What is 3 for these numbers(4 and 10 or 1 and 10)? That is the main question. (2.5 =3 is half of 5; 5 is half of 10)

5

ex 4: 7 and 17

(-1) (-1)(4.5 = 5 is half of 9) (*2) (-1) This time we get 9!(8.5 = 9 is half of 17) (*2) (-1)

ex 5: 4 and 17

(-1)(2.5 = 3 is half of 5) (*2) (-1)(8.5 = 9 is half of 17) (*2) (-1)

Can you understand the regularity? Every time our "secondary" target is half of "main" target. To reach our secondary target, we always use (-1). And whenever our m is smaller than our secondary target, we update our secondary target with its half. However we shouldn't forget our second targets. Because we will use them again. How many secondary targets is there? We can count them in loop with if statement, or we can use dynamic memory allocation ways.

Let's use this way for one more example and see if it works:

ex 6: 11 and 29

11 < (29%2 = 15)

11 > (15%2 = 8)

11 (-1) (-1) (-1) = 8

When we reach our secondary target, then we update m by (*2), and up to our "next" secondary target(if we couldn't reach) we update m by (-1).

8 (*2) (-1) = 15

15 (*2) (-1) = 29

(ENG/TR) Algorithm to draw diamond shape/ Elmas çizen algoritma

1            *

2           **

3          ***

4         ****

5        *****

6       ******

7      *******

8     ********

9    *********

0   **********

1  ***********

2   **********

3    *********

4     ********

5      *******

6       ******

7        *****

8         ****

9          ***

0           **

1            *

ENGLISH

Whenever we try to find an algorithm, first we should find "regularity". Our diamond's middle which has 11 character length, is the largest entry. We see that we have "direct proportion" from up to middle. Then from middle to last line, we have "inverse proportion". I mean;

1. line, we write 1 * into 10. space

2. line, we write 2 * into 9. space

3. line, we write 3 * into 8. space

...

11. line, we write 11 * into 0. space

12. line, we write 10 * into 1. space

13. line, we write 9 * into 2. space

14. line, we write 8 * into 3. space

...

21. line, we write 1 * into 10. space

Now, it is easy to see the way to write this code: up to line 11 decrease space by 1, increase * by 1; from line 11 up to 21 increase space by 1, decrease * by 1.

TÜRKÇE

Her ne zaman bir algoritma bulmak istesek, ilk olarak "düzen"i bulmalıyız. Elmasımızın 11 karakter uzunluğundaki ortası, en uzun girdimiz. Orta kısma kadar "doğru orantı" olduğunu görüyoruz. Sonra ortadan, son satıra doğru "ters orantı"mız var. Yani:

1. satırda, 1 *'i 10. boşluğa yazıyoruz

2. satırda, 2 *'i 9. boşluğa yazıyoruz

3. satırda, 3 *'i 8. boşluğa yazıyoruz

...

11. satırda, 11 *'i 0. boşluğa yazıyoruz

12. satırda, 10 *'i 1. boşluğa yazıyoruz

13. satırda, 9 *'i 2. boşluğa yazıyoruz

14. satırda, 8 *'i 3. boşluğa yazıyoruz

...

21. satırda, 1 *'i 10. boşluğa yazıyoruz

Şimdi kodumuzu yazmanın yolu kolay: 11. satıra kadar boşluğu 1 azalt, *'i 1 arttır; 11. satırdan 21. satıra kadar boşluğu 1 arttır, *'i 1 azalt.

(ENG/TR) Algorithm to find prime number (Prime number bulmak için algoritma)

ENGLISH

Question: Find if inputted number(n) is prime or not.

ANSWER

First of all, we should think that how we find prime numbers in real life. We take a number(ex. 11), and try to find its dividers except 1(if there is). 

In example of 11, first we look 2. "11%2" not equals 0. So continue with 3. "11%3" not equals 0... We continue like that until the end(which is 11%5). As you see, our last element which will be checked is half of given number. Because we can not find integer multiplier for integer greater than half of number. So if we check these conditions, we can find if this number is prime or not.

You can update this algorithm like that: check 2 in anywhere else, then start from 3, increase value by 2. It may increase performance a little bit; but we accept that for large numbers, these two algorithms have same complexity.

TÜRKÇE

Soru: Girilen sayının(n) asal olup olmadığını bulunuz.

CEVAP

İlk olarak, gerçek hayatta bir sayının asal olup olmadığını nasıl anladığımızı düşünmeliyiz. Bir sayı alıyoruz(örn. 11), ve o'nun 1 dışındaki bölenlerini bulmaya çalışıyoruz(eğer varsa).

11 örneğinde, ilk olarak 2'ye bakarız. "11%2", 0'a eşit değildir. Dolayısıyla 3 ile devam ederiz. "11%3", 0'a eşit değildir... Bu şekilde devam ederiz sona kadar(yani 11%5) devam ederiz. Gördüğünüz üzere, kontrol edilecek son eleman, sayımızın yarısıdır. Çünkü sayımızın yarısından büyük tam sayılar için, tam sayı olan bir çarpan bulamayız. Bundan dolayı bu durumları kontrol edersek, bu sayının asal sayı olup olmadığını bulabiliriz.

Bu algoritmayı şu şekilde güncelleyebilirsiniz: 2'yi başka bir yerde kontrol edin, Sonra 3'ten başlayıp, değeri 2 arttırın. Bu, performansı birazcık arttırabilir; ama biz her iki algoritma içinde, çok büyük sayılar için, bu algoritmaların aynı karmaşıklığa sahip olduğunu kabul ederiz.

(C Language) (ENG/TR) Dynamic memory allocation (Dinamik hafıza tahsis etme)

ENGLISH

Actually, C language does not provide us a function for this work. However, there are functions in "stdlib.h" library about this.

malloc(), calloc(): These functions allocate space about determined size(n) for you, and return pointer. In other words, it returns an address. We can make steps for this purpose:

1)Initialize a pointer: int *ptr;

2)Get an integer n from user(or determine yourself)

3)Allocate determined memory space for pointer: ptr = (double*)malloc(n*sizeof(double));

Let's read this function from left to right: "We have double pointer. Allocate 'n times double' size for it."

After this, we can use this pointer as array! Like: ptr[0], ptr[1], ..., ptr[n - 1]

3)If we write this part again with calloc(): ptr = (double*)calloc(n,sizeof(double));

Let's read this function: "We have double type pointer. Allocate 'n times double' size for it."

Logic is the same actually. Only basic different is: 

malloc(): allocates memory about determined byte. 

calloc(): allocates determined size for array.

However, in both types, we can use this pointer as array like: ptr[0], ptr[1], ..., ptr[n - 1]

And we can write which type we want instead of double's;

When our work is done with this memory, then we should "free" this memory with free(name of pointer) function to improve performance. Because we don't want to carry "useless" weight anymore. 

Example: free(ptr);

However, we may want to change the size of pointer. That is why we use "dynamic memory allocation". The function we have to use is realloc(). I think it is relevant to "reallocation".

 ptr = realloc(ptr, new size); is the example of usage. You can write the new size as integer.

Aslında C dili bize bu iş için bir fonksiyon sunmuyor. Ama "stdlib.h" kütüphanesinde bununla ilgili fonksiyonlar mevcut.

malloc(), calloc(): bu fonksiyonlar sizin için belirli bir büyüklük(n) kadar yer ayırır ve pointer olarak return eder. Yani döndürdüğü değer bir adrestir. Kullanımını şu şekilde adımlara sokabiliriz:

1)Bir pointer initialize edin: double *ptr;

2)Kullanıcıdan bir integer(tam sayı) n değeri alın(veya siz verin)

3)Pointer'a istediğiniz büyüklükte bir bellek alanı ayırın: ptr = (double*)malloc(n*sizeof(double));

Bu fonksiyonu soldan sağa okursak: "double bir pointer'ımız var. Buna n tane double'lık yer ayır." anlamına gelir. Aslında basit bir İngilizce bilgisiyle kolayca anlaşılabilir bir yapıya sahip. Bunu tanımladıktan sonra pointer'ımızı bir array olarak kullanabiliriz: örnek: ptr[0], ptr[1], ..., ptr[n - 1]

3)Bu kısmı calloc() ile yazarsak: ptr = (double*)calloc(n,sizeof(double));

Bu fonksiyonu okuyalım: "double tipinde bir pointer'ımız var. Bu pointer'a n tane double'lık yer ayır." Mantık aynı aslında. Sadece temelindeki fark: 

malloc() kullanırken istenilen byte kadar yer ayırırız.

calloc() kullanırken array için istenilen kadar yer ayırırız. 

Ama iki türlü de ptr'mizi array olarak kullanabiliriz. 

ptr[0], ptr[1], ..., ptr[n - 1]

Ve double'lar yerlerine istediğimiz type'ı yazabiliriz.

Bu array ile işimiz bittikten sonra, performans için, hafızamızda bize yük olmasını istemeyiz. Bu yüzden hafızayı "serbest" bırakırız. Bu terim gerekli fonksiyonun özellikle aklınızda kalmasını sağlayabilir:

 free(ptr); .Yani free(pointer ismi) yazıp hafızamızı serbest bırakıyoruz.

Ama hafızamızı değiştirmek isteyebiliriz. Aslında dinamik hafızayı kullanmamızın nedeni de budur. Kullanmanız gereken fonksiyon realloc() tur. Yani ingilizce "reallocation" (yeniden tahsis) kelimesiyle alakalıdır sanıyorum. 

ptr = realloc(ptr, yeni alan); 

bu kullanımın bir örneğidir. "yeni alan" yerine girmek istediğiniz yeni alanı yazabilirsiniz.