Google Interview Question for Software Engineers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
6
of 8 vote

Seems to me like a variant of longest increasing subsequence problem

#include <iostream>
#include <cmath>
#include <vector>

using namespace	std;

int maximum_number_of_elements(vector<int> arr)	{
  vector<int> dp(arr.size());
  int m = 0;
  dp[0] = 1;
  for(int i = 1; i < arr.size(); i++) {
    int	_m = 1;
    for(int j = i - 1; j >= 0; j--) {
      if(abs(arr[i] - arr[j]) <= i - j)	_m = max(_m, 1 + dp[j]);
    }
    dp[i] = _m;
    m =	max(m, dp[i]);
  }
  return m;
}

int main() {
  vector<int> r{13, 5, 4, 16, 15};
  cout << maximum_number_of_elements(r) << "\n";
}

- CodeTillDeath September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

//O(nlogn) with AVL tree.

private static class Node
{
	int value;
	int idx;
	public Node(int v, int i){
	value = v;
	idx = i;
	}
}

public static int countPairs(int[] arr){
	if(arr == null || arr.length <= 1){
	return -1;
	}
	
	Node h = new Node(arr[0],0);
	int ct = 0;
	for(int i = 1; i < arr.length; i++){
		int lo = arr[i] - i;
		int hi = arr[i] + i;
		//count values
		ct += (count(lo,hi,h,arr[i],i))*2;
		h = insertAvl(h,arr[i],i);
		
	}
	return ct;
}

private static int count(int lo, int hi, Node h, int x, int idx){
	if(h == null|| h.value < lo || h.value > hi){
		return 0;
	}
	int total = count(lo,hi,h.left,x,idx);
	if(Math.abs(x - h.value) <= Math.abs(idx - h.idx))
	{
		total++;
	}
	return total;
}

- divm01986 September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;
public class c1{
public static void main(String args[])throws Exception{
int i,j,n,c=0,d1=0,d2=0,z=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the size.");
n=Integer.parseInt(br.readLine());
int arr[] = new int[n];
for(i=0;i<n;i++)
{
z++;
System.out.println("Enter the value of element:"+z);
arr[i] = Integer.parseInt(br.readLine());
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++){
d1=Math.abs(arr[i]-arr[j]);
d2=Math.abs(i-j);
if(d1>d2)
c++;
}
}
System.out.println(c);
}
}

- Atul Parashar September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;
public class c1{
public static void main(String args[])throws Exception{
int i,j,n,c=0,d1=0,d2=0,z=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the size.");
n=Integer.parseInt(br.readLine());
int arr[] = new int[n];
for(i=0;i<n;i++)
{
z++;
System.out.println("Enter the value of element:"+z);
arr[i] = Integer.parseInt(br.readLine());
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++){
d1=Math.abs(arr[i]-arr[j]);
d2=Math.abs(i-j);
if(d1>d2)
c++;
}
}
System.out.println(c);
}
}

- Atul Parashar September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

this is maximum clique problem. NP-complete. No polynomial solution.

- Anonymous September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This needs to try out every combination of two numbers in the list of n elements. Brute force way:

public static Set<Integer> pick(int[] nums) {
    Set<Integer> resultList = new HashSet<>();
    for(int i=0; i<nums.length; i++) {
      for(int j=0; j<nums.length && j!=i; j++) {
        if(Math.abs(nums[i] - nums[j]) <= Math.abs(i-j)) {
          resultList.add(nums[i]);
          resultList.add(nums[j]);
        }
      }
    }
    return resultList;
  }

- keshy September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This needs to test out all combinations of 2 numbers to be considered. A set can be used to do deduplication.

public static Set<Integer> pick(int[] nums) {
    Set<Integer> resultList = new HashSet<>();
    for(int i=0; i<nums.length; i++) {
      for(int j=0; j<nums.length && j!=i; j++) {
        if(Math.abs(nums[i] - nums[j]) <= Math.abs(i-j)) {
          resultList.add(nums[i]);
          resultList.add(nums[j]);
        }
      }
    }
    return resultList;
  }

