## Directi Interview Question

• 0

Country: India

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

We can use a stack

``````Prev_Smaller_Element[0] = Null
stack.push(arr[0])

for i = 1 to N - 1
if(stack.top() < arr[i])
Prev_Smaller_Element[i] = stack.top()
else
while(stack.top >= arr[i] && !stack.empty())
stack.pop()

if(!stack.empty())
Prev_Smaller_Element[i] = stack.top()
else
Prev_Smaller_Element[i] = Null

stack.push(arr[i])``````

Complexity :- O(N)

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

This is O(N*N)

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

No its O(N) becuase each element gets pushed/popped only once. Nested loops does not necessarily mean its O(N*N) always.

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

You need to push the data into stack again for each loop. It is O(N^2).

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

let the array be ::
1 9 8 6 3 4 8 2 10
null 1 1 1 1 3 4 1 1
bt actual soln should be
null 1 1 1 1 3 6 1 9

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

@rajnish
According to the question Position of Y should be as large as possible and not the value of Y. So the correct output for your input is :- null 1 1 1 1 3 4 1 2. My solution is giving this correct answer.

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

@Anirban
awesome work

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

Nice Solution. +1.

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

1. Use augmented BST where each node will contain two extra fields, one keeping track of the index of the element, another keeping track of the largest index of element less than this node's element.
Making clarifications, while inserting a value in BST, if it is less than root node, update the second field only if it is larger than the field stored there. If the field value is not set, then store this index.
2. Insert the elements into BST, if we use self balancing BST, the running time complexity is O(nlogn).
3. For each element in the array, search it in BST & print its corresponding field .

Let me know if i am missing anything.

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

"another keeping track of the largest index of element less than this node's element"

How will you keep this field updated as other inserts are done?

Logic similar to yours can lead to a correct solution, but it needs to be described better.

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

start from back looking for X.
After hitting X look for Y which is the less than X.. once you hit such number .. return it
or else move till the start of the array and return null if there is no number < X

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

How would you ensure complexity less than O(n^2) ?

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

Well.. what you should do is maintain a stack...

For each element say 'X' start popping elements till you find a 'Y' which is smaller that 'X' . Return value of 'Y' and Insert 'X' into the stack.

This ensure a time complexity less than O(n^2). In fact just O(n). Because complexity = No. of pushes = O(n). :)

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

``````var array = [ ..... ];

function gohil90Question ( pos, arr ) {
var val = arr[ pos ];

while( pos-- )
if( arr[ pos ] < val )
return pos;

return NULL;
}``````

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

That's N*N Complexity in worst case...!!!:D

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

1. Build a minleft[] which contains the element less than arr[i] from 0 to i-1 ,else -1.
2. Build a maxright[] which contains the element greater than arr[i] from i+1 to N-1 ,else -1.
3. run a loop from 0 to N-1,stat cheching the elements of minleft[] & maxright[].
if(minleft[i]<maxright[j]) j++ update maxdiff(j-i)
else i++

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

Assumption : there are no duplicate in input array

``````public class Prog1 {

public static void main(String[] args) {

int arr[] = {1,3,5,6,2,11,4} ;
int value = 2 ;

System.out.println("Soln "+solve(arr,value));

}

public static int solve(int []arr,int value) {

int closer = -1 ;
int i = 0 ;

while(i<arr.length && arr[i]!=value) {

if(arr[i] < value && arr[i] > closer )
closer = arr[i] ;

++i ;
}

return closer ;
}

}``````

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

Maintain a parallel sorted array of same size in following manner.

Maintain a tail pointer. At any point, the active array is between starting element and the element at the tail.

Insertion rules
1. For a new number x do binary search in the array and position the element against the next larger element. If there is no such element, add the element in the last.
2. Print element and its predecessor and move tail pointer to this index.

Example :
Given list
7, 1, 6, 5, 8, 3, 2, 9

``````Element   Array      Action           Tail             Printed
7              7            Inserted 7      index1         7, null
1              1            Replaced 7    index1         1, null
6              1,6         Inserted 6      index2          6,1
5              1,5         Replaced 6    index2          5,1
8              1,5,8      Inserted 8      index3          8,5
3              1,3         Replaced 5    index2          3,1
2              1,2         Replaced 3    index2          2,1
9              1,2,9      Inserted 9      index3          9,2``````

Since, we are using binary search for detecting the right location of element in the sorted array, operation wouldn't cost more than logK (Where k is avg. no. of elements in the array). K will be less than n .

Use of tail index saves us from shifting operations in array. So, no added time for it.

Complexity is O(nlogK)

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

Here is c++ code which works perfectly in n*log(n) order, although you might make the tree a balenced tree, which is not a big deal

``````#include <iostream>
using std::cout;
using std::endl;

struct node
{
int key_value;
int less_index;
node *left;
node *right;
};

class btree
{
public:
btree();
~btree();
int insert(int key, int index);
void destroy_tree();
private:
void destroy_tree(node *leaf);
node *root;
};

void nsquare_y_founder(int *A, int size_A)
{
for(int i=0; i<size_A; ++i)
{
int j=i-1;
for( ; j>-1 && A[j] >= A[i]; --j);
if(j==-1)
cout<<"For the value x = "<<A[i]<< " its y value is 0"<<endl;
else
cout<<"For the value x = "<<A[i]<< " its y value is "<<A[j]<<endl;
}
}

