Expedia Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
public static char getMaxcount(String temp)
{
Map<Character, Integer> map=new LinkedHashMap<Character, Integer>();
char maxCountchar=temp.charAt(0);
for(int i=0;i<temp.length();i++)
{
char c=temp.charAt(i);
map.put(c, map.get(c)==null?1:map.get(c)+1);
if(map.get(maxCountchar)<map.get(c))
{
maxCountchar=c;
}
}
return maxCountchar;
}
Your program will return the wrong result for an input such as abba. You can maybe have another map object with the character as key and it's first position in the string as the value. Once you're done with processing the string, you can go through the first map, and in case of a tie, check the 2nd map to get the first encountered character.
import java.util.*;
public class RepeatedExample {
public static void main(String[] args)
{
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
String theString = "aaba";
for (int i = 0; i < theString.length(); i++) {
if ( map.containsKey(theString.charAt(i))) {
map.put (theString.charAt(i), map.get(theString.charAt(i)) + 1 );
} else {
map.put (theString.charAt(i), 1);
}
}
for(Map.Entry item:map.entrySet())
System.out.println(item.getKey() + ": " + item.getValue());
}
}
//Java code for O(n) solution:
String printMaximumOccurringCharacter(String s) {
if (s == null || s.length() > 10000)
return "Given string size is out of bounds";
int[] intArray = new int[256];
int max = 0;
int indexOfMaxInString = -1;
int indexOfMax = -1;
int indexOfEqualMax = -1;
for (int i = 0; i < s.length(); i++) {
int intValue = s.charAt(i);
intArray[intValue]++;
// check for maximum counts and
if (intArray[intValue] > max) {
max = intArray[intValue];
indexOfMax = intValue;
indexOfEqualMax = -1;
} else if (intArray[intValue] == max) {
indexOfEqualMax = intValue;
int indexOfEqualMaxInString = i;
if (indexOfMaxInString == -1)
indexOfMaxInString = i;
if (indexOfEqualMaxInString < indexOfMaxInString) {
indexOfMax = indexOfEqualMax;
indexOfMaxInString = indexOfEqualMaxInString;
}
}
}
System.out.println((char) indexOfMax);
System.out.println(intArray[indexOfMax]);
return "Success";
}
---------------------------
For the sample Input #02
String s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
The Output is:
a
4
Sucess
String input = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz ";
String output = "";
LinkedHashMap map = new LinkedHashMap<Character, Integer>();
int maxCount = 0;
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
if(null == map.get(ch)){
map.put(ch, 1);
}else{
int count = (Integer)map.get(ch);
map.put(ch,++count);
}
}
Iterator it = map.keySet().iterator();
while (it.hasNext()) {
Character o = (Character) it.next();
Integer count = (Integer)map.get(o);
if(maxCount < count){
maxCount = count;
}
}
Iterator it1 = map.keySet().iterator();
while (it1.hasNext()) {
Character o = (Character) it1.next();
Integer count = (Integer)map.get(o);
if(count == maxCount){
output = o+"";
break;
}
}
System.out.print(output);
String givenString = string.Empty;
givenString = "bchjbdchcbjdchdbcydbcdcnE#$^(*(hhydgdhdbd";
Int32 length = givenString.Length;
var temp = givenString.ToCharArray();
char maxchar = temp[0];
int count = 0;
int count2 = 0;
Console.Write(temp);
for (int i = 0; i < length; i++)
{
count2 = 0;
for (int j = 0; j < length; j++)
{
if (temp[i] == temp[j])
count2++;
}
if (count2 > count)
{
count = count2;
maxchar = temp[i];
}
}
Console.Write("\n" + maxchar.ToString() + "=" + count.ToString());
Console.Read();
package com.test.sonal;
public class MaximumNumberOfChar {
public static void main(String abc[])
{
String ab1 = "hfvhhhhtytyfdfdddddddddddeeeeeeeeeeeeggggggggggggg";
int num[] = new int[256];
int i = 0;
int maxIndex = -1;
int max = -1;
while(i<ab1.length())
{
char c = ab1.charAt(i);
if(num[c] >= 0)
{
num[c]=num[c]+1;
if(num[c] > max)
{
max = num[c];
maxIndex = i;
}
} i++;
}
System.out.println("\n max"+ max + "\n maxIndex"+ maxIndex + "value at max index "+ab1.charAt(maxIndex));
}
}
public static void PrintFirstRepeatedCharacterApproach1()
{
Console.Write("Enter the string to find first repeated character: ");
string input = Console.ReadLine();
if (string.IsNullOrEmpty(input) || input.Length <= 1)
{
Console.WriteLine("Input string cannot be null and length should be greater than 1.");
return;
}
char highestRepeatedChar = input[0];
int[] counts = new int[256];
int[] charOrder = new int[256];
for (int i = 0; i < charOrder.Length; i++)
charOrder[i] = -1;
int co = 0;
for (int i =0; i <input.Length; i++)
{
char c = input[i];
if (charOrder[c] == -1)
charOrder[c] = co++;
counts[c]++;
if (counts[highestRepeatedChar] < counts[c])
{
highestRepeatedChar = c;
}
}
char firstRepChar = highestRepeatedChar;
for (int i = 0; i < 256; i++)
{
if ((int)highestRepeatedChar != i && counts[highestRepeatedChar] == counts[i] && charOrder[i] < charOrder[highestRepeatedChar])
{
firstRepChar = (char)i;
break;
}
}
Console.WriteLine("First repeated character '{0}' and count: {1}", firstRepChar, counts[firstRepChar]);
}
...its cost is o(3n), which is o(n).
Cannot rely on hashtable keys, as they are not returned in the order of insertion.
package com.xyz.test;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class PrintMaxAppearingCharacter {
public PrintMaxAppearingCharacter() {
// TODO Auto-generated constructor stub
}
public static char findMaxAppearChar(char [] arr)
{
HashMap<Character, Integer> hm = new LinkedHashMap<Character, Integer>();
Integer MaxFrequency = 0;
char result = arr[0];
// int length = arr.length-1;
for(Character c:arr)
{
if(hm.containsKey(c)){
int frequency = hm.get(c);
frequency++;
hm.put(c, frequency);
}
else{
hm.put(c, 1);
}
}
Iterator<Character> itr = hm.keySet().iterator();
while(itr.hasNext()){
Character key = itr.next();
Integer value = hm.get(key);
if(value> MaxFrequency){
result = key;
MaxFrequency = value;
}
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String testObj = "testValue";
//char [] arr1 = {'d','b','c','c','a'};
char [] arr1 = testObj.toUpperCase().toCharArray();
System.out.println(PrintMaxAppearingCharacter.findMaxAppearChar(arr1));
}
}
public static void printMaximumOccuringCharacter(String str) {
//Since the input string only contains ASCII characters, create an int array of length 256
int[] chars = new int[256];
//For each character in the string, increment the value that's in the position of the character's integer value
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
chars[ch]++;
}
int maxPos = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] > chars[maxPos]) {
maxPos = i;
}
}
//The maximum frequency
int maxFreq = chars[maxPos];
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (chars[ch] == maxFreq) {
System.out.println(ch);
break;
}
}
}
In java using hashMap
public void printMaxOccuranceCharacter2(final String input) {
if (input == null) {
return;
}
final Map<String, Integer> countByCharacter = new LinkedHashMap<String, Integer>();
final int len = input.length();
int pos = 0;
int maxCount = 0;
String character = "";
while (pos < len) {
final char c = input.charAt(pos);
Integer count = countByCharacter.get(Character.toString(c));
if (count == null) {
count = new Integer(0);
}
count = count + 1;
countByCharacter.put(Character.toString(c), count);
if (maxCount < count) {
maxCount = count;
character = Character.toString(c);
}
pos++;
}
System.out.println("Max characters: " + character);
}
public void printCharMax(String inp) {
Map<Character, Integer> mapChars = new HashMap<Character, Integer>();
int maxShow = 0;
char foundChar = inp.charAt(0);
for(int i = 0;i < inp.length(); i ++) {
char temp = inp.charAt(i);
int initVal = 1;
if(mapChars.containsKey(temp)) {
initVal+= mapChars.get(temp);
if(initVal > maxShow) {
foundChar = temp;
maxShow = initVal;
}
}
mapChars.put(inp.charAt(i), initVal);
}
System.out.println(foundChar);
}
public static void getMaxCharCount(String input){
int[] charArr = new int[128];
int maxCount = 0;
int maxIndex=0;
for(char c : input.toCharArray()){
if( maxCount < charArr[c]+1){
charArr[c] +=1;
maxCount = charArr[c];
maxIndex = c;
}
}
System.out.println("Max char is "+ (char)maxIndex);
}
// Java Implementation
// Time Complexity is O(n) where n is the length of string and space complexity is O(1)
void printMaximumOccuringCharacter(String str) {
Map<Integer, Entry> occurrenceMap = new HashMap<Integer, Entry>();
int maximumOccuringCharacter = 0;
for (int index = 0; index < str.length(); index++) {
int character = str.charAt(index);
if (null != occurrenceMap.get(character)) {
occurrenceMap.get(character).setCount(occurrenceMap.get(character).getCount() + 1);
} else {
occurrenceMap.put(character, new Entry(1, index));
}
if (character != maximumOccuringCharacter) {
Entry entry = occurrenceMap.get(maximumOccuringCharacter);
if (null == entry || occurrenceMap.get(character).getCount() > entry.getCount()) {
maximumOccuringCharacter = character;
} else if (occurrenceMap.get(character).getCount() == entry.getCount()) {
if (occurrenceMap.get(character).getStartingIndex() < entry.getStartingIndex()) {
maximumOccuringCharacter = character;
}
}
}
}
System.out.println("Maximum Occuring Character is " + ( char ) maximumOccuringCharacter);
}
public static char MaxRepeatedChar(string str)
{
char maxrepeated = ' ';
int max = 0;
Dictionary<char, int> sDict = new Dictionary<char, int>();
foreach(char c in str)
{
if(!sDict.ContainsKey(c))
{
sDict.Add(c, 1);
}
else
{
sDict[c]++;
}
}
foreach(KeyValuePair<char,int> keyvalue in sDict)
{
if(keyvalue.Value>max)
{
max = keyvalue.Value;
maxrepeated = keyvalue.Key;
}
}
return maxrepeated;
}
String str="aabbccddeeffgggghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyz";
HashMap<Character,Integer> hash=new HashMap<>();
for(int i=0;i<str.length();i++)
{
if(hash.containsKey(str.charAt(i)))
{
hash.put(str.charAt(i),hash.get(str.charAt(i))+1);
}
else
{
hash.put(str.charAt(i),1);
}
}
PriorityQueue<Character> pq=new PriorityQueue<>((a,b)->hash.get(b)-hash.get(a));
pq.addAll(hash.keySet());
System.out.print(pq.peek());
Two solutions come to mind both require O(N) time.
- mo February 20, 2014A. Using HashMap
B. Using static array of size 128 initialized to 0. Each position indicating ASCII value.
C. Increment the count based on the comparison, save the max