Duplicates in array elements and sorting

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)

• I just want to mention a fringe case obstacle. If the values in the array are floats (or any other type of value that will be mutated when used as an array key), then any answer that applies values as keys as a means to check for duplicate-ness will be prone to inaccuracy. Jan 28 '21 at 2:24

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.

• 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... May 27 '16 at 7:24
• Haha- me too :-) May 27 '16 at 9:37

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.

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