Adobe Interview Question
SDE1sCountry: India
Interview Type: In-Person
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
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.
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.
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.
/*
* 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;
}
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;
}
#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;
}
}
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;
}
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)
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
LEAST GREATER ELEMENT. ARE YOU DOING THAT?
YOU ARE DOING LEFTMOST GREATER ELEMENT ARENT YOU?
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)
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
}
}
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?
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;
}
//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;
}
}
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.
// 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;
}
//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;
}
/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));
}
}
}
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
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);
}
/*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();
}
}
}
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;
}
}
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).
Not sure if we can use binary search since the array from index p+1 to n-1 is not sorted.
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;
}
min.add(out[i]) should be min.add(in[i]) and should occur outside the else but otherwise good
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.
Here is an O(nlogn) [amortized] approach using a threaded BST where each node points to the next in order successor.
- kr.neerav July 02, 20141) 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.