Adobe Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

Here is an O(nlogn) [amortized] approach using a threaded BST where each node points to the next in order successor.
1) read the array from right to left
2) Insert each element into a threaded BST.
3) Output the inorder successor after each insertion.

Perhaps we could reshape the threaded tree in between to make it balanced and increase performance but am not sure if we can modify a threaded tree.

- kr.neerav July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I thought the same thing. its the best solution so far..

- rupani5990 July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you explain in more details

- ryaan July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure ryaan
The brute force solution O(n^2) does not structure the data in any way. So to optimize it lets try to bring a structure in the data. The operation to optimize is the linear search of the next greater element to the right, currently O(n). If all the elements on the right were in the form of a BST the search would take O(logn) time (if the BST was threaded. please lookup on internet for more information about binary threaded tree). So we start by building the tree from the right of the array (step 1) Each time we insert a new element in the BST we find out its successor which is the output we desire.
I have mentioned it as amortized performance as its not a balanced BST that we are using. Am not sure if we can build a balanced threaded BST.
Hope it helps

- kr.neerav July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 votes

Just a balanced tree is enough to give an O(nlogn) (guaranteed) algorithm. No need for threaded tree. You can always find the required number in O(log n) time in a "normal" balanced tree.

- Anonymous July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yup you are right we can extract the inorder successor from a BST in logn time. So we will use the balanced BST instead of a threaded BST.

- kr.neerav July 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your logic doesn't seems to be correct. Being in-order successor only means the next largest number to the given number. In the question it's asked to find the the next largest number which is on the right-side.

- santoshgupta.nits July 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is not considering , if a number has appered before or after in the list.
just replacing with next greater number.

- Anonymous September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* time: O: (N*lgN)
	 * space: O(N)
	 */
	
	private int[] nearestBiggerToRight(int[] arr){
		int[] sol = new int[arr.length];
		NavigableSet<Integer> tree = new TreeSet<>();
		
		for( int i = arr.length-1; i >= 0; i-- ){
			Integer greater = tree.higher(arr[i]);
			sol[i] = greater == null ? -1 : greater;
			tree.add(arr[i]);
		}
		return sol;		
	}

- m@}{ July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution O(nlogn)

std::vector<int> solve(const std::vector<int> &input) 
    {
        std::vector<int> output(input.size());
        std::set<int> sorted;
        int lastIndex = int(input.size() - 1);
        for( int i = lastIndex; i >= 0; --i)
        {
            auto iter = sorted.upper_bound(input[i]);
            if( iter == sorted.end())
            {
                output[i] = -1;
            }
            else
            {
                output[i] = *iter;
            }
            sorted.insert(input[i]);
        }
        return output;
    }

- raj July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Solution would be, breate a binary search tree from the given array.
Now from pick one element, find it's inorder successor, delete it from tree and continue this till you get empty tree.

- instance July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<stack>
using namespace std;

void nextgreaterelement(int a[],int n)
{
    stack<int> s;
    int next,element;
    s.push(a[0]);
    for(int i=1;i<n;i++)
    {
        next=a[i];
        if(!s.empty())
        {
            element=s.top();
            s.pop();
            while(element<next)
            {
                cout<<element<<"->"<<next<<endl;
                if(s.empty())
                break;
                element=s.top();
                s.pop();
            }
            if(element>next)
            s.push(element);
        }
        s.push(next);
    }
    while(!s.empty())
    {
        element=s.top();s.pop();
        cout<<element<<"->"<<"-1"<<endl;
    }
}

- Anonymous July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will give you the immediate value which is greater than the current node not the least one on right side.

- Geekyprateek August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nLogn) solution using C++ map (BST). Scanning the array from right to left, insert the element into the map (BST). If the element inserted is the max., then print -1, else print the next highest element. This could also have been achieved using PriorityQueue in C++.

Note that the output is in reverse order.

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

