PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Beautiful Strings solution: Facebook hacker Cup 2013 Qual Round

(No Ratings Yet)

January 29, 2013 by puzzler Leave a Comment

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the first question in the qualification round of 2013 hacker cup.

When John was a little kid he didn’t have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could… he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)

You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input

The input file consists of a single integer m followed by m lines.

Output

Your output should consist of, for each test case, a line containing the string “Case #x: y” where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.

Constraints

5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

Example Input

5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves

Example Output

Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646

Solution:

Key is to read the question clearly, first convert string to Lower Case, then iterate over the characters of the string, if a character is in the range ‘a’ to ‘z’ put it in a hashmap (with key as character and value as number of occurrences). Now take the values in the hashmap in a list and sort the list in descending/ascending order. multiply first/last number by 26 then next number by 25 and so on. I think it will be more clear by this Java code.

Complexity of this solution is O(n) in time and O(1) in space.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class BeautifulStrings {

	public Long getBeauty(String s) {
		int i = -1;
		Map<Character, Integer> lettersOccurencesMap = new HashMap<Character, Integer>();
		try {
			while (true) {
				i++;
				Character c = s.charAt(i);
				c = Character.toLowerCase(c);
				if (c < 'a' || c > 'z') {
					continue;
				}
				// Increasing the number of occurence by 1
				Integer occurence = lettersOccurencesMap.get(c);
				if (occurence == null) {
					occurence = 1;
				} else {
					occurence++;
				}
				lettersOccurencesMap.put(c, occurence);
			}
		} catch (StringIndexOutOfBoundsException e) {
			System.out.println("Reached @ the end of the string");
		}

		ArrayList<Integer> integerList = new ArrayList<Integer>(
				lettersOccurencesMap.keySet().size() * 4 / 3);
		for (Character letter : lettersOccurencesMap.keySet()) {
			integerList.add(lettersOccurencesMap.get(letter));
		}

		// Collection.sort sorts in ascending order
		Collections.sort(integerList);

		Long beauty = 0L;

		int nextHighestBeauty = 26;
		for (i = integerList.size() - 1; i >= 0; i--) {
			Integer occurence = integerList.get(i);
			beauty = beauty + (occurence * nextHighestBeauty);
			nextHighestBeauty--;
		}
		return beauty;
	}
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
Balanced Smileys solution: Facebook hacker Cup 2013 Qual Round

Checkout more Interview Questions Tags: Easy, Interview, Java, Solved Puzzles

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Dead Pixels solution: Facebook hacker cup 2013 Round 1
  • Security problem solution: Facebook hacker cup 2013 Round 1
  • Sort the array in O(N)
  • Find all non duplicate pairs that sum to S
  • Average speed of train
  • Objective Questions set C/C++ – Part 5
  • Objective Questions set C/C++ – Part 4
  • Bullseye Solution: Google codejam 2013 Round 1A
  • Swap two integer variables
  • Charging Chaos Solution – Google CodeJam

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous