In this month’s col­umn, we dis­cuss the topic of au­to­matic re­la­tion ex­trac­tion from text us­ing nat­u­ral lan­guage pro­cess­ing tech­niques.

OpenSource For You - - CODE SPORT -

In last month’s col­umn, I had de­scribed cer­tain tech­niques for in­for­ma­tion ex­trac­tion from un­struc­tured texts us­ing nat­u­ral lan­guage pro­cess­ing. In this month’s col­umn, we take a break from this and dis­cuss a few in­ter­view ques­tions in gen­eral com­puter sci­ence and data sci­ence. 1. Given an ar­bi­trary in­te­ger N, how many unique bi­nary trees can be cre­ated con­tain­ing N nodes? Can you come up with an al­go­rithm which can pro­gram­mat­i­cally list all pos­si­ble bi­nary trees con­sist­ing of N nodes? 2. You are given two un­sorted lists of in­te­gers. You are asked to cre­ate a sorted list con­sist­ing of all the el­e­ments in the two lists. Can you write an al­go­rithm for this? What is the run­ning time of your code, in the worst case? 3. You are given a list of N nodes in a tree, with each node rep­re­sented by an in­te­ger. For each node, you are also given the de­tails of its par­ent node. You are not given the edges of the tree ex­plic­itly, but you are told that it is a bi­nary tree. You are asked to write code to per­form an in-or­der tra­ver­sal of the tree us­ing this in­for­ma­tion. How would you solve this prob­lem: (a) If you are told that you can per­form pre-pro­cess­ing on the in­for­ma­tion and can use any amount of ad­di­tional stor­age; (b) You are told that you can use only a con­stant amount of ad­di­tional stor­age. 4. You are given an ar­bi­trary tree T (not nec­es­sar­ily bi­nary), with each tree node con­tain­ing a pair of in­te­gers (X and Y). Each tree node can have an ar­bi­trary num­ber of chil­dren nodes, at each level of the tree. You are given two num­bers, A and B, and are told to find out if the nodes N1 and N2 con­tain­ing the in­te­gers A and B are lo­cated at the same level of the tree. Note that N1 and N2 can be two sep­a­rate nodes or be the same node. It is only re­quired that N1 and N2 should be lo­cated at the same level of the tree, and they need not be sib­lings. Write an al­go­rithm to de­ter­mine whether the tree T con­tains A and B at the same level. What is the ex­e­cu­tion time com­plex­ity of your code? 5. You are given an ar­ray of size N. Each el­e­ment of the ar­ray can take only one of the three val­ues (0, 1 or -1). You are told to find the long­est con­tigu­ous se­quence of 1s in the ar­ray. Write a C func­tion to find the start and end of the con­tigu­ous se­quence of 1s in the ar­ray. Now you are told that you can flip K con­tigu­ous se­quence of (-1) to 1 where K is a dy­nam­i­cally pro­vided in­put to the func­tion. In that case, how would you de­ter­mine the long­est con­tigu­ous se­quences of 1s in the ar­ray af­ter flip­ping K el­e­ments which were -1 to 1? What is the time and space com­plex­ity of your func­tion? 6. Given an ar­ray of N in­te­gers, you are asked to find out whether the given ar­ray is an arith­metic se­ries (a se­quence of num­bers where there is a con­stant dif­fer­ence be­tween any two con­sec­u­tive num­bers of the se­ries). What is the com­plex­ity of your func­tion? Now, you are given a mod­i­fied prob­lem where your task is to con­vert a given ar­ray into an arith­metic se­quence by drop­ping off those ar­ray el­e­ments which pre­vent it from be­ing an arith­metic se­quence. How would you solve this prob­lem? What is the time com­plex­ity of your func­tion? 7. Given an ar­bi­trar­ily long char­ac­ter string, you are asked to find out the most fre­quently oc­cur­ring char­ac­ter as well as the least fre­quently oc­cur­ring char­ac­ter. Write a C func­tion to solve this prob­lem, given a char­ac­ter string of size N. Now you are told that in­stead of be­ing a fixed size char­ac­ter string, you are given a stream of char­ac­ters which come dy­nam­i­cally as in­put. At any point in time, you should be able to print the most fre­quent and least fre­quent char­ac­ters in the stream (note that if two or more char­ac­ters have the same high­est fre­quency, you can choose to print any of them as the most fre­quent char­ac­ters). What is the time and space

Newspapers in English

Newspapers from India

© PressReader. All rights reserved.