## Google Interview Question for SDE1s

Country: United States

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

This can be done in two ways:

Approach 1: Construct the final line which takes O(2^k) time where k is the max row in all queries. Each query will only take O(1) time. The downside of this approach is it requires O(2^k) space.

Approach 2: Without construct the lines, it takes O(k) time for each query, and only takes O(1) space.

``````//Approach 1
public static List<Integer> build(List<Integer> list, int level){
if(level == 0)return list;
List<Integer> newList = new ArrayList<Integer>();
for(int each:list){
if(each == 0){
}
else{
}
}
return build(newList,level-1);
}

//Approach 2
public static int query(int ith, int left, int right, int bit){
if(left == right){
return bit;
}
else{
int mid = left-(right-left)/2;
if(left <= ith && mid >= ith){
return query(ith,left,mid,bit);
}
else return query(ith,mid+1,right,1-bit);
}
}
public static void main(String[] args){
List<Integer> list = new ArrayList<Integer>();
list = build(list,4);
for(int each:list){
System.out.print(each+" ");
}
System.out.println();
for(int i=0;i<16;i++){
System.out.print(query(i,0,15,0)+" ");
}
}``````

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

0
01
0110
01101001
.......
You could find that prefix is same as previous line, and postfix is the reverse of number of prefix. So jth is the only variable you need to care.

jth is 0 indexed.

``````int get_ans(int k, int jth){
int str = {0,1,1,0};
if (jth < 4){
return str[jth];
}
bool reverse = 0;
while (jth >= 4){
jth = jth - pow(2,(int)log(jth));
reverse ^= 1;
}
if (reverse){
return str[jth] ^1;
}
return str[jth];
}``````

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

``````import math

def bit_at(k, j):
def _bit_at(k_r, j_r):
if k_r == 0:
return 0
parent_bit = _bit_at(k_r - 1, j_r // 2)
str_ = [0, 1] if not parent_bit else [1, 0]
return str_[j_r % 2]
assert 0 <= math.log(j + 1, 2) <= k
return _bit_at(k, j)``````

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

``````int find_jth_bit(int k, int j){
if(j>=pow(2,k)) return -1;
if(k==0){
if(j==0)return 0;
else return -1;
}
if(k==1){
if(j==0) return 0;
else if(j==1) return 1;
else return -1;
}
bool toggled=false;

while(k>1){
if(j%2!=0) toggled=(!toggled);
j=j/2;
k--;
}
if(!toggled){
if(j==0) return 0;
if(j==1) return 1;
}else{
if(j==0) return 1;
if(j==1) return 0;
}

}``````

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

``````def fbit(k, j):
if k == 0:
return 0

return int(fbit(k-1, j) if j < 2**(k-1) else not fbit(k-1, j % 2**(k-1)))``````

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

``def fbit(k, j):``

``if k == 0:``

``return 0``

``return int(fbit(k-1, j) if j < 2**(k-1) else not fbit(k-1, j % 2**(k-1)))``

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

time: O(k) space: O(k) using recursion

``````#include <iostream>
using namespace std;

int FindValue(int k, int j)
{
if(k == 0)
{
return 0;
}
int x = FindValue(k-1, j/2);
if(x == 0)
{
if(j%2 == 0)
{
return 0;
}
return 1;
}
else
{
if(j%2 == 0)
{
return 1;
}
return 0;
}
}

int main() {
cout<<FindValue(3, 4);
}``````

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.