Google Interview Question Software Engineers
Country: India
Interview Type: In-Person
// MaxPrefix.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
//#include <vector>
#include <queue>
using namespace std;
struct Comparator;
class Node {
public:
friend Comparator;
Node(int value, int initiaIndex);
bool operator < (const Node & rhs);
//private:
int _value;
int _initialIndex;
};
Node::Node(int value, int initiaIndex) : _value(value), _initialIndex(initiaIndex){
}
struct Comparator
{
bool operator()(Node * i, Node * j){
if(i->_value > j->_value){
return true;
} else if(i->_value == j->_value) {
return i->_initialIndex > j->_initialIndex;
}
return false;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
priority_queue<Node *, std::vector<Node *>, Comparator> minHeap;;
minHeap.push(new Node(-3,0));
minHeap.push(new Node(0,1));
minHeap.push(new Node(2,2));
minHeap.push(new Node(4,3));
minHeap.push(new Node(10,4));
minHeap.push(new Node(-4,5));
minHeap.push(new Node(6,6));
minHeap.push(new Node(2,7));
minHeap.push(new Node(8,8));
minHeap.push(new Node(9,9));
minHeap.push(new Node(4,10));
int maxPrefix = 0;
while(minHeap.size() > maxPrefix){
Node * node = minHeap.top();
minHeap.pop();
if(minHeap.size() - node->_initialIndex > maxPrefix){
maxPrefix = minHeap.size() - node->_initialIndex;
}
}
printf("%d", maxPrefix);
getchar();
return 0;
}
Here's my solution
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int n,i,j,count,max=0;
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
int[] arr=new int[n];
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
for(i=0;i<n-1;i++){
count=0;
if(max>i)
break;
for(j=i+1;j<n;j++){
if(arr[i]<arr[j])
count++;
}
if(count>max){
max=count;
}
}
System.out.println(max);
}
}
O(nlogn) Solution - Create a Min Heap O(n), Extract Minimum elements n times : n * O(logn)
We don't need to traverse the Input Array, Once Heap is built.
Intuition : Always look for the smallest element from right. For an example, if smallest
value appears at index j then the MaxPrefix can never start from an index k>j.
Step Wise Algorithm:
1. Create a Min Heap(Containing Both Index in the input array and its value) using input array
2. Extract min element from the Heap: Lets say its index in input array was i, then ans=(n-i)
3. m=1 (Next Time, extracted minimum will be m+1th i.e. 2nd Smallest Element Over All)
4. Extract min element from the heap: It gives m+1th smallest Element Over All.
Lets say its index in input array was j, then if j>i, then j can not be a part of the solution.
However, j<i, then ans=max(ans,n-i-m) and i=j
5. m++
6. GO TO STEP 4
public int findMaxPrefix(int[] input) {
if (input == null || input.length == 0) {
return -1;
}
int max =0;
int j=0;
List<Integer> integerList = new ArrayList();
for(int num: input){
int current=0;
for(int i=j+1; i<input.length; i++){
if(input[i]>num){
current++;
}
}
j++;
integerList.add(current);
}
return Collections.max(integerList);
}
Use an AVL tree where the nodes have 3 attributes-an int value from the array, the size of the left subtree, the size of the right subtree. Traverse the array from right to left, for each element, insert it into the AVL tree and also compute the number of values greater then this value. Keep a variable that stores the maximum prefix size and update as new values are inserted into the AVL tree.
Here is the solution. Worst case complexity is O(n * n), but tends to O(n) in average case.
int max-maxPrefix(int a[], int n) {
int temp, i;
int result = maxPrefix(a, 0, n);
int pivot = a[0];
for (i = 1; i < n - 1; i++) {
if (a[i] >= pivot)
continue;
if (n - i - 1 <= result)
break;
temp = maxPrefix(a, i, n);
if (temp > result) {
result = temp;
pivot = a[i];
}
}
return result;
}
int maxPrefix(int a[], int index, int n) {
int result = 0, i;
for (i = index + 1; i < n; i ++)
if (a[i] > a[index])
result ++;
return result;
}
This simple solution has worst-case complexity O(n*n), but average case is O(n).
* Start from left, first element is pivot point
* Skip the number, if it is greater than pivot, pivot's maxPrefix would be more than this.
* Skip the last few numbers, when we can't get a better maxPrefix than current one.
int max-maxPrefix(int a[], int n) {
int temp, i;
if (n <= 0)
return -1;
int result = maxPrefix(a, 0, n);
int pivot = a[0];
for (i = 1; i < n - 1; i ++) {
if (a[i] >= pivot)
continue;
if (n - i - 1 <= result)
break;
temp = maxPrefix(a, i, n);
if (temp > result) {
result = temp;
pivot = a[i];
}
}
return result;
}
int maxPrefix(int a[], int index, int n) {
int result = 0, i;
for (i = index + 1; i < n; i ++)
if (a[i] > a[index])
result ++;
return result;
}
package com.google;
public class MaxOfRightInt {
public static void main(String args[]){
int[] array = {10, -4, 6, 2, 8, 9, 4};
int[] maxOfEach = new int[array.length];
int big = 0;
for(int i=0; i< array.length; i++) {
int j = i;
while (j< array.length){
if(array[j] > array[i]){
maxOfEach[i]++;
}
j++;
}
if(maxOfEach[i] > big){
big = maxOfEach[i];
}
}
System.out.println (big);
}
}
package com.google;
public class MaxOfRightInt {
public static void main(String args[]){
int[] array = {10, -4, 6, 2, 8, 9, 4};
int[] maxOfEach = new int[array.length];
int big = 0;
for(int i=0; i< array.length; i++) {
int j = i;
while (j< array.length){
if(array[j] > array[i]){
maxOfEach[i]++;
}
j++;
}
if(maxOfEach[i] > big){
big = maxOfEach[i];
}
}
System.out.println (big);
}
}
Average Case - O(n) solution:
function findMaxPrefix(arr) {
if (arr == null || arr.length < 2) {
return 0;
}
var maxPrefix = 0;
var tempPrefix = 0;
var start = 0;
var i = start+1;
while( i < arr.length) {
if (arr[start] <= arr[i]) {
tempPrefix++;
i++;
} else {
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
tempPrefix = 0;
start = i;
i = start+1;
}
}
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
return maxPrefix
}
Average case O(n) solution:
function findMaxPrefix(arr) {
if (arr == null || arr.length < 2) {
return 0;
}
var maxPrefix = 0;
var tempPrefix = 0;
var start = 0;
var i = start+1;
while( i < arr.length) {
if (arr[start] <= arr[i]) {
tempPrefix++;
i++;
} else {
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
tempPrefix = 0;
start = i;
i = start+1;
}
}
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
return maxPrefix
}
function findMaxPrefix(arr) {
if (arr == null || arr.length < 2) {
return 0;
}
var maxPrefix = 0;
var tempPrefix = 0;
var start = 0;
var i = start+1;
while( i < arr.length) {
if (arr[start] <= arr[i]) {
tempPrefix++;
i++;
} else {
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
tempPrefix = 0;
start = i;
i = start+1;
}
}
if (tempPrefix > maxPrefix) {
maxPrefix = tempPrefix;
}
return maxPrefix
}
I believe an O(nlogn) solution should be like:
I am assuming we have a SortedList class which has the necessary binary search which gives the correct location to insert the item even if it is not in the list, and sortedAdd functions both working in O(log n) time. Also assuming the SortedList is in descending order.
SortedList sortedList = new SortedList();
int maxNum =-1;
int maxVal = -1;
for(int i=arr.length-1;i>=0;i++)
{
int numGreat = sortedList.binarySearch(arr[i]); // log n
if(numGreat > maxVal)
{
maxVal = numGreat;
maxNum = arr[i];
}
sortedList.sortedAdd(arr[i]);//log n
}
return maxNum;
This problem can be solved with complexity O(n) using deque: d[i] is the closest number on the right that is greater than numbers[i]:
Class NumberManager {
public:
numberManager(vector<int> nums){
numbers = nums //=========> copy vector, simple a = b
initializeDeque();
}
int maxPrefix(int pos) {
return d[pos];
}
private:
vector<int> numbers; //list of numbers
vector<pair<int, int>> d; //deque
void initializeDeque(){
for(int i = numbers.size() - 1; i >= 0; i--){
while (!d.empty() && numbers[i] >= d.end()->first){
d.pop_back();
}
if (d.empty()) {
d.push_back({number[i], 0});
} else {
d.push_back({number[i], d.end->second + 1});
}
}
}
};
@alokkumar since I cant post reply to your comment:
Consider the array: {6,3,5,2,4,0,-1} , n = 6 (-1 indicates null)
MinHeap of indexes with min element: 5,3,1,4,2,0 (these are indexes so arr[5] = 0)
Step 1: m = 0, minElement: index = 5, element = 0, ans = 6-5-1 = 0 (i think there is a typo in step 1 of your algo)
minHeap = {3,4,1,-1,2,0,-1}, i = 5
Step 2.1: m=1, minElement: index = 3, element = 2, ans = max(ans, 6 - 5 - 1) = 0 which is correct there are no element on the right of 2 greater than 2
minHeap = {1,4,0,-1,2,-1,-1}, i = 3
Step 2.2: m=2, minElement: index = 1, element = 3, ans = max(ans, 6-3-2) = 1 which is wrong there are 2 elements on the right greater than 3 (5 and 4) so this algo doesnt work.
Can you please tell me if I have misunderstood something? Thanks
O(nlogn) algorithm using segment tree:
1. create a copy of the given array and sort it.
2. generate a mapping between the indices of original and sorted array.
3. create a range sum segment tree with all leaf node values as 0 (deactivated)
4. On the original array iterate from right to left and for each element get the mapped index value as pos:
query range sum for the range (pos+1,n)
Check if this value is the maximum yet found.
update pos in segment tree to value 1 (activated)
This is O(n) solution:
public void maxPrefix(int[]a){
int minSoFar=a[0];
int currentMin=a[0];
int maxPrefixSoFar=0;
int currentMaxPrefix=0;
for(int i=1; i<a.length; i++){
if(a[i]>currentMin){
currentMaxPrefix++;
}else{
if(currentMaxPrefix>maxPrefixSoFar){
maxPrefixSoFar=currentMaxPrefix;
minSoFar=currentMin;
}
if((a.length-i-1)<maxPrefixSoFar){
break;
}
currentMin=a[i];
currentMaxPrefix=0;
}
}
if(currentMaxPrefix>maxPrefixSoFar){
maxPrefixSoFar=currentMaxPrefix;
minSoFar=currentMin;
}
System.out.println("Element:\t"+minSoFar);
System.out.println("MaxPrefix:\t"+maxPrefixSoFar);
}
public class MaxPrefix{
public int maxPrefix(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int min = arr[arr.length - 1];
int count = 0;
int max = 0;
int n = arr.length;
for (int i = arr.length -2; i >= 0; i--) {
if (arr[i] < min) {
max = Math.max(max, n - i -1);
min = arr[i];
}
}
return max;
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class MaxPrefixTest{
@Test
public void maxPrefixTest1() {
int[] arr = {10,-4,6,2,8,9,4};
int expected = 5;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest2() {
int[] arr = {1,2,2,2,3,3,4};
int expected = 6;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest3() {
int[] arr = {4,3,2,1,0};
int expected = 0;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest4() {
int[] arr = {0,0};
int expected = 0;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
}
just keep the minimum traversing from right side of the array, every time you encounter new minimum update the count. this will be O(n), I would be happy if people comment about the correctness of this algo
package com.interview.array;
public class MinimumLengthWord {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {10, -4, 6, 2, 8, 9, 4};
int max = 0;
int count = 0;
for (int i = 0; i < arr.length - 1; i++) {
if (arr.length - i < max) {
break;
}
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i])
count++;
}
if (count > max) {
max = count;
}
count = 0;
}
System.out.println(max);}}
Really simple solution. Just find the minimum element and calculate the count.
function maxPrefix(arr) {
var count = 0;
var min = arr[arr.length - 1];
for (var i = arr.length - 2; i >= 0; i--) {
var num = arr[i];
if (num < min) {
min = num;
count = arr.length - 1 - i;
}
}
return count;
}
Construct AVL tree starting from rightmost element of the array. Maintain and update count of element greater than currently inserted element. Compare the result of count after each insertion, to get the max.
- Saheb Preet singh June 19, 2016