Google Interview Question for Software Engineers


Country: United States




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

We can use the binary representation of number start from 0 till the binary representation of the number is less that the given N.

private void genNumber(final int N) {
	int k = 0;
	while (true) {
		int result = Integer.parseInt(Integer.toBinaryString(k));
		if (result > N) {
			break;
		}
		System.out.print(result + " ");
		k++;
	}
}

- Prashanth February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void getSum(int x) {
		int sum = 0;

		for (int i = 0; i < x; i++) {

			if (String.valueOf(i).contains("0") || String.valueOf(i).contains("1") ) {
				
				if(String.valueOf(i).matches("^[0-1]*$")){

				sum += i;

				System.out.println(i + " >> " + sum);
				}
			}

			
		}
	}

- Saurabh February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public static void getSum(int x) {
int sum = 0;

for (int i = 0; i < x; i++) {

if (String.valueOf(i).contains("0") || String.valueOf(i).contains("1") ) {

if(String.valueOf(i).matches("^[0-1]*$")){

sum += i;

System.out.println(i + " >> " + sum);
}
}


}
}
}}

- Saurabh February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void getSum(int x) {
int sum = 0;

for (int i = 0; i < x; i++) {

if (String.valueOf(i).contains("0") || String.valueOf(i).contains("1") ) {

if(String.valueOf(i).matches("^[0-1]*$")){

sum += i;

System.out.println(i + " >> " + sum);
}
}


}
}

- Saurabh February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<html>
public static void getSum(int x) {
int sum = 0;

for (int i = 0; i < x; i++) {

if (String.valueOf(i).contains("0") || String.valueOf(i).contains("1") ) {

if(String.valueOf(i).matches("^[0-1]*$")){

sum += i;

System.out.println(i + " >> " + sum);
}
}


}
}
</html>

- Saurabh February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<p class="p1">public static void<span class="s1"> getSum(</span>int <span class="s2">x</span><span class="s1">) {</span></p>
<p class="p2"><span class="s3">int</span> <span class="s2">sum</span> = 0;</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">for</span> (<span class="s3">int</span> <span class="s2">i</span> = 0; <span class="s2">i</span> &lt; <span class="s2">x</span>; <span class="s2">i</span>++) {</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">if</span> (String.valueOf(<span class="s2">i</span>).contains(<span class="s4">"0"</span>) || String.valueOf(<span class="s2">i</span>).contains(<span class="s4">"1"</span>) ) {</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">if</span>(String.valueOf(<span class="s2">i</span>).matches(<span class="s4">"^[0-1]*$"</span>)){</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s2">sum</span> += <span class="s2">i</span>;</p>
<p class="p3">&nbsp;</p>
<p class="p2">System.<span class="s5">out</span>.println(<span class="s2">i</span> + <span class="s4">" &gt;&gt; "</span> + <span class="s2">sum</span>);</p>
<p class="p2">}</p>
<p class="p2">}</p>
<p class="p3">&nbsp;</p>
<p class="p3">&nbsp;</p>
<p class="p2">}</p>
<p class="p2">}</p>

- saurabh February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<p class="p1">public static void<span class="s1"> getSum(</span>int <span class="s2">x</span><span class="s1">) {</span></p>
<p class="p2"><span class="s3">int</span> <span class="s2">sum</span> = 0;</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">for</span> (<span class="s3">int</span> <span class="s2">i</span> = 0; <span class="s2">i</span> &lt; <span class="s2">x</span>; <span class="s2">i</span>++) {</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">if</span> (String.valueOf(<span class="s2">i</span>).contains(<span class="s4">"0"</span>) || String.valueOf(<span class="s2">i</span>).contains(<span class="s4">"1"</span>) ) {</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s3">if</span>(String.valueOf(<span class="s2">i</span>).matches(<span class="s4">"^[0-1]*$"</span>)){</p>
<p class="p3">&nbsp;</p>
<p class="p2"><span class="s2">sum</span> += <span class="s2">i</span>;</p>
<p class="p3">&nbsp;</p>
<p class="p2">System.<span class="s5">out</span>.println(<span class="s2">i</span> + <span class="s4">" &gt;&gt; "</span> + <span class="s2">sum</span>);</p>
<p class="p2">}</p>
<p class="p2">}</p>
<p class="p3">&nbsp;</p>
<p class="p3">&nbsp;</p>
<p class="p2">}</p>
<p class="p2">}</p>

