# Interview Questions 13

September 5, 2010 1 Comment

1. Give a string, print total count of substrings (length>=2) which are palindromes. He was expecting better than O(n2) time complexity.

2. How do you implement a linked list without using dynamic memory allocation? So basically you need to use an array as a linked list.

3. Give an algorithm to compress a memory. To be more clear if you are given a memory of some stored data here and there and some empty and null memory in between, how will you fragment and compress your memory?

4. Given a 3d plane, and infinite points find kth closest point from a given point.

5. Given a statement which took an integer, incremented it by 1 and then branched to another location which you provide, implement addition of two numbers multiplication, etc using just that statement

6. You dont know the required size of the array.how will you allocate space for the array.for eg. if you allocate 100 blocks then user can have just 10 elements or 1000 elements.

7. What happens after entering URL address at the browser(details of how we get to see the web page)?

8. Sorted Array is rotated n times. You have to find the current index of the some element X. If element is not present then return the maximum element of the array in O(log n).

9. There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

10. Given a dictionary of words and a string with all spaces removed, return whether the string is composed of valid words

e.g

helloworld-> hello world (valid)

isitniceinhere-> is it nice in here (valid)

zxyy-> invalid

1. I know how to do in N^2. but m unable to do in less than this.. please give some hint..