program to find maximum time repeated number in array

Thread Starter

Fanfire174

Joined Mar 13, 2018
240
I want help, this program may, following question I was asked in interview, I tried to solve it But I couldn't get answer .

Numbers = [ 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1]

2 repeats two times
3 repeats two times
9 repeats two times
4 repeats only once
5 repeats two times
1 repeats four times
-2 repeats only once

Find the number who repeating maximum time in sequence. In the sequence number 1 is repeating four times

My attempt to solve problem

C:
#include<stdio.h>

int main ()
{
     int i;  
     int a1 = 2; int a2 = 3; int a3 = 9; int a4 = 4, int a5 = 2; int a6 = 9, int a7 = 5; int a8 = 1; int a9 =1; int a10 = 3; int a11 = 1;
     int a12 = -2, int a13 = -5; a14 = 1;
   
     int N1 = 0; int N2 = 0; int N3 = 0; int N4 = 0; int N5 = 0; int N6 = 0, int N7 = 0; int N8 = 0; int N9 =0; int N10 = 3; int N11 = 0;
     int N12 = 0; int N13 = 0; N14 = 0;
   
    int Numbers[] = { 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1}
   
    for (i = 1, i < 15; i++)
    {
        if (a1 == Number[i])
        {
            N1++;
        }
    }
   
    for (i = 2, i < 15; i++)
    {
        if (a2 == Number[i])
        {
            N2++;
        }
    }
           
 
       for (i = 3, i < 15; i++)
    {
        if (a3 == Number[i])
        {
            N3++;
        }
    }
       
    ...............
   
    for (i = 14, i < 15; i++)
    {
        if (a14 == Number[i])
        {
            N14++;
        }
    }
   
    return 0;
}
 

402DF855

Joined Feb 9, 2013
267
Better to use an array of counts. If the count array bounds the inputs fine, otherwise use another array to map inputs to counts. Cycle through the list then find the maximum count.
 

WBahn

Joined Mar 31, 2012
26,398
Your approach requires that you know exactly what data is going to be in the array so that you can write your program. Well, in that case just do it by hand and be done with it. The interviewer is looking to see if you can come with with an approach that works for the general case of a problem and is giving you just one specific example. If your ability limits you to only working with the specific example given and not the more general problem, then the interview will have served its purpose and the interviewer can move on to viable candidates.

Though you haven't even solve the specific example given. After your program runs, what is the answer?
 

bug13

Joined Feb 13, 2012
1,934
Here is my solution, I am keen to know your critiques/thoughts/improvement suggestions:

C:
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef struct MAX_REPEAT{
    int         data;
    unsigned    count;
}max_repeat_t;

typedef struct TMP{
    uint8_t     isVacant;
    int         data;
    unsigned    count;
}tmp_t;

/*! \brief  Get the number that repeated the most
*  \param  data    - pointer to data array
*  \param  len     - array size
*  \retval number that repeated the most and repeated count
*/
max_repeat_t getMaxRepeat(int *data, unsigned len);

/*! \brief  Set the data to default values
*  \param  data    - pointer to data storage
*  \param  len     - data storage size
*/
void TmpData_init(tmp_t *data, unsigned len);

/*! \brief  Find out if data exit
*  \param  data    - pointer to data storage
*  \param  len     - data storage size
*  \param  val     - value to be check
*  \retval Does not exit = -1, otherwise return index number
*/
int TmpData_isExit(tmp_t *data, unsigned len, int val);

/*! \brief  Add one data to the tmp data
*  \param  data    - pointer to data storage
*  \param  len     - data storage size
*  \param  val     - data to be added
*/
void TmpData_add(tmp_t *data, unsigned len, int val);
     


int main(int argc, char **argv){

    int data[] = {2, 3, 9, -2, 4, 2, 9, -2, 5, 1, 1, 3, 1, -2, 5, 1, 10, -2, -2};

    max_repeat_t maxRepeat = getMaxRepeat(data, sizeof(data)/sizeof(data[0]));

    printf("Max repeat: data [%d], count [%u]\n", maxRepeat.data, maxRepeat.count);

    return 0;
}

max_repeat_t getMaxRepeat(int *data, unsigned len){
    max_repeat_t ret = {
        .data   = 0,
        .count  = 0,
    };

    /* create a list */
    tmp_t *tmp = (tmp_t *)malloc(sizeof(tmp_t) * len);

    /* initial data */
    TmpData_init(tmp, len);

    /* loop through all the data */
    for(unsigned i = 0; i < len; i++){
       
        /* find index */
        int index = TmpData_isExit(tmp, len, data[i]);

        if (index == -1){
            /* add data to list if not exit aleady */
            TmpData_add(tmp, len, data[i]);
        }else{
            /* increase count if already in the list */
            tmp[index].count++;
        }
    }


    /* find maximum count index */
    unsigned    tmp_index = 0;
    unsigned    tmp_count = 0;
    for(unsigned i = 0; i < len; i++){
        /* debug print */
        printf("index [%02u], vacant: [%u], data: [%03d], count: [%02u]\n", i, tmp[i].isVacant, tmp[i].data, tmp[i].count);
       
        if (tmp_count < tmp[i].count){
            tmp_count = tmp[i].count;
            tmp_index = i;
        }
    }

    /* update result */
    ret.data = tmp[tmp_index].data;
    ret.count = tmp[tmp_index].count;

    free(tmp);
    tmp = NULL;

    return ret;
}

