## Twitter Interview Question for Software Development Managers

Team: International
Country: United States
Interview Type: Phone Interview

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

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

``````#include <stdio.h>
#include <conio.h>
#define MAX_CHAR 256

int secondHighestFrequency(char arr[])
{
int i;
int max,min;
int n=MAX_CHAR;
int arr1[MAX_CHAR]={0};
int arr2[MAX_CHAR],j;
for(i=0;arr[i]!='\0';i++)
{
arr1[arr[i]]++;
}
max=arr1[0];
for(i=0;i<n;i++)
{
if(arr1[i]>max)
max=arr1[i];
}
for(i=0;i<n;i++)
{
min=arr1[i];
if(min<max)
{
arr2[j]=min;
j++;
}
}
int sec_max=arr2[0];
for(i=0;i<j;i++)
{
if(arr2[i]>sec_max)
sec_max=arr2[i];
}
for(i=0;i<j;i++)
{
if(sec_max==arr1[i])
printf("The character that occurs with second most frequency is %c",(char)i);
}
}
int main()
{
char arr[]="aaaabbccc";
secondHighestFrequency(arr);
}``````

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

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

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

How would you sort the counts? Wouldn't that take O(n log n) time ?

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

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

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

How much time does it take to build the heap (to add characters, starting from scratch)?

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

@Jay Fibonacci Heap is O(1) insert

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

I don't think heap is O(1), isnt it O(log n)? Because you have to potentially shuffle log n elements?

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

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

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

after that print second value from last.

Please make comment if solution is not correct and feasible.

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

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

}``````

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

Correction:

``````if (tempFreq > firstHighestFreq) {
if (firstHighestChar != c) {
secondHighestFreq = firstHighestFreq;
secondHighestChar = firstHighestChar;
}
firstHighestFreq = tempFreq;
firstHighestChar = c;
} else if (tempFreq > secondHighestFreq) {
secondHighestFreq = tempFreq;
secondHighestChar = c;
}``````

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

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.

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

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

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

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

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

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

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

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

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

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

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

``````void secondHighOccurencesOfCharacter() {
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);
}``````

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

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

This can be problematic to pre-allocate an array, depending on where the characters in the input are coming from.

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

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.

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

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.

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

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.

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

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.

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

In linear time, you can put each character and its frequency into a hash table.

Then iterate through the hash table and keep a running count of the most frequent and second most frequent characters.

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.

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