Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Seems a bit ambiguous as not sure if need to print all words of just the duplicates.
I'll let the caller decide to print only dupes or not.
O(n) Solution is the actual leanest way to do this reading words twice (once in the array and once on the Dictionary);
public static void PrintArrayCounts(string[] A, bool printOnlyDupes)
{
var words = Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); // Either this or making to Lower every word
foreach(string a in A)
{
if(!words.ContainsKey(a))
{
words.Add(a, 1);
}
else
{
words[a]++;
}
}
StringBuilder sb = new StringBuilder();
foreach(KeyValuePair<string, int> word in words)
{
if(d.Value > 1 || !printOnlyDupes)
{
sb.Append(d.Key);
sb.Append("--");
sb.Append.(d.Value));
}
}
Console.WriteLine(sb.ToString());
}
/**
* @param args
*/
public static String countElement(String input[]) {
String output = "";
Set<String> inputSet = new HashSet<String>();
for (int i = 0; i < input.length; i++) {
inputSet.add(input[i]);
}
for (String setValue : inputSet) {
int count = 0;
for (int i = 0; i < input.length; i++) {
if (setValue.equalsIgnoreCase(input[i])) {
count++;
}
}
if(!output.contains(setValue.toUpperCase() + "-" + count + ";")){
output += setValue.toUpperCase() + "-" + count + ";";
}
}
return output;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String input[] = { "Good", "Word", "good", "WoRD", "GoOD" };
String output = countElement(input);
System.out.println(output);
}
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
List<String> strings = new ArrayList<>();
Map<String, Integer> data = new TreeMap<>((s1, s2) -> s1.compareToIgnoreCase(s2));
strings.add("Good");
strings.add("word");
strings.add("good");
strings.add("woRd");
strings.forEach(s -> {
if (data.containsKey(s)) {
data.put(s, data.get(s) + 1);
} else {
data.put(s, 1);
}
});
data.forEach((k, v) -> System.out.println(k + "=" + v));
}
}
def wordCount(list1):
for x in range(0,len(list1)):
list1[x] = list1[x].upper()
dict1 = {}
for x in range(0,len(list1)):
if list1[x] in dict1:
dict1[list1[x]].append(x)
else:
dict1[list1[x]] = [x]
for key in dict1:
print key.capitalize(), " - " , len(dict1[key])
how about this? Might be a little big on space complexity but works.
public class ArrayProgram {
private static HashMap<String, Integer> map = new HashMap<String,Integer>();
private static String [] array = {"Good","Word","good","woRd","anil","radha"};
public static void main(String[] args) {
for(String str : array){
if(map.containsKey(str.toLowerCase())){
int total = map.get(str.toLowerCase());
map.put(str.toLowerCase(), ++total);
}else{
map.put(str.toLowerCase(), 1);
}
}
}
void printArray(){
Set<String> set = map.keySet();
for(String s : set){
System.out.println("key "+s+" is present "+map.get(s.toLowerCase())+" number of times");
}
}
}
import java.util.*;
public class CountWordsusingMap {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] arr={"good","word","tito","english","GOOD","Word","WORD","good","english","hindi",
"rahul","rahul","english","RAhul"};
HashMap<String,Integer> map=new HashMap<String,Integer>();
for(String str:arr)
{
String key=str;
key=key.toLowerCase();
if(map.containsKey(key))
{
map.put(key, map.get(key)+1);
}
else
{
map.put(key, 1);
}
}
Set<String> Keys=map.keySet();
Iterator<String> it=Keys.iterator();
while(it.hasNext())
{
String value=it.next();
System.out.println(value +"---" +map.get(value));
}
}
}
public void countWOrd(String[] str){
try{
HashMap<String,Integer> map = new HashMap<String,Integer>();
for(int i = 0;i<str.length;i++){
int ch = 0;
StringBuilder sb = new StringBuilder();
int count = 1;
for(int j = 0;j<str[i].length();j++){
ch = str[i].charAt(j);
if(ch >=65 && ch<=90){
ch = ch+32;
}
sb = sb.append((char)ch);
}
if(map.containsKey(sb.toString())){
count++;
}
map.put(sb.toString(), count);
}
for(Map.Entry m : map.entrySet()){
System.out.println(m.getKey()+" > "+m.getValue());
}
}catch(Exception ex){
ex.printStackTrace();
}
}
public void countWOrd(String[] str){
try{
HashMap<String,Integer> map = new HashMap<String,Integer>();
for(int i = 0;i<str.length;i++){
int ch = 0;
StringBuilder sb = new StringBuilder();
int count = 1;
for(int j = 0;j<str[i].length();j++){
ch = str[i].charAt(j);
if(ch >=65 && ch<=90){
ch = ch+32;
}
sb = sb.append((char)ch);
}
if(map.containsKey(sb.toString())){
count++;
}
map.put(sb.toString(), count);
}
for(Map.Entry m : map.entrySet()){
System.out.println(m.getKey()+" > "+m.getValue());
}
}catch(Exception ex){
ex.printStackTrace();
}
}
string s[]={"Good","Word","good","woRd"};
map<string,int>mp;
int l=((sizeof s)/(sizeof s[0]));
for(int i=0;i<l;i++){
string x=s[i];
transform(x.begin(),x.end(),x.begin(),::tolower);
mp[x]++;
}
string tofind="Good";
string keeporigional=tofind;
transform(tofind.begin(),tofind.end(),tofind.begin(),::tolower);
cout<<keeporigional<<"->"<<mp.find(tofind)->second;
import java.util.HashMap;
import java.util.Map;
public class CountWords {
public static void main(String[] args) {
String arr[] = {"Good","woRD","good","GOod","test","word"};
countWords(arr);
}
public static void countWords(String arr[]){
Map<String, Integer> map = new HashMap<String, Integer>();
String temp = null;
for (int i = 0; i < arr.length; i++) {
temp = arr[i];
temp = temp.toLowerCase();
if(map.get(temp) != null ){
Integer count = map.get(temp);
map.put(temp, ++count);
}else{
map.put(temp, 1);
}
}
System.out.print(map);
}
}
Use a hash table.
-key word in lower case.
-value its frequency.
--Increase the value when the word is already there in hash otherwise just put it in hash table.
Here is the code.
import java.util.Enumeration;
import java.util.Hashtable;
public class FrequencyWords {
public static void main(String[] args) {
String[] arr = {"Good", "bad", "good", "word", "woRd"};
countFrequency(arr);
}
public static void countFrequency(String[] arr){
Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
for(int i=0;i<arr.length;i++){
if(ht.get(arr[i].toLowerCase())==null){
ht.put(arr[i].toLowerCase(), 1);
}else{
ht.put(arr[i].toLowerCase(), ht.get(arr[i].toLowerCase()) + 1);
}
}
Enumeration<String> enumKey = ht.keys();
while(enumKey.hasMoreElements()){
String str = enumKey.nextElement();
Integer value = ht.get(str);
System.out.println(str + " -- "+ value);
}
}
}
Using a Hashmap, and Arrays.asList(map) to easily iterate over the hashmap:
package goldmansachs;
import java.util.Arrays;
import java.util.HashMap;
public class countDuplicates {
public static void main(String args[]){
String arr[] = {"Good","Word","GOod","wOrd","Giant","nerd","NErd"};
countDupes(arr);
}
public static void countDupes(String arr[]){
HashMap<String,Integer> map = new HashMap<String,Integer>();
int l = arr.length;
for(int i=0;i<l;i++){
String a = arr[i].toLowerCase();
if(map.containsKey(a)) //if true
{
int freq = map.get(a);
freq = freq+1;
map.put(a,freq);
}
else{
map.put(a,1);
}
}
//iterate through hashmap using an iterator
System.out.println(Arrays.asList(map));
}
}
public class ArrayProblem1 {
public static Map<String,Integer> countString(String stringArray[]){
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
for(String str: stringArray){
if(hashMap.containsKey(str.toLowerCase())){
hashMap.put(str.toLowerCase(), 1+hashMap.get(str.toLowerCase()));
}else{
hashMap.put(str.toLowerCase(), 1);
}
}
return hashMap;
}
public static void print(Map<String, Integer> map){
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey()+" : "+entry.getValue());
}
}
public static void main(String[] args) {
String stringArray[] = {"Good","word","good","woRd"};
Map<String,Integer> map = countString(stringArray);
print(map);
}
}
public class ArrayProblem1 {
public static Map<String,Integer> countString(String stringArray[]){
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
for(String str: stringArray){
if(hashMap.containsKey(str.toLowerCase())){
hashMap.put(str.toLowerCase(), 1+hashMap.get(str.toLowerCase()));
}else{
hashMap.put(str.toLowerCase(), 1);
}
}
return hashMap;
}
public static void print(Map<String, Integer> map){
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey()+" : "+entry.getValue());
}
}
public static void main(String[] args) {
String stringArray[] = {"Good","word","good","woRd"};
Map<String,Integer> map = countString(stringArray);
print(map);
}
}
#include <iostream>
#include <unordered_map>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
string to_lower(string str) {
string result;
for(char c : str) {
result += tolower(c);
}
return result;
}
int main(){
vector<string> words{"Good", "GOOD", "HeLLo", "iftheN", "IFTHEN", "hi"};
unordered_map<string, int> mp;
for(string s : words) {
s = to_lower(s);
if(mp.find(s) == mp.end()) {
mp[s] = 1;
} else {
++mp[s];
}
}
for(auto i : mp) {
cout << i.first << " - " << i.second << endl;
}
return 0;
}
#include <iostream>
#include <unordered_map>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
string to_lower(string str) {
string result;
for(char c : str) {
result += tolower(c);
}
return result;
}
int main(){
vector<string> words{"Good", "GOOD", "HeLLo", "iftheN", "IFTHEN", "hi"};
unordered_map<string, int> mp;
for(string s : words) {
s = to_lower(s);
if(mp.find(s) == mp.end()) {
mp[s] = 1;
} else {
++mp[s];
}
}
for(auto i : mp) {
cout << i.first << " - " << i.second << endl;
}
return 0;
}
Are these your homeworks?
Build a symbol table, use lowercase string as a KEY, store a number of occurences of this string in VALUE. At query time, given a string s, convert it to a lower case, if KEY=s is in a table return corresponding VALUE, null otherwise.
The complexity of constructing a symbol table either O(N) or O(N log N) depending on implementation. Query time will be amortized O(1). A cample code is shown below:
public class Finder {
private Map<String, Integer> st;
public Finder (String[] words) {
st = new HashMap<String, Integer>();
for (String key : words) {
key = key.lowercase();
if (st.containsKey(key))
st.put(key, st.get(key)+1);
else
st.put(key, 1);
}
}
public int count(String s) {
String key = s.lowercase();
retun st.containsKey(key)?st.get(key):0;
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void printRepeatedWord(String[] a)
{
int count=1;
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[i].equalsIgnoreCase(a[j].toLowerCase()))
{
count++;
}
}
System.out.print(" "+a[i]+"-"+count);
count =1;
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
String a[] ={"Good","word","good","woRd"};
printRepeatedWord(a);
}
}
O(N^2)? If I understand the task the goal is given a word return the number of occurrences of this word in the String[] a, case insensitive.
Change the string to lower case using toLowerCase() method before you compare,then count the occurrence.
- Mohan K January 10, 2015