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){
				newList.add(0);
				newList.add(1);
			}
			else{
				newList.add(1);
				newList.add(0);
			}
		}
		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.add(0);
		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)+" ");
		}
	}

- jiahuang December 24, 2017 | Flag Reply
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[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];
}

- lxfuhuo December 31, 2017 | Flag Reply
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)

- Brad January 01, 2018 | Flag Reply
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;
    }

}

- Anonymous January 05, 2018 | Flag Reply
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)))

- dhd January 23, 2018 | Flag Reply
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)))

- dhd January 23, 2018 | Flag Reply
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);
}

- Nishagrawa March 28, 2019 | 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