Google Interview Question for Software Engineers


Country: United States




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

I found my mistake. I just have to return 0 instead of -1.

- Parth Patel February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

My working solution, I think this could be further optimized:

private static int getHigestNumDivisibleByThree(int[] arr) {

		int sum = 0;
		StringBuilder str = new StringBuilder();
		Arrays.sort(arr);

		for (int i = arr.length; i > 0; i--) {
			sum = sum + arr[i - 1];
			str.append(arr[i - 1]);
		}

		int remainder = sum % 3;
		if (remainder == 0)
			return Integer.parseInt(str.toString());

		str = new StringBuilder();

		boolean condition = true;
		int removeNum = 0;
		while (condition && remainder <= 9) {
			if (contains(arr, remainder)) {
				removeNum = remainder;
				break;
			}
			remainder = remainder + 3;
		}
		if (removeNum == 0)
			return 0;
		for (int i = arr.length; i > 0; i--) {
			if (removeNum == arr[i - 1]) {
				continue;
			}
			str.append(arr[i - 1]);
		}
		return Integer.parseInt(str.toString());
	}

	private static boolean contains(int[] arr, int num) {
		for (int i : arr)
			if (i == num)
				return true;
		return false;
	}

- getPDat February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple backtracking will help
1. Sort the string (954311)
2. if sorted string is divided by 3, return the result.
3. remove one by one from the end and check if it is divisible by 3. In case of 954311, we start with removing last '1'. As 9431 is not divisible by 3 put the 1 back and do the same with same with next 1 and so on. You will realize only when you remove 5 you will get the rest of the number divisible by 3.
4. Concept is very similar to 8 queen problem but just here instead here the constraint is divisibility by 3.

Found a better solution:
Let's start with a element 'x'. Every element when you are adding to 'x' will either increase it by 1 or by 2 for sure right when doing mod by 3.Think about this.

Now all you have to do is to figure out which "bad" apples are causing the sum to be not divisible by 3.

sum of entire array mod 3 will let you know, how much offset you are from being divisible by 3. It can be either by 1 or by 2 right?
example 12331 sum of this is (1+2+3+3+1)%3=1

Now sort the entire array. This step is intuitive right? After that you just have to go from end to beginning figuring out which array element mod 3 is giving me the offset we calculated earlier.

You will also notice that maximum of 2 elements should be removed to make any digit greater than 2 to be divisible by 3. Right? As explained earlier, if you add any two random or same digits to existing sum the entire sum will be divisible by 3.
proof:
x + a + b
if x is not divisible by 3 then adding 'a' and adding 'b' will make it divisible by 3 because adding 'a' will increase the sum by either 0,1 or 2. and in all cases when adding 'a' and 'b' the entire sum becomes divisible by 3.

Code

def foo(a):
  a = sorted([int(i) for i in a], reverse=True)
  s = sum([int(i) for i in a])
  if s%3 == 0:
    return a
  
  mod = s%3
  n = len(a)
  index_to_be_removed = []
  #if no >= 3, there has to be answer 
  for i in range(2):
    if index_to_be_removed:
      break
    for j in range(n-1, 0, -1):
      if a[j]%3 == mod:
        index_to_be_removed.append(j)
        break
      if i:
        for k in range(j):
          if not a[k]%3 or not a[j]%3:
            continue
          if (a[j] + a[k])%3 == mod:
            index_to_be_removed.append(j)
            index_to_be_removed.append(k)
  for i in index_to_be_removed:
    a = a[0:i]+a[i+1:]  
  print("".join([str(i) for i in a]))

foo("6532")

- aka February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def max_num(digits):
    dp = {0: 0}
    for d in sorted(digits, reverse=True):
        for q, v in list(dp.iteritems()):
            v2 = 10 * v + d
            q2 = v2 % 3
            if q2 not in dp or dp[q2] < v2:
                dp[q2] = v2
    return dp[0]

