Post date: Jul 15, 2013 4:48:22 AM
Problem
For a technical phone screen:
Given a string "aaabbcccc", write a program to find the character with the second highest frequency.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the character with the second highest frequency
Created Date : 15-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <string>
using namespace std;
using namespace stdext;
bool FindSecondFreqChar(string str, char& secondChar)
{
unordered_map<char, int> um;
int maxFreq = 0;
for(auto it = str.begin(); it != str.end(); ++it){
if(um.find(*it) == um.end()){
um.insert(pair<char, int>(*it, 1));
}
else{
um[*it] ++;
}
maxFreq = max(maxFreq, um[*it]);
}
int secondFreq = 0;
for(auto it = um.begin(); it != um.end(); ++it){
if(it->second != maxFreq){
secondFreq = max(secondFreq, it->second);
}
if(secondFreq == it->second){
secondChar = it->first;
}
}
if(um.size() == 1){
cout << "There are only one character in the string" << endl;
return false;
}
else if(secondFreq == 0 && um.size() > 1){
cout << "All characters have same frequency" << endl;
return false;
}
else{
return true;
}
}
void DoTest(string str)
{
if(str.size() == 0){
cout << "The string is empty";
}
else{
cout << "The string is: " << str << endl;
char secondChar;
if(FindSecondFreqChar(str, secondChar)){
cout << "The character with second highest frequency is ";
cout << secondChar << endl;
}
}
cout << "-------------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("");
DoTest("aaabbcccc");
DoTest("aaabbccccdddddddddddeeeeeeeeee");
DoTest("aaaabbbbcccc");
DoTest("abc");
DoTest("a");
DoTest("aaaaaaaaa");
return 0;
}
Output
The string is empty-------------------------------
The string is: aaabbcccc
The character with second highest frequency is a
-------------------------------
The string is: aaabbccccdddddddddddeeeeeeeeee
The character with second highest frequency is e
-------------------------------
The string is: aaaabbbbcccc
All characters have same frequency
-------------------------------
The string is: abc
All characters have same frequency
-------------------------------
The string is: a
There are only one character in the string
-------------------------------
The string is: aaaaaaaaa
There are only one character in the string
-------------------------------
Press any key to continue . . .