Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

public static boolean isColorful(int number){
		if(number < 10) return true;
		
		String colorString = String.valueOf(number);
		int length = colorString.length();
		
		List<Integer> colorMap = new ArrayList<Integer>();
		
		for(int i =  1; i < length; i++){
			for (int j = 0;  j+i <= length; j++){
				String sub = colorString.substring(j, j+i);
				int product = getProduct(Integer.parseInt(sub));
				if(colorMap.contains(product)) return false;
				else{
					colorMap.add(product);
				}
			}
		}
		return true;
	}

	private static int getProduct(int digits) {
		if(digits < 10) return digits;
		int num = digits;
		int product = 1;
		while(num > 0){
			product = product * (num % 10);
			num = num / 10;
		}
		return product;
	}

- Sathish October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can check for the presence of 0 or 1 in the colorString and return false if they are present. Eg: 206 or 216 are not colorful numbers

- Deepak B October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think without adding the condition for 0 or 1, the above code will produce correct output

- Kunal A November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Wont your code include 36 combination in number 326, which is invalid....

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

Wont your code also consider combination 36 in 326, which is not correct..

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

This is O(n^3). There is a better one with O(n^2) use dynamic programming.

- Yang Zheng July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

There are a few things that would preclude a number being a colorful number:
1. Having duplicate digits and more than 2 digits (if the number were '22', that would okay since 2*2 = 4 but 223 would not be okay since it would have two 2 * 3 computations)
2. the products of all subsets with |n| > 1 must not be duplicated or equal to another digit
3. (implied) 1 and 0 cannot be in the number since due to their properties
4. (implied) since the number is limited to 8 unique digits, full enumeration of all subsequences is teniable (~O(2^8) max subsequences)
5. (implied) all numbers with 2 digits are acceptable as long as they don't contain '0' or '1'

Approach taken is dynamic where:
Acceptable (n) = for all p in prod(n-1), n * p not in prod(n-1)
prod(n) = prod(n-1) + {for all p in prod(n-1), n * p} + n
prod(0) = {}

Runtime is O(n^2) where n is the number of digits in the number.

public static boolean isColorful(int number){
    if(number < 0){
        return IllegalArgumentException();
    }
    //break the number into it's digits
    int[] digits = computeDigits(number);
    //if the number is less than 3 digits, simply check that they are not 1 or 0
    if(digits.length == 0){
        return false;
    }
    if(digits.length == 1){
        return digits[0] != 0 && digits[0] != 1;
    }
    if(digits.length == 2){
        return digits[0] != 0 && digits[0] != 1  && digits[1] != 0 && digits[1] != 1;
    }
    //cache of all previously computed products
    HashSet<Integer> cache = new HashSet<Integer>();
    for(int i = 0; i < digits.length; i++){
        int digit = digits[i];
        // cannot be 0 or 1
        if(digit == 0 || digit == 1){
            return false;
        //not duplicates
        if(cache.contains(digit)){
           return false;
        }
        //check all products with previous contents
        ArrayList<Integer> newProducts = new ArrayList<Integer>(cache.size());
        for(Integer oldProd : cache){
            Integer newProd = oldProd * digit;
            if(cache.contains(newProd)){
                return false;
            }
            newProducts.add(newProd);
        }
        cache.addAll(newProducts);
        cache.add(digit);
    }
    return true;
}

private static int[] computeDigits(int number){
    ArrayList<Integer> digitsList = new ArrayList<Integer>();
    while(number > 0){
        digitsList.add(number % 10);
        number /= 10;
    }
    int[] results = new int[digitsList.size()];
    for(int i = 0; i < results.length; i++){
        results[i] = digitsList.get(i);
    }
    return results;
}

- Zortlord October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

'''
Colorful Number: 
A number can be broken into different sub-sequence parts. Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245. And this number is a colorful number, since product of every digit of a sub-sequence are different. That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40 
But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12. 
You have to write a function that tells if the given number is a colorful number or not.
'''

def colorful(number):
	number_as_list = number_to_int_list(number)
	products = []
	
	for i in range(1, len(number_as_list) + 1):
		# need to take i at a time
		for j in range(0, len(number_as_list)):
			
			if j+i > len(number_as_list):
				break
			
			sub_list = number_as_list[j:j+i]
			product = reduce(lambda x, y: x * y, sub_list)

			if product in products:
				return False
			
			products.append(product)
	
	return True

def number_to_int_list(number):
	number_as_list = []
	while (number > 0):
		digit = number % 10
		number /= 10
		number_as_list = [digit] + number_as_list
	return number_as_list
	
# usage
print (colorful(3245))
print (colorful(326))
print (colorful(22))
print (colorful(1245))

- dbhage November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use state DP for not calculating products, which have already been calculated.

bool getProductResult(int n)
{
	char str[100];
	sprintf(str,"%d",n);
	string s(str);
	set<int> products;
	set<int>::iterator it;
	bool result=true;
	int len=s.size();
	if (len<=1)	return true;
	int dp[1<<len];
	for(int i=0;i<len;++i)
	{
		dp[1<<i]=s[i]-'0';
		it=products.find(s[i]-'0');
		if (it!=products.end())	
			result=false;
		else 
			products.insert(s[i]-'0');
	}
	for(int l=2;l<=len && result;++l)
	{
		int end=len-l;
		for(int i=0;i<=end && result;++i)
		{
			int state=0;
			for(int j=i+1;j<i+l;++j)
				state|=1<<(len-j-1);
			int singleState=1<<(len-i-1);
			int completeState=state|singleState;
			dp[completeState]=dp[singleState]*dp[state];
			it=products.find(dp[completeState]);
			if (it!=products.end()) 
				result=false;
			else 
				products.insert(dp[completeState]);			
		}
	}
	
	return result;
}

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

Why is there any need too recalculate the same product. One you see a same product you return false? Don't understand why storing products would help

- Ajak6 March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudocode:
1. Break the given number into indivdual digits.
2. Store these digits into an array.
3. Now , calculate the product of all the possible subsequences and store the result in a set.
4. Repeat step 3 unless there is a duplicate element. In that case , return false.
5. If step 3 never returns false return true.

Here is the implementation :

public class ColorfulNumber {
	
	public static void main(String[] args) {
	   System.out.println(isColorful(3245));
	   System.out.println(isColorful(326));
	}
	
	static boolean isColorful(int number){
		
		Set<Integer> s = new HashSet<>();
		String num = number+"";
		int[] digits = new int[num.length()];
		for(int i=0;i<num.length();i++){
			digits[i]=Integer.parseInt(num.charAt(i)+"");
			s.add(digits[i]);
		}
		
		for(int i=2;i<num.length();i++){
			for(int j=0;j<digits.length-i+1;j++){
				int tempi=i;
				int tempj=j;
				int product=1;
				while(tempi>0){
					product*=digits[tempj++];
					tempi--;
				}
				if(s.add(product)==false){
					return false;
				}
			}
		}
		
		
		return true;
	}

}

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

#include <algorithm>
#include <set>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
#include <cmath>
#include <vector>

using namespace std;


bool isColorful (int myNum){

	if (myNum/10 == 0){
		return true;
	}

	unordered_map<int, int> myVector;

	int numLength = (int)(log10(myNum)+1);
	for (int i = 1; i < numLength; ++i){
		int newNum = myNum;
		int newNumLength = (int)(log10(newNum)+1);
		for (int j = newNumLength+1-i; j >= 1; --j){
			int numPush = newNum%((int)pow(10,i));
			if ((int)(log10(numPush)+1) > 1){
				int x = numPush%10;
				int nL = (int)(log10(numPush)+1);
				for (int k =1; k <nL; ++k){
					if (x == 1 || x == 0){
						return false;
					}
					numPush = numPush/10;
					x = x*(numPush%10);

				}
				numPush = x;
			}
			if (numPush == 0 || numPush == 1){
				return false;
			}
			myVector[numPush] = 1;
			newNum = newNum/10;
		}
	}

	int mySize = 0;
	for (int i = 2; i <= numLength; ++i){
		mySize = mySize + i;
	}


	if (mySize > myVector.size()){
		return false;
	}
	return true;

}






int main(){


	cout << "Please enter a number: " << endl;

	int myNum;

	cin >> myNum;

	if (isColorful(myNum) == true){
		cout << "\nNumber is colorful." << endl;
	} else {
		cout <<"\nNumber is not colorful." << endl;
	}

	return 0;
}

- benjamin.k.taylor@vanderbilt.edu November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// here is simple solution to above problem

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class colourfull_no {
public static void main(String args[])
{
System.out.println(color_test("3245"));
System.out.println(color_test("326"));
System.out.println(color_test("322"));
}

static boolean color_test(String num){
String number=num+"";
ArrayList st1 = new ArrayList();
for(int i=0;i<number.length();i++)
{
for(int j=i+1;j<=number.length();j++)
{
String str1=new String();
str1=number.substring(i,j);
int k,a=0, prod=1;
k=Integer.parseInt(str1);
while(k!=0)
{
a=k%10;
k=k/10;
prod=prod*a;
}
st1.add(prod);
}
}
System.out.println(st1);
Set<Integer> set = new HashSet<Integer>(st1);
if(set.size() < st1.size())
{
return false;
}
else{return true;}
}

}

- Davi_singh November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int length = int (Math.log10(n)+1);

int A[length-1];

int b = 10;
for (i=0,i<length,i++){
A[i]=number%b;
b=b*10;
}

int product[length*length];
for (i=0,i<length-1,i++){
for(j=0;j<length-i,j++)
product[j] = A[i]*A[i+j+1];
}

Then compare each product element with others

- maybe November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int length = int (Math.log10(n)+1);

int A[length-1];

int b = 10;
for (i=0,i<length,i++){
	A[i]=number%b;
	b=b*10;
}

int product[length*length];
for (i=0,i<length-1,i++){
	for(j=0;j<length-i,j++)
	product[j] = A[i]*A[i+j+1];
}

Then compare each product element with others

- maybe November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashSet;

public class ColorfulNumber {

	private static boolean isColorfulNumber(int number){
		
		int lengthOfNumber = String.valueOf(number).length();
		int numbers[] = new int[lengthOfNumber];
		int newNumber = number;
		for(int i = 0; i < lengthOfNumber; i++){
			numbers[i] = (int) (newNumber / Math.pow(10,lengthOfNumber - i - 1)) ;
			newNumber = (int) (newNumber % Math.pow(10,lengthOfNumber - i - 1)) ;
		}
		ArrayList<Integer> products = new ArrayList<Integer>();
		for(int i = 0; i < lengthOfNumber; i++){
			int product = numbers[i];
			products.add(product);
			for(int j = i + 1; j <= lengthOfNumber - 1; j++ ){
				product = product * numbers[j];
				products.add(product);
			}
		}
		HashSet<Integer> productSet = new HashSet<Integer>(products);
		if(products.size() == productSet.size()){
			return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		
		boolean isColorful = isColorfulNumber(3245);
			System.out.println(isColorful);

	}

}

- Django November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package ProblemSolving;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.Exception;
import java.lang.Integer;
import java.lang.String;
import java.lang.System;
import java.util.HashSet;
import java.util.Set;

/**
 * Colorful Number:
 * A number can be broken into different sub-sequence parts.
 * Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245.
 * And this number is a colorful number, since product of every digit of a sub-sequence are different.
 * That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40
 * But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12.
 */
public class ColorfulNumber {
    public static void main(String[] args) throws Exception {
        String numString = new BufferedReader(new InputStreamReader(System.in)).readLine();
        int num = Integer.parseInt(numString);
        int length = numString.length();
        int[] digits = new int[length];
        int index = length - 1;
        Set<Integer> productSet = new HashSet<Integer>();

        while (num > 0) {
            digits[index] = num % 10;
            if(productSet.contains(digits[index]))
            {
                System.out.println("Not a colorful number");
                return;
            }else{
                //System.out.println("Added "+digits[index]+" at "+index);
                productSet.add(digits[index]);
            }
            num = num / 10;
            index--;
        }
        for (int x = 1; x < length; x++) {
            int product = 1;
            for(int i=0;i<x;i++)
            {
                product = product*digits[i];
            }

            for (int y = x; y < length; y++) {
                if(productSet.contains( product * digits[y]))
                {
                    System.out.println("Not a colorful number");
                    //System.out.println("Not a colorful number "+ product * digits[y]+" exists");
                    return;
                }else{
                    //System.out.println("Added "+ product * digits[y]);
                    productSet.add( product * digits[y]);
                }
            }
        }
        System.out.println("Colorful number");
    }
}

- Dheeraj Sachan November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No 1, no 0, no duplicates allowed. For fast prod[i->j] calculation, do prod[0->n] / prod[0->i-1] / reverseprod[j+1 -> n]. O(n^2), O(n).

bool isColorful(int num) {
	if (num == 0 || num == 1) return true;
	if (num < 0) return false;
	// num to vector
	vector<int> seq;
	vector<bool> check(8, false);
	// no 0, no 1, no duplicate
	while (num) {
		if (num % 10 == 0 || num % 10 == 1 || check[num % 10 - 2]) return false;
		check[num % 10 - 2] = true;
		seq.push_back(num % 10);
		num /= 10;
	}
	int low(0), high(seq.size() - 1);
	while (low < high) swap(seq[low++], seq[high--]);

	// calc sequential prod and rev prod.
	vector<int> seqprod(seq.size());
	seqprod[0] = seq[0];
	for (int i = 1; i < seq.size(); ++i) seqprod[i] = seqprod[i - 1] * seq[i];
	vector<int> revprod(seq.size());
	revprod[seq.size() - 1] = seq.back();
	for (int i = seq.size() - 2; i >= 0; --i) revprod[i] = revprod[i + 1] * seq[i];
	set<int> s;
	for (int st = 0; st < seq.size(); ++st) {
		for (int ed = st; ed < seq.size(); ++ed) {
			// cal prod[st]*prod[st+1]*...*prod[ed]
			int leftprod(1), rightprod(1);
			if (st > 0) leftprod = seqprod[st - 1];
			if (ed < seq.size() - 1) rightprod = revprod[ed + 1];
			if (s.count(revprod[0] / leftprod / rightprod)) return false;
			s.insert(revprod[0] / leftprod / rightprod);
		}
	}

	return true;
}

- XiaoPiGu December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IP_ColorfulNumber
{
    class Program
    {
        static void Main(string[] args)
        {
            ColorFul game = new ColorFul();

            game.checkifcolorful();

            Console.ReadLine();

        }
    }

    class ColorFul
    {
        public bool checkifcolorful()
        {
            Console.WriteLine("Enter a number");

            String num = Console.ReadLine();

            ArrayList product = new ArrayList();

            int sum = 0;
            
            for (int i = 0; i < num.Length; i++)
            {
                if (product.Contains(Convert.ToInt32(num[i]) - 48) || (Convert.ToInt32(num[i]) - 48) == 0 || (Convert.ToInt32(num[i]) - 48) == 1)
                {
                    Console.WriteLine("This number is not colorful");
                    return false;
                }
                else
                    product.Add(Convert.ToInt32(num[i] - 48));
            }

            for (int i = 0; i < num.Length; i++)
            {
                sum = Convert.ToInt32(num[i]) - 48;

                for (int j = i+1; j < num.Length; j++)
                {
                    if (i == 0 && (Convert.ToInt32(num[j]) - 48) == Convert.ToInt32(num[num.Length - 1]) - 48)
                    {

                    }
                    else
                    {
                        sum *= Convert.ToInt32(num[j]) - 48;
                        if(product.Contains(sum))
                        {
                            Console.WriteLine("This number is not coloful");
                            return false;
                        }
                        else
                        {
                            product.Add(sum);
                        }
                    }
                }
            }

            Console.WriteLine("This number is coloful");

            return true;
        }
    }
}

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

import java.util.HashMap;


public class Colorful {
public static boolean color(String s1){
	String sub,ssub;
	int kmer=0, sum = 1, num = 0;
	boolean color = true;
	HashMap map = new HashMap();
	for(int k = 1 ; k<= s1.length(); k++)
	{
		for(int i = 0 ; i <= (s1.length() - k) ; i++)
		{
			sub = s1.substring(i, i+k);
			if(sub.length()> 0){
				for(int j = 0; j<sub.length();j++)
				{
				ssub = Character.toString(sub.charAt(j));
				kmer = Integer.parseInt(ssub);
				//System.out.println("Previous product:" +sum+ "Current int:" +kmer);
				sum = sum * kmer;
				}
			}
			else
			{
				kmer = Integer.parseInt(sub);
				sum = kmer;
			}
			//System.out.println(" String: " +sub+ " Product: " +sum);
		
			if (map.containsValue(sum) == false)
			{
				map.put(sub,new Integer(sum));
			}
			else
			{
				System.out.println("Not a Colorful Number!");
				color =  false;
				System.exit(0);
			}
			sum = 1; 
			kmer = 0;
		}
	}
	
	return color;
	
}

public static void main(String argc[]){
	boolean c = color("326");
	if(c == true){
		System.out.println("Colorful Number!");
	}
}
}

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

I think this method will work and is more efficient I guess. Please do comment to see if it doesnt give desired output.

1. find digits my using / and % operator. eg for 3,2,4,8 for 3248
2. Since for product to be same, one of the digit has to be multiple of other (eg 4 multiple of 2)

3) we shall implement this

for ( i=0;i<no of digits;i++)
	int count=0;
	for(j=0;j<no of digits;j++)
		-> Create a hashmap
		if(a[j]%a[i]==0)
			if(hashmap.contains(a[j]%a[i])
				return false // not a colorful number
			else
				add in hashmap(a[j]%a[i])
				count++;
		else
			if the digit already exists 
				return false
			else
				add the digit as such in hashmap, 

			if(count>=2) // if some digit divides more than 2 digits i.e. remainder 0
				{
				 repeat the same process of division as above and at some point 				 there will be a clash in hashmap and it will return false
}

Please advise on above solution.

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

Think this should work

public class test {
	
	public static void main(String[] args){
		int num = 235;
		String snum = Integer.toString(num);
		int length = snum.length();
		double amount = Math.pow(2,length);
		char[] c = snum.toCharArray();
		int[] com = new int[(int) (amount )];
		for (int i = 1; i <amount; i++){
			String k = Integer.toString(i,2);
		
			
			if(k.length() <length){
				int t = length-k.length();
				for(int s=0; s< t;s++){
					k="0"+k;
				
				}
			}
			char[] m = k.toCharArray();
			int value = 1;
			for (int n = 0; n < length; n++){
				if(m[n] == '1'){
					value = Integer.parseInt(c[n]+"")*value;
				}
			}
			com[i]=value;
			
		}
		boolean check = false;
		for(int j =1;j < amount;j++){
			int temp =com[j];
			com[j]=-1;
			for(int l = 1; l < amount; l++){
				check=check||(temp==com[l]);
			}
		}
		if(check==false){
			System.out.println("colorful");
		}
		else{
			System.out.println("not colorful");
		}
	}
}

- Anon November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is based on Array structure only.

public class ColorFulNumber {

	public ColorFulNumber(int number) {
		// TODO Auto-generated constructor stub
		if(isColorful(number))
			System.out.println(number+" is a colorful number");
		else
			System.out.println(number+" is not a colorful number");
	}

	public boolean isColorful(int number) {
		if (number < 10)
			return true;

		String[] sub = new String[getLength(number)];
		subNumber(number, sub);
		print(sub);
		int[] nums = calculateSubNumber(sub);
		print(nums);
		return isColorful(nums);
	}
	
	public boolean isColorful(int[] nums){
		for(int i=0; i<nums.length;++i){
			for(int j=i+1; j< nums.length; ++j){
				if(nums[i] == nums[j])
					return false;
			}
		}
		return true;
	}

	public int[] calculateSubNumber(String[] sub) {
		int[] n = new int[sub.length];
		for (int i = 0; i < sub.length; ++i) {
			n[i] = productOfString(sub[i]);
		}
		return n;
	}

	public int productOfString(String number) {
		int result = 1;
		for (int i = 0; i < number.length(); ++i) {
			result = result * Integer.parseInt(number.charAt(i) + "");
		}
		return result;
	}

	public void print(Object[] sub) {
		for (int i = 0; i < sub.length; ++i)
			System.out.print(sub[i] + "--,\t");
		System.out.println();
	}
	
	public void print(int[] sub) {
		for (int i = 0; i < sub.length; ++i)
			System.out.print(sub[i] + ",\t");
		System.out.println();
	}

	public void subNumber(int number, String[] sub) {
		String n = String.valueOf(number);
		int count = 1;
		int k=0;
		for(;count <n.length();++count){
			for(int i=0; (i+count)<= n.length(); ++i){
				sub[k] = n.substring(i,i+count);
				++k;
			}
		}
	}

	public int getLength(int number) {
		int result = 0;
		for (int i = 2; i <= String.valueOf(number).length(); ++i)
			result += i;
		return result;
	}

}

- Phuong November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean colorfulNumber(int number) {
	   
	   ArrayList<Integer> bag = new ArrayList<Integer>(); 
	   
	   int marker; 
	   while(number != 0){
		   bag.add(number % 10); 
	       number /= 10; 
	   }
	   
	   if(bag.size() <= 1) { return false;}
	   marker= bag.size(); 
	   
	   for (int i = 1, j = marker-1; i < marker -1;i++,j--) {
		  
		  int forward = bag.get(i-1) * bag.get(i);
		  int backward = bag.get(j) * bag.get(j-1);
		  
		  if(bag.contains(forward) || bag.contains(backward)){
			 return false;    
		  }else{
			  bag.add(forward);
			  bag.add(backward);
		  }
	   }
	   return true; 
	}

- Anonymous January 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int colorful(int a) {
	    
	String s = String.valueOf(a);

        Map<Integer, Integer> map = new HashMap<>();

        int temp = 0;
        
        while (temp < s.length()) {
            //if immediate next is same return 0
            if (map.containsKey(s.charAt(temp) - '0')) return 0;
            map.put(s.charAt(temp) - '0', s.charAt(temp) - '0');
            temp++;
        }

        int i = 0;
        int j = 1;
        int n = s.length();

        while (j < n) {

            int val1 = s.charAt(i++) - '0';
            int val2 = s.charAt(j++) - '0';

            if (map.containsKey(val1*val2))
                return 0;

            map.put(val1 * val2, val1 * val2);
        }
        return 1;
}

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

Why we need DP and complex logics? Is it the requirement or any test cases needs to be covered?

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

Why we need DP and other complex solutions. Is it fulfils the requirement or any test cases needs to be covered?

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

public int colorful(int A) {
        HashSet<Integer> hashSet = new HashSet<>();
        ArrayList<Integer> numbers = new ArrayList<>();

        while (A != 0) {
            int num = A % 10;
            numbers.add(num);
            A /= 10;
        }

        Collections.reverse(numbers);
        int n = numbers.size();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int prod = 1;
                for (int k = i; k <= j; k++) {
                    prod = prod * numbers.get(k);
                }
                if (hashSet.contains(prod))
                    return 0;

                hashSet.add(prod);
            }
        }

        return 1;

}

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