- americano February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def max_num(digits):
    dp = {0: 0}
    for d in sorted(digits, reverse=True):
        for q, v in list(dp.iteritems()):
            v2 = 10 * v + d
            q2 = v2 % 3
            if q2 not in dp or dp[q2] < v2:
                dp[q2] = v2
    return dp[0]

- americano February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def max_num(digits):
    dp = {0: 0}
    for d in sorted(digits, reverse=True):
        for _, v in list(dp.iteritems()):
            v2 = 10 * v + d
            q2 = v2 % 3
            if q2 not in dp or dp[q2] < v2:
                dp[q2] = v2
    return dp[0]

- americano February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is as follows,

public static String getLargestNumberDivisibleBy3(ArrayList<Integer> arrList){        
        PriorityQueue<Integer> bucket1 = new PriorityQueue<Integer>();
        PriorityQueue<Integer> bucket2 = new PriorityQueue<Integer>();
        for(Integer i:arrList){
            if(i%3==1){ 
                // all numbers with reminder 1
                bucket1.add(i);
            }else if(i%3==2){
                // all numbers with reminder 2
                bucket2.add(i);
            }      
        } 
        while(arrList.size() >= 0 ){
            int sum=0;
            for(Integer i:arrList){
                sum=sum+i;
            }
            if(sum%3==0){
                break;
            }else if(sum%3==1){
                // if there is a number in bucket1 - chose the minimal else: take minimal from bucket 2
                if(bucket1.size() > 0){
                    arrList.remove(bucket1.remove());
                }else{
                    arrList.remove(bucket2.remove()); 
                }  
            }else if(sum%3==2){
                // if there is a number in bucket2 - chose the minimal else: take minimal from bucket 1
                if(bucket2.size() > 0){
                    arrList.remove(bucket2.remove());
                }else{
                    arrList.remove(bucket1.remove()); 
                }
            }
        }      
        Collections.sort(arrList);
        Collections.reverse(arrList);
        StringBuilder str = new StringBuilder();
        for(Integer i:arrList){
            str.append(i);
        }
        if(str.toString().equals("")){
            str.append("0");
        }
        return str.toString();
    }

Some of the testcase,

i/p - 1,2,3,4,5,6,7,8,9,0
o/p - 9876543210

i/p - 2,5
o/p - 0

i/p - 3, 4, 0, 1, 5
o/p - 5430

- srd3v February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package org.practice.test;

import java.util.List;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class FindSumOfThree {

public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);

//Step 1: Sort the list

Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});

// Step 2: Find the sum of list

sum=sumOfList(numberLst);

if(sum%3==0){
printLst(numberLst);
}else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}


}

private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}


private static int divideFurtherByThree(List<Integer> numberLst){

int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);

}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0){

return removeNum;
}

}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}
}

}

- Pila February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package org.practice.test;

import java.util.List;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class FindSumOfThree {

public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);

//Step 1: Sort the list

Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});

// Step 2: Find the sum of list

sum=sumOfList(numberLst);

if(sum%3==0)
printLst(numberLst);
else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}
}

private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}


private static int divideFurtherByThree(List<Integer> numberLst){

int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);

}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0)
return removeNum;
}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}
}

}

- Pila February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindSumOfThree {

public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);

//Step 1: Sort the list

Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});

// Step 2: Find the sum of list

sum=sumOfList(numberLst);

if(sum%3==0)
printLst(numberLst);
else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}
}

private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}


private static int divideFurtherByThree(List<Integer> numberLst){

int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);
}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0)
return removeNum;
}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}}

}

- Pila February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution in C++

const int DIVISOR = 3;

unordered_map<int, list<int>> getModulos(const vector<int>& _array)
{
	unordered_map<int, list<int>> modulos(DIVISOR);

	for (int i = 0; i < (int)_array.size(); i++)//calculate each number in the array % 3 - result will always be 0, 1, or 2
	{
		int modulo = _array[i] % DIVISOR;
		modulos[modulo].push_back(i); //store the index so it can be removed later
	}

	return modulos;
}