- keshi September 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Set<Integer> pick(int[] nums) {
    Set<Integer> resultList = new HashSet<>();
    for(int i=0; i<nums.length; i++) {
      for(int j=0; j<nums.length && j!=i; j++) {
        if(Math.abs(nums[i] - nums[j]) <= Math.abs(i-j)) {
          resultList.add(nums[i]);
          resultList.add(nums[j]);
        }
      }
    }
    return resultList;
  }

- cool93jain September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since A[i] and A[j] can have any value, we need to test every possible combination of A[i] and A[j]. The problem asks just to count the number of possible distinct index pairs:

public static int maxNumber(int[] a) {
	int count = 0;
	for (int i = 0; i < a.length - 1; i++) {
		for (int j = i + 1; j < a.length; j++) {
			if (Math.abs(a[i] - a[j]) <= Math.abs(i - j)) {
				count += 2;
			}
		}			
	}
	return count;
}

- Anonymous September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Need to check every possible combination of A[i] and A[j]. Problem asks just to count distinct index pairs found that satisfies condition.
O(1) space and O(n^2) time:

public static int maxNumber(int[] a) {
	int count = 0;
	for (int i = 0; i < a.length - 1; i++) {
		for (int j = i + 1; j < a.length; j++) {
			if (Math.abs(a[i] - a[j]) <= Math.abs(i - j)) {
				count += 2;
			}
		}			
	}
	return count;
}

- guilhebl September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

recursive answer O(n^2)

int numFollowingRule(int[] arr) {
	int num = 0;
	for (int i = 0; i < arr.length; i++) {
		num += applyRule(arr, i);
	}
	return num;
}

int applyRule(int[] arr, int i) {
	int count = 0;
	for (int j = i;j < arr.length; j++) {
		if (Math.abs(arr[i] - arr[j]) > Math.abs(i - j)) {
			count += 1;
		}
	}
	return count;
}

- AJGoley September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(n^2) solution which helps to understand the idea. It can get improved.

int main() {
  vector<int> r;
        r.push_back(13);
        r.push_back(1);
        r.push_back(1);
        r.push_back(2);
        r.push_back(3);



        int maxNum = 0;
        for(int i = 0 ; i < r.size(); i++){
                int tempMax = 0;
                for(int j = 0 ; j < r.size(); j++){
                        if(abs(r[i] - r[j]) <= abs(i-j)) tempMax++;
                }
                maxNum = max(maxNum, tempMax);
        }

        cout << "Max Number: " << maxNum << endl;
}

- IB September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does the i has to be less than j? Because A[i]-A[j] can be negative if i is greater than j in this array. which is less than i-j and fulfills the condition.

- Denis September 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript:

function getMax(arList) {
	var count = 0;
  // pointer a
  for (var i=0; i<arList.length; i++) {
  	// pointer b
    for (var j=0; j<arList.length; j++) {
      if (j > i && Math.abs(arList[i] - arList[j]) <= Math.abs(i - j) ) {
      	count++;    	
    	}
    }
  }
  return count;
}

alert(getMax([13, 5, 4, 16, 15]));

- Anonymous September 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript:

function getMax(arList) {
	var count = 0;
  // pointer a
  for (var i=0; i<arList.length; i++) {
  	// pointer b
    for (var j=0; j<arList.length; j++) {
      if (j > i && Math.abs(arList[i] - arList[j]) <= Math.abs(i - j) ) {
      	count++;    	
    	}
    }
  }
  return count;
}

alert(getMax([13, 5, 4, 16, 15]));

- Cuccias September 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java, I could not reach a better order than O(n/2) which would probably round to O(n) with larger arrays. This works by starting from both ends of the array so and calculating and stopping once both pointers meet in the middle.

public List<Pair> getMax(int[] numbers) {
     List<Pair> pairs = new ArrayList<>(numbers.length);
     int i = 0;
     int j = i + 1;
     while(numbers.length - j > i) {
           if(isValidPair(i, i+1)) {
                pairs.add(new Pair(numbers[i], numbers[j]));
           }

           if(isValidPair(numbers.length - 1 - j, numbers.length - 1 - i)) {
                pairs.add(new Pair(numbers[numbers.length - 1 - j], numbers[ numbers.length - 1 - i]));
           }
           i++;
     }
     return elements.size();
}

public boolean isValidPair(int i, int j) {
     int maxOne = numbers[i];
     int maxTwo = numbers[j];
     return Math.abs(maxOne - maxTwo) < Math.abs(i, j));
}