- Anonymous February 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
public static void main(String[] args) {
printAll("1",123);

printAll("0",123);
}
static void printAll(String suff,int n){
int val= Integer.valueOf(suff);
if(val > n)
return;
else{
System.out.println(val);
if(val!=0){
printAll(suff+"1",n);
printAll(suff+"0",n);
}


}
}
}

- viveksingh.heritage February 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
    public static void main(String[] args) {
        printAll("1",123);
        
        printAll("0",123);
    }
    static void printAll(String suff,int n){
        int val= Integer.valueOf(suff);
        if(val > n)
            return;
        else{
            System.out.println(val); 
            if(val!=0){
                printAll(suff+"1",n);
                printAll(suff+"0",n);
            }
                
           
        }
  }
}

- viveksingh.heritage February 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Steps:
1. Find the biggest 10^n number before "number"
2. Put into array 10^0 ... 10^n. We have smth like [1, 10, 100, 1000]
3. Print all the combinations

Exclude the steps if any of the pre-conditions are known already.

- denis.zayats February 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> getNumbers(int input) {
		List<Integer> numbers = new ArrayList<Integer>();
		int index = 0;

		if (input > 0) {
			numbers.add(0);
		}

		if (input > 1) {
			numbers.add(1);
			while (++index < numbers.size()) {
				int number = numbers.get(index);
				int next1 = number * 10;
				if (next1 < input)
					numbers.add(next1);
				int next2 = next1 + 1;
				if (next2 < input)
					numbers.add(next2);
			}
		}
		return numbers;
	}

- Viv February 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> getNumbers(int input) {
List<Integer> numbers = new ArrayList<Integer>();
int index = 0;

if (input > 0) {
numbers.add(0);
}

if (input > 1) {
numbers.add(1);
while (++index < numbers.size()) {
int number = numbers.get(index);
int next1 = number * 10;
if (next1 < input)
numbers.add(next1);
int next2 = next1 + 1;
if (next2 < input)
numbers.add(next2);
}
}
return numbers;
}

- Viv February 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List<Integer> numbers = new ArrayList<Integer>();
int index = 0;
if (input > 0)
numbers.add(0);
if (input > 1) {
numbers.add(1);
while (++index < numbers.size()) {
int number = numbers.get(index);
int next1 = number * 10;
if (next1 < input)
numbers.add(next1);
int next2 = next1 + 1;
if (next2 < input)
numbers.add(next2);
}
}
return numbers;

- v February 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List<Integer> numbers = new ArrayList<Integer>();
		int index = 0;
		if (input > 0)
			numbers.add(0);
		if (input > 1) {
			numbers.add(1);
			while (++index < numbers.size()) {
				int number = numbers.get(index);
				int next1 = number * 10;
				if (next1 < input)
					numbers.add(next1);
				int next2 = next1 + 1;
				if (next2 < input)
					numbers.add(next2);
			}
		}
		return numbers;

- viv February 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone please clarify the question?

- Henry March 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(logn) ruby solution, using a tree to make base 10 binary numbers:

def gen_nums(n)
 depth = Math.log10(n).floor
 puts 0
 gen_to_depth("", depth, n)
end

def gen_to_depth(str, levels_left, n)
 return if levels_left == -1
 with_one = str.dup.prepend("1")
 with_zero = str.dup.prepend("0")
 if with_one.to_i <= n
  puts with_one.to_i
  gen_to_depth(with_one, levels_left-1, n)
 end
 gen_to_depth(with_zero, levels_left-1, n)