Could someone please explain this to me - the problem states:

"326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12."

Why is 326 not colorful, even though 6 != 12 ?

- Kuzma November 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> asListOfDigits(int number) {
        return String.valueOf(number)
                .chars()
                .mapToObj(d -> Integer.valueOf("" + (char) d))
                .collect(Collectors.toList());
    }

    public static boolean isColorful(int number) {
        List<Integer> numbers = asListOfDigits(number);
        Set<Integer> products = new HashSet<>();

        for (int index = 1; index < numbers.size(); index++) {
            for (int pos = 0; pos + index <= numbers.size(); pos++) {
                Integer product = numbers.subList(pos, pos + index)
                        .stream()
                        .collect(Collectors.reducing(1, x -> x, (x, y) -> x * y));

                if (!products.add(product)) {
                    // When add returns false it means the set already contains the element
                    return false;
                }
            }
        }

        return true;
    }

- Carlos Cordero January 12, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) solution by first pre-computing the cumulative product array (in O(n)) and then iterating over all subsequences (pairs of start and end indices) and computing their products in O(1) time:

public static boolean isColorful(int number) {
    // pre-compute cummulative product array (while breaking number into digits)
    String strNum = String.valueOf(number);
    // first element is set to 1 so we don't have to deal with edge cases later
    int[] cumProd = new int[strNum.length() + 1];
    int i = 0;
    cumProd[i++] = 1;
    for (char c : strNum.toCharArray()) {
        cumProd[i] = (c - '0')*cumProd[i - 1];
        i++;
    }
    
    // now for computing the product of subsequence (start, end] (start exclusive, end inclusive) 
    // we simply need to compute cumProd[end]/cumProd[start] in O(1) time
    Set<Integer> prods = new HashSet<>();
    // since start is exclusive (i.e. not included in the product computed by cumProd[end]/cumProd[start])
    // this is where the first element in cumProd we set earlier becomes useful
    for (int start=0; start < cumProd.length - 1; start++) {
        for (int end=start + 1; end < cumProd.length; end++) {
            int prod = cumProd[end]/cumProd[start];
            if (prods.contains(prod)) return false;
            prods.add(prod);
        }
    }
    return true;
}