void TmpData_init(tmp_t *data, unsigned len){
    memset(data, 0, sizeof(tmp_t) * len);
    for(unsigned i = 0; i < len; i++)
        data[i].isVacant = 1;
}

int TmpData_isExit(tmp_t *data, unsigned len, int val){
    for(unsigned i = 0; i < len; i++){
        if ((data[i].isVacant == 0) && (data[i].data == val)){
            return i;
        }
    }
    return -1;
}

void TmpData_add(tmp_t *data, unsigned len, int val){
    for(unsigned i = 0; i < len; i++){
        if (data[i].isVacant == 1){
            data[i].isVacant = 0;
            data[i].data = val;
            data[i].count = 1;
            return;
        }
    }
}
 

wayneh

Joined Sep 9, 2010
16,844
My answer is in Swift but should be clear.
Code:
var A = [ 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1]
let B = A.sorted()
print(B)                          //  "[-2, 1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 9, 9]"
var candidate = 0
var run = 0
var runMax = 0
for i in 1...A.count-1 {
    if B[i] == B[i-1] {          // A run has been detected
        run += 1                 // Update the run count
        if run > runMax {        // Check against the longest run so far
            candidate = B[i]     // Record details of leading candidate, here just its value as requeted
            runMax = run         // Update the longest run count
        }
    } else {                     // Run has ended
        run = 0                  // Reset the run counter
    }
}
print(candidate)                //  "1"
 
Last edited:

dl324

Joined Mar 30, 2015
12,522
Find the number who repeating maximum time in sequence.
Here's a solution in Perl:
Code:
#!/usr/bin/perl

@numAry = (2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1);
$maxNum = $maxCount = 0;

grep($count{$_}++, @numAry);

foreach $k (sort(keys(%count))) {
  printf("Occurrences of %d: %d\n", $k, $count{$k});
  if ($count{$k} > $maxCount) {
    $maxCount = $count{$k};
    $maxNum = $k;
  }
}
printf("\nMax count = %d, %d occurrences\n", $maxNum, $count{$maxNum});
Results:
Occurrences of -2: 1
Occurrences of 1: 4
Occurrences of 2: 2
Occurrences of 3: 2
Occurrences of 4: 1
Occurrences of 5: 2
Occurrences of 9: 2

Max count = 1, 4 occurrences

EDIT: replaced with code to solve the actual problem.
 
Last edited:

Thread Starter

Fanfire174

Joined Mar 13, 2018
240
Though you haven't even solve the specific example given. After your program runs, what is the answer?
Actually, I could not solve, but the approach that came to my mind, I shared with you, The purpose of asking questions was that I had to see that where I am mistaken in thinking
Here is my solution, I am keen to know your critiques/thoughts/improvement suggestions:
Your code gives the output as I wanted, I need to spend more time to understand your code.
My answer is in Swift but should be clear.
I am trying to convert your algorithm to code. Maybe it takes me a little longer

Thank you to all of you. I've got enough help Now next to this, I have to write the program by understanding a logic of code[/QUOTE]
 

wayneh

Joined Sep 9, 2010
16,844
I am trying to convert your algorithm to code. Maybe it takes me a little longer
One thing I considered but left out was a line to exit early if/when there aren’t enough remaining digits to exceed the best candidate run. For instance you get to three remaining digits but your biggest count so far is 4. No need to keep looking. This would be more relevant if the array were much larger.
 

WBahn

Joined Mar 31, 2012
26,398
Here is my solution, I am keen to know your critiques/thoughts/improvement suggestions:
I haven't reviewed your code, but a first glance reveals an approach that sets up data structures and functions to tackle the problem in small chunks. That might impress an interviewer or it might send a message you don't want -- it depends on the mindset the interviewer was coming from when they posed the question. You can't control their mindset and they may actually not even be aware of what it is until they see that the approach you are taking isn't meshing with what they were expecting and then they are likely to find justifications for why your approach is somehow obviously deficient in order to bolster their opinion of what they had in mind. It's a pretty natural tendency and they may or may not be able to step back and consider your approach on its own merits.

To manage that situation you can explore up front what their mindset by asking some clarifying questions. Not only will this put you and the interviewer closer to being on the same page, it will demonstrate that you are aware of the reality that solutions to problems are almost always context-dependent. In this case you might ask questions like: Which is more important, speed of execution or limiting memory usage? Which is more important, getting a solution up and running quickly at the expense of elegance and error handling, or taking the time to stand up a more robust and maintainable solution? Are there any assumptions I can make regarding the nature of the data, such as min/max values? How are ties to be handled?
 

WBahn

