Epic Systems Interview Question for Software Developers


Country: United States
Interview Type: Written Test




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

It's a little confusing what is meant by permutations in this sense. Normally permutations refers to any re-ordering of an entire set, so permutations for 1234 would be 1243, 1423, 1432, etc.

Combinations, on the other hand, refer to selections from a set where order is disregarded. This is more along the lines of what the question seems to refer to, but all combinations would include subsets of just a single digit, which it seems we are excluding.

1. Compute all combinations (of size > 1) of the number's digits
2. For each combination, compute the product of the digits it contains.
3. Hash that product to a hash table, on a collision with a hash table item with the same product return false.
4. Return true if/when the for loop completes

def getCombinationsOfSizeGreaterThanOne(aNumber):
    if len(aNumber) == 2:
	return [[aNumber[0], aNumber[1]]
    currentCombos = getCombinationsOfSizeGreaterThanOne(aNumber[1:])
    newCombos = []
    for combo in currentCombos:
        newCombos.append(aNumber[0] + currentCombo)
    return newCombos + currentCombos

def isColorful(aNumber):
    combos = getCombinationsOfSizeGreaterThanOne(aNumber)
    comboProducts = {}
    for combo in combos:
	product = 1
        for digit in combo:
            product *= digit
        if comboProducts.contains(product):
	    return False
    return True

I'm not sure there's a more efficient way, because we have to consider all valid combinations.

- acannon828 February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tried the same approach. But this code finds all possible combinations.
Means for number 1234, combination 123 and combination 321 are treated as different. But product of their digits will be same.
So with this code, I think number can never be colorful.

- chetan February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will it work with 2,2,4,4.

2*2*4 = 16
4*4 = 16

- tihor February 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No 2244 is also not colorful. Repeating digits.

- chetan February 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about [3,4] and [1,3,4]? Does 1234 is a perfect colorful number?

- ico0018 July 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) If length of number <= 2 => colorful
2) If all digits are same => not colorful
3) If there are at least two different digits and at least on digit appears more than once => not colorful
4) otherwise we have the following situation. We have set of digits where at least 2 different digits and all digits appear only once or does not appear at all, which means that number of digits in this set < 10. Now lets try all possible combinations (2 ^ 10 with max product < 400000) and save product in set, if we meet some product twice => not colorful, otherwise colorful.
the code below illustrates the idea

char []a = next().toCharArray();
        int n = a.length;
        if (n <= 2) {
            System.out.println("colorful");
            return;
        }
        int []c = new int[10];
        for(int i = 0; i < n; ++i) c[a[i] - '0']++;
        int size = 0;
        boolean hasMoreThanOne = false;
        for(int i = 0; i < 10; ++i) {
            if (c[i] > 0) ++size;
            if (c[i] > 1) hasMoreThanOne = true;
        }
        
        if (size == 1) {
            System.out.println("not colorful");
            return;
        }
        if (hasMoreThanOne) {
            System.out.println("not colorful");
            return;
        }
        int []set = new int[400000];
        for(int mask = 0; mask < (1<<n); ++mask) {
            if (Integer.bitCount(mask) <= 1) continue;
            int prod = 1;
            for(int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) > 0) {
                    prod *= (a[i] - '0');
                }
            }
            if (set[prod] > 0) {
                System.out.println("not colorful");
                return;
            }
            ++set[prod];
        }
        System.out.println("colorful");

- Darkhan.Imangaliev February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in C++. It's pretty much the same algorithm as posted by the other people.

#include <vector>
#include <string>
#include <iostream>
#include <set>

typedef std::vector<int> IntVector;
typedef std::vector<IntVector> IntVecVector;

IntVecVector powerset(const IntVector &V)
{
	IntVecVector S;
	int i;
	
	S.push_back(IntVector());

	for (i = 0; i < V.size(); ++i) {
		IntVecVector s = S;
		int j, n = s.size();
		for (j = 0; j < n; ++j) {
			s[j].push_back(V[i]);
		}
		S.insert(S.end(), s.begin(), s.end());
	}

	return S;
}

bool colorful(const IntVecVector &S)
{
	std::set<int> mults;
	int i;

	for (i = 0; i < S.size(); ++i) {
		int j, n = S[i].size();
		int m = 1;
		for (j = 0; j < n; ++j) {
			m *= S[i][j];
		}

		std::pair<std::set<int>::iterator, bool> x = mults.insert(m);
		if (x.second == false) return false;
	}

	return true;
}