void makeDivisisbleByDivisor(vector<int>& _array)
{
	unordered_map<int, list<int>> modulos = getModulos(_array);

	//indicates the number (if any) that needs to be removed from the array in order to be divisible by 3
	int moduloRemainder = ( modulos[1].size() + (modulos[2].size() * 2) ) % DIVISOR;
	
	int index = 0;

	if (modulos[moduloRemainder].empty()) //if we need to remove %2 but that array is empty remove 2 from %1
		index = DIVISOR - moduloRemainder; //should always be 1...
	else
		index = moduloRemainder;

	while (moduloRemainder > 0) //should execute a whopping 2 times max
	{
		int temp = modulos[index].back();
		modulos[index].pop_back();

		_array.erase(_array.begin() + temp);
		moduloRemainder -= index;
	}
}

//could probably utilize string stream but lazy
int convertVectorToInt(const vector<int>& _array) 
{
	int result = 0;

	for (int i = 0; i < (int)_array.size(); i++)
		result = (result * 10) + _array[i]; //multiply by ten to shift left

	return result;
}

int answer(vector<int> _array)
{
	sort(_array.rbegin(), _array.rend());

	makeDivisisbleByDivisor(_array);

	return convertVectorToInt(_array);
}

- undefined February 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is easy to think it is a largest number problem but it is not. For eg : List(9,6,3,0). largest number is 9630 which is divisible by 3. Like wise 3069 is divisible by 3. It is about taking a set of numbers and creating a subset which is divisible by 3. It is a subset sum problem and the subset sum should be divisible by 3.

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

A bit different approach.
1. get sum
1. if (sum % 3) = 0; return number
2. if (sum % 3) = 1; remove 1 or 4 or 7 return number
3. if (sum % 3) = 2; remove 2 or 5 or 8 return number
return 0

//C#
public static int GetMax3Divisible(int[] arr)
{
    int[] digitCounts = GetDigitCounts(arr);
    int sum = GetSum(arr);//get sum of digits

    int rem = sum % 3;
    if (rem == 1)
    {//we have to remove 1 or 4 or 7 to get the number divisible by 3
        if (!(RemoveNumber(digitCounts, 1) || RemoveNumber(digitCounts, 4) 
            || RemoveNumber(digitCounts, 7)))//Note. Language should support Shortcircuit 
        { 
            return 0;
        }
    }
    else if (rem == 2)
    {//we have to remove 2 or 5 or 8 to get the number divisible by 3
        if (!(RemoveNumber(digitCounts, 2) || RemoveNumber(digitCounts, 5)
            || RemoveNumber(digitCounts, 8)))//Note. Language should support Shortcircuit 
        {
            return 0;
        }
    }
    return GetNumber(digitCounts);
}

private static int[] GetDigitCounts(int[] arr)
{
    //transfer the values to an array of digit counts
    int[] digitCounts = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] >= 0 && (arr[i] < 10))
        {
            digitCounts[arr[i]]++;
        }
        else
        {
            throw new ArgumentOutOfRangeException();
        }
    }
    return digitCounts;
}

private static Boolean RemoveNumber(int[] digitCounts, int number)
{
    if (digitCounts[number] > 0)
    {
        digitCounts[number]--;
        return true;
    }
    else if (number % 2 == 0)
    {
        number = number / 2;
        if (digitCounts[number] > 1)
        { //remove 2 elements
            digitCounts[number] = digitCounts[number] - 2;
        }
        return true;
    }
    return false;
}


private static int GetNumber(int[] digitCounts)
{
    int number = 0;
    for (int i = digitCounts.Length - 1; i >= 0; i--)
    {
        while (digitCounts[i]-- > 0 )
        {
            number = number * 10 + i;
        }
    }
    return number;
}

