Amazon Interview Question SDETs
Country: United States
Interview Type: Phone Interview
As Fernando pointed out, the problem is solvable in O(n)
More generic, the problem is a k-the element selection
problem that occures in different flavours.
If k is small compared to n, it's worth keeping the k elements
in sorted order to select the kth in O(1) at the end of the algo.
time complexity: O(n*k) that is O(n) if k is constant (e.g. 2)
space complexity: O(n)
n is the number of characters in the input string
from collections import defaultdict
def kth_most_repeating_word(str, kth):
i = 0
n = len(str)
word_freq = defaultdict(int)
kcount = [(0, '') for i in range(kth)]
while i < n:
# extract word
while i < n and str[i] == ' ': i += 1 #skip leading spaces
if i == n: break
j = i + 1
while j < n and str[j] != ' ': j += 1 #skip trailing spaces
word = str[i:j]
i = j + 1
# count word occurence
count = word_freq[word] + 1
word_freq[word] = count
# place the element in the sorted list of k length
if kcount[-1][0] < count:
# check if word is already in k-top (can be done more efficient)
k = len(kcount) - 1
for m in range(kth):
if kcount[m][1] == word:
k = m
break
# do "insertion sort"
kcount[k] = (count, word)
while k > 0 and kcount[k - 1][0] < kcount[k][0]:
kcount[k - 1], kcount[k] = kcount[k], kcount[k - 1] #swap
k -= 1
# return result
return kcount[-1][1] if kcount[-1][0] > 0 else None
Can be done in linear time.
One pass to tokenize the string, another to create a dictionary to carry the count of the words and one last time to find which is the second most repeated word
import sys
def second_most_repeated_word(sentence):
last = 0;
words_counter = {}
words = []
x = 0
while x != len(sentence):
if sentence[x] == ' ':
words.append(sentence[last:x])
while sentence[x] == ' ': x += 1
last = x
continue
x += 1
if last != x: words.append(sentence[last:x])
for word in words:
if word not in words_counter: words_counter[word] = 1
else: words_counter[word] += 1
first = sys.maxint; second = sys.maxint; f_w = ''; s_w = ''
for word, count in words_counter.items():
if count < first:
if first != sys.maxint:
second = first
s_w = f_w
first = count
f_w = word
if count > first and count < second:
second = count
s_w = word
return s_w
Here is the same basically in a python one liner
from collections import Counter
def second_most_repeated_word(sentence):
return Counter(sentence.split()).most_common(2)[1][0]
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
Please suggest if below code is correct
import operator
my_dict = {}
count=0
fruits=['aaa','bbb','ccc','aaa','bbb','aaa']
for i in fruits:
if i in my_dict:
count=count+1
my_dict[i]=count
else:
my_dict[i]=1
sorted_x = sorted(my_dict.items(), key=operator.itemgetter(1))
for k,v in sorted_x:
print (k,v)
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
and
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
and
and package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
and
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see hey"));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
and
and
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see "));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
and
and package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see "));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
package com.indus.training.persist.impl;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class CheckSen {
public static void main(String[] args) {
Sentence sen = new Sentence();
System.out.println(sen.method("hey bye hey bye see see see "));
}
}
class Sentence {
public String method(String s) {
StringTokenizer st = new StringTokenizer(s, " ");
ArrayList<String> al = new ArrayList<String>();
HashMap<Integer, String> hm = new HashMap<Integer, String>();
while (st.hasMoreTokens()) {
String n = st.nextToken();
al.add(n);
}
for (int i = 0; i < al.size(); i++) {
int b = 0;
for (int j = 0; j < al.size(); j++) {
if (al.get(i).equals(al.get(j))) {
b++;
}
}
hm.put(b, al.get(i));
}
Map<Integer, String> tm = new TreeMap<Integer, String>(hm);
for (Integer keys : tm.keySet()) {
}
Object[] keys = tm.keySet().toArray();
Integer seckey = (Integer) keys[keys.length-2];
return tm.get(seckey);
}
}
import java.util.Hashtable;
import java.util.Scanner;
public class SecondMost{
public static void main(String args[]){
Scanner in = new Scanner(System.in).useDelimiter("\n");
Hashtable<String , Integer> hash = new Hashtable<String,Integer>();
String k= in.next(),s;
Scanner sp = new Scanner(k).useDelimiter(" ");
while(sp.hasNext()){
s=sp.next();
if(!hash.containsKey(s))
hash.put(s,1);
else
hash.put(s,hash.get(s)+1);
}
//For Finding Second most String in Hash
String maxStr="",secondMaxStr="",temp;
int maxInt=0,secondMaxInt=0,value;
//for Finding First Max ----> O(n)
for(String key:hash.keySet()){
value=hash.get(key);
if(maxInt<value){
maxInt=value;
maxStr=key;
}
}
for(String key:hash.keySet()){
if(key.equals(maxStr))
continue;
value=hash.get(key);
if(secondMaxInt<value){
secondMaxInt=value;
secondMaxStr=key;
}
}
System.out.println(secondMaxStr);
}
}
Please suggest if given below code is correct
import operator
my_dict = {}
count=0
fruits=['aaa','bbb','ccc','aaa','bbb','aaa']
for i in fruits:
if i in my_dict:
count=count+1
my_dict[i]=count
else:
my_dict[i]=1
sorted_x = sorted(my_dict.items(), key=operator.itemgetter(1))
for k,v in sorted_x:
print (k,v)
Here is another approach to find the Nth highest occurrence..
string inputString = "aaa bbb ccc aaa bbb aaa";
string[] seperator = { " " };
int findNthHighest = 2;
var splitInputString = inputString.Split(seperator, StringSplitOptions.RemoveEmptyEntries);
Dictionary<string, int> findTheOccurrence = new Dictionary<string, int>();
// Add each of the unique string and occurences
foreach (string str in splitInputString)
{
if (findTheOccurrence.ContainsKey(str))
{
int incrementValue = 0;
bool existingToken = findTheOccurrence.TryGetValue(str, out incrementValue);
findTheOccurrence.Remove(str);
findTheOccurrence.Add(str, ++incrementValue);
}
else
{
findTheOccurrence.Add(str, 1);
}
Console.WriteLine(str);
}
// Verify Current List
foreach (KeyValuePair<string, int> KP in findTheOccurrence)
{
Console.WriteLine(string.Format("{0} - {1} ", KP.Key, KP.Value));
}
string tempHighestKey = string.Empty;
int tempHighestValue = 0;
// Check for the n highest
for (int i = 0; i < findNthHighest; i++)
{
tempHighestKey = string.Empty;
tempHighestValue = 0;
foreach (KeyValuePair<string, int> KP in findTheOccurrence)
{
if (KP.Value > tempHighestValue)
{
tempHighestValue = KP.Value;
tempHighestKey = KP.Key;
}
}
findTheOccurrence.Remove(tempHighestKey);
}
Console.WriteLine(string.Format("The {0} Highest: - {1} --- {2}", findNthHighest, tempHighestKey, tempHighestValue));
Console.ReadKey();
import java.io.*;
import java.util.*;
public class Driv
{
public static void main(String[] args)
{
int i;
int max=0;
int sec=0;
String secmax="";
String firmax="";
List<String> x=new ArrayList<String>();
Scanner s=new Scanner(System.in);
for(i=0;i<7;i++)
x.add(s.next());
HashMap<String,Integer> hm=new HashMap<String,Integer>();
for(String str:x)
{
if(hm.containsKey(str))
{
hm.put(str,hm.get(str)+1);
}
else
hm.put(str,1);
}
for(Map.Entry<String,Integer> entry: hm.entrySet())
{
if(entry.getValue()>max)
{
sec=max;
secmax=firmax;
max=entry.getValue();
firmax=entry.getKey();
}
else if(entry.getValue()> sec)
{
sec=entry.getValue();
secmax=entry.getKey();
}
}
System.out.println("The second most repeating string is:"+secmax);
}
}
public static String getSecondMostRepeatedWord(String str){
Map<String,Integer> countMap = new HashMap<String,Integer>();
StringTokenizer tokenizer = new StringTokenizer(str);
while(tokenizer.hasMoreTokens()){
String word = tokenizer.nextToken();
if(countMap.containsKey(word)){
countMap.put(word, countMap.get(word)+1);
}else{
countMap.put(word, 1);
}
}
int max=Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;
String secondMosrRepeatedWord =null;
String maxOccuringWord =null;
for(Map.Entry<String, Integer> entry : countMap.entrySet()){
if(entry.getValue() > max){
if(max != Integer.MIN_VALUE){
secondMax=max;
secondMosrRepeatedWord= maxOccuringWord;
}
max = entry.getValue();
maxOccuringWord=entry.getKey();
}else if(entry.getValue() > secondMax){
secondMax = entry.getValue();
secondMosrRepeatedWord = entry.getKey();
}
}
return secondMosrRepeatedWord;
}
public static String getSecondMostRepeatedWord(String str){
Map<String,Integer> countMap = new HashMap<String,Integer>();
StringTokenizer tokenizer = new StringTokenizer(str);
while(tokenizer.hasMoreTokens()){
String word = tokenizer.nextToken();
if(countMap.containsKey(word)){
countMap.put(word, countMap.get(word)+1);
}else{
countMap.put(word, 1);
}
}
int max=Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;
String secondMosrRepeatedWord =null;
String maxOccuringWord =null;
for(Map.Entry<String, Integer> entry : countMap.entrySet()){
if(entry.getValue() > max){
if(max != Integer.MIN_VALUE){
secondMax=max;
secondMosrRepeatedWord= maxOccuringWord;
}
max = entry.getValue();
maxOccuringWord=entry.getKey();
}else if(entry.getValue() > secondMax){
secondMax = entry.getValue();
secondMosrRepeatedWord = entry.getKey();
}
}
return secondMosrRepeatedWord;
}
public static String getSecondMostRepeatedWord(String str){
Map<String,Integer> countMap = new HashMap<String,Integer>();
StringTokenizer tokenizer = new StringTokenizer(str);
while(tokenizer.hasMoreTokens()){
String word = tokenizer.nextToken();
if(countMap.containsKey(word)){
countMap.put(word, countMap.get(word)+1);
}else{
countMap.put(word, 1);
}
}
int max=Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;
String secondMosrRepeatedWord =null;
String maxOccuringWord =null;
for(Map.Entry<String, Integer> entry : countMap.entrySet()){
if(entry.getValue() > max){
if(max != Integer.MIN_VALUE){
secondMax=max;
secondMosrRepeatedWord= maxOccuringWord;
}
max = entry.getValue();
maxOccuringWord=entry.getKey();
}else if(entry.getValue() > secondMax){
secondMax = entry.getValue();
secondMosrRepeatedWord = entry.getKey();
}
}
return secondMosrRepeatedWord;
}
public static string GetMostRepeatingWord(string listOfWords)
{
string[] tokens = listOfWords.Split(' ');
Hashtable map = new Hashtable();
foreach (var c in tokens)
{
if (!map.Contains(c))
{
map.Add(c,1);
}
else
{
map[c] = Convert.ToInt32(map[c]) + 1;
}
}
return map.Cast<DictionaryEntry>().OrderByDescending(i => i.Value).Skip(1).First().Key.ToString();
}
public static string GetMostRepeatingWord(string listOfWords)
{
string[] tokens = listOfWords.Split(' ');
Hashtable map = new Hashtable();
foreach (var c in tokens)
{
if (!map.Contains(c))
{
map.Add(c,1);
}
else
{
map[c] = Convert.ToInt32(map[c]) + 1;
}
}
return map.Cast<DictionaryEntry>().OrderByDescending(i => i.Value).Skip(1).First().Key.ToString();
}
public static string GetRepeatingWord(string listOfWords)
{
string[] tokens = listOfWords.Split(' ');
Hashtable map = new Hashtable();
foreach (var c in tokens)
{
if (!map.Contains(c))
{
map.Add(c,1);
}
else
{
map[c] = Convert.ToInt32(map[c]) + 1;
}
}
return map.Cast<DictionaryEntry>().OrderByDescending(i => i.Value).Skip(1).First().Key.ToString();
}
#include <iostream>
#include <string>
std::string a[6]={"aaa","bbb","ccc","aaa","bbb", "aaa"};
//std::string a[6]={"aaa","aaa","aaa","aaa","aaa", "aaa"};
int c[2]={0};
int i = 0;
void countall(std::string r[]){
std::string temp = r[i];
if( temp.compare("aaa") == 0 ) c[0]++;
if( temp.compare("bbb") == 0 ) c[1]++;
if( temp.compare("ccc") == 0 ) c[2]++;
if(i < 6) {
i++;
countall(a);
}
}
int main(){
countall(a);
std::cout << "aaa=" << c[0] << " " << "bbb=" << c[1] << " " << "ccc=" << c[2] << std::endl;
return 0;
}
aaa=3 bbb=2 ccc=1
@Test
public void test_key_frequency_map() {
String[] array={"aaa","bbb","ccc","aaa","bbb", "aaa"};
Arrays.sort(array);
List distinctSortedList=Arrays.stream(array).distinct().collect(Collectors.toList());
distinctSortedList.forEach(System.out::println);
System.out.println("Second frequency:"+distinctSortedList.get(1));
}
@Test
public void test_key_frequency_map() {
String[] array={"aaa","bbb","ccc","aaa","bbb", "aaa"};
Arrays.sort(array);
List distinctSortedList=Arrays.stream(array).distinct().collect(Collectors.toList());
distinctSortedList.forEach(System.out::println);
System.out.println("Second frequency:"+distinctSortedList.get(1));
}
public void test_key_frequency_map() {
//String[] array= {"aaa", "bbb","ccc","qq","ccc","qq","ff","aaa","cc","bbb","ccc","qq","ff","aaa","bbb","aaa"};
String[] array={"aaa","bbb","ccc","aaa","bbb", "aaa"};
Arrays.sort(array);
List distinctSortedList=Arrays.stream(array).distinct().collect(Collectors.toList());
distinctSortedList.forEach(System.out::println);
System.out.println("Second frequency:"+distinctSortedList.get(1));
}
package DS.BasicProgrammingJava.interviewsspecial;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class P4 {
public static void main(String args []){
P4 p4 = new P4();
List<String> data = new ArrayList<String>();
HashMap<String,Integer> map = new HashMap<>();
data.add("aaa");
data.add("bbb");
data.add("ccc");
data.add("aaa");
data.add("bbb");
data.add("aaa");
data.add("ccc");
//data.add("ccc");
//find the count of words
for(String entry:data){
System.out.println(entry);
}
String secondHigh = null;
int first = Integer.MIN_VALUE;
int second =Integer.MIN_VALUE;
int val = 0;
for(String value:data){
if(!map.containsKey(value))
{
map.put(value,1);
}
else {
map.put(value, map.get(value)+1);
}
val = map.get(value);
if(val > first) {
second = first;
first = val;
}
}
for( Map.Entry<String,Integer> entry : map.entrySet()){
if(second==entry.getValue()){
secondHigh = entry.getKey();
break;
}
}
System.out.println("second repeating word is "+secondHigh);
}
}
public String getsecondmostrepeatingword(String word)
{
//set hashmap
HashMap <String, Integer> words = new HashMap<>();
for (String str:word.split(" "))
{
if (!words.containsKey(str))
{
words.put(str, 1);
}
else
{
words.replace(str, words.get(str).intValue() + 1);
}
}
//remove duplicate entries
Collection<Integer> list = words.values();
for(Iterator<Integer> itr = list.iterator(); itr.hasNext();)
{
if(Collections.frequency(list, itr.next())>1)
{
itr.remove();
}
}
//move to list and sort
List<Map.Entry<String,Integer>> list2 = new LinkedList<Map.Entry<String, Integer>>(words.entrySet());
Collections.sort(list2, new Comparator<Map.Entry<String,Integer>>() {
public int compare(Map.Entry<String,Integer> o1,
Map.Entry<String,Integer> o2)
{
return (o1.getValue()).compareTo(o2.getValue());
}
});
return list2.get(list2.size()-2).getKey().toString();
}
{ public String getsecondmostrepeatingword(String word)
{
//set hashmap
HashMap <String, Integer> words = new HashMap<>();
for (String str:word.split(" "))
{
if (!words.containsKey(str))
{
words.put(str, 1);
}
else
{
words.replace(str, words.get(str).intValue() + 1);
}
}
//remove duplicate entries
Collection<Integer> list = words.values();
for(Iterator<Integer> itr = list.iterator(); itr.hasNext();)
{
if(Collections.frequency(list, itr.next())>1)
{
itr.remove();
}
}
//move to list and sort
List<Map.Entry<String,Integer>> list2 = new LinkedList<Map.Entry<String, Integer>>(words.entrySet());
Collections.sort(list2, new Comparator<Map.Entry<String,Integer>>() {
public int compare(Map.Entry<String,Integer> o1,
Map.Entry<String,Integer> o2)
{
return (o1.getValue()).compareTo(o2.getValue());
}
});
return list2.get(list2.size()-2).getKey().toString();
}}
my two cents:
import java.util.HashMap;
import java.util.Map;
public class SecondMostRepeatingWord {
String secondMostRepeating(String sentence) {
Map<String, Integer> stat = new HashMap<>();
for (String w : sentence.split("\\s+")) {
stat.put(w, stat.getOrDefault(w, 0) + 1);
}
String firstMostRepeating = null;
int firstCounter = -1;
String secondMostRepeating = null;
int secondCounter = -1;
for (Map.Entry<String, Integer> s: stat.entrySet()) {
if (s.getValue() >= firstCounter) {
if (s.getValue() == firstCounter) {
continue;
}
secondMostRepeating = firstMostRepeating;
secondCounter = firstCounter;
firstMostRepeating = s.getKey();
firstCounter = s.getValue();
} else if (s.getValue() > secondCounter) {
secondMostRepeating = s.getKey();
secondCounter = s.getValue();
}
}
return secondMostRepeating;
}
}
- nvat July 04, 2017import java.util.HashMap; import java.util.TreeMap; public class SecondMostRepeatingWord { public static void main(String[] args){ System.out.println(secondMostRepeatingWord("abc ddd abc test abc ddd test")); System.out.println(secondMostRepeatingWord("abc ddd ddd ddd abc ddd test")); System.out.println(secondMostRepeatingWord("ddd test ddd test ddd test")); System.out.println(secondMostRepeatingWord("ddd ddd ddd ddd ddd ddd")); System.out.println(secondMostRepeatingWord("")); } private static String secondMostRepeatingWord(String string) { HashMap<String,Integer> map= new HashMap<>(); for(String str:string.split(" ")){ if(!map.containsKey(str)){ map.put(str, 1); } else { map.put(str,map.get(str)+1); } } TreeMap<Integer, String> finalMap = new TreeMap<>(); for(String word : map.keySet()){ finalMap.put(map.get(word), word); } System.out.println("Map ===="+map); System.out.println("TreeMap ===="+finalMap); return finalMap.size()<2? finalMap.get(finalMap.keySet().toArray()[finalMap.size()-1]): finalMap.get(finalMap.keySet().toArray()[finalMap.size()-2]); } }