1
\$\begingroup\$

I was asked an question for writing a program where the input will be array of numbers;

the output of the program will be array of numbers without duplicates.

I coded in javaScript which runs on node, as follows.

In my first attempt, I first sorted the numbers in ascending order and then I removed the duplicates by comparing the number from previously occurred numbers

the code is as follows,

var numList = [];

// below function is used to capture the 
// command-line parameters for array and the
// number to be searched
(function(){
    process.argv.forEach(function (val, index, array) {
        var idx = 0, ar = undefined;

        try{

            if(index === 2){

                ar = val.split(",");

                // convert the numbers present as string values is array
                // to array of numbers
                for(idx = 0; idx < ar.length; idx++){
                    numList.push(parseInt(ar[idx]));
                }
            }           

        }catch(e){
            console.log(e)
        }

    });
})();



console.log(" Input Array ",numList);

numList = uniqueNumArray01(numList);


console.log(" Array without duplicate numbers ",numList)

function uniqueNumArray01(numberList){
    var _numberList = [],
        nextIndex = 0; 
        currentIndex = 0,
        prevIndex = 0, 
        temp = 0,
        isSwapped  = false,
        index = 0;

    // do bubble sort on input array of numbers
    do{
        isSwapped  = false;
        for(index = 0; index < numberList.length; index++){
            currentIndex = index;
            nextIndex = index + 1;

            if(nextIndex >= numberList.length){             
                break;
            }

            if(numberList[currentIndex] > numberList[nextIndex]){
                temp = numberList[currentIndex];
                numberList[currentIndex] = numberList[nextIndex];
                numberList[nextIndex] = temp;
                isSwapped = true; 
            }

        }// end of for
    }while(isSwapped === true);

    console.log("Sorted Number array ",numberList);

    // create array of unique numbers
    for(index = 0; index < numberList.length; index++){
        if(index === 0){
            currentIndex = index;
            prevIndex = index;

            _numberList.push(numberList[currentIndex]); 
        }else{
            currentIndex = index;

            if(numberList[currentIndex] !== numberList[prevIndex]){
                _numberList.push(numberList[currentIndex]);
            }

            prevIndex = currentIndex;
        } // end of else

    } // end of for

    return _numberList;

} // en of uniqueNumArray01

The output of the above code is as follows,

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node duplicateNum01.js 12,34,12,56,12,34,56,1,2,12,12,12
 Input Array  [ 12, 34, 12, 56, 12, 34, 56, 1, 2, 12, 12, 12 ]
Sorted Number array  [ 1, 2, 12, 12, 12, 12, 12, 12, 34, 34, 56, 56 ]
 Array without duplicate numbers  [ 1, 2, 12, 34, 56 ]

He was not satisfied;

So I suggested an another solution where I wont sort the array, instead I will first iterate through the array and on each iteration I will check if the number present in current iteration is present in previous positions.

Hence to check if the current number ever exists in previous positions, I will again start from start index and do comparison; this I will do till the previous index of the current one.

My next solution is as follows,

console.log(" Input Array ",numList);

numList = uniqueNumArray02(numList);

console.log(" Array without duplicate numbers ",numList);

function uniqueNumArray02(numberList){
    var index = 0, 
        _numberList = [],// new array holding non repeating numbers
        startIndex = 0,
        lastIndex = 0,
        currentNumber = 0,
        prevNumber = 0, 
        isDuplicateFound = false;

    for(index = 0; index < numberList.length; index++){
        currentNumber = numberList[index];
        startIndex = 0;         
        isDuplicateFound = false;


        if(index === 0){
            _numberList.push(currentNumber);
        }else{

            // search for occurance of number in previous part of array
            // till the current index
            for(startIndex = 0; startIndex < index; startIndex++){
                prevNumber = numberList[startIndex];

                if(prevNumber === currentNumber){
                    isDuplicateFound = true;
                    break;
                }
            } // end of for

            if(isDuplicateFound === false){
                _numberList.push(currentNumber);    
            }

        }// end of else
    }// end of for

    return _numberList;
}// end of uniqueNumArray02 

The output of the above program is as follows,

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node duplicateNum01.js 12,34,12,56
 Input Array  [ 12, 34, 12, 56 ]
 Array without duplicate numbers  [ 12, 34, 56 ]

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node duplicateNum01.js 12,34,12,56,12,34,56,1,2,12,12,12
 Input Array  [ 12, 34, 12, 56, 12, 34, 56, 1, 2, 12, 12, 12 ]
 Array without duplicate numbers  [ 12, 34, 56, 1, 2 ]

But the interviewer was not satisfied; but appreciated my application of logic.

Is there a better solution for the above problem.

Requesting to please do a code review and also suggest if I can do better here, please guide me, waiting for valuable reply.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's also possible to turn the array into a set, then back to an array, which will remove duplicates. Array.from(new Set(numList)) \$\endgroup\$ – Kruga Jul 4 '17 at 8:27
1
\$\begingroup\$

Flag variables are ugly

Flag variables generate mental overhead. You set a flag to something, and then later you check its value to do something. You have to register the intention of the flag variable in your memory, remember it when you see it again. And the best part, make sure to not change it incorrectly. When the program doesn't work as intended, one of the first debugging steps is verifying that the flag variable wasn't modified somewhere by mistake. It's very annoying. Always look for ways to achieve your purpose without flag variables when possible.

A very good way to get rid of a flag variable is to introduce a helper function. Let's eliminate isDuplicateFound used in the second implementation:

function unique(nums) {
    var unique = [],
        seen = new Tracker(),
        index,
        num;

    for (index = 0; index < nums.length; index++) {
        num = nums[index];

        if (!seen.contains(num)) {
            unique.push(num);
            seen.add(num);
        }
    }

    return unique;
}

What is Tracker? I don't know, but I know it should have contains and a add methods. This implementation is short, and hopefully easy to read, with distractions removed. The essence of the implementation logic should be quite clear and natural.

Of course the Tracker and its methods are missing. The interview would likely ask to implement those.

Time complexity

You haven't mentioned anything about the time complexity of the implementation. It's important to mention that during an interview, and discuss about alternatives.

Your implementation was \$O(N^2)\$. The example started in the previous section still leaves that question open. Using a hash set, it could become \$O(N)\$.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

The simple way to turn any list of numbers or strings into a unique set is to use them as the keys in an object, since keys are inherently unique. So you do:

function uniqueArray(array) {
  var obj = {};
  array.forEach(el => obj[el] = true);
  return Object.keys(obj);
}
console.log(uniqueArray([ 12, 34, 12, 56, 12, 34, 56, 1, 2, 12, 12, 12 ]));

| improve this answer | |
\$\endgroup\$

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.