Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
//C# implmentation
static int MaxCharacterRepeatation(string _str)
{
int Max = 1;
Dictionary<int,int> charset = new Dictionary<int, int>();
for (int i = 0; i <_str.Length; i++)
{
int val = _str[i];
if (!charset.ContainsKey(val))
{
charset.Add(val, 1);
}
else
{
charset[val] = charset[val]+1;
if (charset[val] > Max)
{
Max = charset[val];
}
}
}
return (Max);
}
}
#JavaScript
s = "dfsdfsasd"
function getHighestCharCount(s){
var count = {};
for(c in s){
var key = s[c];
if( count[key] == undefined){
count[key] = 1;
}else{
count[key]++;
}
}
var highest = 0;
for(i in count){
highest = count[i] > highest ? count[i] : highest;
}
return highest;
}
getHighestCharCount(s);
O(n)
#JavaScript
s = "dfsdfsasd"
function getHighestCharCount(s){
var count = {};
for(c in s){
var key = s[c];
if( count[key] == undefined){
count[key] = 1;
}else{
count[key]++;
}
}
var highest = 0;
for(i in count){
highest = count[i] > highest ? count[i] : highest;
}
return highest;
}
getHighestCharCount(s);
O(n)
int PasswordCount(char * password)
{
int r[256] = {0}; //256 characters in ascii
int max = 0;
int l = strlen(password);
for(int i=0;i<l;i++)
{
int c = password[i];
int count = 1;
for(int n=i+1;n<l;n++)
{
if(r[c] != 0)
break;
if(c == password[n])
{
count++;
}
}
if(count > max)
{
max = count;
}
}
return max;
}
#include <vector>
#include <string>
#include <functional>
#include <iostream>
#include <unordered_map>
std::pair<char, int> countCharsAndReturnMax(std::string str, std::unordered_map<char, int>& counts)
{
std::pair<char, int> max;
for(auto c : str)
{
if(counts[c]++ > max.second)
max = std::make_pair(c, counts[c]);
}
return max;
}
int main(int argc, char** argv)
{
std::unordered_map<char, int> counts;
auto maxEntry = countCharsAndReturnMax("Facebook", counts);
std::cout << "Given strings has following char histogram:" << std::endl << std::endl;
for(auto e : counts)
{
if(e.first == maxEntry.first)
std::cout << ">>";
else
std::cout << " ";
std::cout << " '" << e.first << "' : " << e.second << " times" << std::endl;
}
return 0;
}
Python has some ways of doing this very elegantly, but typically interviewers want you to implement it at its base level, as can be seen here:
def get_max_repeated(string):
chars = {}
max = 1
for c in string:
if c not in chars:
chars[c] = 1
else:
current = chars[c]+1
chars[c] = current
if current > max:
max = current
return max
print get_max_repeated("coffee tuffee")
A java version:
public int countChar(String s){
int[] count=new int[256] ;
for(int i=0;i<s.length();i++){
int index=handleCase(s.charAt(i));
count[index]++;
}
int max=0;
for(int i=0;i<256;i++){
max=Math.max(max,count[i]);
}
return max;
}
public int handleCase(char c){
if (c>='a'&&c<='z')
return c-32;
else return c;
}
Notice that 'coffee tuffee' actually has character counts of 4 for both char e and char f. It might be useful to know which characters return the highest count to discriminate multiple max counts. Here is a definition that will do just that:
def parsewords(the_words):
return sorted([(list(words).count(c), c) for c in list(set(list(words)))])[::-1])
I have left off the exceptions that might want to be handled, e.g. white spaces, upper versus lower case, etc. to simplify the code.
The idea is to create a list of length N from the_words, and then using list comprehension, create a reverse-sorted list. Given 'coffee tuffee' the definition returns:
[(4, 'f'), (4, 'e'), (1, 'u'), (1, 't'), (1, 'o'), (1, 'c'), (1, ' ')]
Correction: the_words in nthe argument should be replaced with words.
A more readable form is given by:
def pwords(words):
list_chars = list(words)
set_chars = set(list_chars)
result = []
for c in set_chars:
result.append([list_chars.count(c), c])
return sorted(result)[::-1]
Another possibility in python using a simple generator:
And of course, you can always add in the
bit before that if you want...
- Oblique63 March 27, 2013