Google Interview Question
Software EngineersCountry: United States
<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"> </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> < <span class="s2">x</span>; <span class="s2">i</span>++) {</p>
<p class="p3"> </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"> </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"> </p>
<p class="p2"><span class="s2">sum</span> += <span class="s2">i</span>;</p>
<p class="p3"> </p>
<p class="p2">System.<span class="s5">out</span>.println(<span class="s2">i</span> + <span class="s4">" >> "</span> + <span class="s2">sum</span>);</p>
<p class="p2">}</p>
<p class="p2">}</p>
<p class="p3"> </p>
<p class="p3"> </p>
<p class="p2">}</p>
<p class="p2">}</p>
<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"> </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> < <span class="s2">x</span>; <span class="s2">i</span>++) {</p>
<p class="p3"> </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"> </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"> </p>
<p class="p2"><span class="s2">sum</span> += <span class="s2">i</span>;</p>
<p class="p3"> </p>
<p class="p2">System.<span class="s5">out</span>.println(<span class="s2">i</span> + <span class="s4">" >> "</span> + <span class="s2">sum</span>);</p>
<p class="p2">}</p>
<p class="p2">}</p>
<p class="p3"> </p>
<p class="p3"> </p>
<p class="p2">}</p>
<p class="p2">}</p>
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);
}
}
}
}
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;
}
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;
}
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;
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;
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
/*
* 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;
}
/*
* 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
/*
* 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;
}
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
}
We can use the binary representation of number start from 0 till the binary representation of the number is less that the given N.
- Prashanth February 06, 2018