3
\$\begingroup\$

I've been given this little test exercise for an interview as php developer, and I'd like to hear from you if my solution is good (enough) or if the problem could have been solved in a better way. Please keep in mind that I've no academic training in CS or equivalent (rather the opposite) and my career started as a self-taught developer.

Given the array:

$numbers = array(
   1,  68,86, 52, 35, 86, 1, 24, 13, 72, 1
);

Take the duplicates and print them out in a string separated by a comma (ex. "a,b,c,d"), ordered in ascendent way.

$holder = [];  // holder for the duplicates
$prev = 0; // previous number
sort($numbers); // sorted them now, so the loop is one-time only

foreach($numbers as $num) {
   if ($prev == $num) {
      $holder[$num] = $num;
      /*I put the $num as index of the array so any double occurrence will overwrite any similar one, to avoid dupes on the $holder that would have compelled me to scan it again.*/
   }
   $prev = $num;  // assign the current number so on the next iteration
                  // i will compare with the next
}

echo implode(',', $holder); //print them out comma separated

I'm not sure if this is an optimal way or could be optimized / made better further. I'm guessing it's an \$O(n)\$ algorithm but again, I admit I have poor theoretical knowledge...

EDIT

My mistake, the requirements were for results sorted, I'm sorry for not pointing it out (I thought I did)

\$\endgroup\$
  • \$\begingroup\$ I am wondering what the expected output was. Did they just want to know which numbers occurred more than once? 1,86 Or did they want to know how many times a non-unique number occurred? 1,1,1,86,86? Or did they want to know how many EXTRA occurrences there were? 1,1,86? \$\endgroup\$ – mickmackusa Sep 16 '17 at 5:37
5
\$\begingroup\$

Since it's an interview, they're probably looking for one of two things:

  • You show that you understand logic
  • You know PHP

It's never advisable to "recreate the wheel", and PHP has built-in methods to do what you're looking for - for example:

// Count how many times each array value occurs in the array
$occurrences = array_count_values($numbers);
// Filter out any that aren't duplicates
$duplicates = array_filter($occurrences, function($count) { return $count > 1; });
// Format the output as requested
$output = implode(',', array_keys($duplicates));

I note you don't say you have a requirement to sort anything, so don't bother.

If I were hiring you I'd obviously prefer you had both of the points above, but I'd rather that you used PHP to its ability as much as possible. Aside from that, this is a code review site, so the same answer would stand in that case. Example.

\$\endgroup\$
  • \$\begingroup\$ I forgot to mention that the output should be sorted. To tell the truth, I've been developing in php for years and still have to resort to online docs to look for some of the various array functions the language has... \$\endgroup\$ – Damien Pirsy May 27 '16 at 7:24
  • \$\begingroup\$ Haha- me too :-) \$\endgroup\$ – Robbie Averill May 27 '16 at 9:37
2
\$\begingroup\$

This is an OK solution, but it's not \$O(n)\$, because of the sort step. The average performance of sort is \$O(n \log n)\$, and this is the most expensive operation of your implementation.

You can improve this to do without sorting, at the expense of using \$O(n)\$ extra space:

$found = [];
$duplicates = [];
foreach ($numbers as $num) {
    if (array_key_exists($num, $found)) {
        $duplicates[$num] = $num;
    }
    $found[$num] = true;
}

echo implode(',', $duplicates);

I also renamed $holder to $duplicates, as the latter doesn't describe itself well.

\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, what is the search efficiency of array_key_exists? Are the keys stored in a heap or a tree? \$\endgroup\$ – Colin Basnett May 25 '16 at 23:59
  • 2
    \$\begingroup\$ Arrays in php are hash tables, so checking if a key exists is O(1) \$\endgroup\$ – janos May 26 '16 at 5:54
  • \$\begingroup\$ Thanks for your answer, I actually made a mistake in my question: results had to be sorted \$\endgroup\$ – Damien Pirsy May 27 '16 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.