Directi Interview Questions
- 2of 2 votes
Answershow to do this round1 question 1:
- dsAlgo August 15, 2014 in India
http://www.geeksforgeeks.org/directi-interview-set-5-campus/
A string can contain only a, b or c. There cannot be 2 consecutive same character. First and last character cannot be same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple answer display lexicographically smallest string. For no answer possible display “Not Possible”.| Report Duplicate | Flag | PURGE
Directi SDE1 - 2of 2 votes
AnswersI/P: An array of Integers: which will be used to construct a binary search tree in the order they appear.
- poorna.chandra.akp April 20, 2014 in India
o/p: all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.
Eg:
I/P: 4, 3, 1, 2, 6, 5, 7
o/p:4 , 6, 3, 7, 5, 1, 2
4, 3, 2, 1, 6, 5, 7
and soo on.| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer - 1of 1 vote
AnswersQuestion 2 / 2 (Weighted Stone Arrangement)
- kri1311 February 09, 2014 in India
You are given an infinite number of stones.
The 1st stone has the weight 1
The 2nd stone has the weight 3
The tth stone has the weight W(t) = 2 * W(t-1) + W(t-2)
Thus, the weights of the first 10 stones are
1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363
Note that you only have one stone of each weight.
You have a weighing machine which is the age old 2-pan balance. You wish to use this machine to measure the weight of an item whose weight is T. The item will always be kept on the right pan. A stone may be kept on either one of the pans. Also, it is not required to use all the stones.
The stones have a weird magnetic property, due to which, the kth stone cannot be in the same pan as the (k-1)th stone. This means that the stone with weight 239 cannot be in the same pan as the stone with weight 99, or in the same pan as the stone with weight 577; and so on.
For example,
T = 11 can be measured as
LEFT PAN: 1, 17
RIGHT PAN: 7
Note that the other alternative
LEFT PAN: 1, 3, 7
RIGHT PAN:
is Illegal since 3 cannot be in the same pan as 1 (or 7 cannot be in the same pan as 3).
T = 21 can be measured as
LEFT PAN: 41
RIGHT PAN: 3, 17
It can be proven that to measure any weight T, there exists a unique arrangement of stones that satisfy the given constraints and measure weight T. Thus, T = 11 or T = 21 can only be measured by the respective arrangements above.
You are given T in the input. Output the arrangement of stones that measures T.
Input Specification
The input contains a single positive integer T.
Output Specification
Output the weights of the stones used on the left pan in increasing order, one number per line. Then output a blank line. Followed by the weights of the stones used on the right pan in increasing order. Note that it is assumed that the item will be kept on the right pan.
If there is no stone kept on the right pan, simply output the weights of the stones used on the left pan in increasing order as above, followed by a blank line.
Constraints
1 ≤ T ≤ 1015
Sample Input 1
11
Sample Output 1
1
17
7
Sample Input 2
21
Sample Output 2
41
3
17
Sample Input 3
1000
Sample Output 3
3
41
239
1393
99
577| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Coding - 0of 0 votes
AnswerDirecti Off Campus Interview Process 2013-14
- kri1311 February 09, 2014 in India
.......................................................................
This is year 4096 and humans have found a medicine for immortality in the year 2048. Tukro a famous online social networking site founded in the year 3072 was celebrating its 1024th anniversary. To celebrate the occasion its CEO, Shark, and his team had launched a unique personalised video of length 17min 4sec for each user. The video consisted of a collage of all popular posts made by the user on Tukro.
Raka shared this video with all his friends without reviewing it. Immediately after he finished watching the 1024 second length clip he realised that he made a huge mistake. The video was made of all posts made by Raka, irrespective of the privacy settings of the individual post.
A post is compromised if a friend who was not supposed to see the original post, has seen it now. Raka wants to know how many of his posts have been compromised. Tukro provides the list of users who have watched the video till now. Help Raka find how many posts were compromised.
Raka has N friends, identified by a unique integer between 0 and N-1.
Raka has L lists of friends, identified by a unique integer between 0 and L-1.
Each list can be of length at the most N.
One friend cannot be added more than once to the same list.
A list must have at least one friend.
A friend may be added to multiple lists.
Visibility of a post in Tukro works through two filters
Include Filter: An array of lists, from the L lists above. Friends can view a post if they belong to any friend list, specified in the Include Filter.
Exclude Filter: An array of lists, from the L lists above. Friends can view a post if their name does not belong to any friend list, specified in the Exclude Filter.
Some caveats of the above are
If no Filter is active, the post is visible to all friends
If only Include Filter is active, a friend can see the post only if he is present in at least one of the lists of Include Filter.
If only Exclude Filter is active, a friend can see the post only if he is not present in any of the lists of exclude filter.
If both Include and Exclude Filters are active, a friend can see the post if and only if
he is present in at least one of the lists of include filter and
he is not present in any of the lists of exclude filter
if he is present in both an include filter list, and exclude filter list, he should not be able to see the post
Input Specification
First line contains a single integer N, the number of friends.
Second line contains a list of integers separated by a single space. The first integer V, represents the number of friends who viewed the video. There are V other integers in the line representing the ID's of friends who viewed the video.
Third line contains a single integer L representing the number of lists.
L lines follow. Each line representing a list. The first integer of the line A, denotes the size of the list; followed by A integers, each denoting the friends in the list.
Next line contains a single integer P denoting the number of posts in the video. 2 * P lines follow. Each pair denoting the Include Filter and Exclude Filters of one post respectively.
First two lines denote the Include and Exclude Filters for first post
Next two lines denote the Include and Exclude Filters of second post
and so on..
An include filter is represented by a list of space separated integers. The first integer B represents the number of lists in the filter. B may be 0, to denote that the include filter is not active. If B is more than 0, the include filter is active and the next B integers in the line denote the ID's of lists present in the include filter.
Exclude filters are also represented in the same format.
Output Specification
Print a single integer specifying the number of posts that are compromised according to the definition above.
Constraints
1 ≤ N ≤ 10000
1 ≤ V ≤ N
1 ≤ L ≤ 6
1 ≤ P ≤ 100000
Note that the constraints on N and P are large.
Your solution will exceed time limits if its complexity is O(N*P).
Even O(V*P) solutions may exceed time limit!
Note the small constraint on L.
Sample Input 1
10
8 1 2 5 6 0 9 8 7
4
2 4 3
2 7 6
3 0 1 5
3 2 8 9
4
0
1 0
1 1
0
0
0
3 1 2 3
0
Sample Output 1
1
Explanation
There are 10 friends. Their ID's are from 0 to 9
8 of them viewed the video = {0,1,2,5,6,7,8,9}
There are 4 lists
List-0 has 2 friends {3,4}
List-1 has 1 friend {7,6}
List-2 has 3 friends {0,1,5}
List-3 has 3 friends {2,8,9}
There are 4 posts
Post-0 doesn't have any include filter but has List-0 - {3,4} - in exclude filter
3, or 4, have not seen the video
Hence Post-0 is not compromised
Post-1 has an include filter of List-1 - {7,6} - and no exclude filter.
But other friends have seen the video
Hence Post-1 is compromised
Post-2 doesn't have any filters. Such a post was intended to be seen by anyone.
Hence Post-2 is not compromised.
Post-3 has a include filter of List-1, List-2 and List-3.
Their union is {0,1,2,5,6,7,8,9}
These are the exact friends who saw the video
Hence Post-3 is not compromised
Hence only 1 post is compromised.
Sample Input 2
5
2 2 3
5
1 0
1 1
1 2
1 3
1 4
4
3 2 3 4
1 0
3 1 2 3
0
3 0 1 3
0
3 2 3 4
1 0
Sample Output 2
1| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Coding - -1of 3 votes
AnswersGiven N,O where N=No. of digits that can be displayed on calculator and O=No. of multiplication to be performed.
- lorinahmed November 27, 2013 in India
The numbers used for the multiplication can be from {2,3,...8,9}
2<=N<=8
2<=O<=30
write function that will return the largest num that can be obtained after O multiplication.
Eg: N=2, O=3
the function should return 98, since the maximum no. generated after 3 multiplications 2*7*7.
function should return -1 for error or invalid.| Report Duplicate | Flag | PURGE
Directi Developer Program Engineer - 1of 3 votes
AnswersGiven N,O where N=No. of digits that can be displayed on calculator and O=No. of numbers which are to be multiplied.
- gowin October 31, 2013 in United States
The numbers used for the multiplication can be from {2,3,...8,9}
2<=N<=8
2<=O<=30
Write function that will return the largest number that can be obtained after multiplying O numbers.
Eg: N=2, O=3
The function should return 98, since the maximum no. generated after multiplying 3 numbers is 2*7*7. Function should return -1 for error or invalid.
The function returns whether it is possible to form the number num by multiplying mult numbers| Report Duplicate | Flag | PURGE
Directi - 1of 1 vote
AnswersGive N=no. of players
- arpitbaheti7 October 24, 2013 in India
K=No. of fans
likeMatrix=It is a sting array of size K where each element of array have size N.
(contains 0 and 1 only) where if a[i][j] ==1 represents fan(i) likes player(j)
Ex. N=5
K=3
like={ "10101","00001","01011","...","...." }
Count min. no. of players required to put in team such that each fan likes atleast one player.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer - 0of 2 votes
AnswersQuestion 1 / 1 (Path Explosion EASY)
- MJRocks October 04, 2013 in India
You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties
Each internal node in T had exactly 2 children
Each internal node in T was represented by an uppercase English alphabet (A-Z)
Each leaf node in T was represented by a lowercase English alphabet (a-z)
You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below
toPostOrderString (node)
if node is leaf
return node.value
else
T = ""
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T
Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in "Now you see me" ( don't tell anyone they are real !! )
You remember the string you memorised back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves - 1 unique path to each leaf.
You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.
You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively
N, the number of nodes in T
S, the string representation of the post-order traversal of T. Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.
Note
It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node.
For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely.
It is not necessary that all characters in T are unique. There may be several nodes with the same value.
In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string.
Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.
Consider the following tree
A
/ \
t B
/ \
/ \
B A
/ \ / \
x y a b
This tree is given in Sample Case 1 as
N = 9
S = "txyBabABA"
K = 2
A = "AA"
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves - 1 for each leaf.
- A-t
- A-B-B-x
- A-B-B-y
- A-B-A-a
- A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which "AA" exists as a sub-sequence. Of course, there are only 2 such paths
- A-B-A-a
- A-B-A-b
Hence the expected answer is 2.
In the same T above
The answer for A = "BB", is 2
The answer for A = "BA", is 2
The answer for A = "AB", is 4
The answer for K = 1 and A = "A", is 5
The answer for K = 1 and A = "B", is 4
The Sample Case 2 has a little more complicated T. The string S in Sample Case 2 is yeBgeuCBxAB.
Constraints
N ≤ 10000
K ≤ 100
The expected time complexity of the algorithm is O(N).| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Trees and Graphs - 0of 2 votes
AnswersGiven a normal string S and regular expression string P find out whether P can be transformed into S or not?
- Rohit July 25, 2013 in India
for example:- P is "b*ba" and S is "bbba" now we have to return true as S can be obtained from P.
P.S:- Time complexity matters.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of N positive integers, N being even, and a number K, find out if it is possible
- sam March 22, 2013 in India
to form pairs of the numbers present in the array such that the sum of numbers in each pair is
divisible by K.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAlice and Bob are playing a game. The game is played as follows :
- sam March 22, 2013 in India
- There are N piles of coins on the table. Pile i has A[i] coins.
- In each turn, each player can pick up 1 or more coins from the leftmost non-empty pile.
- If a player picks up a coin from pile i , all coins from piles 0 to i-1 should have been taken.
- The person who picks up the last coin loses the game.
Alice and Bob play the game alternately. Alice plays first. Given the number of piles N and the
number of coins Ai in pile i, you have to determine which player will win the game, assuming
both play optimally.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Brain Teasers - 0of 2 votes
AnswersGiven n positive real numbers, find whether there exists a triplet among this set such that, the sum of the triplet is in the range (1, 2). Do it in linear time and O (1) space.
- abbi031892 February 17, 2013 in India| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose you have some guests arriving at a party. For each guest, you are given the arrival and departure time. When a guest arrives he is given a wine glass and when he leaves he returns that wine glass (it becomes available to be given to another guest). Find the minimum number of wine glasses needed to serve all the guests. The arrival and departure team can only be between 1800 to 2359 hours.
- yogi.rulzz December 15, 2012 in India| Report Duplicate | Flag | PURGE
Directi Developer Program Engineer Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a binary tree, such that each node contains a number. Find the maximum possible sum in going from one leaf node to another.
- yogi.rulzz December 15, 2012 in India| Report Duplicate | Flag | PURGE
Directi Developer Program Engineer Algorithm - 0of 0 votes
Answers#include <stdio.h>
- r.it.igec November 11, 2012 in India
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
#define _uint64_t
unsigned long long int i,R,L;
int f1(unsigned long long int num);
//unsigned long long int a[999999999];
unsigned long long int *a=NULL;
unsigned long long int j,r;
unsigned long long int main()
{
//printf("enter Minimum value for Delicious Dishes\n");
scanf("%llu",&L);
//printf("enter Maximum value for Delicious Dishes\n");
scanf("%llu",&R);
j=L+1;
a=(unsigned long long int *)malloc(sizeof(R-L));
//int f1(int a[]);
for(i=0;i<(R-L);i++)
{
//j=L+1;
*(a+i)=j;
j=j+1;
}
//printf("Now Delicious Dishes List is Ready.....:\n\n { ");
for(i=0;i<R-L;i++)
{
r=f1(*(a+i));
if(r==1)
{
//printf("not Delicious Dishes List:\n");
//printf("%d",a[i]);
}
else{
printf(" %llu ,",*(a+i));
}
}
//printf(" };\n\n");
//int random;
//srand(time(NULL));
//random=a[rand()%(sizeof(a) /sizeof(a[0]))];
printf("%llu\n ",*(a+4));
return 0;
}
int f1(unsigned long long int k)
{
unsigned long long int rep=0;
while(k>0)
{
if(rep & 1 <<(k%10))
return 1;
rep|= 1 << (k % 10);
k = k / 10;
}
return 0;
}
its give result correct but in large input value ex L=123456,R=123456789 its give core dump i have already using standard gcc compiler and take unsigned long long int but still giving runtime error core dump can anyone hel me for resolve this bugs| Report Duplicate | Flag | PURGE
Directi Algorithm - 0of 0 votes
Answersfind ginen BT is BST or not?
- Andi November 08, 2012 in India| Report Duplicate | Flag | PURGE
Directi Algorithm - 0of 0 votes
AnswersAn array of n length, filled with 0's,1's and 2's, how to sort effectively?
- Andi November 08, 2012 in India
Input:{0,1,2,2,1,1,0,2,1,0}
Output: {0,0,0,1,1,1,1,2,2,2}| Report Duplicate | Flag | PURGE
Directi Algorithm - 0of 0 votes
AnswersA Matrix of cells is given. A cell may be desert (represented as 1) or forest (represented as 0). Now every year all forests adjacent to desert convert to deserts. You are supposed to find out how many forests will be there after 'k' years (also give their location).
- gurumukhi November 04, 2012 in India
** : on phone interview, interviewer will ask you to code on the online real-time editors like collabedit.com, sync.in or docs.google.com| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
Answersgiven a character array of the form a[100]="aabbccc".You have to write an algorithm to convert it into
- ashishgpt45 October 22, 2012 in United States
"a2b2c3" inplace.Try for O(n) solution.| Report Duplicate | Flag | PURGE
Directi Algorithm - 0of 0 votes
AnswersHow we can perform insert, delete and findMax operations in O(1) time using a given queue ?
- pradegup October 02, 2012 in India| Report Duplicate | Flag | PURGE
Directi - 1of 1 vote
AnswersGiven an array of Integers of size n, Find element appearing more than n/2 times
- azharu92 September 20, 2012 in India| Report Duplicate | Flag | PURGE
Directi Intern Algorithm - 0of 0 votes
AnswersGiven encoded version of string like 'a2b2cd3' - It means string preceeding number is repeated digit number of times.'a2b2cd2' = 'aabbcdcd'
- rayasamharish September 08, 2012 in India
Input
You are provided a template in which you have to implement one function exploreString. The declaration of exploreString looks like
int exploreString ( string A, int k )
A is the compressed string.
k is an integer. find character at kth position.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the best way to cut a rod of length N units into smaller pieces such that we get maximum benefit. The prices for each smaller pieces of rod is given for cut of length from 1 to N.
- samant.bit July 28, 2012 in India
Example
Length |1 2 3 4 5 6 7 8
-----------------------------------------
price |1 5 8 9 10 17 17 20| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer - 0of 0 votes
AnswersFind the longest Palindromic sub sequence of a given sequence, for example if the sequence is XAYBZBA then length of longest palindromic sub sequence is 5 and it is ABZBA
- samant.bit July 28, 2012 in India| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a number of points on the XY-plane, [(x0,y0),(x1,y1),(x2,y2),...].
- majestic12 July 22, 2012 in India
A point (xi,yi) is dominant to another point (xj,yj) iff xi>xj and yi>yj.
Calculate all pairs of points such that one dominates the other.
A time complexity less then O(n*n) was required.| Report Duplicate | Flag | PURGE
Directi Intern Algorithm - 0of 0 votes
AnswersYou are given a tree with N nodes. Every node in the tree has a given weight. Your goal is to divide the given tree in two trees by removing exactly one edge such that the difference of sum of weights in the new trees is minimum.
- Ankit July 15, 2012 in India
Input
First line contains integer T, the number of test cases. First line of each test case contains integer N, the number of nodes. Next line contains the N integers, weight of node 0, 1 .. N - 1. The next N - 1 line contain two space separated integers x and y, describing an edge, where x and y are 0 based indices for nodes in the tree.
Constraints
T <= 100, N <= 1000
Output
Output a single line for each test case, which contains the min absolute difference between the sum of the nodes of the two trees.
Example
Input:
2
3
8 7 8
1 0
2 1
9
5 5 4 1 8 8 3 5 2
1 0
2 0
3 1
4 1
5 3
6 0
7 5
8 1
Output:
7
13
Author: xyler
Date Added: 15-07-2012
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersTwo numbers are called friendly if they share a digit. For example 1239 and 9760 are friendly where as 1234 and 9876 are not. You are given N numbers and you have to calculate the count of pairs of numbers that are friendly.
- Ankit July 15, 2012 in India
Input
First line of input contains an integer T, the number of test cases. For each test case, the first line contains N, the number of integers given. The next N lines contain N integers.
Constraint
T <= 10, N <= 10 ** 4, Each given number is between 1 and 10 ** 18
Output
For each test case, print a line containing the count of pairs of number that are friendly.
Example
Input:
2
5
2837 2818 654 35 931
5
183 665 908 774 362
Output:
6
3
Author: xyler
Date Added: 15-07-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm