Geek asks and answers

Interview - Write a program to remove even elements

I was asked today, and I know that the answer is simple, but it kept me to the last.

Question

Write a program to remove even numbers stored in ArrayListcontaining 1 - 100.

I just said wow

Here you will go the way I implemented it.

ArrayList source = new ArrayList(100);
for (int i = 1; i < 100; i++)
{
    source.Add(i);
}


for (int i = 0; i < source.Count; i++)
{
    if (Convert.ToInt32(source[i]) % 2 ==0)
    {
        source.RemoveAt(i);
    }
}

//source contains only Odd elements

Twist

He asked me what computational complexity of this gives him the equation. I just did it and said that it is linear, directly proportional to N (input).

he said: hmmm .. so that means I need to wait longer to get the results, when the input size increases, am I right? Yes sirr you are

Set it up for me, make it Log(N)try as much as you could say. I failed in this part.

  • , , .

: , .

+5
7

:

, , - , , ( ). , O (N).

, , , , .

, , , .

, , - , ( , b-... ), ( sotring ).

?

+4

, O (N ^ 2), - O (N) .

, O (N) () O (N) = > O (N) * O (N).

, . ( , ). . , , N-1 :

1 2 3 4 5 6...
<---
2 3 4 5 6...

, , N-1 + N-2 + ... + 1 + 0, (N) * (N-1) / 2 ( ), O (N ^ 2).

+5

, , - , - .

int read = 0
int write = 0;

, ; . , , , .

for (int read = 0; read < source.Count; read++) {
  if (source[read] % 2 != 0) {
    source[write] = source[read];
    write += 1;
  }
}

ArrayList, `write '.

O (n ^ 2) O (n).

(: )

+2

ArrayList ( , )

+ 1, + 2 , .

for (int i = source.Count - 1 ; i > 0; i = i i 2)
{
   source.RemoveAt(i);
}

. , , source 1-100 .

+1

, ArrayList, , (, O(n)). , , , .

+1

, , , :

Initial List:       1, 2, 3, 4, 5, ..., 98, 99
                         /  /  /  ///  /
After 1st removal:  1, 3, 4, 5, ..., 98, 99, <empty>
                            /  ///  /   /
After 2nd removal:  1, 3, 5, ..., 98, 99, <empty>, <empty>

, , .

( , ), :

for (int i = source.Count-1; i >= 0; --i)  {
  if (Convert.ToInt32(source[i]) % 2 == 0) {
    // No need to re-check the same element during the next iteration.
    source.RemoveAt(--i);
  }
}
+1

IF, , .

, n. . , .

  • , . ( O(1).)
  • , . ( O(log(n)).)
    • 0 1 , . , .
    • , . 2 .
    • 4 2, , 3, 2 . 4 .
    • Continue this pattern with blocks 2**i(if you add a counter for the lower half in the upper half) times - now each entry in this array is a coefficient counter below.log2(n)
  • Each processor inserts its value into the correct slot.
  • Truncate the array to the desired size.

I bet something like this is the answer your friend has in mind.

+1
source

More articles:


All Articles