nk
BAN USER- -1of 1 vote
AnswersPrint a rectangle on screen only if it doen't intersect with other rectangles which are already drawn on screen.Minimise number of comparisons
- nk in United States for InDesign
Note :- the rectangles are axis-aligned| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - 0of 0 votes
AnswersGiven a matrix with letters in each square and you have to find words which are there in the dictionary (like Children's Crosswords). You have been given a function which outputs 1 if the given word is in the dictionary. The word could be bidirectionally horizontal, vertical or diagonal. Write an optimal algorithm for printing all such words.
- nk in India| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a string of ‘n’ characters where n is even. The string only consist of 6 type of characters: (){}[]. The task is to form a well formed expression. A well formed expression consist of proper nesting of braces and their is no priority between the braces like [ > } > ). You can edit any bracket and change it to remaining types for accomplishing the task.
- nk in India
Example
A. "(){}" is valid
B. "({[]})” is valid
C. “((})” is invalid| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm
First count the total no. of nodes in the tree to allocate the matrix
We can do iterative inorder traversal using Queue.
At any time, if we go upwards, it means all the nodes on this path has been traced and we need to fill the ancestor matrix.
now we iterate all nodes in the queue and mark it as the ancestor of the deepest node.
Here we assume that every node is labelled with a positive integer.
Time Complexity :- O(N) [inorder traversal] + O(NlogN) [marking the elements of matrix]
Space Complexity :- O(LogN) [for Queue] + O(N^2) for matrix
. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .
it is a simple graph reachability problem.
here the character matrix can be plotted as a graph where ..... shows the nodes are connected. while w shows disconnected.
we can apply dfs/bfs from the source node and if we reach a node w, then return else recurse for each connected node,if we reach X,then true else false.
I think it can be done in worst case O(n+ logn) time.
In the 3rd dimension,
Choose the middle layer,now check if the element to be searched is in the range of this layer. key >= a[i][0][0] && key <= a[i][n][n]
then search this layer in O(n) time -- standard Young tableau search
else if key < a[i][0][0]
go to previous layer
else
go to next layer
the layer search works in a binary seach fashion -- O(logn)
@all :-
- nk October 06, 2012u have to minimise the number of comparisons
and there are multiple rectangles with co-ordinates given
(top,left,bottom,right)
Plz note - "minimise the number of comparisons "