CareerCup

Here is the code in O(n):
a. Make an array of size 256 to hold all the character count
b. Find the max count in the array
c. Find the second max count in the array by storing all counts less than max in another array and finding the max of those counts which becomes the second count
d. At last print the character

#include <stdio.h>
#include <conio.h>
#define MAX_CHAR 256

int secondHighestFrequency(char arr[])
{
	int i;
	int max,min;
	int n=MAX_CHAR;
	int arr1[MAX_CHAR]={0};
	int arr2[MAX_CHAR],j;
	for(i=0;arr[i]!='\0';i++)
	{
		arr1[arr[i]]++;
	}
	max=arr1[0];
	for(i=0;i<n;i++)
	{
		if(arr1[i]>max)
			max=arr1[i];
	}
	for(i=0;i<n;i++)
	{
		min=arr1[i];
		if(min<max)
		{
			arr2[j]=min;
			j++;
		}
	}
	int sec_max=arr2[0];
	for(i=0;i<j;i++)
	{
		if(arr2[i]>sec_max)
			sec_max=arr2[i];
	}
	for(i=0;i<j;i++)
	{
		if(sec_max==arr1[i])
			printf("The character that occurs with second most frequency is %c",(char)i);
	}
}
int main()
{
	char arr[]="aaaabbccc";
	secondHighestFrequency(arr);
}

First, naive cut.

1.) Iterate through the string.
2.) Look up each character in a hash table. This map stores a reference to an item in a max-heap
3.) Use that reference to increase the reference count in the max-heap
4.) That max-heap stores a count, and the letter that it counts
5.) When done processing, take the max of the heap twice.

O(n) to go through the input array
O(log n) for the heap maintenance

struct heap_struct{
	int count;
	char c;	

	heap_struct(const int& COUNT, const char& C) : count(COUNT), c(C){}
	bool operator<(const set_struct& rhs){
		return count < rhs.count;
	}
};

typedef heap<set_struct> heap_t;
heap_t count_heap;

typedef hash_table<char, set_t::iterator> hash_t;
hash_t char_hash;

int count_letters(const std::string& input, const int& rank){
	// check our inputs
	if(0 == input.size()){
		return -1;
	}
	if(0 >= rank){
		return -1;
	}

	// Iterate throught the characters
	for(unsigned int i = 0; i < input.size(); ++i){
		char c = input[i];

		hash_t::iterator hash_iter = char_hash.find(c);

		// Insert the item
		if(char_hash.end() == hash_iter){
			heap_t::iterator heap_iter = 
				count_heap.insert(heap_struct(0, c));
			hash_iter = char_hash.insert(std::pair(c, heap_iter));
		}

		// Increment the count
		hash_iter.second->count++;
	}

	// Return the Nth item
	int ret = -1;
	for(int i = 0; i < rank; i++){
		ret = heap.max();
	}

	return ret;
}

String str = "aaabbcccc";
HashMap<String, String> map = new HashMap<String, String>();
int pos = 0;
int count = 0;
for(int j = 0 ; j < str.length() ; j = pos) {
char current = str.charAt(j);
count = 0 ;
pos = j;
for(int i = pos ; i < str.length() ; i++) {
if(current == str.charAt(i)) {
++count;
map.put(Character.toString(str.charAt(i)), Integer.toString(count));
++pos;
}
}
}
//unsorted map
System.out.println("unsorted \n" + map.toString());

LinkedHashMap<String, String> sortedMap = sortHashMapByValuesD(map);
//sorted map based on value
System.out.println("value based sorting \n" + sortedMap);
}

private static LinkedHashMap<String, String> sortHashMapByValuesD(HashMap<String, String> passedMap) {
List<Map.Entry<String, String>> list = new LinkedList<Map.Entry<String,String>>(passedMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
public int compare(Entry<String, String> o1,
Entry<String, String> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});

Map<String, String> sortedMap = new LinkedHashMap<String, String>();

int counter = 0;
for(Map.Entry<String, String> entry: list) {
++counter;
sortedMap.put(entry.getKey(), entry.getValue());
if(counter == 2) secondEntry = entry.getKey();
}
return (LinkedHashMap<String, String>) sortedMap;
}

after that print second value from last.

