CareerCup

is the output correct in the question

{1,2,3,6,1,3,6,7,3,9,4,2} -> Input
{1,1,1,1,1,1,1,1,3,3,3,3} -> output should be
{1,1,1,1,3,3,3,3,3,3,3} -> output given

correct me if wrong

Hash table

var node = list.First;
            if (node == null) return;

            var freqList = new LinkedList<int>();
            var scores = new Dictionary<int, int>();

            // Initialize the arrays and dictionary
            int mostFrequentValue = node.Value;
            int mostFrequentCount = 1;
            scores.Add(node.Value, 1);
            freqList.AddFirst(node.Value);

            node = node.Next;

            while (node != null)
            {
                if (scores.ContainsKey(node.Value))
                {
                    scores[node.Value]++;
                    if (mostFrequentValue != node.Value)
                    {
                        if (scores[node.Value] > mostFrequentCount)
                        {
                            mostFrequentValue = node.Value;
                            mostFrequentCount = scores[node.Value];
                        }
                    }
                    else
                    {
                        mostFrequentCount++;
                    }
                }
                else
                {
                    scores.Add(node.Value, 1);
                }

                freqList.AddLast(mostFrequentValue);
                node = node.Next;
            }

question not clear?

Please explain the question again..?

and

I think either sample data or question is not clear.

Question is "create a new array such that element at index "i" will be the element with highest frequency so far till i'th index in original array"

Yes, Question not clear.

Use a max heap along with a hash table.
Loop through the array and for every value, get the heap node (which stores count) from the hash table and increase the count for the node. The element at the top of the heap will be the one with the maximum frequency.

The Qs and output doesn't match.The Qs and output doesn't match.

I don't quite understand the question

#define SIZE(A) (sizeof(A)/sizeof(A[0]))

void PrintFrequencies(int *a, int n)
{
	int i;
	int m=INT_MIN;
	int max=INT_MIN;
	int val;
	try
	{
		if(a==NULL || n<0) throw "\nInvlaid Input\n";
	}catch(const char *s)
	{
		puts(s);
		return;
	}
	
	for(i=0;i<n;i++)
	{
		if(a[i]>m)
			m=a[i];
	}

	int *t=new int[m+1];
	memset(t,0,sizeof(int)*(m+1));
	
	val=a[0];

	
	for(i=0;i<n;i++)
	{
		t[a[i]]++;
		if(t[a[i]]>max)
		{
			max=t[a[i]];
			val=a[i];
		}
		printf("%d ",val);
	}	
	printf("\n");

	delete [] t;
}

Use c++11 compiler:

#include <iostream>
#include <string>
#include<vector>
#include<unordered_map>

using namespace std;

std::vector<int> get_freq_map( std::vector<int> & arr);

int main()
{
   cout << "Hello World" << endl; 
   
   std::vector<int> input = {1,2,3,6,1,3,6,7,3,9,4,2 };
   std::vector<int> output = get_freq_map( input);
   
   for (auto &i: output) {
       std::cout << i ;
   }
   std::cout <"\n";
   return 0;
}

std::vector<int> get_freq_map( std::vector<int> & arr) {
    
    std::unordered_map<int, int> a_map;
    
    int max_freq_value = arr[0];
    std::vector<int> freq_map;
    freq_map.push_back(max_freq_value);
    a_map[arr[0]] = 1;

    for ( auto &i : arr) {
        if (&i == &arr[0]) continue;
        if ( a_map.find(i) == a_map.end()){
            a_map[i] = 0;
        } else {
            a_map[i]++;
        }
        if ( a_map[i] > max_freq_value) {
            max_freq_value= i;            
        }
        freq_map.push_back(max_freq_value);
    }
    return freq_map;
}