end

- Henry March 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* Give a decimal number, such as 123. Asking a total of smaller num
* than 123 made up by 1 and 0 composed of decimal numbers.
* 111, 110, 101, 100, 11, 10, 1, 0.
*/
public static int smallerNumComposedOf1and0(final int compareNo) {
int noOfColumn = 0, tmp=compareNo;

if(compareNo == 0) return 0;
else if(compareNo==1) return 1;

/*
* Find out how many digit we have in given compareNo.
* Based on this we construct array which have value made up by 1 and 0 composed
* of decimal number(compareNo).
*/
while(tmp != 0) {
noOfColumn++;
tmp /=10;
}

/*
* Create array to store value made up by 1 and 0 composed of decimal number(compareNo).
*/
int noOfRow = (int) ((noOfColumn <= 2)? 2 : Math.pow(2, noOfColumn-1));
int dp[][] = new int[noOfRow][noOfColumn];

/*
* Initialize array based on each column value based on pattern.
* Example for 4 digit.
* 1000
* 1001
* 1010
* 1011
* 1100
* 1101
* 1110
* 1111
*/
dp[0][0] = 1;
dp[noOfRow-1][0] = 1;
for(int i=noOfColumn-1; i>0; i--) {
dp[i][0] = 1;
int relationShip = (int)Math.pow(2, (noOfColumn-1)-i);
byte setToZeroOrOne = 0;
for(int j=0; j<noOfRow;j++) {
dp[j][i] = setToZeroOrOne;
if(relationShip == 1 || (((j+1) % relationShip) == 0)){
setToZeroOrOne = (byte) ((setToZeroOrOne == 1) ? 0 : 1);
}
}
}

//Check where does given number exist in dp of 1/0
for(int i=noOfRow-1; i>=0; i++) {
int constructNo = 1;
for(int j=1; j<noOfColumn;j++)
constructNo = (constructNo * 10) + dp[i][j];
if(compareNo > constructNo) {
int result = 0;
for(int k=noOfColumn-1; k>0; k--)
result += (k==1) ? 2 : Math.pow(2, k-1);
return result + i + 1 ;
}
}
return 0;
}

- jhunter April 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
	 * Give a decimal number, such as 123. Asking a total of smaller num 
	 * than 123 made up by 1 and 0 composed of decimal numbers. 
	 * 111, 110, 101, 100, 11, 10, 1, 0.
	 */
	public static int smallerNumComposedOf1and0(final int compareNo) {
		int noOfColumn = 0, tmp=compareNo;
		
		if(compareNo == 0) return 0;
		else if(compareNo==1) return 1;
		
		/*
		 * Find out how many digit we have in given compareNo.
		 * Based on this we construct array which have value made up by 1 and 0 composed 
		 * of decimal number(compareNo).
		 */
		while(tmp != 0) {
			noOfColumn++;
			tmp /=10;
		}
		
		/*
		 * Create array to store value made up by 1 and 0 composed of decimal number(compareNo).
		 */
		int noOfRow = (int) ((noOfColumn <= 2)? 2 : Math.pow(2, noOfColumn-1));
		int dp[][] = new int[noOfRow][noOfColumn];
		
		/*
		 * Initialize array based on each column value based on pattern. 
		 * Example for 4 digit.
		 * 1000
		 * 1001
		 * 1010
		 * 1011
		 * 1100
		 * 1101
		 * 1110
		 * 1111 
		 */
		dp[0][0] = 1;
		dp[noOfRow-1][0] = 1;
		for(int i=noOfColumn-1; i>0; i--) {
			dp[i][0] = 1;
			int relationShip = (int)Math.pow(2, (noOfColumn-1)-i);
			byte setToZeroOrOne = 0;
			for(int j=0; j<noOfRow;j++) {
				dp[j][i] = setToZeroOrOne;
				if(relationShip == 1 || (((j+1) % relationShip) == 0)){
					setToZeroOrOne = (byte) ((setToZeroOrOne == 1) ? 0 : 1);
				}
			}
		}
		
		//Check where does given number exist in dp of 1/0
		for(int i=noOfRow-1; i>=0; i++) {
			int constructNo = 1;
			for(int j=1; j<noOfColumn;j++)
				constructNo = (constructNo * 10) + dp[i][j];
			if(compareNo > constructNo) {
				int result = 0;
				for(int k=noOfColumn-1; k>0; k--)
					result += (k==1) ? 2 : Math.pow(2, k-1);
				return result + i + 1 ;
			}
		}
		return 0;
	}

