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

- mo February 20, 2014 | Flag Reply
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;
}

- Anonymous February 21, 2014 | Flag Reply
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.

- Gengis Khan February 22, 2014 | Flag
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());
}
}

- DeepakN March 07, 2014 | Flag Reply
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

- kckarigar March 10, 2014 | Flag Reply
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

- ishankgupta08 March 18, 2014 | Flag
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);

- Varun March 25, 2014 | Flag Reply
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();

- Akash Malhotra March 28, 2014 | Flag Reply
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));
}

}

- Anonymous March 29, 2014 | Flag Reply
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.

- Nagesh Agastya April 02, 2014 | Flag Reply
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));
	}

}

- Mohammad Sabir May 14, 2014 | Flag Reply
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;
    }
  }

}

- Lumberjack September 06, 2014 | Flag Reply
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.

- bhavi February 21, 2015 | Flag Reply
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);
    }

- programmer March 06, 2015 | Flag Reply
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;
}

- Mindcloud November 22, 2015 | Flag Reply
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;
}

- Mindcloud November 22, 2015 | Flag Reply
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);
	}

- Duong PHAM February 29, 2016 | Flag Reply
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);

}

- ankeynigam October 09, 2016 | Flag Reply
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);
        }

- Kapil July 12, 2017 | Flag Reply
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;
        }

- gkr July 31, 2017 | Flag Reply


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