Joined Mar 31, 2012
26,398
Excellent point. An exception I failed to consider in my quick-and-dirty solution. Which proves your points about context mattering.
Usually, in an interview type situation, you get sufficient points just for recognizing the issue and stating what you are going to do; if you spot it ahead of time, superb, but even if you recognize it as you are implementing your solution, you are way ahead of the normal candidate. If they really want to see you do something different, they will tell you; but sometimes if you ask a good set of questions up front they will just stop you and move on to the next question concluding that if you know enough to ask the right questions that you either can do the programming or could learn how to do it with no problem in the case of an unfamiliar or low-experience language or platform.
 

davidl

Joined Jan 3, 2014
3
One thing I considered but left out was a line to exit early if/when there aren’t enough remaining digits to exceed the best candidate run. For instance you get to three remaining digits but your biggest count so far is 4. No need to keep looking. This would be more relevant if the array were much larger.
Good point, although this assumes that the array length is fixed or you don't care what the actual max count is (ie you only care what number has the max occurrence). A real application of this problem is that the values are being read from a sensor and hence appear as a continuous list eg Temperatures or Voltages.

An associative array makes coding this solution very simple, and allows ties to be listed as the answer. Rough pseudo-code follows:

Define ResultArray as array
Define ResultHigh as number

Loop through source array
ResultArray(SourceArrayValue) ++
IF (ResultArray(SourceArrayValue) > ResultHigh) ResultHigh = ResultArray(SourceArrayValue)

PRINT "Max Count is" ResultHigh
PRINT "Maximum number(s) are"

Sort ResultArray by Value
Loop through ResultArray
IF ResultArrayValue >= ResultHigh PRINT ResultArrayKey

Apology for the rough code - hopefully the meaning is clear. The main point is that you can use the associative array's key (ie the number being counted) or value (the number of counts) as required

HTH,

David

P.S. Long time lurker ..... First time poster :)
 

vanderghast

Joined Jun 14, 2018
51
Assuming a table in a database, TheNumbers, with the field TheNumber ( one line, or record, per number), then the SQL statement should do the job (a "GroupBy query, in Microsoft Access) :
SELECT theNumber, COUNT(*)
FROM theNumbers
GROUP BY theNumber
ORDER BY COUNT(*) DESC;

In many languages, you can run a scalar query (a query returning a single value), to return just the specific number, and you can chose to use (the query is right, the code itself is pseudo code):
dbConnection.RunScalar("SELECT TOP 1 theNumber FROM theNumbers GROUP BY theNumber ORDER BY COUNT(*) DESC, theNumber ASC;")
Note than in case there are ex-equo, say 11 and 32 appears both 8 times (and are the most frequent ones), here, the smallest one, 11 will be singled out, since the ORDER BY clause order them in descending value of their count, but in ASCending value ot the number itself.

Additionnal note: in many database, you can do it "GRAPHICALLY". See the picture as example, for Access 360.
Annotation 2020-03-06 135112.jpg

Furthermore, you can probably collect your data directly into the database, leaving the data completely outside your program / MCU.
 

ApacheKid

Joined Jan 12, 2015
326
I want help, this program may, following question I was asked in interview, I tried to solve it But I couldn't get answer .

Numbers = [ 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1]

2 repeats two times
3 repeats two times
9 repeats two times
4 repeats only once
5 repeats two times
1 repeats four times
-2 repeats only once

Find the number who repeating maximum time in sequence. In the sequence number 1 is repeating four times

My attempt to solve problem

C:
#include<stdio.h>

int main ()
{
     int i;
     int a1 = 2; int a2 = 3; int a3 = 9; int a4 = 4, int a5 = 2; int a6 = 9, int a7 = 5; int a8 = 1; int a9 =1; int a10 = 3; int a11 = 1;
     int a12 = -2, int a13 = -5; a14 = 1;
 
     int N1 = 0; int N2 = 0; int N3 = 0; int N4 = 0; int N5 = 0; int N6 = 0, int N7 = 0; int N8 = 0; int N9 =0; int N10 = 3; int N11 = 0;
     int N12 = 0; int N13 = 0; N14 = 0;
 
    int Numbers[] = { 2, 3, 9, 4, 2, 9, 5, 1, 1, 3, 1, -2, 5, 1}
 
    for (i = 1, i < 15; i++)
    {
        if (a1 == Number[i])
        {
            N1++;
        }
    }
 
    for (i = 2, i < 15; i++)
    {
        if (a2 == Number[i])
        {
            N2++;
        }
    }
         

       for (i = 3, i < 15; i++)
    {
        if (a3 == Number[i])
        {
            N3++;
        }
    }
     
    ...............
 
    for (i = 14, i < 15; i++)
    {
        if (a14 == Number[i])
        {
            N14++;
        }
    }
 
    return 0;
}
What you seek is an example algorithm for finding the mode (as it's termed in statistics) of an array.

Notice how compact and elegant this can be in a functional language like F# compared to say C++.
 

JohnInTX

Joined Jun 26, 2012
4,377
Notice how compact and elegant this can be in a functional language like F# compared to say C++
I've often stated my belief that reading lots of *good* code is a great way to learn not only coding but the problem solving methods behind the code itself. Unfortunately there is so much junk code out there, I'm reluctant to give that advice to a beginner. Thanks for the links to a good reference.
 
Top