Please make comment if solution is not correct and feasible.

Pretty simple solution here... just use a hash table and keep track of the highest frequency and second highest frequency characters. O(n) time complexity. Some optimizations could probably be made...

public static void main (String[] args) {
        String origStr = "aaabbcccc";
        
        Hashtable<Character, Integer> hashtable = new Hashtable<>();
        
        int firstHighestFreq = 0, secondHighestFreq = 0;
        char firstHighestChar = ' ', secondHighestChar = ' ';
        
        for (int i = 0; i < origStr.length(); i++) {
            Character c = origStr.charAt(i);
            if(!hashtable.containsKey(c)) {
                hashtable.put(c, 1);
            } else {
                int tempFreq = hashtable.get(c);
                hashtable.put(c, ++tempFreq);
                
                if (tempFreq > firstHighestFreq) {
                    firstHighestFreq = tempFreq;
                    firstHighestChar = c;
                } else if (tempFreq > secondHighestFreq) {
                    secondHighestFreq = tempFreq;
                    secondHighestChar = c;
                }
            }
        }
        
        System.out.println("The second highest frequency character is " + secondHighestChar + ", which occurs " + secondHighestFreq + " times.");
        
    }

For this particular question, the character with second max count can be found like this:

#include <iostream>
#include <string>

int main(int argc, char * argv[])
{
	using namespace std;
	int maxCount = 0, secondMaxCount = 0;
	char maxChar ='\0', secondMaxChar = '\0';

	int currentCount = 0;
	char currentChar = '\0';

	string stream = "aaaabbbbbbbbbbccccccjjjjjjjjjjjssssskkkkkkkllllllleeeeeeeeeooooppppppppp";

	if(stream.length() > 0)
	{
		currentChar = stream[0];
		currentCount = 1;
		for(int i=1; i < stream.length(); ++i)
		{
			if(stream[i] == currentChar)
			{
				++currentCount;
			}
			else
			{
				if(maxCount < currentCount)
				{
					secondMaxCount = maxCount;
					secondMaxChar = maxChar;

					maxCount = currentCount;
					maxChar = currentChar;
				}
				else if(secondMaxCount < currentCount)
				{
					secondMaxCount = currentCount;
					secondMaxChar = currentChar;
				}

				currentChar = stream[i];
				currentCount = 1;
			}
		}

        if(maxCount < currentCount)
        {
            secondMaxCount = maxCount;
            secondMaxChar = maxChar;

            maxCount = currentCount;
            maxChar = currentChar;
        }
        else if(secondMaxCount < currentCount)
        {
            secondMaxCount = currentCount;
            secondMaxChar = currentChar;
        }
    }

    cout << "max - char: " << maxChar << ", count: " << maxCount << endl
        << "second max - char: " << secondMaxChar << ", count: " << secondMaxCount << endl;

	return 0;
}

If the interviewer ask to generalize the solution for kth max character, then we can create an array of size 256 to store count of each character that occurs in the string, sort this array (ascending sort) and then find the kth element in the sorted array.

#include <stdio.h>

/* Given a string "aaabbcccc", write a program to find the character with the second highest frequency. */

char second_highest(char *s, int n) {
    
    int max = 0, max2 = 0, i, index = -1, index2 = -1; /* index2 and max2 hold second highest */
    int count[256] = {0};
    
    for (i = 0; i < n; i++) {
        
        count[s[i]]++;
        
        if (count[s[i]] > max) {
            max2 = max;
            index2 = index;
            max = count[s[i]];
            index = i;
        }
    }
    return index2;
}

int main() {

    char s[10] = "aaabbcccc";
    
    int index = second_highest(s, 10);
    
    if (index != -1)
        printf("%c\n", s[index]);
    
    return 0;
}

in javascript..

function getMax(str) {
var count = 0,
maxCount = 0,
previousLetter = null,
winner = null;

for (var i = 0; i < str.length; i++) {
var currentLetter = str[i];

// if current letter is different than preivous letter set new count
// else increment count
if (currentLetter !== previousLetter) {
count = 1
} else {
count++;
}

// if count is greater than maxCount set to current one
if (count > maxCount) {
maxCount = count
winner = currentLetter
} else if (count === maxCount) {
winner = winner + ', ' + currentLetter
}

// set previous letter to current one before going to next
previousLetter = currentLetter
}

console.log(winner, maxCount)
}

