Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
You missed last step fetch and display the max from Hashtable.
And if we use Hashtable we may need another O(n) to fetch and display the max.
Hi Srigopal, if we maintain a max_counter and max_char and keep them updated, I don't think it needs the last step to fetch and display the max from Hashtable, instead it will directly display the max_counter and max_char.
package com.test;
public class CharacterCount {
/**
* @param args
*/
public static void main(String[] args) {
String str="abcbdserersgassereasssraa";
countMaxCharacter(str);
}
public static void countMaxCharacter(String str)
{
int[] asciiArr=new int[255];
char[] charArr=str.toCharArray();
int maxCount=1;
char occursMost=' ';
int charAscii;
for(int index=0;index<charArr.length;index++)
{
charAscii=(int)charArr[index];
int charCount=asciiArr[charAscii];
asciiArr[charAscii]=++charCount;
if(charCount>maxCount)
{
maxCount=charCount;
occursMost=charArr[index];
}
}
System.out.println("Character Occurs Most "+occursMost+" Count "+maxCount);
}
}
## Implementing the solution in python
## let 'str' be the given string
letter_count={}
for x in str:
if letter_count.has_key(x):
letter_count+=1
else:
letter_count=1
print d
C++ Approach:
char arr[] = "test test for this exercise";
sort(arr, arr + sizeof(arr) / sizeof(char), [](char a, char b) {return a < b;});
char compare = arr[0];
char letter = arr[0];
int current = 1;
int max = 1;
for(int i = 1; i < sizeof(arr) / sizeof(char); i++)
{
if(compare == arr[i])
current++;
else
{
compare = arr[i];
current = 1;
}
if(current > max)
{
max = current;
letter = compare;
}
}
cout << letter << " " << max << endl;
public static void MaxRepeatCharInString(string text)
{
IDictionary<char, int> charsWithTheirCnt = new Dictionary<char, int>();
// O(n)
for (int lpCnt = 0; lpCnt < text.Length; lpCnt++)
{
if (charsWithTheirCnt.ContainsKey(text[lpCnt]))
{
charsWithTheirCnt[text[lpCnt]] = int.Parse(charsWithTheirCnt[text[lpCnt]].ToString()) + 1;
}
else
{
//O(1)
charsWithTheirCnt.Add(text[lpCnt], 1);
}
}
System.Collections.Hashtable ht = new System.Collections.Hashtable();
// O(1) worst case O(n)
KeyValuePair<char, int> maxRepeatChar = charsWithTheirCnt.FirstOrDefault( aa => aa.Value == charsWithTheirCnt.Values.Max());
MessageBox.Show("The character repated most no of times in given string is '" + maxRepeatChar.Key + "' and its count is " + maxRepeatChar.Value);
}
public class CountChar {
public void findFreq(String input){
Map<Character,Integer> map = new HashMap<Character,Integer>();
char commonChar = 0;
int count = 0;
for(int i=0; i<input.length(); i++){
char ch = input.charAt(i);
if(map.containsKey(ch)){
map.put(ch, map.get(ch)+1);
}else{
map.put(ch, 1);
}
}
for(char c: map.keySet()){
if(map.get(c)> count){
count = map.get(c);
commonChar = c;
}
}
System.out.println("The character is "+ commonChar +" with " + count + " occurrences");
}}}
package careerCup;
import java.util.HashMap;
import java.util.Map;
public class CharaterCount {
public CharaterCount() {
// TODO Auto-generated constructor stub
}
/**
* @param args
*/
public static void main(String[] args)
{
countDuplicates("akjsdaineafdjbadpebfjasdkgasgenbdflkjdfabfaadslkjadgbewakdngkjbd");
}
public static void countDuplicates(String str)
{
if(str == null || str.length() == 1)
return;
int countDups = 0;
int maxDup = 0;
char mostDuped = '?';
Map<Character, Integer> counts = new HashMap<Character, Integer>();
char [] chars = str.toCharArray();
for(char each : chars)
{
Integer temp = counts.get(each);
if(temp == null)
temp = 1;
else
{
countDups++;
temp++;
}
counts.put(each, temp);
if(temp > maxDup)
{
maxDup = temp;
mostDuped = each;
}
}
System.out.println(str);
System.out.println("Total dupes: " + countDups);
System.out.println("Total dupes: " + mostDuped + " @ " + maxDup);
}
}
output:
akjsdaineafdjbadpebfjasdkgasgenbdflkjdfabfaadslkjadgbewakdngkjbd
Total dupes: 50
Total dupes: a @ 11
A simple Solution in Perl.
my %charMap=();
my $charString = "akjsdaineafdjbadpebfjasdkgasgenbdflkjdfabfaadslkjadgbewakdngkjbd";
my $stringLength = length($charString);
my $counter=0;
my $currentIndex;
while($counter < $stringLength){
$currentIndex = substr($charString,$counter,1);
if (exists $charMap{$currentIndex}){
$charMap{$currentIndex}++;
}
else{
$charMap{$currentIndex}=1;
}
$counter++;
}
for my $key ( keys %charMap) {
print "$key\t$charMap{$key}\n";
}
}
public class CharacterCount {
public static void main(String args[]){
String str="abcbdserersgassereasssraarrrrrr";
CharacterCount(str);
}
public static void CharacterCount(String sat){
String sat1 = sat;
String dupchar = "";
for(int i=0;i<sat1.length();i++){
int count=0;
for(int j=0;j<dupchar.length();j++){
if(sat1.charAt(i) == dupchar.charAt(j)){
count++;
}
}
if(count==0){
dupchar=dupchar.concat(String.valueOf(sat1.charAt(i)));
}
}
int[] val = new int[dupchar.length()];
for(int st=0;st<dupchar.length();st++){
int value=0;
for(int en=0;en<sat.length();en++){
if(dupchar.charAt(st)==sat.charAt(en)){
value++; }
}
val[st] = value;
}
int temp=0;
for(int fd=0;fd<val.length;fd++){
if(temp<val[fd]){
temp = val[fd];
}
}
for(int fd=0;fd<val.length;fd++){
if(temp==val[fd]){
System.out.println("Values Occurance : " + val[fd] + " Character Occured " + dupchar.charAt(fd));
}
}
}
C# Console Application
using System;
using System.Collections.Generic;
using System.Linq;
namespace Algorithm2
{
class Program
{
class tekrar
{
public char character { get; set; }
public int duplicationCount { get; set; }
}
static void Main(string[] args)
{
string word = Console.ReadLine();
List<tekrar> list = new List<tekrar>();
foreach (char item in word)
{
if (list.Find(a => a.character == item) == null)
{
list.Add(new tekrar() { character = item, duplicationCount = 1 });
}
else
{
list.Find(a => a.character == item).duplicationCount += 1;
}
}
list = list.OrderByDescending(a => a.duplicationCount).ToList();
Console.Write(string.Format("{0} is duplicated {1} times ", list.First().character, list.First().duplicationCount));
Console.Read();
}
}
}
Using hash (ASCII table in C++):
char GetMostRepeatedChar(char *s, int *repeatedCount)
{
char repeatedChar = '\0';
int hash[256];
int repeated = 0;
if (s && repeatedCount)
{
for (int i = 0; i < 256; hash[i++] = 0);
while (*s)
{
hash[*s] += 1;
s++;
}
repeated = hash[0];
repeatedChar = 0;
for (int i = 1; i < 256; i++)
{
if (hash[i] > repeated)
{
repeated = hash[i];
repeatedChar = i;
}
}
*repeatedCount = repeated;
}
return repeatedChar;
}
Just about all if not all of the above are flawed. Those are assuming that there is a single character that is the highest. There could be multiple. My code in C# is this
int[] chrOffset = new int[char.MaxValue];
string str = "test test for this exercise";
char[] charOfStr = str.ToCharArray();
for (int i = 0; i < charOfStr.Length; i++)
{
chrOffset[(int)charOfStr[i]]++;
}
int highest = 0;
List<int> highNum = new List<int>();
for (int i = 0; i < chrOffset.Length; i++)
{
if (highest > chrOffset[i])
{
//do nothing
}
else
{
if (highest < chrOffset[i])
{
highest = chrOffset[i];
highNum.Clear();
}
highNum.Add(i);
}
}
for (int i = 0; i < highNum.Count; i++)
{
Console.WriteLine((char)highNum[i]);
}
Console.WriteLine("Count of those is " + highest);
Console.ReadKey();
class SolutionCharacterAppearingTheMostInAString {
public void getCharacterAppearingTheMostInAString(String str) {
int[] charMap = new int[256];
int max = 0;
for (int i = 0; i < str.length(); i++) {
charMap[str.charAt(i)]++;
if (max < charMap[str.charAt(i)]) {
max = charMap[str.charAt(i)];
}
}
for (int i = 0; i < str.length(); i++) {
if (max == charMap[str.charAt(i)]) {
System.out.println("Character: " + str.charAt(i)
+ " appears maximum number of time i.e: "
+ charMap[str.charAt(i)]);
charMap[str.charAt(i)] = -1;
}
}
}
}
void findMostFrequentChar(String inp){
char[] chAr = inp.toCharArray();
int[] asciiArr = new int[127];
int max = 0;
char mostFrequent = ' ';
for(int i = 0; i<chAr.length;i++){
asciiArr[chAr[i]]++;
if(asciiArr[chAr[i]]>max){
max = asciiArr[chAr[i]];
mostFrequent = chAr[i];
}
}
System.out.println("Character: " + mostFrequent + " occurs " + max+ " times, which is maximum." );
}
public static void findChar(String inp){
char[] chAr = inp.toCharArray();
int[] asciiArr = new int[127];
int max = 0;
char mostFrequent = ' ';
for(int i = 0; i<chAr.length;i++){
asciiArr[chAr[i]]++;
if(asciiArr[chAr[i]]>max){
max = asciiArr[chAr[i]];
mostFrequent = chAr[i];
}
}
System.out.println("Character: " + mostFrequent + " occurs " + max+ " times, which is maximum." );
}
Use a hash table with count of the character as value in key value pair.. keep on increasing value as u find the same char. Also, maintain a max_counter and max_char
- An Enthusiast April 25, 2014Time Complexity O(n), Space Complexity O(n) .. n = number of characters in string