int main(int argc, char *argv[])
{
	std::string word = argv[1];
	int i, n = word.length();

	IntVector V;
	V.reserve(n);

	for (i = 0; i < n; ++i) {
		int d = (int)(word[i] - '0');
		V.push_back(d);
	}

	const IntVecVector S = powerset(V);

	bool r = colorful(S);

	if (r) {
		std::cout << "Colorful\n";
	}
	else {
		std::cout << "Not colorful\n";
	}

	return 0;
}

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

I think it can be solved without finding permutation or combination

For example 1234, In this example all the digits are prime number and non repeating, and hence it will be a perfect color.

Another example : 6392.
In the above example all numbers are unique but not prime.
So we will try to find the prime factor of all the number , if the prime factors are repeated with any of the existing digits, it means its not perfect color. Like in the above example
3*3
3*2
3,
2 Prime factors are common and hence it cannot be perfect color.

- Satynendra February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Prime factors will always be same. I am not sure I quite got your solution. Suppose I try for number 9234.
Prime factors are
3 * 3
2
3
2 * 2
But its still colorful number.
Possible combinations are {92, 93, 94, 23, 24, 34, 923, 924, 934, 234}
None of the combination pair having same product.

- chetan February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If all the digits are unique, its colorful, other wise its not

public static void colorfull(int num)
        {
            ArrayList list = new ArrayList();
            ArrayList tempList = new ArrayList();
            ArrayList multiplication = new ArrayList();
            string tempString = num.ToString();

            if (tempString.Length < 3)
            {
                Console.WriteLine("Number is less than three digits");
                return;
            }

            for (int i = 0; i < tempString.Length; i++)
            {
                list.Add(tempString[i]);
            }

            foreach (Char x in list)
            {
                if (!tempList.Contains(x))
                {
                    tempList.Add(x);
                }
            }

            if (tempList.Count == list.Count)
            {
                Console.WriteLine("Colorfull !!! ");
            }
            else
            {
                Console.WriteLine("Not Colorfull !!! ");
            }

        }

- Ajloun February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Take example 6392. All digits are unique, still not colorful.
coz 6*3 = 9*2

- chetan February 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test1 {
	static Hashtable <Integer,Integer> h =new Hashtable<Integer,Integer>();
	public static int contains(String str)
	{
		int sum=1;
		for(int i=0;i<str.length();i++)
			sum*=str.charAt(i)-'0';
		return sum;
	}
	
	public static boolean number(String num,int start,int rem,String str)
	{
		if (rem==0&&h.containsKey(contains(str))) 
			{
			System.out.println(contains(str));
			System.out.println("here");
			return false;
			}
		else if (rem==0&&h.containsKey(contains(str))==false)
			{
			h.put(contains(str), 1);
			System.out.println(str+"      "+contains(str)+"     ");
			return true;
			}
		int i=start;
		for (;i<num.length();i++)
			if (number(num,i+1,rem-1,str+num.charAt(i))==false) break;
		if (i!=num.length()) return false;
		else return true;
	}
	
	public static void main(String[] args) {
		String num = String.valueOf(194);
		boolean sol = true;
		for (int i=2;i<num.length();i++)
			if (number(num,0,i,"")==false)
				{
					
					sol=false;
					break;
				}
		System.out.println(sol);
	}
}

- Venu Madhav Chitta February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test1 {
	static Hashtable <Integer,Integer> h =new Hashtable<Integer,Integer>();
	public static int contains(String str)
	{
		int sum=1;
		for(int i=0;i<str.length();i++)
			sum*=str.charAt(i)-'0';
		return sum;
	}
	
	public static boolean number(String num,int start,int rem,String str)
	{
		if (rem==0&&h.containsKey(contains(str))) 
			{
			System.out.println(contains(str));
			System.out.println("here");
			return false;
			}
		else if (rem==0&&h.containsKey(contains(str))==false)
			{
			h.put(contains(str), 1);
			System.out.println(str+"      "+contains(str)+"     ");
			return true;
			}
		int i=start;
		for (;i<num.length();i++)
			if (number(num,i+1,rem-1,str+num.charAt(i))==false) break;
		if (i!=num.length()) return false;
		else return true;
	}
	
	public static void main(String[] args) {
		String num = String.valueOf(194);
		boolean sol = true;
		for (int i=2;i<num.length();i++)
			if (number(num,0,i,"")==false)
				{
					
					sol=false;
					break;
				}
		System.out.println(sol);
	}
}