public class secondHighest {
	
 private static int findSecondMax(int count[]){
	 
	  int i=0;
	  int MAX = count[0];
	  int index=0;
	  int maxindex=0;
	  int secondMax = 0;
	  for(i=1;i< count.length;i++){
		  if(count[i] > MAX ){
			  if(i!=1){
			  secondMax = MAX;
			  index = maxindex;
			  }
			  MAX = count[i];
			  maxindex = i;
		  }
		  else{
			 if(count[i] < MAX && count[i] > secondMax){
				 secondMax = count[i];
				 index = i;
			 }
		  }
	  }
	 return index; 
 }
  public static void main(String args[]){
	  
	  String s = "aab";
	  
	  if(s.length() <= 1){
		  System.out.println(s);
	  }
	  int count[] = new int[256];
	  for(int i=0;i<s.length();i++){
		  
			  count[(int)s.charAt(i) -97]++;  
		  }
	  
	  int c=  findSecondMax(count);
	  System.out.println("second highest frequency " + (char)(c+97));
  }
}

I would consider to store in a hashtable, and sort by the value (which is the frequency appeared in a string), and return the second key of the hashtable

def highest_frequency(arr):
  """
  Given a string "aaabbcccc", write a program to find the character with the second highest frequency.
  """
  # empty string, check input and pass non-empty string
  if not arr:
    return
  
  # a hash table to store values
  hashtable = {}
  
  # iterate through the input string and store the frequency of each character into a key-value pair in the hash table
  for elem in arr[:]:
    if elem in hashtable.keys():
      val = int(hashtable.get(elem, "none"))
      val += 1
      hashtable[elem] = val
    else:
      hashtable[elem] = 1
  
  # sort the hashtable by its value and grab the second highest
  output = sorted(hashtable, key=hashtable.get, reverse=False)
  return output[1]
  
res = highest_frequency('aaabbcccc')
print res

In Java, used a hashmap to keep a running tally of char counts, and pointers to the highest and second highest chars

public char findSecondHighestFrequency(String c){
        if(c.length() == 0)
            return '?';

        // Convenience map of chars found, and their counts
        HashMap<Character, Integer> frequencyMap = new HashMap<>();

        // Keep track of highest and second-highest frequency chars
        Character highestCount = null;
        Character secondHighestCount = null;

        int idx = 0;
        //Loop over chars in string
        for(char character : c.toCharArray()){
            if(frequencyMap.containsKey(character)) {
                frequencyMap.put(character, frequencyMap.get(character) + 1);
            }
            else
                frequencyMap.put(character, 1);

            // Set char pointers accordingly
            if(idx == 0)
                highestCount = character;
            else if(idx > 0 && frequencyMap.size() > 1 && secondHighestCount == null) {
                secondHighestCount = character;
            }

            // If current char is more frequent than the current highest, swap them
            if(frequencyMap.get(character) > frequencyMap.get(highestCount)){
                char temp = highestCount;
                highestCount = character;
                secondHighestCount = temp;
            }

            idx++;
        }

        // Return second highest if there are more than two chars provided
        return secondHighestCount != null ? secondHighestCount : highestCount;
    }

void secondHighOccurencesOfCharacter() {
		String str = "aadddbbcccc";
		int [] ascii = new int[str.length()];
		int highest = Integer.MIN_VALUE;
		int secondHighest = Integer.MIN_VALUE;
		
		for (int i = 0 ; i < str.length() ; i++) {
			ascii[str.charAt(i)-97]++;
		}
		
		for (int i = 0 ; i < ascii.length ; i++) {
			System.out.println("First & Second = "+ highest + " , " + secondHighest);
			if (ascii[i] > highest) {
				secondHighest = highest;
				highest = ascii[i];
			} else if (ascii[i] > secondHighest) {
				secondHighest = ascii[i];
			}
		}
		System.out.println("First & Second Highest="+ highest + " , " + secondHighest);
	}

