In this month’s column, we discuss the topic of automatic relation extraction from text using natural language processing techniques.

In last month’s column, I had described certain techniques for information extraction from unstructured texts using natural language processing. In this month’s column, we take a break from this and discuss a few interview questions in general computer science and data science. 1. Given an arbitrary integer N, how many unique binary trees can be created containing N nodes? Can you come up with an algorithm which can programmatically list all possible binary trees consisting of N nodes? 2. You are given two unsorted lists of integers. You are asked to create a sorted list consisting of all the elements in the two lists. Can you write an algorithm for this? What is the running time of your code, in the worst case? 3. You are given a list of N nodes in a tree, with each node represented by an integer. For each node, you are also given the details of its parent node. You are not given the edges of the tree explicitly, but you are told that it is a binary tree. You are asked to write code to perform an in-order traversal of the tree using this information. How would you solve this problem: (a) If you are told that you can perform pre-processing on the information and can use any amount of additional storage; (b) You are told that you can use only a constant amount of additional storage. 4. You are given an arbitrary tree T (not necessarily binary), with each tree node containing a pair of integers (X and Y). Each tree node can have an arbitrary number of children nodes, at each level of the tree. You are given two numbers, A and B, and are told to find out if the nodes N1 and N2 containing the integers A and B are located at the same level of the tree. Note that N1 and N2 can be two separate nodes or be the same node. It is only required that N1 and N2 should be located at the same level of the tree, and they need not be siblings. Write an algorithm to determine whether the tree T contains A and B at the same level. What is the execution time complexity of your code? 5. You are given an array of size N. Each element of the array can take only one of the three values (0, 1 or -1). You are told to find the longest contiguous sequence of 1s in the array. Write a C function to find the start and end of the contiguous sequence of 1s in the array. Now you are told that you can flip K contiguous sequence of (-1) to 1 where K is a dynamically provided input to the function. In that case, how would you determine the longest contiguous sequences of 1s in the array after flipping K elements which were -1 to 1? What is the time and space complexity of your function? 6. Given an array of N integers, you are asked to find out whether the given array is an arithmetic series (a sequence of numbers where there is a constant difference between any two consecutive numbers of the series). What is the complexity of your function? Now, you are given a modified problem where your task is to convert a given array into an arithmetic sequence by dropping off those array elements which prevent it from being an arithmetic sequence. How would you solve this problem? What is the time complexity of your function? 7. Given an arbitrarily long character string, you are asked to find out the most frequently occurring character as well as the least frequently occurring character. Write a C function to solve this problem, given a character string of size N. Now you are told that instead of being a fixed size character string, you are given a stream of characters which come dynamically as input. At any point in time, you should be able to print the most frequent and least frequent characters in the stream (note that if two or more characters have the same highest frequency, you can choose to print any of them as the most frequent characters). What is the time and space