## Expedia Interview Question for Developer Program Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

Two solutions come to mind both require O(N) time.
A. 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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

Comment hidden because of low score. Click to expand.
0
of 0 votes

This will fail when input String is "abbacc"
result will be b , 2

It should be a , 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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();``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

similar ques in cracking the coding interview. It uses array of size 256 to track the chars.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public char FindMaxChar(string input)
{
return input.GroupBy(x => x).OrderByDescending(x => x.Count()).First().Key;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static char FindMaxChar(string input)
{
return input.GroupBy(x => x).OrderByDescending(x => x.Count()).First().Key;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More