I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Second Highest Frequency

07.18.2013
| 6565 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Calculate The Second Highest Frequency 

Write a method that accepts a String and returns the  character with the second highest frequency. For example "aabbbc" would return 'a'. If the string contains spaces, they can be disregarded from the count.

Catch up on all our previous puzzlers here

Comments

Milind Deo replied on Thu, 2013/07/18 - 6:32am

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 *
 * @author milind
 */
public class SecondHighestFrequency {

    private Map<Character, Character> charMap;
    private Map<Character, Integer> countMap;

    public SecondHighestFrequency() {
        super();
        this.charMap = new HashMap<Character, Character>();
        this.countMap = new HashMap<Character, Integer>();
    }

    public static void main(String[] args) {
        String str = "abccaaccdd";
        new SecondHighestFrequency().findSecondHighestFrequecny(str);

    }

    /**
     * This is the method which will found out duplicate character and add the
     * count in the string
     *
     * @param str
     */
    public void findSecondHighestFrequecny(String str) {

        char charArrr[] = str.toCharArray();
        for (int i = 0; i < charArrr.length; i++) {
            char ch = charArrr[i];
            if(ch !=' '){
            	if (this.charMap.get(new Character(ch)) == null) {
                    this.charMap.put(new Character(ch), new Character(ch));
                } else {
                    // If Duplicate try to get the coun value from Map
                    Integer count = this.countMap.get(new Character(ch));
                    if (count == null) {
                        this.countMap.put(new Character(ch), new Integer(2));
                    } else {
                        this.countMap.put(new Character(ch), count+1);
                    }
                }
            }
        }
        // Now Sort the count Map
        MapValueComparator comp = new MapValueComparator(countMap);
        TreeMap<Character, Integer> treeMap = 
        		new TreeMap<Character, Integer>(comp);
        treeMap.putAll(countMap);
        if(treeMap.size() >=2) {
        	System.out.println("Second Highest value :"+
        treeMap.entrySet().toArray()[1]);
        }else{
        	System.out.println(" There is no Second Value only one "
        			+ "value present");
        }
    }
}
/**
 * Comparator
 * @author milind
 *
 */
class MapValueComparator implements Comparator<Character> {

    Map<Character, Integer> original;
    public MapValueComparator(Map<Character, Integer> original) {
        this.original = original;
    }
    public int compare(Character a, Character b) {
        if (original.get(a) >= original.get(b)) {
            return -1;
        } else {
            return 1;
        } 
    }
}

Andreas Schilling replied on Thu, 2013/07/18 - 7:55am

 Here's my solution with some guava magic. Most awesome library ever :-)

import java.util.Collection;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

import com.google.common.base.CharMatcher;
import com.google.common.base.Function;
import com.google.common.base.Functions;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multimaps;
import com.google.common.collect.Ordering;
import com.google.common.primitives.Chars;


/**
 * 
 * @author aschilling
 */
public class TestCountCharacters
{
  @Test
  public void testSecondHighestFrequency()
  {
    Assert.assertEquals( 'a', secondHighestFrequence( "aabbbc" ).charValue() );
    Assert.assertEquals( 'b', secondHighestFrequence( "aaaabbbc" ).charValue() );
    Assert.assertEquals( 'c', secondHighestFrequence( "abcc  aaaaccdd" ).charValue() );
    Assert.assertNull( secondHighestFrequence( "aa" ) );
  }


  private Character secondHighestFrequence( final String input )
  {
    final Multimap<Character, Character> bins =
            Multimaps.index(
                    Chars.asList( CharMatcher.isNot( ' ' ).retainFrom( input )
                            .toCharArray() ), Functions.<Character> identity() );
    final Function<Collection<Character>, Integer> collectionToSize =
            new Function<Collection<Character>, Integer>()
            {
              @Override
              public Integer apply( final Collection<Character> collection )
              {
                return collection.size();
              }
            };

    final Function<Character, Integer> collectionSize =
            Functions.compose( collectionToSize, Functions.forMap( bins.asMap() ) );
    final List<Character> twoMostFrequent =
            Ordering.natural().onResultOf( collectionSize ).greatestOf( bins.keySet(), 2 );
    return twoMostFrequent.size() == 2 ? twoMostFrequent.get( 1 ) : null;
  }
}

