Linkedin Interview Question


Country: United States
Interview Type: Phone Interview




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

public int getNumOfCommonChars(String[] inputs) {
		// Return 0 if null / empty input or only one string is provided
		if(inputs == null || inputs.length < 2) {
			return 0;
		} else {
			//create an int array to hold # times character appears 
			int[] charCounts = new int[256];
			for(String input : inputs) {
				Set<Character> uniqueCharSet = new HashSet<Character>();
				for(int i=0; i < input.length(); i++) {
					char ch = input.charAt(i);
					if (!uniqueCharSet.contains(ch)) {
						uniqueCharSet.add(ch);
						charCounts[(int) ch] += 1;
					}
				}	
			}
		
			int commonCharCount = 0;
			for (int i=0; i < 256; i++) {
				if (charCounts[i] == inputs.length()) {
					commonCharCount++;
				}
			}
			
			return commonCharCount;
		}
	}

- AndyS June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Good catching on the corner case where we should consider only the unique elements in each string for the count array.

- deepak_gta June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srinivas June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- JustStudying June 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ERROR_SUCCESS August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Your Roommate August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JustStudying
Nice idea to use bitset, but it does't work if there are more than 32 input strings.

- Goalchaser December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if we want to count duplicate char as two different characters we will need number of strings * 26 matrix
- First pass fill the matrix Nx26 with each row containing frequency of char for that position
- Next, traverse the matrix and add min in each column and return the addition

- codealtecdown October 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Paras Dattani June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- rishi August 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

complexity id O(n) IN TIME

- rishi September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about C code?

- Jatin Gandhi June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

c or c# is also fine

- satya June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- AlgoAlgae June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Bad Complexity. You can better it by using a count Array.

- deepak_gta June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have to check each character in each string. No matter what technique you apply.

- AlgoAlgae June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- deepak_gta June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sravanakumar[ARICENT] June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kamal Sharma June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dima June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Ashok Gowla June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- sunil s June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Clay Schubiner June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the interview question is asking for an implementation of intersection function.

- sabz July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hired. :)

- Your Boss August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice

- hits January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vera June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- sabz July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sabz July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- The Internet August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Apologies! There is no need for the call to ToCharArray(), because the string class in C# already supports a char enumerator, as evidenced by the call in the for loop.

- The Internet August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is how my manager usually solves these kinds of questions:

static void Manager(Problem intersectProblem)
{
	Employee e = new Employee();
	e.SolveProblemForMe(intersectProblem);
	return; // Usually home by 5PM.
}

- Anonymous August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- elgeish September 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz provide some suggestions to this code

- Anonymous September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Bilbo90 September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ahsrah September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- abj October 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Abj October 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- pavel.kogan January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- l January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vall February 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sauravmaximus October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mailchiranjib January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- hprem991 June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- AlgoAlgae June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hprem991 June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- AlgoAlgae June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hprem991 June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Gentlemen ... I believe we have a case of the Internets here.

- Wouldn't you like to know? August 13, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More