- jhunter April 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

jhunter

/*
	 * Give a decimal number, such as 123. Asking a total of smaller num 
	 * than 123 made up by 1 and 0 composed of decimal numbers. 
	 * 111, 110, 101, 100, 11, 10, 1, 0.
	 */
	public static int smallerNumComposedOf1and0(final int compareNo) {
		int noOfColumn = 0, tmp=compareNo;
		
		if(compareNo == 0) return 0;
		else if(compareNo==1) return 1;
		
		/*
		 * Find out how many digit we have in given compareNo.
		 * Based on this we construct array which have value made up by 1 and 0 composed 
		 * of decimal number(compareNo).
		 */
		while(tmp != 0) {
			noOfColumn++;
			tmp /=10;
		}
		
		/*
		 * Create array to store value made up by 1 and 0 composed of decimal number(compareNo).
		 */
		int noOfRow = (int) ((noOfColumn <= 2)? 2 : Math.pow(2, noOfColumn-1));
		int dp[][] = new int[noOfRow][noOfColumn];
		
		/*
		 * Initialize array based on each column value based on pattern. 
		 * Example for 4 digit.
		 * 1000
		 * 1001
		 * 1010
		 * 1011
		 * 1100
		 * 1101
		 * 1110
		 * 1111 
		 */
		dp[0][0] = 1;
		dp[noOfRow-1][0] = 1;
		for(int i=noOfColumn-1; i>0; i--) {
			dp[i][0] = 1;
			int relationShip = (int)Math.pow(2, (noOfColumn-1)-i);
			byte setToZeroOrOne = 0;
			for(int j=0; j<noOfRow;j++) {
				dp[j][i] = setToZeroOrOne;
				if(relationShip == 1 || (((j+1) % relationShip) == 0)){
					setToZeroOrOne = (byte) ((setToZeroOrOne == 1) ? 0 : 1);
				}
			}
		}
		
		//Check where does given number exist in dp of 1/0
		for(int i=noOfRow-1; i>=0; i++) {
			int constructNo = 1;
			for(int j=1; j<noOfColumn;j++)
				constructNo = (constructNo * 10) + dp[i][j];
			if(compareNo > constructNo) {
				int result = 0;
				for(int k=noOfColumn-1; k>0; k--)
					result += (k==1) ? 2 : Math.pow(2, k-1);
				return result + i + 1 ;
			}
		}
		return 0;
	}

- jhunter April 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use dynamic programming... Dp[I] will store the total number from last position.. Dp[i+1]=dp[i]+dp[i-2];

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

I understood the question to ask for the number of combinations, not the combinations themselves.

func numCombinations(v int) int {
	tally := 0

	vstr := strconv.Itoa(v)
	for vstr != "" {
		// Edge cases for the last digit
		if len(vstr)==1 {
			switch vstr {
			case "0":
				// Nothing
			case "1":
				tally ++
			default:
				tally += 2
			}
			break
		}
		
		// Check most significant digit
		msd := vstr[:1]
		switch msd {
			case "1":
				tally += 1 << (len(vstr)-1)
				vstr = strings.TrimLeft(vstr[1:], "0")
			default:
				tally += 1 << len(vstr)
				break;			
		}
	}
	
	return tally
}

- BW January 18, 2021 | 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