2
\$\begingroup\$

I was asked in an interview to find the a number in an sorted array of numbers which has occurred maximum number of times. Also find the count of occurrence of that number.

I solved it in javascript, please follow the code

var numArray = [];


// takes the space separated numbers from commanline
// and inserts in array numArray.
process.argv.forEach(function(val, index, array){
   if(index > 1){
      numArray.push(parseInt(val));
   }    
});

(findMaxOccuredNum)(numArray);

function findMaxOccuredNum(nums){
   var currentCount = 0,
       prevCount = 0, 
       currentNum = 0,
       prevNum = 0; 

   for(var i = 0; i < nums.length; i++){
       if((nums[i] === 0 && i === 0) || (i === 0 && nums[i] !== 0)){
          currentNum = nums[i];
          currentCount++;   
       }else if(nums[i] === currentNum){
          currentCount++;
       }else {
          if(prevCount < currentCount){
              prevNum = currentNum;
              prevCount = currentCount;
              currentNum = nums[i]; 
              currentCount = 1;
          }else{
              currentNum = nums[i]; 
              currentCount = 1;
          }

       }//else
   }// for

   if(prevCount < currentCount){
      console.log("NUM "+currentNum+" occurred "+currentCount+" times");
   }else{
      console.log("NUM "+prevNum+" occurred "+prevCount+" times");
   }
} //findMaxOccuredNum

Below are some outputs

rahul@rahul:~/myPractise/Algo$ node NumCount.js 1 1 1 2 3 4 9 9 
NUM 1 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 1 2 2 2 3 3 6 6
NUM 2 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 0 0 1 1 3 3 3 5 5
NUM 3 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 0 0 0 1 1 3 
NUM 0 occurred 3 times

Requesting to please review my code and give your valuable comments on whether my code is the perfect solution for the above problem or it can be solved in better way.

\$\endgroup\$
  • 1
    \$\begingroup\$ A binary type search for the end point would probably be faster. I am not familiar with java but this seems odd (nums[i] === 0 && i === 0) || (i === 0 && nums[i] !== 0) \$\endgroup\$ – paparazzo Feb 3 '17 at 15:23
3
\$\begingroup\$

You should always question the question when given problems like this. For example, what if the input data is empty? What if there are two different values that appear the same number of times? etc. What if there are negative values?

Also, when dealing with problems like this its often best to separate the function doing the work, from the code presenting the result.

I would return an object from the function so that the "calling" code can look like:

var result = maxVal(data)
if (result.count) {
    console.log("NUM "+result.value+" occurred "+result.count+" times");
} else {
    console.log("No values in the data");
}

Then, I would also simplify your logic a whole bunch. You don't need to keep all those nested if statements.... You need just one test condition, and then an if/else condition...

function findMaxOccuredNum(nums){
    var result = {
        count: 0,
        value: 0
    };

    if (!nums) {
        return result;
    }

    var value = 0;
    var count = 0;

    for (var i = 0; i < nums.length; i++) {
        if (nums[i] != value) {
            count = 0
            value = nums[i];
        }
        count++;
        if (count > result.count) {
            result.count = count;
            result.value = value;
        }
    }
    return result;
}

function findMaxOccuredNum(nums){
        var result = {
            count: 0,
            value: 0
        };

        if (!nums) {
            return result;
        }
    
        var value = 0;
        var count = 0;
    
        for (var i = 0; i < nums.length; i++) {
            if (nums[i] != value) {
                count = 0
                value = nums[i];
            }
            count++;
            if (count > result.count) {
                result.count = count;
                result.value = value;
            }
        }
        return result;
    }

    function format(result) {
        return `Value ${result.value} & Count ${result.count}`;
    }
Result: <input id="output" type="text" cols="90">
<p>
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,4,5])));" value="[0,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,0,0,0,,1,2,3,4,4,5])));" value="[0,0,0,0,,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([-1,-1,-1,0,1,2,4,4,5])));" value="[-1,-1,-1,0,1,2,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,5])));" value="[0,1,2,3,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,4,5])));" value="[0,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([])));" value="[]">
<input type="button" onClick="alert(format(findMaxOccuredNum()));" value="null">

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

To expand a bit on what rolfl posted, you could also solve the problem by reducing the array to a string and using string split to quickly count the total occurrences of each number:

