Have answered inline: Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm to find the ‘l’ words in the newspaper.
Trivial hash-dictionary search operation. Takes O(m*l), where m=length of maximum length word in the set l. Q2) Find the next higher number in set of permutations of a given number. Sorting and just returning next element, takes O(nlogn). Hashing takes O(n). Just iterate through the list, and as and when you encounter a number, check if its a permuation of the given number. If yes, update min(a variable thats used to keep track of the minimum found upto that element), else just pass that element simply. Finally, return min. Q3) Given preorder of a BST, find if each non-leaf node has just one child or not. To be done in linear time. If the word non-leaf node is strictly considered, the root should also be included. Thus, traverse the given preorder of the BST, and in case any violation happens, the answer is no, otherwise yes. Violation meaning, if you pass a node that is less than the root(which will subsequently be updated to the current node as you iterate through the loop), you should never encounter a value that is greater than the root(or, again, any subsequent node encountered). On 7/4/12, Decipher <ankurseth...@gmail.com> wrote: > Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm > to find the ‘l’ words in the newspaper. > > Q2) Find the next higher number in set of permutations of a given number. > > Q3) Given preorder of a BST, find if each non-leaf node has just one child > or not. To be done in linear time. > > Q4) Given a dictionary of words, two APIs > Is_word(string) > Is_prefix(string) > And a NxN matrix with each postion consisting of a character. If from any > position (i,j) you can move > in any of the four directions, find out the all the valid words that can be > > formed in the matrix. > (looping is not allowed, i.e. for forming a word position if you start from > > (i,j) and move to (i-1,j) then > from this position you cannot go back to (i,j)) > > Q5) Given that there are n players and each one of them has played exactly > one game with every > other player. Also given is an API that tells whether player ‘a’ won or > lost to player ‘b’, where ‘a’ and > ‘b’ could be any of the players. Arrange the n players in a length n array > such that player at position > ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/LzG-OrtjDmoJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
