PayPal Interview Question for Member Technical Staffs


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.
Please double test the code.
runtime O(n)
worstcase aux space O(n)

- S O U N D W A V E October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E October 23, 2013 | Flag
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.

- krshnsh October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- krshnsh October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it only compiles on one platform: back of envelope

- S O U N D W A V E October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- micvog October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@micvog, try it on paper

- Urik's twin Cookie Monster (dead now) October 27, 2013 | Flag
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) ?

- rams May 07, 2015 | Flag
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)
	answer[i] = -1;

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();
while(!still_without_answer.empty()&&input[smallest_without_answer]<input[i])
{
	answer[smallest_without_answer ] = input[i];
	still_without_answer.pop();
}
int smallest_number_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).

- Darida October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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])
{
	answer[smallest_without_answer ] = input[i];
	still_without_answer.pop();
}

- Nirmisha October 24, 2013 | Flag
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;
}

- Krzysztof.G October 23, 2013 | Flag Reply
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)

- Anonymous October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

LOL!

- Anonymous October 23, 2013 | Flag
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] + " ");

}

}


}

- Anonymous October 24, 2013 | Flag Reply
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] + " ");

}

}


}

- Anonymous October 24, 2013 | Flag Reply
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;
}
}

- Anonymous October 24, 2013 | Flag Reply
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+" ");
		}
	}

- shashi_kr October 26, 2013 | Flag Reply
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))

- Anonymous October 26, 2013 | Flag Reply
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).

- Cleonjoys November 12, 2013 | Flag Reply
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;
}
}
}

- dev February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * To change this license header, choose License Headers in Project Properties.
 * 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]+" ");
        }
    }
    
    
}

- Anonymous March 19, 2014 | Flag Reply
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)));
		
	}
	
}

- screwthatinterview April 10, 2014 | Flag Reply
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;
}
}

- Manjunath J June 20, 2014 | Flag Reply
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);

}

- Francis February 25, 2015 | Flag Reply
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 +" ");
}

}

}

- Ritesh July 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int main() {
// your code goes here
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;
}

- roypathik8 October 14, 2015 | Flag Reply
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); 
		result.add(nums[len-1]);
		for ( int i = len-2; i>= 0; i--) {
			while(!q.isEmpty() && nums[i] > nums[q.peekLast()] ) {
				q.pollLast();
			}
			if ( q.isEmpty()) {
				result.add(0, nums[i]);
			}else {
				result.add(0, nums[q.peekLast()]);
				q.add(i);
			}
		}
		return result; 
	}

- cji February 22, 2018 | Flag Reply
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);
    	}
    }
}

- Anonymous February 08, 2019 | Flag Reply
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);
    	}
    }
}

- hpatel100@hawk.iit.edu February 08, 2019 | Flag Reply
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] + " ");

}

}


}

- Anonymous October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chandu October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Please correct me if I am wrong

- Dibyendu October 23, 2013 | Flag Reply
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 );
}
}

- m@}{ October 23, 2013 | Flag Reply
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

- Sonny Wicaksono October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Anonymous October 31, 2013 | Flag
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
of 0 votes

Your solution has O(N^2) time.

- m@}{ October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
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