int main(int argc, char const *argv[])
{
	int n, temp;
	cin>>n;
	std::map<int, bool> m;
	vector<int> in;
	for (int i=0; i<n; i++)
	{
		cin>>temp;
		in.push_back(temp);
	}
	for (int i = n-1; i >= 0; --i)
	{
		temp = in[i];
		pair<map<int, bool>::iterator,bool> p = m.insert(make_pair(temp,true));
		
		if(!m.empty() && (p.first)->first != (m.rbegin())->first)		//checking if the new element added is not the highest
			cout<<(++p.first)->first<<"\t";
		else	
			cout<<"-1\t";
	}
	return 0;
}

- sc.shobhit July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you use PriorityQueue? Please enlighten us.

- Anonymous July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

best solution is by using binary search tree.
Insert all the elements in to BST. this takes O(N)
Now go through the array and find its successor,(this will be the leftmost leaf, in its right subtree, if it has left subtree, or parent node, or null) and replace it with successor if exits or delete the element. this will take O(NlogN)
total time will be O(NlogN)

- satish July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude insertion into bst only takes O(nlogn)

- progeek July 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can be done much much simpler in O(n) by looking it from right to left.

/*
Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. 
Since there is no element next to the last element, replace it with -1. For example, if the array is {16, 17, 4, 3, 5, 2}, 
then it should be modified to {17, 5, 5, 5, 2, -1}.
*/
 
// O(n) run time 
int[] replaceNextGreaterElement(int[] in){
    if(in==null)
        return null;
    //the last element in the array will always be -1 as there is no element to the right of it.
    // the last element is the greatest from the right at this point.
    int max_from_right=in[in.length-1];
    in[in.length-1]=-1;
    
    //now walk from right to left.
    for(int i =in.length-2;i>=0;i--)
    {
        //store current element in temp.
        int temp=in[i];
        in[i]=max_from_right;
        
        //update max if needed 
        if(temp>max_from_right)
        {
            max_from_right=temp;
        }
    }
    
    return in;
}
 
//adapted from geeksforgeeks

- KodeSeeker July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LEAST GREATER ELEMENT. ARE YOU DOING THAT?

YOU ARE DOING LEFTMOST GREATER ELEMENT ARENT YOU?

- Anonymous July 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're not following the requirements. You have to replace every element with an element that was originally to the right of it AND that element must be greater than it.

- Raghav July 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The inorder traversal method is incorrect. In the example in the questionm 43 should be replaced with 80 but the inorder successor in the tree is 58. The inorder successor does not have any relation to how the elements appear in the actual array.
The trick is start inserting elements into a BST from the right. On insertion, remember the most recent left child path you took while inserting the current element. The node you last took the left child of is the value we replace the current element with.
The invariant is on inserting element at index i, the only elements in the BST are the elements at index > i.
The last "left turn" node keeps track of the smallest number greater than curr element.
If no left turns are taken, replace it with -1.
Time complexity is O(n^2) if numbers are sorted in ascending order from left to right.
A balanced binary tree will O(n log n)

- deadbeef21 July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can scan the array from left to right
for each item
rank<- find the rank of that item
find the item i<-from array which has the rank (rank+1);
then base on i's value
replace iteam.
end for.

- AMU July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ArrayPlacement::rightMax( vector<int> & arr)
{
	set<int> mset(arr.begin(), arr.end()); //O(n)
	for( unsigned i = 0; i < arr.size(); ++i )//n times
	{
		auto itr = mset.find(arr[i]);//O(log n)
		itr++; 
		if( itr != mset.end() )
		{
			arr[i] = *itr;
		}
		else
		{
			arr[i] = -1;
		}
		mset.erase( --itr );//amortized constant
	}
}

- WaqtHH July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well, can't we just sort the array with quicksort (O(nlogn)) and do another pass from left to right(O(n)) on the sorted array to make the replacements? Am I missing something?

- TS_2014 July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lets take an example
3,2,4,1
The actual answer is 4,4,-1,-1
By your method:
Quicksort: 1,2,3,4
Replace next greater on right: 2,3,4,-1
Hope it helps