private static int GetSum(int[] arr)
{
    int sum = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        sum = sum + arr[i];
    }
    return sum;
}

public static void Test()
{
    int[] a = { 2, 2, 4, 1,1};

    Console.WriteLine("Number = {0}", GetMax3Divisible(a));
}

- IC February 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

l,m=[i for i in raw_input()],[]
n=sorted([int(j) for j in l])[::-1]
if int(''.join([str(o) for o in n]))%3==0:
 print int(''.join([str(o) for o in n]))
else:
 for p in range(len(n)):
  m.append(n.pop((len(n)-1)-p))
  a=int(''.join([str(k) for k in n]))
  if a%3==0:
   q=sorted([int(r) for r in str(a)])
   print ''.join([str(s) for s in q[::-1]])
  else:
   n.append(m[0])
   del m[:]

- gokul kishan February 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Google3Multiple {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		List<Integer> ls = new ArrayList<Integer>();
		ls.add(3);
		ls.add(1);
		ls.add(4);
		ls.add(1);
		ls.add(5);
		ls.add(9);
		List<Integer> al = findVal(ls);
		System.out.print(al);
	}
	
	private static List findVal(List<Integer> ls)
	{
		List<Integer> rel  = new ArrayList<Integer>();
		List<Integer> temp  = new ArrayList<Integer>();
		
		for(Integer i:ls)
		{
			if(i%3!=0)
				temp.add(i);
			else
			{
				rel.add(i);
			}
		}
		
		if(temp.size()!=0)
		{
			List<List<Integer>> al = new ArrayList<>();
			List<Integer> rl = new ArrayList<>();
			
			
			combination(al,rl,0,0,temp);
			String [] res = new String[al.size()];
			int c=0;
			for(List<Integer> l:al)
			{  StringBuffer sb = new StringBuffer();
				for(int j:l){
				  sb.append(j);
				}
				res[c++]=sb.toString();
			}
			
			int max =-999;
			for(int j=0;j<res.length;j++)
			{
				max=Math.max(max, Integer.parseInt(res[j]));
			}
			System.out.println(max);
			
			while(max!=0)
			{
				rel.add(max%10);
				max=max/10;
			}
			
		}
		else
		{
			rel.addAll(ls);
			
		}
		Collections.sort(rel, Collections.reverseOrder());
		return rel;
	}

	
	private static void combination(List<List<Integer>> al, List<Integer>rl, int start,int target,List<Integer> input)
	{
		
		if(target!=0 && target%3==0)
		{
			al.add(new ArrayList<>(rl));
		}
		
		
		for(int i=start;i<input.size();i++)
		{
			rl.add(input.get(i));
			combination(al,rl,i+1,target+input.get(i),input);
			rl.remove(rl.size()-1);
		}
		
		
		
		
		
	}
	
}

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

package career_cup;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class ListOfNumbers {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("enter the list");

		List<Integer> al = new ArrayList<Integer>();

		 for (int i = 0; i < 20; i++) {
		 int next = sc.nextInt();
		 if(next>0 && next <10 )
		 al.add(next);
		 else
		 break;
		 }

		Collections.sort(al, Collections.reverseOrder());

		Set<Integer> set = new TreeSet<Integer>(Collections.reverseOrder());
		subelements(al, set);
		int number=0;
		int len =set.size();
		Iterator<Integer> itr = set.iterator();
		for (int i = 0; i < len; i++) {
			number = itr.next();
			if(number%3==0)
			{
				System.out.println("the result is " + number);
				break;
			}
			else if (i== len-1){
				System.out.println("the result is  0"  );
				break;
			}
		}

	}

	private static void subelements(List<Integer> al, Set<Integer> set) {
		int rem = 0, number;
		for (int i = 0; i < al.size(); i++) {
			rem = al.remove(i);
			number = number(al);
			if (number > 0)
				set.add(number);
			subelements(al, set);
			al.add(i,rem);
		}
	}

	public static int number(List<Integer> al) {
		int len = al.size(), sum = 0;
		for (int i = 0; i < len; i++) {
			sum += al.get(i) * Math.pow(10, len - 1 - i);
		}
		return sum;
	}

}