void nlogn_y_founder(int *A, int size_A)
{
btree mytree;
for(int i=0; i<size_A; ++i)
{
int j=mytree.insert(A[i],i);
if(j==-1)
cout<<"For the value x = "<<A[i]<< " its y value is 0"<<endl;
else
cout<<"For the value x = "<<A[i]<< " its y value is "<<A[j]<<endl;
}
}

int main() {
int A[]={12,25,13,44,11,42,15,20,54,17};
cout<<"Here is the n^2 algorithm output: "<<endl;
nsquare_y_founder(A, 10);
cout<<"Here is the nlog(n) algorithm output: "<<endl;
nlogn_y_founder(A, 10);

return 0;
}

int btree::insert(int key, int index)
{
int index_of_y = -1;
if(root!=0)
{
node *current = root;
bool flag = true;
while(flag)
{
if(key< current->key_value)
{
current->less_index = index; //updating less_index
if(current->left!=0)
current = current->left;
else
{
current->left=new node;
current->left->key_value=key;
current->left->less_index = index;
current->left->left=0;    //Sets the left child of the child node to 0
current->left->right=0;   //Sets the right child of the child node to 0
flag = false;
}
}
else if(key>=current->key_value)
{
index_of_y = (index_of_y > current->less_index ? index_of_y : current->less_index); //updateing index_of_y
current->less_index = index_of_y; //updating less_index for the current node
if(current->right!=0)
current = current->right;
else
{
current->right=new node;
current->right->key_value=key;
current->right->left=0;  //Sets the left child of the child node to 0
current->right->less_index = index;
current->right->right=0; //Sets the right child of the child node to 0
flag = false;
}
}
}
}
else
{
root=new node;
root->key_value=key;
root->left=0;
root->right=0;
root->less_index = index;
}
return(index_of_y);
}

btree::btree()
{
root=0;
}
btree::~btree()
{
destroy_tree(root);
}

void btree::destroy_tree(node *leaf)
{
if(leaf!=0)
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
delete leaf;
}
}``````

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

working c code
{{
//Time Complexity- O(nlogn)
#include<stdio.h>
int main()
{
int i,j,k,l,m,n,flag,arr[1000],max,tree[1000][4],temp,ans[1000];
scanf("%d",&n);
for(i=0;i<=n;i++)
{
for(j=0;j<4;j++)
{
tree[i][j]=-1;
}
}
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
tree[i][0]=arr[i];
tree[i][3]=i;
}

tree[1][0]=arr[1];

i=2;max=-1;
while(i<=n)
{max=-1;
temp=1;flag=0;
while(!flag)
{
if(tree[i][0]<tree[temp][0])
{
tree[temp][3]=i;
if(tree[temp][1]==-1)
{tree[temp][1]=i;flag=1;}
else
temp=tree[temp][1];
}
else if(tree[i][0]>tree[temp][0])
{
if(tree[temp][3]>max)
max=tree[temp][3];
if(tree[temp][2]==-1)
{tree[temp][2]=i;flag=1;}
else
temp=tree[temp][2];
}

}
ans[i]=max;
i++;

}
ans[1]=-1;
for(i=1;i<=n;i++)
printf("%d ",ans[i]);

return 0;

}

}}

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

``````# your code goes here

a=[int(x) for x in raw_input().split(' ')]

l=[None]
s=[a[0]]
for i in range(1,len(a)):

while len(s)>0 and s[len(s)-1]>=a[i]:
s.pop()
if len(s)>0:
l.append(s[len(s)-1])
else:
l.append(None);

s.append(a[i])
print l``````

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

we just save the local min and max

``````#include <iostream>
using namespace std;
int v[]={5,4,7,9,1,15}; // initial array
int n=6; //v.length
int r[100]; // response arrray
// r will have 0 if there are no numbers to make the conditions true and 1 if there are
int main()
{
int min=v[0];  // save the minimum so far
int max=v[0];
for (int i=1; i<n; i++ )
{
if (v[i]<min ) min=v[i];  // has no smaller intem before him
else
{
r[i]=max;  // has item and therefore r=1
if ( v[i]>max ) max=v[i];
}
}
for ( int i=0; i<n; i++)
cout<<v[i]<<" ";
cout<<endl;
for ( int i=0; i<n; i++)
cout<<r[i]<<" ";
cout<<endl;
return 1;
}``````

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

condition 3 is not meeting it says position of y should be as large as possible ,not the value of it

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

This is not O(N) but O(N*N)

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

// values : array of integers
// precedents : array of indices, where indices are in accordance with the problem statement rules
void SmallerPrecedent(int[] values, int[] precedents)
{
int i;

if (values.Length == 0)
return;

precedents = new int[values.Length);
precedents[0] = Int32.MinValue;

for (i = 1 ; i < values.Length ; i++)
{
if ((values[i] >= values[i - 1]))
precedents[i] = precedents[i - 1];

precedents[i] = FindDecreasingValuePrecedent(values, precedents, i);
}

}

int FindDecreasingValuePrecedents(int[] values, int[] precedents, int position)
{
int i;

Debug.Assert(position > 0);

for (i = position - 1 ; i >= 0 ; )
{
int precedent = precedents[i];

if (precedent == Int32.MinValue)
return (precedent);

if (values[precedent] <= values[position])
return (predecent);

i = precedent;
}

return (Int32.MinValue);
}

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

This is O(N*N)

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

Dynamic programming

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.