Linkedin Interview Question
Country: United States
Interview Type: Phone Interview
Good catching on the corner case where we should consider only the unique elements in each string for the count array.
In the last for loop the condition should be
charCounts[i] == inputs.length
not
charCounts[i] == inputs.length()
similar
package com.cnu.ds.strings;
public class CommonCharacters {
static public void commonCharracters(String[] strings) {
int[] alphabets = new int[26];
for (String string : strings) {
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (!string.substring(0, i).contains(c + "")) {
alphabets[c - 97]++;
}
}
}
for (int i = 0; i < alphabets.length; i++) {
if (alphabets[i] == strings.length) {
System.out.println((char) (i + 97));
}
}
}
public static void main(String[] args) {
String[] strings = { "aghkafgklt", "dfghako", "qwemnaarkf" };
commonCharracters(strings);
}
}
Isn't this just much simpler??
public static int countBitsSet(int num) {
int c = 0;
for (; num != 0; ++c) {
num &= (num - 1);
}
return c;
}
public static int findNumCommonChars(final String[] strs) {
int[] presence = new int[26];
int numStrings = strs.length;
for (int j = 0; j < numStrings; ++j) {
String str = strs[j];
for (int i = 0; i < str.length(); ++i) {
int c = str.charAt(i) - 97; // Lowercase
if (c < 0 || c >= 26) {
// throw exception
}
presence[c] = presence[c] | (1 << j);
}
}
int count = 0;
for (int i = 0; i < presence.length; ++i) {
if (countBitsSet(presence[i]) == numStrings) {
++count;
}
}
return count;
}
I usually like to reduce the nesting depth of my solution, at least after I am done coding. if-statements checking corner and error cases are predestined for that. In particular, the first if-statement ends on a return statement, so one could remove the else-branch and reduce the indentation depth of the main code by one. I think it would make it more readable.
BTW, why are you counting the occurrences of characters? Don't we only want to know if they are present or not? Shouldn't simple flags suffice? Even if there are no storage benefits in the particular language, would it not make it more comprehensible by mapping these concepts to a semantically closer entity?
@JustStudying
Nice idea to use bitset, but it does't work if there are more than 32 input strings.
public static void findCommonCharacters(List<String> strings)
{
int[] chars = new int[26];
for ( String str : strings )
{
int[] stringcharacters = new int[26];
for ( int i = 0; i < str.length(); i++ )
{
char c = str.charAt(i);
stringcharacters[c - 'a']++;
}
for ( int i = 0; i < 26; i++ )
{
if ( stringcharacters[i] > 0 )
chars[i]++;
}
}
for ( int i = 0; i < 26; i++ )
{
if ( chars[i] == strings.size() )
System.out.println((char) ('a' + i));
}
}
C solution using array.
void commonCharacters(char* str1, char* str2, char* str3)
{
int i=0;
int array[26]={0};
while(*str1!='\0')
{
if(array[*str1-97]==0)
array[*str1-97]=1;
str1++;
}
while(*str2!='\0')
{
if(array[*str2-97]==1)
array[*str2-97]=2;
str2++;
}
while(*str3!='\0')
{
if(array[*str3-97]==2)
array[*str3-97]=3;
str3++;
}
for(i=0;i<26;i++)
{
if(array[i]==3)
printf("%c\n",i+97);
}
}
Time complexity : Theta(nm) where n is number of strings and m is average length of strings.
package com.google.practice;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class CommonChars {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> arr = new ArrayList<String>();
arr.add("aghkafgklt");
arr.add("dfghako");
arr.add("qwemnaarkf");
findCommon(arr);
}
public static void findCommon(List<String> arr){
Set<Character> tmp1 = new TreeSet<Character>();
Set<Character> tmp2 = new TreeSet<Character>();
//Place all chars from first string in tmp1
for(char c:arr.get(0).toCharArray())
tmp1.add(c);
//Parse through all the strings.
for(String s:arr){
for(char c:s.toCharArray()){
if(tmp1.contains(c))
tmp2.add(c);
}
tmp1.clear();
tmp1.addAll(tmp2);
tmp2.clear();
}
System.out.println(tmp1.size()+" : "+tmp1);
}
}
This program works for all the cases and TC is O(N) and SC = N
Input:
aaab
ab
b
O/P: 1
VisitedArray is used to identify only the unique elements in each string.
#include<iostream>
using namespace std;
// Function to find the common characters
int CommonCount( char input[100][100], int m)
{
//Count Array to track the count of each characters
// a to z only has 26 characters
int charcount[26];
bool visited[26];
for(int k =0;k<26;k++)
{
charcount[k] = 0;
visited[k] = false;
}
//set Variables
int count = 0, i = 0, j = 0, index = 0, avalue = 'a';
while(i<m)
{
while(input[i][j] != '\0')
{
index = input[i][j];
index = index%avalue;
if(visited[index] == false)
{
charcount[index] ++;
visited[index] = true;
}
j++;
}
for(int k=0;k<26;k++) visited[k] = false;
i++;
j=0;
}
//Count the common characters
for(int k=0;k<26;k++)
{
if(charcount[k] == m) count++;
}
return count;
}
int main()
{
char input[100][100] = {"aaab","ab","b"};
cout<<CommonCount(input, 3);
return 0;
}
public static List<Character> getChars(String[] strs) {
byte[] charsCountArray = new byte[26];
byte index = 0;
List<Character> returnList = new ArrayList<Character>();
if (strs == null || strs.length == 0)
return null;
for (String string : strs) {
index++;
for (char ch : string.toCharArray()) {
int i = ch - 97;
if (charsCountArray[i] == index - 1)
charsCountArray[i] = index;
}
}
for (byte i = 0; i < charsCountArray.length; i++) {
if (charsCountArray[i] == index) {
returnList.add((char) (i + 97));
}
}
return returnList;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CharacterCounter {
public static void main(String[] args) {
String[] strArray = new String[]{"abcwwede","urturutuyuybdfhjsaha","hgafhwewewgd","dhjhawewejhf","jfhdaewewjjdf","dfjdhwewajfh","abgewedfg"};
char[] ch = getCommonCharacters(strArray);
System.out.println("common chracter are");
for(char c : ch){
System.out.println(c);
}
}
private static char[] getCommonCharacters(String[] strArray) {
Map<Character,Integer[]> outputMap = new HashMap<Character,Integer[]>();
List<Character> li = new ArrayList<Character>();
for(int i=0;i<strArray.length;i++){
String str = strArray[i];
char[] chA = str.toCharArray();
List<Character> list = new ArrayList<Character>();
for(char ch : chA){
if(list.contains(ch))
continue;
list.add(ch);
if(outputMap.get(ch) == null){
Integer[] intAr = new Integer[strArray.length];
for(int r =0;r<intAr.length;r++){
intAr[r] = -1;
}
intAr[0] = i;
outputMap.put(ch, intAr);
}
else{
Integer[] objArr = outputMap.get(ch);
objArr[i] = i;
}
}
}
for(Map.Entry<Character, Integer[]> entry: outputMap.entrySet()){
boolean isCommon = true;
for(Integer integer : entry.getValue()){
if(integer.intValue() ==-1){
isCommon = false;
break;
}
}
if(isCommon){
li.add(entry.getKey());
}
}
char[] ch = new char[li.size()];
int w=0;
for(Character c : li){
ch[w] = li.get(w++);
}
return ch;
}
}
Code in C
Goes once on all of the strings and at the end goes once on the array of common characters
void FindCommonCharactersNum(char *str_list[],int strings_num)
{
int CharAppear[26] = { 0 };
int i , j , pos, count;
char *c_ptr;
//there is no strings in the list
if (strings_num == 0)
{
printf("Strings number should be at least 1");
return;
}
//go through all the strings
for (i = 0; i < strings_num; i++)
{
//point to first character of the current string
c_ptr = &str_list[i][0];
while (*c_ptr != '\0')
{
pos = *c_ptr - 'a';
//if previous string had a character *c_ptr, put index of current string
//to notify that current string has same character as well
if (CharAppear[pos] == i)
{
CharAppear[pos] = i + 1;
}
c_ptr++;
}
}
count = 0;
//find number of i's in the array - number of characters which were
//marked by the last tested string as characters which appeared in last
//before one string
printf("Common characters (if any):\n");
for (j = 0; j < 26; j++)
{
if (CharAppear[j] == i)
{
printf("%c ", j + 'a');
count++;
}
}
printf("\n");
printf("Number of common characters is %d\n", count);
}
string[] str = { "aghkafgklt", "dfghako", "qwemnaarkf" };
var v=str.OrderByDescending(item => item.Length);
str = v.ToArray();
int totals = str.Length;
char ch;
bool flag = false;
int k,j;
int cnt=0;
for(int i=0;i<str[0].Length;i++)
{
ch = str[0].ElementAt(i);
flag = false;
for(j=1;j<str.Length;j++)
{
for(k=0;k<str[j].Length;k++)
{
if(str[j][k]==ch)
{
flag = true;
for(int x=k;x<str[j].Length;x++)
{
if (str[j][x] == ch)
{
str[j] = str[j].Remove(x, 1);
x--;
}
}
break;
}
}
if (k >= str[j].Length)
{
if (!flag)
{
flag = false;
break;
}
}
}
if (flag && j>=str.Length) cnt++;
}
Console.WriteLine(cnt);
}
package com.sunil.carrercup;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class TelephoneDirectory {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Map<String,ArrayList> map=new HashMap<String, ArrayList>();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Set<String> map_key;
ArrayList<String> tel_no = null;
String phone_no;
boolean repeat;
System.out.println("Enter 3 employee phone number information");
for(int i=0;i<5;i++)
{
repeat=false;
System.out.println("Enter :"+(i+1)+"Employee Information:");
System.out.println("****************************************************");
System.out.println("Enter Name:");
String name=br.readLine();
System.out.println("Enter the Telphone no:");
phone_no=br.readLine();
map_key=map.keySet();
for(String s:map_key)
{
if(s.equals(name))
{
tel_no=map.get(s);
tel_no.add(phone_no);
repeat=true;
}
}
if(!repeat)
{
tel_no=new ArrayList<String>();
tel_no.add(phone_no);
}
map.put(name, tel_no);
}
//for retrieving information
System.out.println("Enter the name of employee for phone no:");
String name1=br.readLine();
List<String> detail_phone=map.get(name1);
for(String p:detail_phone)
System.out.println("Phone no:"+p);
// ArrayList<String> telephone_no=new ArrayList<String>();
// telephone_no.add("8431079337");
// map.put("sunil", telephone_no);
System.out.println("map"+map);
//System.out.println("Keys are:"+map_key);
//for(String st:map_key)
//System.out.println(map.get(st));
}
}
Not too hard. Using Python and simple set intersection, we arrive at the optimal O(k) answer where k is the total length of all of the strings.
from sets import Set
def getCommonCharCount(arr):
s = Set(arr[0])
for str in arr:
s = s & Set(str)
return len(s)
print getCommonCharCount(['aghkafgklt', 'dfghako', 'qwemnaarkf']) #outputs 3
I think the interview question is asking for an implementation of intersection function.
Here's another C++ solution using a map for storing the chars.
#include<iostream>
#include<map>
using namespace std;
int findCommonChars(char *strings[], int numStrings){
int i,j;
map<int, int> myMap;
// fill the map with the chars from the first string
for(i=0; i<strlen(strings[0]); ++i){
myMap[strings[0][i]] = 1;
}
// increment the value in the map if any
for(i=1; i<numStrings; ++i){
for(j=0; j<strlen(strings[i]); ++j){
if (myMap.count(strings[i][j]) == 1){
myMap[strings[i][j]] = myMap[strings[i][j]] + 1;
}
}
}
int totalChars = 0;
map<int, int>::iterator it;
// print the elements in the map that have a count equal to the number of strings
for(it = myMap.begin(); it != myMap.end(); ++it){
if (it->second == numStrings){
++totalChars;
}
}
return totalChars;
}
If there are some details about the alphabet used (e.g. english low case, genome alphabet, any special alphabet), the following solution may be used.
For each word calculate a bitstring of size = length of the alphabet, where 1 is set if character is presented in the word.
Then multiple all and return number of 1 bits.
Time: O(n)
Size: O(1)
public int getNumberOfCommon(String[] strings)
{
int res = Integer.MAX_VALUE;
for(String str: strings)
{
int bitstring = 0;
for (int i = 0; i < str.length(); i++)
{
bitstring |= 1 << getPosition(str.charAt(i));
}
res &= bitstring;
}
return Integer.bitCount(res);
}
// calculate position in your alphabet
private int getPosition(char c)
{
return c - 'a';
}
The following algorithm works on general cases for any number of strings in any character. Time complexity is O(n) where n is the total number of characters in all strings. Space complexity is O(max(strlen)) in worse case, where strlen is the length of a given string.
Use two hash sets, the first hash set records all known common characters for strings 0..i-1, the second hash set scans string i and compare against the first hash set to further shorten the set of known common characters. When done, shift the second set to be the first and clear the second set for next string.
Below is the implementation in scala
package CareerCup
import scala.collection.mutable._
object CommonChar extends App {
val strArray = Seq("aghkafgklt","dfghako","qwemnaarkf")
//val strArray = Seq("abcwwede","urturutuyuybdfhjsaha","hgafhwewewgd","dhjhawewejhf","jfhdaewewjjdf","dfjdhwewajfh")//,"abgewedfg")
def countCommon = {
require(strArray.length>1)
var baseSet = Set.empty[Char]++strArray(0)
var shortSet = Set.empty[Char]
for (i<-1 until strArray.length) {
println(baseSet)
shortSet++=strArray(i).filter(baseSet.contains)
baseSet.clear
baseSet++=shortSet
shortSet.clear
}
println(baseSet, baseSet.size)
}
countCommon
}
Same implementation in java
package JCareerCup;
import java.util.HashSet;
import java.util.Iterator;
public class CommonChar {
public static void main(String[] args) {
String[] strArray = new String[] {"aghkafgklt","dfghako","qwemnaarkf"};
HashSet<Character>[] sets = new HashSet[]{
new HashSet<Character>(), new HashSet<Character>()
};
int k=0;
String str = strArray[k];
HashSet<Character> baseSet=sets[0], shortSet=sets[1];
for(int i=0; i<str.length(); i++) baseSet.add(str.charAt(i));
for (k=1; k<strArray.length; k++) {
baseSet = sets[(k+1)%2]; //shift base and short sets
shortSet = sets[k%2];
shortSet.clear();
str = strArray[k];
for (int i=0; i<str.length(); i++) {
char c = str.charAt(i);
if (baseSet.contains(c)) shortSet.add(c);
}
}
baseSet = sets[(k+1)%2]; //final shift to obtain result
Iterator<Character> it = baseSet.iterator();
while(it.hasNext()) System.out.printf("%c,", it.next());
System.out.println(baseSet.size());
}
}
So ... from my experience interviewers will probably acknowledge the following positively, but then proceed to pester you with requests to break it down. However, I usually like to start on any problem with a solution that most clearly reflects the general idea of the approach to solve it.
In the case of this question, one may almost immediately be reminded of having to find the intersection of multiple sets, with each string representing a set of characters, since the order of the characters does not appear to impact the solution. Abstractly speaking, you are asked to find the union
S_u = Union{from i=0 to n} s_i, where s in S and S is a set of a set of characters
How does one most directly express that idea? One approach, in C#, may be the following:
var strings = new[] { "aghkafgklt", "dfghako", "qwemnaarkf" };
HashSet<char> set = new HashSet<char>(strings[0].ToCharArray());
for (int i = 0; i < strings.Length; i++)
set.IntersectWith(new HashSet<char>(strings[i]));
Most modern programming languages, or rather their supporting libraries, have some sort of set containers.
Okay, I know what you are going to say ... that's not the point of the interview! But I think it is good to mention the most obvious solution at least, because - let's face it - in the end that is how most of us would end up solving these kinds of problems in production code, unless the constraints of the context do not further constrain it.
I have sat on both sides of the table during interviews and I usually give people bonus points for mentioning a solution if there is one that is particularly natural and easy to implement in the environment of the language.
An interviewer may ask you to implement a different solution, not using certain standard containers, but at least you already have one working solution in and you can start from that solution.
If the real point of the question is to ascertain whether you know how to efficiently implement an intersection, at least you have communicated to your interviewer that you realize why the intersect operation is relevant and how it would lead to a solution on a high level. You can then proceed to implement that and have delivered not one, but two good solutions for the problem IMHO.
Have a single hashtable.
First run on first string should give unique set of keys (characters) - assign them 1 for their value.
Each subsequent run on characters for a string (index i - one based index) updates the hashvalue to be i - if and only if it finds the value to be i-1.
This way by the time we finish with string N - the keys (characters) that have the value N - are the ones that are there in all the strings.
Just give that count of keys for whom the value is N.
uint CountCommonChars (string[] strArr)
{
char[] charArr = NULL;
uint commonCharCount = 0;
uint numStrings = 0;
Hashtable<char,uint> htable = NULL;
// validate strArr
numStrings = strArr.Length;
// Initialize htable with the first string.
chArr = strArr[0].ToCharArray();
foreach(char c in chArr)
{
if(!htable.Contains(c))
{
htable[c] = 1;
}
}
numStrings = 1;
// For the rest of the strings update hashtable only if the character
// is already in all previous strings.
foreach(string str in strArr)
{
chArr = str.ToCharArray();
foreach (char c in chArr)
{
if(htable.Contains(c) && htable[c] == numStrings)
{
htable[c] = numStrings+1;
}
}
numStrings++;
}
// Evaluate
foreach(char c in htable.Keys())
{
if(htable[c] == numStrings)
{
commonCharCount++;
}
}
return commonCharCount;
}
int count_common_chars(string s[], const int N) {
uint exists = 0, isCommon = ~0;
for (int i = 0; i < N; ++i) {
for (uint j = 0; j < s[i].size(); ++j)
exists |= 1 << (s[i][j] - 'a');
isCommon &= exists;
exists = 0;
}
return get_hamming_weight(isCommon);
}
int get_hamming_weight(uint n) {
int weight = 0;
for (; n > 0; ++weight)
n &= n - 1;
return weight;
}
Assuming your alphabet is a-z.
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string s;
int l,t;
cin>>t;
int count =0;
int a[300]={0};
cin>>s;
string c=s;
int k= l=s.length();
for(int i=0;i<l;i++)
if(a[s[i]]==0)
a[s[i]]++;
for(int i=2;i<=t;i++)
{
cin>>s;
l=s.length();
for(int j=0;j<l;j++)
{
if(a[s[j]]==i-1)
a[s[j]]++;
}
}
for(int i=0;i<k;i++)
if(a[c[i]]==t)
count++;
cout<<count<<endl;
}
Assuming only lowercase letters, you could easily fit unique characters as a bitset within an integer. Once you've set the bitsets for each string, you can just '&' them to get the intersection of characters.
public static int getCommonCharCount(String[] inputs) {
if(inputs == null || inputs.length == 0) return 0;
//assuming Lowercase Ascii only(26 bits)
int[] charset = new int[inputs.length];
for(int i = 0; i < charset.length; i++) {
charset[i] = 0;
}
int i = 0;
for(String input : inputs) {
if(input == null || input.isEmpty()) return 0;
for(char c : input.toCharArray()) {
charset[i] |= (1 << (c - 'a'));
}
i++;
}
int intersection = Integer.MAX_VALUE;
for(int item : charset) {
intersection &= item;
}
int count = 0;
for(int j = 0; j < 26; j++) {
if((intersection & (1 << j)) != 0) {
count++;
}
}
return count;
}
private static Set<Character> uniqueCharacters(String word) {
Set<Character> uniq = new LinkedHashSet<Character>();
for (char c : word.toCharArray())
uniq.add(c);
return uniq;
}
private static Set<Character> getCommonCharacters(String first,
String second) {
Set<Character> uniqInFirst = uniqueCharacters(first);
Set<Character> uniqInSecond = uniqueCharacters(second);
uniqInFirst.retainAll(uniqInSecond);
return uniqInFirst;
}
private static int countCommonCharacters(String[] words) {
Set<Character> uniq = new LinkedHashSet<Character>();
for (int i = 0; i < words.length - 1; i++)
uniq = getCommonCharacters(words[i], words[i + 1]);
return uniq.size();
}
public class CommonChars {
Set<Character> common = new HashSet<Character>();
String[] data;
CommonChars(String[] data){
this.data = data;
for(int i=0;i<data[0].length();i++)
common.add(this.data[0].charAt(i));
}
public int howManyCommonChars(){
int count = 0;
if(data.length < 2)
return common.size();
for(int i=1;i<data.length;i++){
Set<Character> tmp = new HashSet<Character>();
String str = data[i];
for(int j=0;j<str.length();j++){
char ch = str.charAt(j);
if(common.contains(ch))
tmp.add(ch);
if(i>1 && tmp.size()==common.size())
break;
}
if(tmp.size() > 0)
common = tmp;
else
return 0;
}
count = common.size();
return count;
}
public static void main(String[] args){
String[] data = {"afk", "aghkafgklt", "dfghako", "qwemnaarkf" };
CommonChars cc = new CommonChars1(data);
int x = cc.howManyCommonChars();
System.out.println(x);
}
}
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
void displayCommonLetters(std::string* words, int len) {
std::map<char, int> hashMap;
for(int i = 0; i < len; ++i) {
for(int j = 0; j < words[i].size(); ++j)
{
char c = words[i][j];
if(hashMap.find(c) == hashMap.end())
hashMap[c] = 1;
else if(hashMap[c] < i+1)
hashMap[c] += 1;
}
}
std::map<char, int>::const_iterator it = hashMap.begin();
for(;it != hashMap.end(); ++it)
if(it->second == len)
std::cout << it->first;
}
int main(int argc, char *argv[])
{
std::string words[3] = {"aghkafgklt", "dfghako", "qwemnaarkf"};
displayCommonLetters(words, 3);
system("PAUSE");
return EXIT_SUCCESS;
}
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
void displayCommonLetters(std::string* words, int len) {
std::map<char, int> hashMap;
for(int i = 0; i < len; ++i) {
for(int j = 0; j < words[i].size(); ++j)
{
char c = words[i][j];
if(hashMap.find(c) == hashMap.end())
hashMap[c] = 1;
else if(hashMap[c] < i+1)
hashMap[c] += 1;
}
}
std::map<char, int>::const_iterator it = hashMap.begin();
for(;it != hashMap.end(); ++it)
if(it->second == len)
std::cout << it->first;
}
int main(int argc, char *argv[])
{
std::string words[3] = {"aghkafgklt", "dfghako", "qwemnaarkf"};
displayCommonLetters(words, 3);
system("PAUSE");
return EXIT_SUCCESS;
}
O(N)
int CountCommons(const vector<string> &words)
{
int hist_size = 'z'-'a'+1;
vector<int> hist(hist_size, 0);
for (int i=0; i<words.size(); i++)
{
const string &word = words[i];
vector<int> word_hist(hist_size, 0);
for (int j=0; j<word.size(); j++)
word_hist[word[j]-'a']++;
for (int j=0; j<hist_size; j++)
{
if (word_hist[j]>0)
hist[j]++;
}
}
int ret = 0;
for (int i=0; i<hist_size; i++)
{
if (hist[i] == words.size())
ret++;
}
return ret;
}
public int countCommonChars(List<String> strings) {
int[] counts = new int[26];
for (int i = 0; i < strings.size(); i++) {
for (int j = 0; j < strings.get(i).length(); j++) {
if (counts[strings.get(i).charAt(j) - 'a'] < i + 1) {
counts[strings.get(i).charAt(j) - 'a']++;
}
}
}
int count = 0;
for (int i = 0; i < 26; i++) {
if (counts[i] == strings.size()) {
count++;
}
}
return count;
}
How about this :
package interview;
import java.io.*;
import java.lang.*;
import java.util.*;
class Intersection
{
public static void main(String args[])
{
String s1 = "aghkafgklt";
String s2 = "dfghako";
String s3 = "qwemnaarkf";
char[] st1 = s1.toCharArray();
char[] st2 = s2.toCharArray();
char[] st3 = s3.toCharArray();
Set set1 = new HashSet();
for(int i=0;i<s1.length();i++)
set1.add(st1[i]);
Set set2 = new HashSet();
for(int i=0;i<s2.length();i++)
set2.add(st2[i]);
Set set3 = new HashSet();
for(int i=0;i<s3.length();i++)
set3.add(st3[i]);
Set set4 = new HashSet();
set4.addAll(set1);
set4.retainAll(set2);
set4.retainAll(set3);
System.out.println("Common elements across 3 strings : " + set4.size());
}
}
def commonCharacterCounter(l):
n = len(l)
if n == 0 or n == None:
return None
charDict = {}
for i in range(97, 123):
charDict[chr(i)] = False
for s in l:
for c in s:
if charDict.get(c) == None:
continue
if charDict.get(c) == True:
continue
if charDict.get(c) == False:
charDict[c] = True
for k in charDict.keys():
if charDict[k] == False:
del charDict[k]
else:
charDict[k] = False
return len(charDict.keys())
/**
* Idea is to put all the chars from first string in a map with values as
* true. not everytime in the rest of the strings, we can not find a
* character, we set it to false. What we will have in the end is a list of
* common chars (keys) with values true
*
* @param list
* @return
*/
public static int numberOfCommonChars(List<String> list) {
if (list == null || list.size() == 0) {
return 0;
}
if (list.size() == 1) {
return list.get(0).length();
}
Map<Character, Boolean> map = new HashMap<Character, Boolean>();
// This can be further optimized by choosing the shortest string in the
// list
String fStaring = list.get(0);
for (int i = 0; i < fStaring.length(); i++) {
map.put(fStaring.charAt(i), true);
}
for (int i = 1; i < list.size(); i++) {
String s = list.get(i);
for (Map.Entry<Character, Boolean> entry : map.entrySet()) {
if (s.indexOf(entry.getKey()) < 0) {
map.put(entry.getKey(), false);
}
}
}
return Collections.frequency(map.values(), true);
}
I am amazed how the guys commented above let 0(n2) algo for this simple question to be the best and the upgraded version of solution where we can do it is simple 0(n).
Algo :-
Global Variables :
string charString;
int counter=0;
vector<char> commonChar;
for each character "c" in array1
covert it into corresponding string . charString += c;
endofloop;
for each character "c" in array 2
if(charString.contains(c))
commonChar[counter++] = c;
endif if
endof loop//
now for array 3
string array3Stringyfy;
foreach char "c" in array3
array3Stringyfy += c;
endofloop //
for each char "c" in commonChar
if(!array3Stringyfy.contains(c)) // if array3 does NOT contains earlier common character
counter--;
endof if
end of for;
return counter;
Space Constant
Time O(n).
Here is the problem with your solution. Its no different than all the solutions provided before you. Except for your solution works only for 3 strings. If we go by your logic where we are to believe there can only be 3 strings, all the solutions provided above will also have O(n) complexity. Write a nested loop or write a loop n times, both are same but the later is a programmatic catastrophe.
I do understand that for this logic to work it required N inputs but Mr Super Algo.. this is Here for You especially
Write a nested loop or write a loop n times, both are same // COMPILER ERROR .. Do you really mean what you wrote ?? I hope not
Read what follows that statement. I wanted to point out why you think its O(n) and how wrong it is. I hope you got the point.
Thanks for pointing it out. I guess you are genius to point it.
Anyways.. just to suggest from next time. try to maintain the tone as it is an open forum. Also. just to tell U that neither do I mind juniors like U pointing me wrong nor do I agree with whatever you have spoken about .
Calm Down or U will be super great man on the Mission.. :) Chao
- AndyS June 16, 2014