## PayPal Interview Question for Member Technical Staffs

• 4

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
11
of 11 vote

Try some cases brute force on paper, then when you try this case you get the idea
: 4 3 2 1 2 3 4
And it it clear from question itself that the alg. you should scan from right to left.
DS needed is a stack..

And also, as I'm coding I realize we should have sentinel value like INF (you can replace with whatever, maybe even replace with a[i] at that point) when no result exists (especially the rightmost answer):

call invocation of this stack, S:

``````for( i = N-1; i>=0; i-- )
{
while( !S.isEmpty && a[i] >= S.checkTop() )  //try to find > a[i] element
S.pop();

if( S.isEmpty )
result[i]= INF;  //nothing > a[i] to right  (or use a[i] instead of INF)
else
result[i]= S.checkTop();    //this was > a[i] to right

S.push(a[i]);
}``````

Find the bugs.
runtime O(n)
worstcase aux space O(n)

Comment hidden because of low score. Click to expand.
0

Also, folks,
There are some more obvious O(nlogn) solutions that you can work out on paper too that can be a second iteration on design/optimization of runtime over N^2 worst case brute force.

N^2->NlgN ->N

Comment hidden because of low score. Click to expand.
1
of 1 vote

Does not work for 1 5 4 3 5 1 2.
We cannot pop and discard all smaller values like that.
What if a larger values empties the stack. This way it throws away values that may be needed later as in my example.

Comment hidden because of low score. Click to expand.
0

Actually it is correct if nearest means by position rather than value. So I guess you are right. I thought nearest means by value.

Comment hidden because of low score. Click to expand.
0

it only compiles on one platform: back of envelope

Comment hidden because of low score. Click to expand.
0

Looks like the n*logn brute-force is equivalent to this one. Your while loop adds an additional logn complexity no?

Comment hidden because of low score. Click to expand.
0

@micvog, try it on paper

Comment hidden because of low score. Click to expand.
1
of 1 vote

Is it really o(n), For every element v r coparing with all elements in stack till we get greater element. looks like o(n^2) ?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, we have

``int input[n] = {7, 5, 6, 3, 4, 1, 2, 9, 11};``

we want to get

``````int answer[n]; // = {9, 6, 9, 4, 9, 2, 9, 11, -1}
for(int i=0; i<n; ++i)

I mark numbers that doesn't have bigger at right side as -1.
We can replace -1 with anything we need later.

We will save all positions, for which we still didn't find answers in stack.
At the start, stack is empty.

``stack<int> still_without_answer;``

Now, we are going to iterate throw the array.

``for(int i=0; i<n; ++i)``

For each number, we will find all numbers on the left sife, that less then current.
We will delete them from the stack.
So after that, all numbers in the stack will be bigger then current.
That mean that our stack is decreasing order and we can check only the top value, instead of iteration throw stack.

``````int smallest_without_answer = still_without_answer.top();
{
}

After setting current number as answer for smaller numbers, we push them to stack. Now it is the smallest number without answer.

``still_without_answer.push(i);``

This is O(n), becouse we iterate 1 time throw each elements, 1 time put each element to the stack for O(1), and 1 time delete from the stack for O(1).

Comment hidden because of low score. Click to expand.
0

Good One!

But just a small bug...

The second condition in your while loop should always take the top element from stack...