- Anonymous April 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ var a = [3,1,4,1,5,9]; var max = 0; var pattern = function(arr){ if(arr.length==1){ return arr; } var patterns = []; for(var i=0;i<arr.length;i++){ debugger; var copyArr = arr.slice(0,arr.length); copyArr.splice(i,1) var sub_patterns = pattern(copyArr); for(var j=0;j<sub_patterns.length;j++){ var num = arr[i]*Math.pow(10,Math.floor(Math.log10(sub_patterns[j]))+1)+sub_patterns[j]; if(num%3 ==0 && num > max){ max = num; } patterns.push(num); } } return patterns; } pattern(a); console.log(max); }} - aseem April 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var a = [3,1,4,1,5,9];
var max = 0;

var pattern = function(arr){
    if(arr.length==1){
        return arr;
    }
    var patterns = [];
    for(var i=0;i<arr.length;i++){
		debugger;
var copyArr = arr.slice(0,arr.length);
copyArr.splice(i,1)
        var sub_patterns = pattern(copyArr);
        for(var j=0;j<sub_patterns.length;j++){
            var num = arr[i]*Math.pow(10,Math.floor(Math.log10(sub_patterns[j]))+1)+sub_patterns[j];
            if(num%3 ==0 && num > max){
				max = num;
            }
            patterns.push(num);
        }
    }
    return patterns;
    
}
pattern(a);
console.log(max);

- aseem April 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package google;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class LargestNumberDivisibleBy3 {

	public static void main(String args[]) {
		int[] input = { 3, 1, 1 };
		System.out.println(getHigestNumDivisibleByThree(input));
	}

	private static int getHigestNumDivisibleByThree(int[] arr) {

		int sum = 0;
		StringBuilder str = new StringBuilder();
		Arrays.sort(arr);

		for (int i = arr.length; i > 0; i--) {
			sum = sum + arr[i - 1];
			str.append(arr[i - 1]);
		}

		int remainder = sum % 3;
		if (remainder == 0)
			return Integer.parseInt(str.toString());

		str = new StringBuilder();

		ArrayList<Integer> removeNum = new ArrayList<Integer>();
		int remNumCount = 1;
		while (remNumCount <= 2) {
			remainder = sum % 3;
			while (remainder <= 9 * remNumCount) {
				removeNum = contains(arr, remainder, remNumCount);
				if (removeNum != null) {
					break;
				}
				remainder = remainder + 3;
			}
			remNumCount++;
		}
		if (removeNum == null)
			return 0;
		for (int i = 0; i < arr.length; i++) {
			if (removeNum.contains(arr[i])) {
				continue;
			}
			str.append(arr[i]);
		}
		return Integer.parseInt(str.toString());
	}

	private static ArrayList<Integer> contains(int[] arr, int num, int mode) {
		if (mode == 1) {
			for (int i : arr)

				if (i == num) {
					ArrayList<Integer> result = new ArrayList<Integer>();
					result.add(i);
					return result;
				}
			return null;
		} else {
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			for (int i = 0; i < arr.length; i++) {
				if (map.containsKey(num - arr[i])) {
					ArrayList<Integer> result = new ArrayList<Integer>();
					result.add(arr[i]);
					result.add(map.get(num - arr[i]));
					return result;
				}
				map.put(arr[i], i);
			}
			return null;
		}
	}
}