sun east replied on Thu, 2013/07/18 - 8:07am

scala>
scala> def second(str: String): Char = {
     |   val ord = str.groupBy(identity).toSeq.sortBy{ case(c,s) => -s.size }
     |   ord(1)._1
     | }
second: (str: String)Char

scala> second("aabbbc")
res0: Char = a

Luka Matosevic replied on Thu, 2013/07/18 - 8:45am in response to: sun east

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class CharUtil {

    public static Character findSecondHighestFrequency(final CharSequence seq) {
        Character result = null;

        // Build char count map
        final Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < seq.length(); ++i) {
            final char c = seq.charAt(i);
            if (c != ' ') {
                Integer count = map.get(c);
                map.put(c, count != null ? ++count : 0);
            }
        }

        // At least 2 entries ?
        if (map.size() >= 2) {
            final List<Entry<Character, Integer>> entries =
                    new ArrayList<>(map.entrySet());
            Collections.sort(entries,
                    new Comparator<Entry<Character, Integer>>() {
                @Override
                public int compare(final Entry<Character, Integer> e1,
                        final Entry<Character, Integer> e2) {
                    return e2.getValue().compareTo(e1.getValue());
                }
            });

            // Second highest is the second enttry
            result = entries.get(1).getKey();
        }

        return result;
    }

    public static void main(final String... args) {
        final Character c = CharUtil.findSecondHighestFrequency("aabbbc");
    }
}

Star Duster replied on Thu, 2013/07/18 - 4:44pm

No solution cares about the highest frequency appearing twice so how about: 'aaaabbbbcccd'
What is the Second Highest Frequency then?
I would expect 'c'

All current approaches return only one solution but how about: 'aaaabbbcccd'
What is the Second Highest Frequency then?
I would expect 'b' and 'c'

Adam Tankanow replied on Fri, 2013/07/19 - 9:40am