- kr.neerav July 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree with kr.neerav and use BST to solve this problem.
1. Read the input array from right to left
2. Insert each array element into a BST.
Note that I can find out the whether the least greater number for element k exists or not , from existed sub-tree when inserting k: the least greater number for k must be a predecessor
of k if it exists.

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print_array(const int* arr, const int arr_size){ 
  for(int i=0; i<arr_size; i++){
    cout<<arr[i]<<" ";
  }
  cout<<endl;
}
// input: given array of integers 
// output array of ints in which each number is replaced 
//        with a number presented on the right side of it (in the given array)
//        such that the number is the Least Greater than the element

/* naive method: */  
void replace_with_least_greater_number(const int* input, const int arr_size, int* output){
  
  for(int index = arr_size-1; index >=0 ; index--){
    int current_number = *(input+index);
    int replaced_number = -1;
    int sub_arr_size = arr_size-1 - index;
     
    vector<int> sorted_elements;
    for(int j=0; j< sub_arr_size; j++){
      int number_from_tail = *(input + (arr_size-1) - j );
      if (number_from_tail > current_number){
        sorted_elements.push_back(number_from_tail);
      }
    }
    
    if(sorted_elements.size() > 0){
      sort(sorted_elements.begin(), sorted_elements.end()); 
      replaced_number = sorted_elements.front();
    }
    
    *(output+index) = replaced_number;
    // cout<<replaced_number<<endl;
  } 
}

/* BST method: */
struct Node{
  int value;
  Node* left;
  Node* right;
};

class BSTree{
public:
  Node* root;
  BSTree() {
    root = NULL;
  }
  Node* insert(int );
  void print_tree();
  void print(Node*, int);
  
};

Node* BSTree::insert(int num){
  Node* n = new Node;
  n->value = num;
  n->left = NULL;
  n->right = NULL;
  Node* pre = NULL;

  if (root == NULL){ //an empty tree yet
    root = n;
  
  }else{
    Node* current = root; // a copy of root node
    Node* parent = NULL;

    while (current){ // keep on go through the tree
      parent = current;
      if(n->value > current->value){
        current = current->right;
      }else{
        current = current->left;
        if (pre == NULL || pre->value > parent->value){
          pre = parent;  // update the least greater inorder predecessor
        }
      }
    
    }
    // now reach a leaf position, the new node should be inserted as a child of parent
    if(n->value > parent->value){
      parent->right = n;
    }else{
      parent->left = n;
    }
  }
  return pre;
  
}

void BSTree::print(Node* n, int offset){  
  offset++;
  if(n->right != NULL){
    print(n->right, offset);
  }
  for(int i=0; i<=offset; i++){
    cout<<"\t";
  }
  cout<<n->value<<endl;
  if(n->left !=NULL){
    print(n->left, offset);
  }
}

void BSTree::print_tree(){
  print(root, 0);
}


int main(){
  const int input[] = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
  // output should be array of {18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1}
  const int arraysize = sizeof(input) / sizeof(input[0]);
  print_array(input, arraysize);
 
  // test naive method
  int output[arraysize];
  replace_with_least_greater_number(input, arraysize, output);
  print_array(output, arraysize);

  // test BST method
  int output2[arraysize];
  BSTree tree;
  for(int i= arraysize-1; i>=0; i--){
    Node* least_greater_predecessor = tree.insert(input[i]);
    if (least_greater_predecessor == NULL){
      output2[i] = -1;
    }else{
      output2[i] = least_greater_predecessor->value;
    }
  }
  
  //tree.print_tree();
  print_array(output2, arraysize);
  return 0;
}

- ysong.sc July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//In Java

import java.util.ArrayList;
import java.util.Collections;

public class LeastGreaterToRight {
	private static int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93,
			25, 80, 28 };
	public static ArrayList<Integer> temp = new ArrayList<Integer>();
	public static ArrayList<Integer> sorted = new ArrayList<Integer>();

	public static void main(String[] args) {
		System.out.println(ssort(arr));
	}

	public static ArrayList<Integer> ssort(int[] arr) {

		for (int i = 0; i <= arr.length - 1; i++) {
			if (i <= arr.length - 2) {
				temp.clear();
				for (int j = i + 1; j <= arr.length - 1; j++) {
					temp.add(arr[j]);
				}

				Collections.sort(temp);
				int shit = 0;

				for (int k = 0; k < temp.size(); k++) {

					if (temp.get(k) > arr[i]) {

						sorted.add(temp.get(k));
						temp.clear();
						shit = 1;
						break;
					}

				}
				if (shit == 0) {
					sorted.add(-1);
				}
			} else {
				sorted.add(-1);
			}
		}
		return sorted;
	}

}