- Dhruva.Bharadwaj April 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package career_cup;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class ListOfNumbers {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("enter the number of elements to be entered in the list");
		int count = sc.nextInt();

		List<Integer> al = new ArrayList<Integer>();
		System.out.println("enter the list");
		for (int i = 0; i < count; i++) {
			al.add(sc.nextInt());
		}

		Collections.sort(al, Collections.reverseOrder());

		Set<Integer> set = new TreeSet<Integer>(Collections.reverseOrder());

		int num1 = number(al);

		if (num1 % 3 == 0) {
			System.out.println("the result is " + num1);
		} else {
			subelements(al, set);
			int number = 0;
			int len = set.size();
			Iterator<Integer> itr = set.iterator();
			for (int i = 0; i < len; i++) {
				number = itr.next();
				if (number % 3 == 0) {
					System.out.println("the result is " + number);
					break;
				} else if (i == len - 1) {
					System.out.println("the result is  0");
					break;
				}
			}
		}
	}

	private static void subelements(List<Integer> al, Set<Integer> set) {
		int rem = 0, number;
		for (int i = 0; i < al.size(); i++) {
			rem = al.remove(i);
			number = number(al);
			if (number > 0)
				set.add(number);
			subelements(al, set);
			al.add(i, rem);
		}
	}

	public static int number(List<Integer> al) {
		int len = al.size(), sum = 0;
		for (int i = 0; i < len; i++) {
			sum += al.get(i) * Math.pow(10, len - 1 - i);
		}
		return sum;
	}

}

- Hyder April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String formNumbers(int[] inputNumbers) {
        int sum = getSum(inputNumbers);

        List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
                                            .sorted(Comparator.reverseOrder())
                                            .collect(Collectors.toList());

        int remainder = sum%3;
        if (remainder == 0 ) {
            return getResult(integers);
        }

        do {
            if (integers.contains(remainder)){
                integers.remove(Integer.valueOf(remainder));
                sum = integers.stream().mapToInt(x-> x).sum();
                remainder = sum%3;
                if (remainder == 0 && integers.size() == 0) {
                    return "0";
                } else {
                    return getResult(integers);
                }
            } else {
                if (integers.size() > 0) {
                    int largeValue = integers.get(0);
                    if (largeValue < remainder) {
                        remainder--;
                    }else {
                        remainder = remainder + 3;
                    }
                }
            }
        }while (sum > remainder);

        return  "0";
    }

    private static int getSum(int[] inputNumbers) {
        return IntStream.of(inputNumbers).sum();
    }

    private static String getResult(List<Integer> integers) {
        return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
    }

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

public static String formNumbers(int[] inputNumbers) {
        int sum = getSum(inputNumbers);

        List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
                                            .sorted(Comparator.reverseOrder())
                                            .collect(Collectors.toList());

        int remainder = sum%3;
        if (remainder == 0 ) {
            return getResult(integers);
        }

        do {
            if (integers.contains(remainder)){
                integers.remove(Integer.valueOf(remainder));
                sum = integers.stream().mapToInt(x-> x).sum();
                remainder = sum%3;
                if (remainder == 0 && integers.size() == 0) {
                    return "0";
                } else {
                    return getResult(integers);
                }
            } else {
                if (integers.size() > 0) {
                    int largeValue = integers.get(0);
                    if (largeValue < remainder) {
                        remainder--;
                    }else {
                        remainder = remainder + 3;
                    }
                }
            }
        }while (sum > remainder);

        return  "0";
    }

    private static int getSum(int[] inputNumbers) {
        return IntStream.of(inputNumbers).sum();
    }

    private static String getResult(List<Integer> integers) {
        return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
    }