``````while(!still_without_answer.empty()&&input[still_without_answer.top()]<input[i])
{
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Complete example in C++11. Should be O(n):

``````#include <iostream>
#include <vector>
#include <iterator>
#include <sstream>
#include <algorithm>

void findMax(std::vector<int> &v, unsigned int& idx)
{
unsigned int currIdx = idx++;

do {
if (idx == v.size()) return;
if (v[currIdx] < v[idx]) {
v[currIdx] = v[idx];
return;
}
findMax(v, idx);
} while (true);
}

void SetNearestMax(std::vector<int> &v)
{
unsigned int idx = 0;
while (idx < v.size() - 1)
{
findMax(v, idx);
}
}

int main()
{
std::vector<int> v = {7, 5, 6, 3, 4, 1, 2, 9, 11};

std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
SetNearestMax(v);
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

nested for loops make o(n^n) and for loop + for loop make o(n) right/?
for()
{
for()
{
}
}
above is o(n^n)

but

for()
{

}
for()
{
}
the above code gives o(n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

LOL!

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void ReplaceWithMax2Right(int *a)
{
if(a==NULL)
return;
int n=sizeof(a)/sizeof(a[0]);
int max=a[n-1];
for(int i=n-2;i>=0;i--)
{
int tmp=a[i];
a[i]=max;
if(max<tmp)
max=tmp;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void greNext(int []A){
int l=A.length;
int j=1;
Stack eleA=new Stack();
Stack index=new Stack();

eleA.push(A[0]);
index.push(0);

while(j<l){
while(!eleA.isEmpty() && A[j]>eleA.getTop()){
A[index.pop()]=A[j];
eleA.pop();
}

eleA.push(A[j]);
index.push(j);
j++;
}

if(j==l){
while(!index.isEmpty()){
A[index.pop()]=eleA.pop();
}
}

for(int a:A){
System.out.print(a+" ");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I do not think this problem can be solved in O(n) time. The best I can think of is O(n*log(n)*log(n))

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am wondered nobody thought of this, try solving problem from right end, you can do it in O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

if i give the input as 7,5,6,15,4,1,2,9,11 then the output should be 15,6,15,15,9,11,11 i guess. but iam getting 15,6,15,INF,9,2,9,11,15.
please correct me if iam wrong.

can't we use the below code, iam not sure about the complexity,
for(int i=0;i<a.length-1;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[j]>a[i])
{
a[i]=a[j];
break;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

package interview;

import java.util.Scanner;
import java.util.Stack;

/**
*
* @author
*/
public class NextBigNumber {
private int array[];

private Stack<Integer> stack;
public NextBigNumber()
{
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
array = new int[n];
for(int i = 0;i<n;i++)
array[i] = sc.nextInt();
stack = new Stack<Integer>();
}

public void arrange()
{
stack.push(array[array.length-1]);
for(int i=array.length-2;i>=0;i--)
{
int current = array[i];
if(current<=stack.peek())
{
array[i]=stack.peek();
stack.push(current);
}
else
{
while(!stack.empty() && current > stack.peek())
{
stack.pop();

}
if(!stack.empty())
{
array[i]=stack.peek();

}
stack.push(current);
}
}
}

public void print()
{
for(int i = 0;i<array.length;i++)
{
System.out.print(array[i]+" ");
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

just another solution:

``````public class Replace {

Stack<Integer> store = new Stack<Integer>();
int[] input;

public int[] replace(int[] inputArr){
input = inputArr;
replaceHelper(input[input.length-1], input.length-2);
return input;
}

private void replaceHelper(int curr_max, int index){
System.out.println("index: "+index);
System.out.println("curr_max: "+curr_max);
if(index<0) return;
if(curr_max>input[index]){
int next_max=input[index];
input[index] = curr_max;
store.push(curr_max);
//curr_max = input[index];
System.out.println("next_max: "+next_max);
System.out.println("--------------------");
replaceHelper(next_max,--index);
}
else if(!store.isEmpty()){
int prev_max = store.pop();
System.out.println("prev_max: "+prev_max);
System.out.println("--------------------");
replaceHelper(prev_max,index);
}
}

public static void main(String[] args){
Replace rep = new Replace();
int[] inputArr = {7,5,6,3,4,1,2,9,11};
System.out.println("replaced array is: "+Arrays.toString(rep.replace(inputArr)));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ReplaceNearestBiggestNumberArray {

public static void main(String args[]){
int[] origianlArr = {7, 5, 6, 3, 4, 1, 2, 9, 11};
ReplaceNearestBiggestNumberArray in = new ReplaceNearestBiggestNumberArray();
for(int i=0;i<origianlArr.length-1;i++){
origianlArr[i]= in.getNearestBiggestNumArray(origianlArr,i+1,origianlArr[i]);
}
for(int j=0;j<origianlArr.length;j++){
System.out.print(origianlArr[j]+" ");
}
}

public int getNearestBiggestNumArray(int[] arr, int start, int num){
for(int i=start;i<arr.length;i++){
if(num < arr[i]){
return arr[i];
}
}
return 0;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void printArrayWithFirstRightMaximum(int[] a) {
int i = 0;
int j = i+1;
while(i<a.length && j<a.length) {
if(a[i] < a[j]) {
a[i] = a[j];
i++;
j=i+1;
} else {
if(j == a.length-1) {
i++;
j=i+1;
}
j++;
}
}
printArray(a);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LargestRightsideNumber {

public static void main(String[] args) {

int[] arr ={7, 5, 6, 3, 4, 1, 2, 9, 11 };
for(int i=0; i<arr.length-1;i++){

int j=i;
while(arr[i] > arr[j+1]){
j++;
}

arr[i]=arr[j+1];

}

for(int i :arr){
System.out.print(i +" ");
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
using namespace std;

int main() {
int a[]={7,5,6,3,4,1,2,9,11};
int n=sizeof(a)/sizeof(a[0]);
cout<<n<<endl;
vector<int>ans;
ans.push_back(a[n-1]);
stack<int>s;
for(int i=n-2;i>=0;i--)
{
if(a[i]<a[i+1])
{
ans.push_back(a[i+1]);
s.push(a[i+1]);
}
else
{
while(s.top()<=a[i])
{
s.pop();
}

ans.push_back(s.top());
s.push(a[i]);
}
}
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static ArrayList<Integer> rightsideNearestMaximum(int[] nums){
ArrayList<Integer> result = new ArrayList<>();

int len = nums.length;

Deque<Integer> q = new ArrayDeque<>();
q.offer(len-1);
for ( int i = len-2; i>= 0; i--) {
while(!q.isEmpty() && nums[i] > nums[q.peekLast()] ) {
q.pollLast();
}
if ( q.isEmpty()) {
}else {
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class EatenLives{
public static void main(String[] args)
{
boolean flag = false;
int input[] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
for(int i = 0; i<input.length - 1; i++)
{
for(int j = i+1; j<input.length; j++)
{
if(input[i] < input[j] && flag != true)
{
input[i] = input[j];
flag = true;
}
}
flag = false;
}
for(int ip : input)
{
System.out.println(ip);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class EatenLives{
public static void main(String[] args)
{
boolean flag = false;
int input[] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
for(int i = 0; i<input.length - 1; i++)
{
for(int j = i+1; j<input.length; j++)
{
if(input[i] < input[j] && flag != true)
{
input[i] = input[j];
flag = true;
}
}
flag = false;
}
for(int ip : input)
{
System.out.println(ip);
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}

}

Comment hidden because of low score. Click to expand.
0

Is this code of o(n^n) or o(n) ???

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Please correct me if I am wrong

Comment hidden because of low score. Click to expand.
-2
of 2 vote

/**
* time: O(N)
* space: O(N)
*/
void replaceWithBiggestFromRight( int[] arr ){

Deque<Integer> biggestRight = new ArrayDeque<>();

for( int i = arr.length-1; i >=0; i-- ){

int temp = arr[i];

while( ! biggestRight.isEmpty() && biggestRight.peekFirst() <= arr[i] ){
biggestRight.pop();
}

if( ! biggestRight.isEmpty() ){
arr[i] = biggestRight.peekFirst();
}

biggestRight.push( temp );
}
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Heres a method i wrote in ruby. You use a stack, and you go through each element in the array once and push and pop an element once so it should all be O(n)

def replace(array)
stack = Array.new
stack.push(array[array.size-1])
(array.size-2).downto(0) do |i|
while array[i] > stack[stack.size-1] do
stack.pop
if stack.size == 0
break
end
end
stack.push(array[i])
array[i] = stack[stack.size-2]
end
return array
end

Comment hidden because of low score. Click to expand.
0

Best solution is O(n) and uses a stack; the idea is to keep pushing numbers on the stack until we find a number x that is bigger than the top of the stack; then we pop all numbers that are smaller than x and set x to be their first bigger number. Below a c++ implementation:

``````#include <stack>
#include <vector>

std::vector<int> nearest_higher_right(const std::vector<int>& V) {
std::vector<int> result(V.begin(), V.end());
std::stack<std::pair<int, int> > my_stack;

int i = 0;
while (i < V.size()) {
if (my_stack.empty() || my_stack.top().second >= V[i]) {
my_stack.push(std::make_pair<int,int>(i, V[i]));
++i;
} else {
while (!my_stack.empty() && my_stack.top().second < V[i]) {
std::pair<int,int> item = my_stack.top();
result[item.first] = V[i];
my_stack.pop();
}
}
}

return result;
}``````

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.

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.

### 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.