Google Interview Question
SDE1sCountry: United States
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[4] = {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];
}
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;
}
}
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);
}
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.
- jiahuang December 24, 2017