- Bhaskar May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FormNumbersDivisibleBy3 {

    public static void main(String[] args) {
        System.out.println(formNumbers(new int[]{2,2}));
    }

    public static String formNumbers(int[] inputNumbers) {
        int sum = getSum(inputNumbers);

        List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
                                            .sorted(Comparator.reverseOrder())
                                            .collect(Collectors.toList());

        int remainder = sum%3;
        if (remainder == 0 ) {
            return getResult(integers);
        }

        do {
            if (integers.contains(remainder)){
                integers.remove(Integer.valueOf(remainder));
                sum = integers.stream().mapToInt(x-> x).sum();
                remainder = sum%3;
                if (remainder == 0 && integers.size() == 0) {
                    return "0";
                } else {
                    return getResult(integers);
                }
            } else {
                if (integers.size() > 0) {
                    int largeValue = integers.get(0);
                    if (largeValue < remainder) {
                        remainder--;
                    }else {
                        remainder = remainder + 3;
                    }
                }
            }
        }while (sum > remainder);

        return  "0";
    }

    private static int getSum(int[] inputNumbers) {
        return IntStream.of(inputNumbers).sum();
    }

    private static String getResult(List<Integer> integers) {
        return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
    }
}

- binitbhas May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.my;

import java.util.Scanner;


/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.

{{
Test cases
==========

Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311

Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {

/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/


private static String findLargestNumber(int a[]) {

quickSort(a, 0, a.length-1);

int sum = sumOfArray(a);

if((sum % 3) != 0) {

for(int i = 0; i < a.length; i++) {

for(int j = i; j < a.length; j++) {

if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}

}

if(sum % 3 == 0) {
break;
}

sum = sum - a[i];
a[i] = -1;
}
}

String s = "";

for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}

return s;
}

private static int sumOfArray(int a[]) {

int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}

return sum;
}

private static void quickSort(int a[], int low, int high) {

if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}

private static int partition(int a[], int low, int high) {


//Find pivot -- pivot is the last element
int pivot = a[high];

//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;

for(int j = low; j <= high -1; j++) {

if(pivot >= a[j]) {

int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;

}
}

int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;

return i+1;
}


public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();

int a[] = new int[m];

for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}

System.out.println(findLargestNumber(a));

}
}

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

package com.my;

import java.util.Scanner;


/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.

{{
Test cases
==========

Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311

Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {

/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/


private static String findLargestNumber(int a[]) {

quickSort(a, 0, a.length-1);

int sum = sumOfArray(a);

if((sum % 3) != 0) {

for(int i = 0; i < a.length; i++) {

for(int j = i; j < a.length; j++) {

if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}

}

if(sum % 3 == 0) {
break;
}

sum = sum - a[i];
a[i] = -1;
}
}

String s = "";

for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}

return s;
}

private static int sumOfArray(int a[]) {

int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}

return sum;
}

private static void quickSort(int a[], int low, int high) {

if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}

private static int partition(int a[], int low, int high) {


//Find pivot -- pivot is the last element
int pivot = a[high];

//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;

for(int j = low; j <= high -1; j++) {

if(pivot >= a[j]) {

int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;

}
}

int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;

return i+1;
}


public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();

int a[] = new int[m];

for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}

System.out.println(findLargestNumber(a));

}
}

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

package com.my;

import java.util.Scanner;


/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.

{{
Test cases
==========

Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311

Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {

/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/


private static String findLargestNumber(int a[]) {

quickSort(a, 0, a.length-1);

int sum = sumOfArray(a);

if((sum % 3) != 0) {

for(int i = 0; i < a.length; i++) {

for(int j = i; j < a.length; j++) {

if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}

}

if(sum % 3 == 0) {
break;
}

sum = sum - a[i];
a[i] = -1;
}
}

String s = "";

for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}

return s;
}

private static int sumOfArray(int a[]) {

int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}

return sum;
}

private static void quickSort(int a[], int low, int high) {

if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}

private static int partition(int a[], int low, int high) {


//Find pivot -- pivot is the last element
int pivot = a[high];

//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;

for(int j = low; j <= high -1; j++) {

if(pivot >= a[j]) {

int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;

}
}

int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;

return i+1;
}


public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();

int a[] = new int[m];

for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}

System.out.println(findLargestNumber(a));

}
}

