Google Interview Question
Software EngineersCountry: United States
Interview Type: Written Test
//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;
}
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);
}
}
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);
}
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
}
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;
}
}
| 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
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.
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;
Seems to me like a variant of longest increasing subsequence problem
- CodeTillDeath September 25, 2016