Saravanan Anna's Questions Coll'n-2

1. Given a very large sorted array. You don't know the number of elememts, present in the array. How will you find out if the given number is present in the array or not.
 
2. Try to design an efficient data structure to implement t9 search and insert.
 
3. Given a pre-order traversal of a binary search tree. Is it possible for us to re-construct the tree from this.? If so, write a neat code to do that otherwise justify your thought.
 
4. Given a list of all common english words. Design a data structure to do t9 search. Ex: input: 2253 then the output shoule be able, cake, bald, calf etc. You can assume you've infinite amount of memory.
 
5. Write a neat code to do 'atoi'- string to integer. Refer C libray for further info. This is easy question but needs more attention to come up with clean code.
 
6. Given an increasingly sorted integer array with no duplicates. Think a of clean logic to find out if any element with property 
a[i]= i. The element is equal to the index in which it is present.
 
7. Given N number of files and a word. Find all files in which the word occurs. Discuss all possible solutions and complexities.
 
8. Given a file with one word per line. Write an algorithm to find the non repeating words. Try to write unix command to do the same. You may not be knowing this. But google it and find the answer.
 
9. Given an array of integers. Find gcd and lcm of them.
 
10. Given a binary search tree. We need to store this tree in a file and be able to re-constuct the same tree again. Think of possible logics to solve this prob.
 
11. Givn a file with billions of numbers- one per line. You need to find out the top k(which is less than 10,000) numbers among them. Design a neat logic to find that. Assume that you can not store all the billion numbers in main memory- which means you can't sort all numbers at a time.
 
12. Given an array and a number. Find all pairs such that their sum is equal to the given number. Discuss all possible solutions.
 
13. Given two integer arrays and a value as input. Find two elements one from each array elements one from each array such that their sum is equal to the given value. Write a neat code.
 
14. Given two binary trees A and B. Write a neat working code to find if B is a sub-tree of a A. Don't worry about the time complexity.
 
15. Given a string. Write a neat code to say Yes if we can form a palindrome by re-arranging the letters of the given string otherwise No. Discuss various solutions.
 
16. Given an array of n elements and a number k. You need to left rotate the  array by k times. Ex: array has 1, 2, 3, 4 and 5 then rotating it by 3 times gives 4, 5,1, 2 and 3. Discuss the possible solutions, time and space stuffs.  
 
17.Given an array of numbers and a value. Write code to find if there exists a subset of numbers from the array such that summing up the elements in the subset equalts to the given value.  Ex: 1, 2, 5, 8, 6, 10 and the value is 17. One of the subsets is 1, 6, 10 whose sum is 17. So that is the output is true.  Don't worry abt the time or space complexity. Just a working code is fine. :)    
 
18. Given an array of n distinct integers- n is always odd. Gind the median of the array. Median is the one which appears in the middle of the array after sorting. Don't modify the array and no extra space is given.
 
19.Read the man pages of the following commands when you're free in unix lab: top, sort, uniq, du, df, free, cut and paste. Discuss with ur friends. 
 
20. Given a binary tree. Write an algorithm to find if the tree is actually a balanced binary tree. Discuss the complexities.
 
21. Given an array and a value. You need to tell if there exists two numbers from the array whose sum is less than the given value. Write a very very neat code. Tell me the space and time complexity.
 
22. You have a folder wherin you've 1000 files-it may be inside another directory of the given directory. In all the files you need to replace the occurrence of the wore 'fail' by 'pass'. Write unix commands to do this job.
 
23. Read the manual pages of the following commands: awk, sed, grep and find. Discuss with your friends. Happy learning. :) 
 
24. Implement wc command with all the options. Write test cases. Discuss with your friends.  
 
25. Given a directory. Write unix cmd to list all the contents of this directory with permission and all other fields. Wait! This is easy! Just do ls-l. now i want you to print only file name and permission. I dont want rest of the fields. Think abt doing this.s
 
26. Awk is indeed one of the great commands in unix. It's friendly c-like language but you can learn simple usage of this command to appreciate it. Happy learning. :-)