- Venu Madhav Chitta February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simple java solution. I try to find all subsets greater than size 1 and then calculate the product and if it is unique, return true; else false.

import java.util.ArrayList;


public class ColorfulNumber {
	public static boolean checkColorful(int num) {
		String str = String.valueOf(num);
		ArrayList<Integer> array = new ArrayList<Integer>();
		for(int i=0; i<str.length(); i++) {
			int a = str.charAt(i);
			a = a - 48;
			array.add(a);
		}
		ArrayList<Integer> products = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> subsets = getSubsets(array);
		for(ArrayList<Integer> set : subsets) {
			if(set.size() >= 2) {
				int val = 1;
				for(int i=0; i<set.size(); i++) {
					val = val * set.get(i);
				}
				if(!products.contains(val)) {
					products.add(val);
				}
				else {
					return false;
				}
			}
		}
		return true;
	}
	public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> array) {
		ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
		if(array.size() == 0) {
			subsets.add(new ArrayList<Integer>());
		}
		else {
			ArrayList<Integer> array_copy = new ArrayList<Integer>();
			array_copy.addAll(array);
			int first = array_copy.remove(0);
			ArrayList<ArrayList<Integer>> reduced_set = getSubsets(array_copy);
			subsets.addAll(reduced_set);
			reduced_set = getSubsets(array_copy);
			for(ArrayList<Integer> set : reduced_set) {
				set.add(0, first);
			}
			subsets.addAll(reduced_set);
		}
		return subsets;
	}
	public static void main(String args[]) {
		System.out.println(checkColorful(235));
	}
}

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

my simple naive sol

bool isColorful(int num){
	num=abs(num);
	unordered_set<int> checker{};
	while(num!=0){
		int n{num%10};
		if(n==0||n==1) return false;
		if(!checker.insert(num%10).second) return false;
		num/=10;
	}
	vector<vector<int>> vec{};
	unordered_set<int> checker_2(checker);
	auto pos=find_if(checker.cbegin(),checker.cend(),[&](int num){
		bool res{false};
		size_t sz = vec.size();
		for(int i=0;i!=sz;i++){
			vec.push_back(vec[i]);
			vec[i].push_back(num);
			int total= accumulate(vec[i].begin(),vec[i].end(),1,[&](int x,int y){return x*y;});
			res=!checker_2.insert(total).second;
		}
		vec.push_back({num});
		return res;
	});
	if(pos!=checker.end()) return false;
	return true;
}

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

boolean isNoColorful(int n){
int numberOfDigits = 0;
int tempNumber = n;

//First get the number of digits
while(tempNumber>0){
	tempNumber/=10;
	numberOfDigits++;
}

//Make an array of digits
int digits[]=new int[numberOfDigits];
tempNumber=n;
int i=0;
while(tempNumber>0){
	digits[i]=tempNumber%10;
	tempNumber/=10;
	i++;
}

/*Now use bitwise increment to get the combinations of digits.
Eg: If no of digits are 3, increment a counter from 0 to 8 which is nothing but
000,001,010,011,100,101,110,111
Multiply the digits for which the index is set and check if it is unique by using a HashSet.
And voila, you have solved the problem.
*/
int counter=0;
int product=0;
HashSet<Integer> listOfProducts = new HashSet<Integer>();
int powerSetCount = pow(2,numberOfDigits);
for(j=0;j<powerSetCount;j++){
counter++;
	for(k=0;k<numberOfDigits;k++){
		if(counter&(1<<k)){
			product=product*digits[k];
		}
	}
if(!listOfProducts.contains(product)){
	listOfProducts.add(product);
} else {
return false;
}
}
return true;
}

- _memoryleak March 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isNoColorful(int n){
int numberOfDigits = 0;
int tempNumber = n;
while(tempNumber>0){
	tempNumber/=10;
	numberOfDigits++;
}
int digits[]=new int[numberOfDigits];
tempNumber=n;
int i=0;
while(tempNumber>0){
	digits[i]=tempNumber%10;
	tempNumber/=10;
	i++;
}

int counter=0;
int product=0;
HashSet<Integer> listOfProducts = new HashSet<Integer>();
int powerSetCount = pow(2,numberOfDigits);
for(j=0;j<powerSetCount;j++){
counter++;
	for(k=0;k<numberOfDigits;k++){
		if(counter&(1<<k)){
			product=product*digits[k];
		}
	}
if(!listOfProducts.contains(product)){
	listOfProducts.add(product);
} else {
return false;
}
}
return true;
}

- _memoryleak March 03, 2015 | Flag Reply


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