- Senthil Raja June 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LargestNumberDevideBy3 {
/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/
private static String findLargestNumber(int a[]) {
quickSort(a, 0, a.length-1);
int sum = sumOfArray(a);
if((sum % 3) != 0) {
for(int i = 0; i < a.length; i++) {
for(int j = i; j < a.length; j++) {
if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}
}
if(sum % 3 == 0) {
break;
}
sum = sum - a[i];
a[i] = -1;
}
}
String s = "";
for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}
return s;
}
private static int sumOfArray(int a[]) {
int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}
return sum;
}
private static void quickSort(int a[], int low, int high) {
if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}
private static int partition(int a[], int low, int high) {
//Find pivot -- pivot is the last element
int pivot = a[high];
//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;
for(int j = low; j <= high -1; j++) {
if(pivot >= a[j]) {
int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
}
int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;
return i+1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int a[] = new int[m];
for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}
System.out.println(findLargestNumber(a));
}
}

- nsenthilrajaed June 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reference Python thoughts from @americano

import java.util.*;
import java.lang.*;

public class LargestDivisableBy3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
	    int[] nums = new int[]{4,5,2,4,1,1,1,8};
	    System.out.println(getLargestDivisableBy3(nums));

	}
    public static int getLargestDivisableBy3(int[] digits){
        
        Arrays.sort(digits);
        reverse(digits);
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,0);
        
        for(int i=0;i<digits.length;i++){
            Map<Integer,Integer> tempMap = new HashMap<>(map);
            for(int key:map.keySet()){
                int value = map.get(key);
                int temp = value*10+digits[i];
                int r = temp%3;
                if(!tempMap.containsKey(r)){
                    tempMap.put(r,temp);
                }else if(tempMap.get(r)<temp){
                    tempMap.put(r,temp);
                }
            }
            map = tempMap;
        }
        return map.get(0);
        
    }
 
    public static void reverse(int[] array){
        int i=0;
        int j=array.length-1;
        while(i<j){
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
            i++;
            j--;
        }
    }
}

- tiandiao123 September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy Java solution:

private int largestNumberDivBy3_noRecursion(List<Integer> list) {

        if (list.isEmpty()) {
            return 0;
        }

        // sort the numbers
        Collections.sort(list);
        Collections.reverse(list);
        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i);
        }

        int end = sb.length() - 1;
        StringBuilder word = sb;
        while (sb.length() > 0) {

            int num = Integer.parseInt(sb.toString());
             if (num % 3 == 0) return num;

            if (end < 0) {
                // remove the last char and reset the 'end'
                word = word.deleteCharAt(word.length() - 1);
                end = word.length() - 1;
            }            
            sb = new StringBuilder(word);
            sb = sb.deleteCharAt(end);
            end --;
        }

        return 0;
    }

- Hugh May 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the typescript answer O(N)

calculate(){
    let list = this.inputValue.split(',').map(i => +i);
    list = list.sort((a,b)=> b > a? 1: -1 );
    this.sum = list.reduce((prev, curr) => prev + curr)
    this.reminder = this.sum % 3;
    if(this.reminder !== 0) {
      for(var i = list.length - 1; i  >= 0 ; i--) {
        if(list[i] % 3 ===  this.reminder) {
          list[i] = -1;
          break;
        }
      }

      if(list.some(l => l === -1)) {
        list = list.filter(l => l != -1);
      } else {
        var counter = 0;
        for(var i = list.length - 1; i  >= 0 ; i--) {
            if(list[i] % 3 ===  (this.reminder % 2 + 1)) {
              list[i] = -1;
              counter++;
            }
            if(counter == 2) {
              break;
            }
          }
        list = list.filter(l => l != -1);        
      }
    }
    if(list.length > 0) {
      this.name = +(list.join(''));
    } else {
      this.name = 0;
    }
  }

- Nick H. May 18, 2019 | 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