Throwing Clojure into the mix (this solution also addressed Star Duster's comment):

(defn second-highest-frequency
  [^String unsorted-string]
  (->> unsorted-string
       sort
       (partition-by identity)
       (group-by count)
       (into (sorted-map-by >))
       second
       val
       (mapcat distinct)))
Calling this at the REPL yields:
user=> (second-highest-frequency "aabbbc")
(\a)
user=> (second-highest-frequency "aabbbcccaa")
(\b \c)

Alexey Kutuzov replied on Fri, 2013/07/19 - 10:55am

Something like that:

public class Test {
    public static char findSecond(String str) {
        char firstMax = 127, secondMax = 127;
        long[] freq = new long[128];
        for (char c : str.toCharArray()) {
            long curr = ++freq[c];
            if (curr > freq[firstMax]) {
                secondMax = firstMax;
                firstMax = c;
            }
        }
        return secondMax != 127 ? secondMax : firstMax;
    }

    public static void main(String[] args) {
        System.out.println(findSecond("aabbbcccc"));
    }
}

It works for ascii only but has O(str.length) and use fixed mem size for any case.



Alexey Kutuzov replied on Fri, 2013/07/19 - 2:21pm in response to: Alexey Kutuzov

Actually there should be one more condition to check if curr greater than freq[secondMax] value. Without that it will lost case like "aaabbbbbbcccc".

David Whatever replied on Sun, 2013/08/11 - 10:53pm

I decided to try to use Java 8 lambdas again, although I suspect I'm doing some of this in a more difficult fashion than I need to.

Edit: I was hoping to get comments on this, as my plan is to use this as a live demo for a tutorial on Java 8 features which I plan to give in a bit. That said, I revised my earlier entry to have a bit better style, and comments for each step of the way:

public class Final {
  public static void main(String[] args) {
    if(args.length != 1) {
      System.err.println("Usage:");
      System.err.println("{app} \"<string to evaluate>\"");
      return;
    }
    
    // First we convert to a Map of character to occurance count
    // Then, we convert to a TreeMap of occurance count to list of characters
    TreeMap<Long, List<Character>> frequency = args[0]
      .chars()                            // with the characters in an Intstream
      .filter(Character::isLetterOrDigit) // filter out non letter/digit chars
      .map(Character::toUpperCase)        // and convert to upper-case
      .boxed()                            // convert to Stream<Integer>
      .collect(                           // collect results
        groupingBy(                       // grouped into a map 
          (i)->(char)(int)i,              // with key being identity (plus, cast Integer back to Character)
          counting()                      // and with a count for how many times we see each key
        )
      )
      .entrySet()                         // then, take the entries in that map
      .stream()                           // and as a Stream<Map.Entry<Character, Long>>
      .collect(                           // collect results
        groupingBy(                       // grouped by
          Map.Entry::getValue,            // entry value (occurance count)
          TreeMap::new,                   // into a SortedMap (tree map)
          mapping(                        // mapping the entries
            Map.Entry::getKey,            // by entry key
            toList()                      // into a list
          )
        )
      );
 
      Map.Entry<Long, List<Character>> highestCount = frequency.pollLastEntry();
      Map.Entry<Long, List<Character>> secondHighestCount = frequency.pollLastEntry();
      if (highestCount == null) {
        System.out.println("No usable characters appeared in the input string");
        return;
      }
      System.out.println("Character(s) with the highest entry count of " + highestCount.getKey() + ": " + highestCount.getValue());

      if (secondHighestCount != null)
        System.out.println("Character(s) with the second highest entry count of " + secondHighestCount.getKey() + ": " + secondHighestCount.getValue());
      else
        System.out.println("There was no second-highest entry count; acceptable characters occurred equally");
  }

sun east replied on Fri, 2013/07/19 - 6:53pm in response to: Star Duster

Fair enough.

scala>
scala> def second[A](xs: Seq[A]): Set[A] = {
     |   val dict = xs.groupBy(identity).groupBy(_._2.size)
     |   val freq = dict.keys.toSeq.sorted
     |   if(freq.size < 2) Set()
     |   else dict(freq(freq.size-2)).keySet
     | }
second: [A](xs: Seq[A])Set[A]

scala> second("")
res0: Set[Char] = Set()

scala> second("abbccc")
res1: Set[Char] = Set(b)

scala> second("aabbbcccaa")
res2: Set[Char] = Set(b, c)

scala> second(Array(1,1,1,2,2,3,3,4,4,5,6,6,6,6))
res3: Set[Int] = Set(1)

scala> second(Array(1,1,1,2,2,3,3,4,4,5,6))
res4: Set[Int] = Set(2, 3, 4)

matt inger replied on Fri, 2013/07/19 - 10:06pm in response to: sun east

I can up with something very similar, though i did the keyset up front:

  def nthHighest(s:String,i:Int) : Set[Char] = {
    val dict = s.toList.groupBy(identity).groupBy(_._2.size).mapValues(_.keySet).toList.sortBy(_._1).reverse
    if (dict.size > i)
      dict(i)._2
    else
      Set()
  }

I'm still somewhat new to scala, but i live it's expressiveness.  Notice how most of the java solutions (even with the lambas) are so much more verbose.



Kamal Mettananda replied on Wed, 2013/07/24 - 1:35am

I decided to try this puzzle with a test driven approach and wrote initial test cases  followed by the support for multiples of same frequencies. Below is one of the completed code.
 
package com.digizol.puzzle;
 
import java.util.*;
 
public class SortBasedFrequentCharacters {
 
    public char[] getSecondMostFrequent(String text) {
 
        char[] charArray = text.toCharArray();
        Arrays.sort(charArray);
 
        List<Frequency> list = new ArrayList<Frequency>();
        char previous = '\u0000';
        Frequency f = null;
 
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
 
            if (i == 0 || previous != c) {
                f = new Frequency(1, c);
                list.add(f);
                previous = c;
            } else {
                f.count += 1;
            }
        }
 
        Collections.sort(
                        list,
                        new Comparator<Frequency>() {
                            public int compare(Frequency fr0, Frequency fr1) {
                                // sort in descending order
                                return fr1.count - fr0.count;
                            }
                        }
                    );
 
        // supporting multiple characters being most frequent
 
        int currentFrequency = 0;
        boolean secondMostFound = false;
        int start = -1;
        int end = -1;
        for (int i = 0; i < list.size(); i++) {
            Frequency frequency = list.get(i);
            if (i == 0) {
                currentFrequency = frequency.count;
            } else if (currentFrequency != frequency.count) {
                if (secondMostFound) {
                    end = i;
                    break;
                } else {
                    secondMostFound = true;
                    start = i;
                    end = i;
                }
            }
        }
 
        char values[] = null;
        if (secondMostFound) {
            List<Frequency> secondMostFrequencies = list
                    .subList(start, end + 1);
            values = new char[secondMostFrequencies.size()];
            for (int i = 0; i < secondMostFrequencies.size(); i++) {
                values[i] = secondMostFrequencies.get(i).character;
            }
        } else {
            values = new char[0];
        }
        return values;
    }
 
    private class Frequency {
        int count;
        char character;
 
        public Frequency(int count, char character) {
            this.count = count;
            this.character = character;
        }
    }
}

Final test cases are as follows.

package com.digizol.puzzle;
 
import static java.lang.Character.valueOf;
import static org.junit.Assert.assertEquals;
import java.util.*;
import org.junit.*;
 
public class SecondFrequentCharactersTest {
 
    private MapBasedFrequentCharacters sut;
 
    @Before
    public void setup() {
        sut = new MapBasedFrequentCharacters();
        // sut = new SortBasedFrequentCharacters();
    }
 
    @Test
    public void shouldReturnCorrectWhenManyMostFrequentsAndOneSecondMostFrequent() {
        // both i & c are the most frequent, y is the second most frequent
        assertEquals(valueOf('y'),
                                valueOf(sut.getSecondMostFrequent("iiixiiyycbcccc")[0]));
    }
     
    @Test
    public void shouldReturnCorrectWhenManyMostFrequentsAndManySecondMostFrequents() {
        // both i & c are the most frequent, x & y are the second most frequent
        char[] secondMostFrequents = sut.getSecondMostFrequent("iiixxiiyycbcccc");
        assertEquals(2, secondMostFrequents.length);
         
        List<Character> expected = new ArrayList<Character>();
        expected.add('x');
        expected.add('y');
        for (int i = 0; i < secondMostFrequents.length; i++) {
            expected.remove(Character.valueOf(secondMostFrequents[i]));
        }
        assertEquals(0, expected.size());
    }
     
    // previous test cases are modified as below
     
    @Test
    public void shouldReturnNullForEmptyText() {
        assertEquals(0, sut.getSecondMostFrequent("").length);
    }
 
    @Test
    public void shouldReturnNullForTextOfSameCharacter() {
        assertEquals(0, sut.getSecondMostFrequent("dddddddd").length);
    }
 
    @Test
    public void shouldReturnCorrectCharWhenTextHasTwoCharsOneBeingMostFrequent() {
        assertEquals(valueOf('y'), valueOf(sut.getSecondMostFrequent("iiiiiyiiiii")[0]));
    }
 
    @Test
    public void shouldReturnCorrectOneForATextWithOneBeingSecondMostFrequent() {
        // most frequent is 'i', second most is 'd'
        assertEquals(valueOf('d'),
                                valueOf(sut.getSecondMostFrequent("iaibicidieidif")[0]));
    }
}

Robby Pelssers replied on Wed, 2013/07/24 - 6:21am

Edo Kan replied on Wed, 2013/07/24 - 6:27am

on LinqPad

"aabbbc"
	.ToCharArray()
	.GroupBy(c => c)
	.OrderByDescending(g => g.Count())
	.Skip(1)
	.Take(1)
	.Select(g => g.Key)
	.First()

Artur Biesiadowski replied on Wed, 2013/07/24 - 7:53am

Xtend + Guava

val letters = HashMultiset.create("aaabbbbcc".toCharArray)
val freq = letters.elementSet.sortBy[letters.count(it)].reverseView
println(if ( freq.size > 1) freq.get(1) else "");

Mike Hostetler replied on Wed, 2013/07/24 - 10:11am

How come no one put a Python version in yet?


class Freq(object):

   def find_second(self, my_str):

      chars_map= {}

      for ch in [x for x in my_str if x!=" "]:

         count = chars_map.get(ch,0)
         count+=1

         chars_map[ch]=count


      char_count = [(x,chars_map[x]) for x in chars_map]

      if len(char_count)<2:
         return char_count[0][0]

      char_count = sorted(char_count,key=lambda x: x[1])

      return char_count[-2][0]

George Dernikos replied on Wed, 2013/07/24 - 10:14am

LinqPad + F#

"aabbbc".ToCharArray()
|> Array.toSeq
|> Seq.countBy id
|> Seq.sortBy (snd >> (~-))
|> Seq.skip 1
|> Seq.take 1
|> Seq.exactlyOne
|> fst

Robert Kimble replied on Wed, 2013/07/24 - 10:27am in response to: Mike Hostetler

Here's my Python (2.7) version:

from collections import Counter
def second_highest(s_input):
    return Counter(''.join(sorted(s_input)).strip() ).most_common(2)[1][0]

Leandro Santos replied on Wed, 2013/07/24 - 10:42am

Ruby solution.
require 'minitest/autorun'

class SecondHighestFrequencyFinder
	def findFromString(s)
		m = s.chars.inject({}) {|h,c| h[c] = s.count(c);h }

		min = m.values.min
		max = m.values.max

		m.find {|k,v| v < max && v > min }.first
	end
end




class TestSecondHighestFrequencyFinder < MiniTest::Unit::TestCase
	def	setup
		@finder = SecondHighestFrequencyFinder.new
	end

	def test_find_from_string
		assert_equal 'b', @finder.findFromString('aaaaaabbbbccc')
		assert_equal 'a', @finder.findFromString('aaabbbbcc')
	end
end

Artur Biesiadowski replied on Wed, 2013/07/24 - 11:45am in response to: Leandro Santos

@Leandro Santos
Is m sorted? If not, how do you know that you will get second highest frequency, not just random one from the middle?
What about having just 2 distinct letters in string?

Leandro Santos replied on Wed, 2013/07/24 - 1:23pm in response to: Artur Biesiadowski

Thanks for your questions.

Can you show me what you mean with a test string? It's hard to discuss it without having a test case scenario.

Artur Biesiadowski replied on Wed, 2013/07/24 - 3:16pm in response to: Leandro Santos

 @Leandro

Try

"aaabbbb" - will expect a to be an answer, but I think your program will show nothing.

"aaaabccddeeffgghhhiijjkkllmmnnoopp" - h is expected answer, but I think that your program will show one of random letters other than a or b.


Leandro Santos replied on Thu, 2013/07/25 - 10:55am in response to: Artur Biesiadowski

@Artur

This should fix the issue, albeit it is a bit of a brute force solution. I updated the tests to reflect your scenarios.


require 'minitest/autorun'

class SecondHighestFrequencyFinder
	def findFromString(s)
		m = s.chars.inject({}) {|h,c| h[c] = s.count(c);h }

    suv = m.values
    max = suv.max
    target = suv.find_all {|n| n < max}.max

		tuple = m.find {|k,v| v == target }
		tuple.first if tuple
	end
end




class TestSecondHighestFrequencyFinder < MiniTest::Unit::TestCase
	def	setup
		@finder = SecondHighestFrequencyFinder.new
	end

	def test_find_from_string
		assert_equal 'b', @finder.findFromString('aaaaaabbbbccc')
  	assert_equal 'a', @finder.findFromString('aaabbbbcc')
		assert_equal nil, @finder.findFromString('aabb')
		assert_equal 'a', @finder.findFromString('aaabbbb')
    assert_equal 'h', @finder.findFromString('aaaabccddeeffgghhhiijjkkllmmnnoopp')
	end
end

Rafael Naufal replied on Sun, 2013/08/11 - 9:12pm

Leonardo Goslar Otto replied on Fri, 2013/08/16 - 3:27pm

In Brazilian portuguese.
Java solution using TDD: http://blog.rocktto.com/2013/08/quebra-cabeca-dzone-segunda-maior-frequencia/


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.