Directi Interview Question

  • directi-interview-questions
    0
    of 0 votes
    27
    Answers

    There's an array of length N. For every element of array, say 'X' , find a element 'Y' in the same array such that,

    1. Value of Y<Value of X
    2. Position of Y<Position of X
    3. Position of Y should be as large as possible.

    Note: If there's no such element 'Y' fro particular 'X' return NULL. Also give algorithm with time complexity less than O(N*N).

    - gohil90 on June 22, 2012 in India Report Duplicate | Flag
    Directi Algorithm

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)

- Anirban on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(N*N)

- wyb2012 on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anirban on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rajnish on July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anirban on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Anirban
awesome work

- Gaurav on December 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice Solution. +1.

- Murali Mohan on July 17, 2013 | Flag
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.

- Aashish on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on September 15, 2012 | Flag
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

- Siva on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Srikant on October 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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). :)

- srikantaggarwal on October 24, 2012 | Flag
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;
}

- Pantelis on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gohil90 on June 22, 2012 | Flag
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++

- Aashish on June 26, 2012 | Flag Reply
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 ;
	} 

}

- Anonymous on July 03, 2012 | Flag Reply
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)

- Harsh on August 22, 2012 | Flag Reply
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;
  }
}

- AA on September 16, 2012 | Flag Reply
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;




}

}}

- Gaurav Rana on October 20, 2012 | Flag Reply
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;
}

- alexandru.doro on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- svikki2005 on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- wyb2012 on June 23, 2012 | Flag
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);
}

- Anonymous on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(N*N)

- wyb2012 on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Dynamic programming

- coder on June 25, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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