Twitter Interview Question
Software Development ManagersTeam: International
Country: United States
Interview Type: Phone Interview
#include<iostream>
#include<string>
using namespace std;
int main(){
int *check=new int[256];
int heighest=0,pos1=0;
int second_heighest=0,pos2=0;
string s="ssssaaxxx";
for ( std::string::iterator ii=s.begin() ; ii!=s.end() ; ii++ ){
//std::cout<<( *ii)<<std::endl;
check[ int(*ii)]+=1;
if ( check [ int (* ii ) ]>heighest ){
//std::cout<<"1st"<<( *ii)<<std::endl;
if( second_heighest != 0 ){
second_heighest=heighest;
pos2=pos1;
}
heighest=check [ * ii ];
pos1=int(*ii);//std::distance( s.begin(), ii );
//std::cout<<":pos2=:"<<pos2<<std::endl;
} else {
if ( check [ int (* ii ) ] > second_heighest ){
//std::cout<<"2nd"<<( *ii)<<std::endl;
second_heighest=check [ * ii ];
pos2=int(*ii);
}
}//std::cout<<pos1<<":"<<pos2<<std::endl;
//std::cout<<*ii;
}
int a;
//std::cout<<"Pos2="<<pos2<<std::endl;
char c=(char)pos2;
//std::cout<<c<<std::endl;
std::cout<<"second heighest "<<c<<" : "<<second_heighest<<std::endl;
}
output :
suman@suman-laptop:/media/D/coding/c++_stuff$ ./a.out
second heighest x : 3
First, naive cut.
1.) Iterate through the string.
2.) Look up each character in a hash table. This map stores a reference to an item in a max-heap
3.) Use that reference to increase the reference count in the max-heap
4.) That max-heap stores a count, and the letter that it counts
5.) When done processing, take the max of the heap twice.
O(n) to go through the input array
O(log n) for the heap maintenance
struct heap_struct{
int count;
char c;
heap_struct(const int& COUNT, const char& C) : count(COUNT), c(C){}
bool operator<(const set_struct& rhs){
return count < rhs.count;
}
};
typedef heap<set_struct> heap_t;
heap_t count_heap;
typedef hash_table<char, set_t::iterator> hash_t;
hash_t char_hash;
int count_letters(const std::string& input, const int& rank){
// check our inputs
if(0 == input.size()){
return -1;
}
if(0 >= rank){
return -1;
}
// Iterate throught the characters
for(unsigned int i = 0; i < input.size(); ++i){
char c = input[i];
hash_t::iterator hash_iter = char_hash.find(c);
// Insert the item
if(char_hash.end() == hash_iter){
heap_t::iterator heap_iter =
count_heap.insert(heap_struct(0, c));
hash_iter = char_hash.insert(std::pair(c, heap_iter));
}
// Increment the count
hash_iter.second->count++;
}
// Return the Nth item
int ret = -1;
for(int i = 0; i < rank; i++){
ret = heap.max();
}
return ret;
}
How much time does it take to build the heap (to add characters, starting from scratch)?
String str = "aaabbcccc";
HashMap<String, String> map = new HashMap<String, String>();
int pos = 0;
int count = 0;
for(int j = 0 ; j < str.length() ; j = pos) {
char current = str.charAt(j);
count = 0 ;
pos = j;
for(int i = pos ; i < str.length() ; i++) {
if(current == str.charAt(i)) {
++count;
map.put(Character.toString(str.charAt(i)), Integer.toString(count));
++pos;
}
}
}
//unsorted map
System.out.println("unsorted \n" + map.toString());
LinkedHashMap<String, String> sortedMap = sortHashMapByValuesD(map);
//sorted map based on value
System.out.println("value based sorting \n" + sortedMap);
}
private static LinkedHashMap<String, String> sortHashMapByValuesD(HashMap<String, String> passedMap) {
List<Map.Entry<String, String>> list = new LinkedList<Map.Entry<String,String>>(passedMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
public int compare(Entry<String, String> o1,
Entry<String, String> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});
Map<String, String> sortedMap = new LinkedHashMap<String, String>();
int counter = 0;
for(Map.Entry<String, String> entry: list) {
++counter;
sortedMap.put(entry.getKey(), entry.getValue());
if(counter == 2) secondEntry = entry.getKey();
}
return (LinkedHashMap<String, String>) sortedMap;
}
after that print second value from last.
Please make comment if solution is not correct and feasible.
Pretty simple solution here... just use a hash table and keep track of the highest frequency and second highest frequency characters. O(n) time complexity. Some optimizations could probably be made...
public static void main (String[] args) {
String origStr = "aaabbcccc";
Hashtable<Character, Integer> hashtable = new Hashtable<>();
int firstHighestFreq = 0, secondHighestFreq = 0;
char firstHighestChar = ' ', secondHighestChar = ' ';
for (int i = 0; i < origStr.length(); i++) {
Character c = origStr.charAt(i);
if(!hashtable.containsKey(c)) {
hashtable.put(c, 1);
} else {
int tempFreq = hashtable.get(c);
hashtable.put(c, ++tempFreq);
if (tempFreq > firstHighestFreq) {
firstHighestFreq = tempFreq;
firstHighestChar = c;
} else if (tempFreq > secondHighestFreq) {
secondHighestFreq = tempFreq;
secondHighestChar = c;
}
}
}
System.out.println("The second highest frequency character is " + secondHighestChar + ", which occurs " + secondHighestFreq + " times.");
}
Correction:
if (tempFreq > firstHighestFreq) {
if (firstHighestChar != c) {
secondHighestFreq = firstHighestFreq;
secondHighestChar = firstHighestChar;
}
firstHighestFreq = tempFreq;
firstHighestChar = c;
} else if (tempFreq > secondHighestFreq) {
secondHighestFreq = tempFreq;
secondHighestChar = c;
}
For this particular question, the character with second max count can be found like this:
#include <iostream>
#include <string>
int main(int argc, char * argv[])
{
using namespace std;
int maxCount = 0, secondMaxCount = 0;
char maxChar ='\0', secondMaxChar = '\0';
int currentCount = 0;
char currentChar = '\0';
string stream = "aaaabbbbbbbbbbccccccjjjjjjjjjjjssssskkkkkkkllllllleeeeeeeeeooooppppppppp";
if(stream.length() > 0)
{
currentChar = stream[0];
currentCount = 1;
for(int i=1; i < stream.length(); ++i)
{
if(stream[i] == currentChar)
{
++currentCount;
}
else
{
if(maxCount < currentCount)
{
secondMaxCount = maxCount;
secondMaxChar = maxChar;
maxCount = currentCount;
maxChar = currentChar;
}
else if(secondMaxCount < currentCount)
{
secondMaxCount = currentCount;
secondMaxChar = currentChar;
}
currentChar = stream[i];
currentCount = 1;
}
}
if(maxCount < currentCount)
{
secondMaxCount = maxCount;
secondMaxChar = maxChar;
maxCount = currentCount;
maxChar = currentChar;
}
else if(secondMaxCount < currentCount)
{
secondMaxCount = currentCount;
secondMaxChar = currentChar;
}
}
cout << "max - char: " << maxChar << ", count: " << maxCount << endl
<< "second max - char: " << secondMaxChar << ", count: " << secondMaxCount << endl;
return 0;
}
If the interviewer ask to generalize the solution for kth max character, then we can create an array of size 256 to store count of each character that occurs in the string, sort this array (ascending sort) and then find the kth element in the sorted array.
#include <stdio.h>
/* Given a string "aaabbcccc", write a program to find the character with the second highest frequency. */
char second_highest(char *s, int n) {
int max = 0, max2 = 0, i, index = -1, index2 = -1; /* index2 and max2 hold second highest */
int count[256] = {0};
for (i = 0; i < n; i++) {
count[s[i]]++;
if (count[s[i]] > max) {
max2 = max;
index2 = index;
max = count[s[i]];
index = i;
}
}
return index2;
}
int main() {
char s[10] = "aaabbcccc";
int index = second_highest(s, 10);
if (index != -1)
printf("%c\n", s[index]);
return 0;
}
in javascript..
function getMax(str) {
var count = 0,
maxCount = 0,
previousLetter = null,
winner = null;
for (var i = 0; i < str.length; i++) {
var currentLetter = str[i];
// if current letter is different than preivous letter set new count
// else increment count
if (currentLetter !== previousLetter) {
count = 1
} else {
count++;
}
// if count is greater than maxCount set to current one
if (count > maxCount) {
maxCount = count
winner = currentLetter
} else if (count === maxCount) {
winner = winner + ', ' + currentLetter
}
// set previous letter to current one before going to next
previousLetter = currentLetter
}
console.log(winner, maxCount)
}
public class secondHighest {
private static int findSecondMax(int count[]){
int i=0;
int MAX = count[0];
int index=0;
int maxindex=0;
int secondMax = 0;
for(i=1;i< count.length;i++){
if(count[i] > MAX ){
if(i!=1){
secondMax = MAX;
index = maxindex;
}
MAX = count[i];
maxindex = i;
}
else{
if(count[i] < MAX && count[i] > secondMax){
secondMax = count[i];
index = i;
}
}
}
return index;
}
public static void main(String args[]){
String s = "aab";
if(s.length() <= 1){
System.out.println(s);
}
int count[] = new int[256];
for(int i=0;i<s.length();i++){
count[(int)s.charAt(i) -97]++;
}
int c= findSecondMax(count);
System.out.println("second highest frequency " + (char)(c+97));
}
}
I would consider to store in a hashtable, and sort by the value (which is the frequency appeared in a string), and return the second key of the hashtable
def highest_frequency(arr):
"""
Given a string "aaabbcccc", write a program to find the character with the second highest frequency.
"""
# empty string, check input and pass non-empty string
if not arr:
return
# a hash table to store values
hashtable = {}
# iterate through the input string and store the frequency of each character into a key-value pair in the hash table
for elem in arr[:]:
if elem in hashtable.keys():
val = int(hashtable.get(elem, "none"))
val += 1
hashtable[elem] = val
else:
hashtable[elem] = 1
# sort the hashtable by its value and grab the second highest
output = sorted(hashtable, key=hashtable.get, reverse=False)
return output[1]
res = highest_frequency('aaabbcccc')
print res
In Java, used a hashmap to keep a running tally of char counts, and pointers to the highest and second highest chars
public char findSecondHighestFrequency(String c){
if(c.length() == 0)
return '?';
// Convenience map of chars found, and their counts
HashMap<Character, Integer> frequencyMap = new HashMap<>();
// Keep track of highest and second-highest frequency chars
Character highestCount = null;
Character secondHighestCount = null;
int idx = 0;
//Loop over chars in string
for(char character : c.toCharArray()){
if(frequencyMap.containsKey(character)) {
frequencyMap.put(character, frequencyMap.get(character) + 1);
}
else
frequencyMap.put(character, 1);
// Set char pointers accordingly
if(idx == 0)
highestCount = character;
else if(idx > 0 && frequencyMap.size() > 1 && secondHighestCount == null) {
secondHighestCount = character;
}
// If current char is more frequent than the current highest, swap them
if(frequencyMap.get(character) > frequencyMap.get(highestCount)){
char temp = highestCount;
highestCount = character;
secondHighestCount = temp;
}
idx++;
}
// Return second highest if there are more than two chars provided
return secondHighestCount != null ? secondHighestCount : highestCount;
}
void secondHighOccurencesOfCharacter() {
String str = "aadddbbcccc";
int [] ascii = new int[str.length()];
int highest = Integer.MIN_VALUE;
int secondHighest = Integer.MIN_VALUE;
for (int i = 0 ; i < str.length() ; i++) {
ascii[str.charAt(i)-97]++;
}
for (int i = 0 ; i < ascii.length ; i++) {
System.out.println("First & Second = "+ highest + " , " + secondHighest);
if (ascii[i] > highest) {
secondHighest = highest;
highest = ascii[i];
} else if (ascii[i] > secondHighest) {
secondHighest = ascii[i];
}
}
System.out.println("First & Second Highest="+ highest + " , " + secondHighest);
}
public static void secondFreq(String str)
{
Map<Character,Integer> cmap = new HashMap<Character,Integer>();
char ch[] = str.toCharArray();
for(int i=0;i<ch.length;i++)
{
if(cmap.containsKey(ch[i]))
{
cmap.put(ch[i],cmap.get(ch[i]) + 1);
}
else
{
cmap.put(ch[i],1);
}
}
System.out.print(cmap);
Map<Character, Integer> sortedMap = sortByComparator(cmap);
System.out.println(sortedMap);
int[] a = new int[cmap.size()];
System.out.println(" ");
int j=0;
for(char key:cmap.keySet())
{
a[j]=cmap.get(key);
j++;
}
Arrays.sort(a);
//for(int k=0;k<cmap.size();k++)
// System.out.print(a[k]);
System.out.println("Second most popular Element is : " + sortedMap.keySet().toArray()[cmap.size()-2]);
}
private static Map<Character, Integer> sortByComparator(Map<Character, Integer> unsortMap) {
// Convert Map to List
List<Map.Entry<Character, Integer>> list =
new LinkedList<Map.Entry<Character, Integer>>(unsortMap.entrySet());
// Sort list with comparator, to compare the Map values
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
public int compare(Map.Entry<Character, Integer> o1,
Map.Entry<Character, Integer> o2) {
return (o1.getValue()).compareTo(o2.getValue());
}
});
// Convert sorted map back to a Map
Map<Character, Integer> sortedMap = new LinkedHashMap<Character, Integer>();
for (Iterator<Map.Entry<Character, Integer>> it = list.iterator(); it.hasNext();) {
Map.Entry<Character, Integer> entry = it.next();
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}
Idea is to count occurence of each chars, sort them and get the second last element.
public static void secondFreq(String str)
{
Map<Character,Integer> cmap = new HashMap<Character,Integer>();
char ch[] = str.toCharArray();
for(int i=0;i<ch.length;i++)
{
if(cmap.containsKey(ch[i]))
{
cmap.put(ch[i],cmap.get(ch[i]) + 1);
}
else
{
cmap.put(ch[i],1);
}
}
System.out.print(cmap);
Map<Character, Integer> sortedMap = sortByComparator(cmap);
System.out.println(sortedMap);
int[] a = new int[cmap.size()];
System.out.println(" ");
int j=0;
for(char key:cmap.keySet())
{
a[j]=cmap.get(key);
j++;
}
Arrays.sort(a);
//for(int k=0;k<cmap.size();k++)
// System.out.print(a[k]);
System.out.println("Second most popular Element is : " + sortedMap.keySet().toArray()[cmap.size()-2]);
}
private static Map<Character, Integer> sortByComparator(Map<Character, Integer> unsortMap) {
// Convert Map to List
List<Map.Entry<Character, Integer>> list =
new LinkedList<Map.Entry<Character, Integer>>(unsortMap.entrySet());
// Sort list with comparator, to compare the Map values
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
public int compare(Map.Entry<Character, Integer> o1,
Map.Entry<Character, Integer> o2) {
return (o1.getValue()).compareTo(o2.getValue());
}
});
// Convert sorted map back to a Map
Map<Character, Integer> sortedMap = new LinkedHashMap<Character, Integer>();
for (Iterator<Map.Entry<Character, Integer>> it = list.iterator(); it.hasNext();) {
Map.Entry<Character, Integer> entry = it.next();
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}
To do it in O(N), set up an array with space for each character. Then go through the string, incrementing the array slot associated with each character. Finally, go through the array and find the second-largest (in this simple case, just keep a max1 and max2, you could use a heap but that's overkill for just the two items). Works out to O(N) + O(N) = O(N).
This can be problematic to pre-allocate an array, depending on where the characters in the input are coming from.
This *feels* like a valid solution. Assuming that the inputs are characters, you only have 26 possible array indices. However, it's not terribly extensible. Imagine changing it from english -> unicode. You could do it, but you need to understand the performance/space payoff. Regardless, a Hash Table would be a better overall data structure for extensibility in all cases.
Although, I'm not a fan of keeping a count. It would be trivial to say, I want the Nth biggest item, and the count is where your solution falls apart.
I misspoke. I mean, count1 and count2. Count1 == <most frequent item>; Count2 == <2nd most frequent>.
Not a fan of this concept, because it's not easily extensible. What if I want the 5th most frequent item. The 25th most frequent item. The 32124th most frequent item (assume Unicode). This is what I mean by saying it falls apart.
If the string is given like in the example, you don't need to keep the count for each character. You can find the second max in one pass.
The question implies you're finding the second most frequent element in a string of sorted characters. Why are you keeping a count? Why are you overengineering a solution to generalize for the kth most frequent element? Just answer the question, and they'll ask you to generalize it if need be. My solution in Go:
// Given a string "aaabbcccc", write a program to find the character with the second highest frequency.
func SecondHighestFrequency(sorted_str string) rune {
var first, second int
var fChar, sChar rune
for i := 0; i < len(sorted_str); {
char := sorted_str[i]
j := 0
for i < len(sorted_str) && sorted_str[i] == char { i, j = i + 1, j + 1 }
if j > first {
second = first
sChar = fChar
first = j
fChar = rune(char)
} else if j > second {
second = j
sChar = rune(char)
}
}
return sChar
}
Here is the code in O(n):
a. Make an array of size 256 to hold all the character count
b. Find the max count in the array
c. Find the second max count in the array by storing all counts less than max in another array and finding the max of those counts which becomes the second count
d. At last print the character
- vgeek July 15, 2013