function findMaxOccuredNum(nums) {

    var count = 0,
        value = 'n/a',
        nums = nums || [],
        nums_str = nums.reduce(function (a, b) {
            return a + '|' + b;
        }, '');

    nums.forEach(function (num) {
        if (nums_str.split('|' + num).length - 1 > count) {
            count = nums_str.split('|' + num).length - 1;
            value = num;
        }
    });

    return {count, value};

}

With this as a starting point, you can add another condition and your function will also handle for ties (multiple values that have the same max count):

function findMaxOccuredNumTies(nums) {

    var count = 0,
        value = ['n/a'],
        nums = nums || [],
        nums_str = nums.reduce(function (a, b) {
            return a + '|' + b;
        }, '');

    nums.forEach(function (num) {
        if (nums_str.split('|' + num).length - 1 > count) {
            count = nums_str.split('|' + num).length - 1;
            value = [num];
        } else if (nums_str.split('|' + num).length - 1 === count) {
            value.push(num);
        }
    });

    value = value.filter(function (el, i, arr) {
        return arr.indexOf(el) === i;
    }).join();

    return {count, value};

}

With ES6 you can simplify it a little bit:

function findMaxOccuredNumTiesES6(nums=[]) {

    var count = 0,
        value = ['n/a'],
        nums_str = nums.reduce((a, b) = > a + '|' + b, '');

    nums.forEach(function (num) {
        if (nums_str.split('|' + num).length - 1 > count) {
            count = nums_str.split('|' + num).length - 1;
            value = [num];
        } else if (nums_str.split('|' + num).length - 1 === count) {
            value.push(num);
        }
    });

    value = Array.from(new Set(value)).join();

    return {count, value};

}

    function format(result) {

      return `Max Occured Number ${result.value}, Occurences: ${result.count}`;

    }


    function findMaxOccuredNum(nums) {

      var count = 0,
        value = 0,
        nums = nums || [],
        nums_str = nums.reduce(function(a, b) {
          return a + '|' + b;
        }, '');

      nums.forEach(function(num) {
        if (nums_str.split('|' + num).length - 1 > count) {
          count = nums_str.split('|' + num).length - 1;
          value = num;
        }
      });

      return {
        count, value
      };

    }

    function findMaxOccuredNumTies(nums) {

      var count = 0,
        value = ['n/a'],
        nums = nums || [],
        nums_str = nums.reduce(function(a, b) {
          return a + '|' + b;
        }, '');

      nums.forEach(function(num) {
        if (nums_str.split('|' + num).length - 1 > count) {
          count = nums_str.split('|' + num).length - 1;
          value = [num];
        } else if (nums_str.split('|' + num).length - 1 === count) {
          value.push(num);
        }
      });

      value = value.filter(function(el, i, arr) {
        return arr.indexOf(el) === i;
      }).join();

      return {
        count, value
      };

    }

    function findMaxOccuredNumTiesES6(nums = []) {

      var count = 0,
        value = ['n/a'],
        nums_str = nums.reduce((a, b) => a + '|' + b, '');

      nums.forEach(function(num) {
        if (nums_str.split('|' + num).length - 1 > count) {
          count = nums_str.split('|' + num).length - 1;
          value = [num];
        } else if (nums_str.split('|' + num).length - 1 === count) {
          value.push(num);
        }
      });

      value = Array.from(new Set(value)).join();

      return {
        count, value
      };

    }

    console.log('No ties checking:');
    console.log(format(findMaxOccuredNum([0, 1, 2, 3, 4, 4, 5])));
    console.log(format(findMaxOccuredNum([0, 1, 2, 3, 4, 4, 5, 5])));
    console.log('Ties checking:');
    console.log(format(findMaxOccuredNumTies([0, 1, 2, 3, 4, 4, 5])));
    console.log(format(findMaxOccuredNumTies([0, 1, 2, 3, 4, 4, 5, 5])));
    console.log('ES6 ties checking:');
    console.log(format(findMaxOccuredNumTiesES6([0, 1, 2, 3, 4, 4, 5])));
    console.log(format(findMaxOccuredNumTiesES6([0, 1, 2, 3, 4, 4, 5, 5])));

| 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.