public class Pair {
     private int first;
     private int second;

     public Pair(int first, int second) {
          this.first = first;
          this.second = second;
     }

     public int getFirst() {
          return this.first;
     }

     public int getSecond() {
          return this.second;
     }

}

- Josh October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n/2) -> O(n). Works by starting from both ends and calculating and meeting in the middle.

public List<Pair> getMax(int[] numbers) {
     List<Pair> pairs = new ArrayList<>(numbers.length);
     int i = 0;
     int j = i + 1;
     while(numbers.length - j > i) {
           if(isValidPair(i, i+1)) {
                pairs.add(new Pair(numbers[i], numbers[j]));
           }

           if(isValidPair(numbers.length - 1 - j, numbers.length - 1 - i)) {
                pairs.add(new Pair(numbers[numbers.length - 1 - j], numbers[ numbers.length - 1 - i]));
           }
           i++;
     }
     return elements.size();
}

public boolean isValidPair(int i, int j) {
     int maxOne = numbers[i];
     int maxTwo = numbers[j];
     return Math.abs(maxOne - maxTwo) < Math.abs(i, j));
}

public class Pair {
     private int first;
     private int second;

     public Pair(int first, int second) {
          this.first = first;
          this.second = second;
     }

     public int getFirst() {
          return this.first;
     }

     public int getSecond() {
          return this.second;
     }

}

- Josh October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

| A[i] - A[j] | > | i-j |
| A[i] - A[j] | - | i-j | > 0

Four cases arise:

a) (A[i] - i) > (A[j] - j)
b) (A[i] - i) > (A[j] + j)
c) (A[i] + i) > (A[j] - j)
d) (A[i] + i) > (A[j] + j)

for case a) replace A[i] in array by X[i] i.e A[i]-i
thus we need to get all elements where
X[i] > X[j]
which is an O(n) algo using Hash table

- kevseb1993 October 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just to comment a bit on the NP-Completeness suggested by anonymous:

You can define a graph where each node represents an array element, and a vertex between two nodes indicates that these two elements can be picked simultaneously. The solution of the problem is then the maximal set of nodes where each node in the set is connected to all other nodes in the set. Finding this set is called the maximum clique problem, which is NP-Complete for a general graph. However, if you follow the rules to determine compatible pairs of array elements the graph you obtain is a comparability graph (See wikipedia). This particular type of graph that has the property that there exists an ordering of the nodes for which, if there is a vertex between i and j and a vertex between j and k (i < j < k) then there is a vertex between i and k. For this specific type of graph the clique problem actually has an efficient solution, which can be calculated by a DFS search.

- Marc Serra October 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static Set<Integer> getListFollowingeRules(int[] arr){
if(arr == null || arr.length <= 1){
throw new RuntimeException("Input array is null or is empty or has 1 vale");
}
Set<Integer> outputList = new HashSet<Integer>();
for(int i = 0; i < arr.length - 1; i++){
int j=i+1;
while(j <=arr.length -1){
if(Math.abs(i - j) >= Math.abs(arr[i] - arr[j])){
outputList.add(arr[i]);
outputList.add(arr[j]);
}
j++;
}
}

return outputList;

- tesnik03 October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution{
	public int count(int nums[]){
		int max=  1;
		int count = 1;
		for(int i = 1;i<nums.length;i++){
			if(nums[i]-nums[i-1]>1){
				max = Math.max(max, count);
				count = 1;
				continue;
			}
			count++;
		}
		max=  Math.max(count, max);
		return max;
        }

}

- Zhassan November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def pick_elems(arr):
    arr_len = len(arr)
    sol = [1]*arr_len
    for i in xrange(1, arr_len):
        for j in xrange(i):
            if abs(a[i] - a[j]) <= abs(i- j):
                sol[i] = max(sol[i], sol[j] + 1)
    
    print max(sol)
              
a = [1,3,5,4]
pick_elems(a)

- Nitish Garg January 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int count=0;
        for(int i=0; i<arr.length-1;i++){
            for(int j = i+1; j<arr.length;j++) {
                if (Math.abs(arr[i] - arr[j]) > Math.abs(i - j)) {
                    continue;
                } else {
                    count+=2;
                }
            }
        }
        return count;

- Anonymous September 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


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