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

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

}
}``````

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

}
}
}}

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

}
}

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>

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>

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>

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

}
}
}

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

}
}
}``````

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.

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

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

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

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

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)
if (input > 1) {
while (++index < numbers.size()) {
int number = numbers.get(index);
int next1 = number * 10;
if (next1 < input)
int next2 = next1 + 1;
if (next2 < input)
}
}
return numbers;

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)
if (input > 1) {
while (++index < numbers.size()) {
int number = numbers.get(index);
int next1 = number * 10;
if (next1 < input)
int next2 = next1 + 1;
if (next2 < input)
}
}
return numbers;``````

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

Can someone please clarify the question?

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``````

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

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

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

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

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.

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