public static void secondFreq(String str)
  {
    Map<Character,Integer> cmap = new HashMap<Character,Integer>();
    
    char ch[] = str.toCharArray();
    
    for(int i=0;i<ch.length;i++)
    {
     if(cmap.containsKey(ch[i]))
     {
       cmap.put(ch[i],cmap.get(ch[i]) + 1);
       
     }
      else
      {
        cmap.put(ch[i],1);
       
      }
    }
    System.out.print(cmap);
    
    Map<Character, Integer> sortedMap = sortByComparator(cmap);
    System.out.println(sortedMap);
    int[] a = new int[cmap.size()];
    System.out.println(" ");
    int j=0;
    for(char key:cmap.keySet())
    {
      a[j]=cmap.get(key);
      j++;
    }
    Arrays.sort(a);
    //for(int k=0;k<cmap.size();k++)
    // System.out.print(a[k]);
   System.out.println("Second most popular Element is : " + sortedMap.keySet().toArray()[cmap.size()-2]);
    
    
    
  }
  
  private static Map<Character, Integer> sortByComparator(Map<Character, Integer> unsortMap) {

    // Convert Map to List
    List<Map.Entry<Character, Integer>> list = 
      new LinkedList<Map.Entry<Character, Integer>>(unsortMap.entrySet());

    // Sort list with comparator, to compare the Map values
    Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
      public int compare(Map.Entry<Character, Integer> o1,
                                           Map.Entry<Character, Integer> o2) {
        return (o1.getValue()).compareTo(o2.getValue());
      }
    });

    // Convert sorted map back to a Map
    Map<Character, Integer> sortedMap = new LinkedHashMap<Character, Integer>();
    for (Iterator<Map.Entry<Character, Integer>> it = list.iterator(); it.hasNext();) {
      Map.Entry<Character, Integer> entry = it.next();
      sortedMap.put(entry.getKey(), entry.getValue());
    }
    return sortedMap;
  }

Idea is to count occurence of each chars, sort them and get the second last element.

public static void secondFreq(String str)
  {
    Map<Character,Integer> cmap = new HashMap<Character,Integer>();
    
    char ch[] = str.toCharArray();
    
    for(int i=0;i<ch.length;i++)
    {
     if(cmap.containsKey(ch[i]))
     {
       cmap.put(ch[i],cmap.get(ch[i]) + 1);
       
     }
      else
      {
        cmap.put(ch[i],1);
       
      }
    }
    System.out.print(cmap);
    
    Map<Character, Integer> sortedMap = sortByComparator(cmap);
    System.out.println(sortedMap);
    int[] a = new int[cmap.size()];
    System.out.println(" ");
    int j=0;
    for(char key:cmap.keySet())
    {
      a[j]=cmap.get(key);
      j++;
    }
    Arrays.sort(a);
    //for(int k=0;k<cmap.size();k++)
    // System.out.print(a[k]);
   System.out.println("Second most popular Element is : " + sortedMap.keySet().toArray()[cmap.size()-2]);
    
    
    
  }
  
  private static Map<Character, Integer> sortByComparator(Map<Character, Integer> unsortMap) {

    // Convert Map to List
    List<Map.Entry<Character, Integer>> list = 
      new LinkedList<Map.Entry<Character, Integer>>(unsortMap.entrySet());

    // Sort list with comparator, to compare the Map values
    Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
      public int compare(Map.Entry<Character, Integer> o1,
                                           Map.Entry<Character, Integer> o2) {
        return (o1.getValue()).compareTo(o2.getValue());
      }
    });

    // Convert sorted map back to a Map
    Map<Character, Integer> sortedMap = new LinkedHashMap<Character, Integer>();
    for (Iterator<Map.Entry<Character, Integer>> it = list.iterator(); it.hasNext();) {
      Map.Entry<Character, Integer> entry = it.next();
      sortedMap.put(entry.getKey(), entry.getValue());
    }
    return sortedMap;
  }

To do it in O(N), set up an array with space for each character. Then go through the string, incrementing the array slot associated with each character. Finally, go through the array and find the second-largest (in this simple case, just keep a max1 and max2, you could use a heap but that's overkill for just the two items). Works out to O(N) + O(N) = O(N).

In linear time, you can put each character and its frequency into a hash table.

Then iterate through the hash table and keep a running count of the most frequent and second most frequent characters.