- shishio December 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) solution by first pre-computing the cumulative product array (in O(n)) and then iterating over all subsequences (pairs of start and end indices) and computing their products in O(1) time:

public static boolean isColorful(int number) {
    // pre-compute cumulative product array (while breaking number into digits)
    String strNum = String.valueOf(number);
    // first element is set to 1 so we don't have to deal with edge cases later
    int[] cumProd = new int[strNum.length() + 1];
    int i = 0;
    cumProd[i++] = 1;
    for (char c : strNum.toCharArray()) {
        cumProd[i] = (c - '0')*cumProd[i - 1];
        i++;
    }
    
    // now for computing the product of subsequence (start, end] (start exclusive, end inclusive) 
    // we simply need to compute cumProd[end]/cumProd[start] in O(1) time
    Set<Integer> prods = new HashSet<>();
    // since start is exclusive (i.e. not included in the product computed by cumProd[end]/cumProd[start])
    // this is where the first element in cumProd we set earlier becomes useful
    for (int start=0; start < cumProd.length - 1; start++) {
        for (int end=start + 1; end < cumProd.length; end++) {
            int prod = cumProd[end]/cumProd[start];
            if (prods.contains(prod)) return false;
            prods.add(prod);
        }
    }
    return true;
}

- shishio December 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not my own answer but I saw an answer that suggests you generate the digits to multiply via power sets of the digits. I think this implies that the order of the digits in the sequence doesn't matter for the colorful test (even though the actual products may vary from sequence to sequence). Question 1 is: is really it true that the order of the digits doesn't matter for the test? Question 2 is: and if it is true, how do you prove it?

- JohnA September 17, 2022 | 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