Bloomberg LP Interview Question
Software Engineer / DevelopersHi, This is the efficient code in C++ for finding out first most populas character.
char findFirstMostPopulas (char *strPtr)
{
int freq[256] = { 0 };
char *charPtr = strPtr;
while ( *charPtr != '\0')
{
freq[*charPtr]++;
charPtr++;
}
charPtr = strPtr;
char* mostPopulas = charPtr;
while ( *charPtr != '\0' )
{
if (freq[*mostPopulas] < freq[*charPtr])
mostPopulas = charPtr;
charPtr++;
}
return *mostPopulas;
}
Hash Table is the best option ... iterate once over the character of the string, and have a counter to fetch the previous value and increment and insert it again.
//The second solution like Integer arr[255] would fail in case of other characters like åß∂ƒ©˙∆˚¬Ω≈ç∫˜¡™£¢∞¶•ªº
ya but you would have to compute the hash function every-time you come across a new char and insertion and deletion does take a constant amount of time so it would be better to use an array which holds the number of occurrences of every char in the string to there respective position in the string correspondingly in the array to.
#include <stdio.h>
#define N 256
int findMostPopChar(char *s){
int ht[N];
int maxCnt = 0;
int maxInd = -1;
int i;
for(i = 0 ; i < N; i++){
ht[i] = 0;
}
while(*s++){
/* assert to make sure *s is in [0,255] range */
ht[*s]++;
if(ht[*s] > maxCnt){
maxCnt = ht[*s];
maxInd = *s;
}
}
return maxInd;
}
int main(){
char *s = "abjdjdjdjakjdkdjdkjdjdjdjdjkdjkd ";
printf("most pop. char = %c\n", findMostPopChar(s));
return 0;
}
string str("abcdeabcdefghikjaa");
int len = str.length();
int location, maxcount;
char ch;
int noftimes;
location = maxcount = noftimes = 0;
for (int i = 0 ; i < len ; i++)
{
ch = str[i];
noftimes = 0;
for(int j = i+1; j< len ; j++)
{
if(ch == str[j])
{
noftimes++;
}
}
if (noftimes > maxcount )
{
maxcount = noftimes;
location = i;
}
}
return str[location];
}
complexity is o(n2);
Use an integer array of size 255. For each character occurrence increase the corresponding count and compare the new count to current global maximum.
- Anon November 15, 2010