- kp July 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think people here have misunderstood the problem , we don't have to find the inorder successor here or the next greatest element of the array , we have to find the next greater element present in the right side of the element in the array , so even if there is a greater element in the left side of the array of the element being inspected the result would be -1. So , the index of the greater element should be more than the element being inspected. My solution would be like this:
1. Sort array using quick sort or merge sort and put the sorted array in a different array or create a binary search tree.(Time taken : nlogn)
2. In the above step modify the algorithm to store the index of each element in a map.
3. Now start inspecting elements of the array from left to right , pick the element one by one , find the successor from the sorted array or BST created in step one , then find the index of the successor from the map. If the index of the successor is more than the index of the element being inspected then replace the current element being inspected by the successor else replace it by -1.

- praveenkcs28 July 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Final step of algorithm may take O(n2) which is actually a brute force algorithm.

- Anonymous August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// In c

#include<stdio.h>
#define MAX 15

int main(){
int a[MAX]={8,58,71,18,31,32,63,92,43,3,91,93,25,80,28};
int i,j,k,x;

for(i=0;i<MAX;i++){
for(j=i+1;j<MAX;j++){
if(a[i]<a[j]){
x=a[j];
break;
}
}
if(j==MAX){
x=-1;
}else {
for(k=j+1;k<MAX;k++){
if(a[j]>a[k]){
if(a[k]>a[i]){
x=a[k];
j=k;
}
}
}
}
a[i]=x;
}
for(i=0;i<MAX;i++){
printf("%d\n",a[i]);
}
return 0;
}

- Ritu July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//in c
#include<stdio.h>
#define MAX 15

int main(){
	int a[MAX]={8,58,71,18,31,32,63,92,43,3,91,93,25,80,28};
	int i,j,k,x;

for(i=0;i<MAX;i++){
	for(j=i+1;j<MAX;j++){
		if(a[i]<a[j]){
			x=a[j];
			break;
		}
	}
	if(j==MAX){
		x=-1;
	}else {
		for(k=j+1;k<MAX;k++){
			if(a[j]>a[k]){
				if(a[k]>a[i]){
					x=a[k];
					j=k;
				}
			}
		}
	}
	a[i]=x;
}
for(i=0;i<MAX;i++){
	printf("%d\n",a[i]);
}
	return 0;
}

- Ritu July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/Java

import java.util.Scanner;
import java.util.TreeSet;

public class Adobesde1 {

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int i;
        int[] a=new int[n];
        TreeSet<Integer> set=new TreeSet<Integer>();
        for(i=0;i<n;i++)
        {
            a[i]=in.nextInt();
            set.add(a[i]);
        }
        for(i=0;i<n;i++)
        {
            int t=a[i];
            set.remove(a[i]);
            System.out.println(set.ceiling(t));
            
            
        }
    }
}

- Raunak Ladha August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

would this work?

1) sort the original array using counting sort (sortedArray)- O(n+k)
2) for each element in original array (Array) we binary search for its location in the sorted array and return the next element if it exists (check for -1 or end of array), -1 otherwise. - O(logn)
3) set that index to -1 to mark as removed
4) return a new array with the data from step 2

This might make the complexity less than nlogn depending on the initial array given

- C.L. August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void ReplaceNumbers(int[] input)
{
  int[] sortedInput = new int[input.Length];
  for (int i = 0; i < input.Length; i++)
    sortedInput[i] = input[i];
  Quicksort(sortedInput, 0, sortedInput.Length);
  ReplaceNumbers(input, sortedInput, 0);
}

public void ReplaceNumbers(int[] input, int[] sortedInput, int s)
{
  if (s >= input.Length)
    return;

  int index = FindNextBigUsingBinarySearch(sortedInput, input[s]);
  if (index > 0)
  {
    int temp = input[s];
    input[s] = input[index];
    input[index] = temp;
  }
  else
    input[s] = -1;

  ReplaceNumbers(input, sortedInput, s + 1);
}

