Pair socks from pile

Question: How to find pair socks from a pile efficiently?

Resource: http://stackoverflow.com/questions/14415881/pair-socks-from-a-pile-efficiently

Question Owner: amit

ANSWER

Actually, you can do this by selecting one sock and searching all the pile. It is least efficient way I guess.

Try to think this problem like solving a puzzle. Before to solve a puzzl, first, we group all same colors like "yellows go this pile" or "blue ones go there". This method is called hashing(or maybe only I call this like that I do'nt know :))

After we grouped we can search easily them. Try to think this with letters from 'A' to 'Z'. We have 26 pairs as "A-A" or "J-J".

Consider them as colors and say: "First 13 letters are yellow, and last 13 are blue"

We search all socks(letters) and group them according to their colors.

Then, we can look more carefully and notice their patterns to find pairs.

(Algorithm) Find n'th Fibonacci nuber with complexity O(log(n)) and in O(1) space

Question: We have given number n. And it is asked that we have to find n'th Fibonacci number. However, we have two conditions.

1) Complexity should be O(log(n))

2)We should compute this in O(1) space

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

Question Owner: zr.roman

ANSWER

I think, maybe, Term which is "O(1) space" may confuse your mind.

"O(1) space" means you should use same memory for all kind of n's.

Let's try to catch the "regularity" from examples:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

You may think that you can store all Fibonacci numbers, and use binary search algorithm.

However this way is useless, because Fibonacci sequence is infinite. There always be greater Fibonacci number for your last number stored.

I will use formula to compute this by rounding with the help of golden ratio. You can find more about this in this link.

This computing is in O(1) space and has complexity O(1) too. If you have any extra solution pls contact me.

(Algorithm) Turn string into integer

Question: Turn given number(integer) as string into integer.

Ex. "one million two hundreds thousands fifty seven" => 1200057

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

Question Owner: tamashionuth

ANSWER

I modified this example as all words only contain lower case characters. However you can easily handle upper case characters with this algorithm too. Whenever we try to solve a problem, we try to catch the algorithm. However, sometimes it is not enough that get only "regularity", and we also have to "teach" computer some "human-made" words.

As basic, we have twelve numbers and common special words to create an integer.

zero

one

two

three

four

five

six

seven

eight

nine

ten

eleven

twelve

"teen"

I think this key words are enough to create all numbers. We don't have to remember keywords like hundred, thousand, billion etc.

Let's split algorithms we have, to define numbers.

From 0 to 12

We have defined them, so computer can understand when it sees the number.

From 13 to 19

We have "teen" keyword in the whole word(eg. fourteen).

First we have to check if word contains this keyword.

If our answer is "yes", then look whole word's first two letter. These letters tell us what number is.

These two letters are abbreviation of first nine numbers from one.

(eg. thirteen => starts with 1 because of teen, continues with 3 because of th)

From 20 to 99

We look first two letters again. When we see "abbreviation" of first 9 numbers, we can talk about it's first digit. Then look second word and try to match it with our first 9 numbers. If we find matching, we can say it's second digit; if we don't find, it means second digit is zero.

(eg. fifty one => abbreviation of 5 and full word of one. So number is 51)

From 100 to 999

We will only have hundred keyword as extra which is already known by our program.

(e.g five hundred sixty two => 5 because of fi, 6 because of si, and two. So 562)

From 1000 to 9999

We will continue from there with only examples, because I think you get the algorithm.

(e.g ten thousand seven hundred eleven => 10711)

And, so on... We only have one step to reach the number:

1. Catch the keyword

Then write the number easily.

(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