- ShaRai August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Write a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1

e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1*/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Swaparray
{
class Program
{
static void Main(string[] args)
{
int[] arr=new int[15] {8,58,71,18,31,32,63,92,43,3,91,93,25,80,28};
int x=0,i,j;
for (i=0; i<=14;i++)
{
Console.Write(" "+arr[i]+" ");

for (j =i+1; j <= 14; j++)
{
if (arr[i] < arr[j])
{
x = arr[j];
break;

}

}
if (j == 15)
{
x = -1;
}
else
{
for (int k = j + 1; k <= 14; k++)
{
if (arr[j] > arr[k])
{
if (arr[k] > arr[i])
{

x = arr[k];
j = k;
}

}
}
}
arr[i] = x;
}
Console.WriteLine("\n\n");
for (i = 0; i < 15; i++)
{


Console.Write(" " + arr[i] + " ");
}
Console.ReadLine();
}
}
}

- Hemant Bharadwaj August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Used TreeMap<Number,index>;
Once the Number is traversed remove the number from the map
the next highestNumber is always the key next to your current Number.
if the value(idx) is less than the current key's value then mark it as -1



import java.util.TreeMap;


public class LeastValtoRight {
public static void main(String[] args) {
int a [] = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 };
int op[] = formaulateLogic(a);
for (int i=0;i<op.length;i++){
System.out.print(op[i]+",");
}

}

private static int[] formaulateLogic(int[] a) {
int [] op = new int[a.length];
TreeMap<Integer,Integer> m = new TreeMap<Integer,Integer>();
for (int i=0;i<a.length;i++){
m.put(a[i],i);
}

for (int i=0;i<a.length-1;i++){
int idx = m.get(a[i]);
Integer nxtVal;
try{
nxtVal = (int) m.tailMap(a[i]).keySet().toArray()[1];
m.remove(a[i]);
}catch (IndexOutOfBoundsException e){
nxtVal =-1;
}

Integer nextIdx = m.get(nxtVal);
if (nextIdx==null || nextIdx<idx){
op[i]=-1;
}else{
op[i]= nxtVal;
}
}
op[a.length-1]=-1;
return op;
}

}

- phani February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(nlogn) solution.
1. Loop the array from 0 to n-1. Pick every element, say picked element has index "p".
2. Find the "ceil" of the picked number on the array from index "p+1" to "n-1".
3. Replace the number with the ceil value, as desired.
4. Use Binary Search to find the ceil value O(logn).
5. Doing for all n elements thus O(n*logn).

- HardCode July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure if we can use binary search since the array from index p+1 to n-1 is not sorted.

- kr.neerav July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

true, my bad..!!

- HardCode July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can achieve nlgn by using a min heap or min priority queue. Start from right to left, if the min heap is empty or min item is less than the current capture -1 otherwise capture the min value, then insert the current item into the heap and repeat to the left. Time complexity is dominated by the n lgn lg n insertions to the heap so nlgn

public int[] replace(int[] in) {
		int[] out = new int[in.length];
		PriorityQueue<Integer> min = new PriorityQueue<>();
		for (int i = in.length - 1; i > -1; i--) {
			if (min.size() == 0 || min.peek() < in[i]) {
				out[i] = -1;
			} else {
				out[i] = min.peek();
				min.add(out[i]);
			}
		}
		return out;
	}

- Ed July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

min.add(out[i]) should be min.add(in[i]) and should occur outside the else but otherwise good

- Ed July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

this is wrong since it always compares to the min item to the right, you need the next highest. storing in a tree and then retrieving the next highest would do

- Anonymous July 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* time: O(n^2logn), space: n */
1. do a merge sort on a new array
2. do a binary search on each element, and find the next value.

- Jacky Lai July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

O(n log n) solution is to sort array first, then simply iterate through array and replace each element with the next element if it is greater. If it isn't greater, go to next one. This has expected/average time of O(n log n), but worst-case performance is O(n^2) if all elements are the same and you cannot find an element greater.

- Derek C. July 02, 2014 | Flag Reply


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