# Interview Questions 6

March 27, 2010 8 Comments

Time for some **relatively** easy **interview** style problems 🙂

1. Given an array of integers A[N], find the maximum value of (j-k) such that A[k] <= k and j > k.(taken from this blog).

2. A certain program makes use of malloc and free several times. Anyway, you forgot to free one block of memory allocated with one malloc. What strategy do you use to check the place where the unpaired malloc is located? (taken from this blog).

3. Find the longest path in a DAG.

4. Given a>0 can you compute a^-1 without any division?

5. 100 digits are chosen at random. What is the probability to find two numbers, a and b, such that a^2=b and each digit is used just one time in forming the two numbers?

6. You are given a sequence of m distinct numbers extracted by a set of 1…n numbers, with m < n. Can you give an efficient algorithm for identifying a number non in the sequence. (taken from this blog)

7. Given stock values for a share per day for a company for last say 1 year. Find the maximum loss that any share holder could have made?. Assume that share holder can buy and sell only once.

8. Given an array of integers from 1 to N, and given a number X, how many ways are there to pick X elements from the array such that no two elements in the selected X elements are consecutive.

9. Given a log file which has customer id and corresponding to that id it has a page id visited by that customer. Given such log files for 3 consecutive days, design an algo to find those customers which visited the site on exactly 2 out of 3 days and visited at least 3 distinct pages. Discuss the design and space complexity. Optimize (question is not about using unix tricks)

10. Given a log file with first field being an url and second being the render time of that page. find the page with least render time. Url is accessed many times like 50 times or 100 times. every access has an entry so we have to find the average.

11. Which is the DS used in dictionary mode in mobile (t9)

12. Write a program which given a numerator and a denominator, prints the fractional value in a special format. eg. Numerator: 1, Denominator: 3. So Num/Denom = 0.3333333333, but output should be .(3) similarly 0.123123 as .(123) also 0.34232323 as 0.34(23)

13. Given a string construct a new string containing the occurrences of unique characters in it. You can

assume that only a-z & A-Z appear in the string with ‘a’ being different from ‘A’. Also the letters in the output string must be in the order of their occurrence in the input string.

e.g. for the string “ThunderBirdFirefox” you must return the string “T1h1u1n1d2e2r3B1i2F1f1o1x1”

14. Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

15. If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it??

The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System.

as 10 = 8 + 2 ==> 10010

also 10 = 5 + 3 + 2 ==> 1110

16. There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers

doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from

the pond and goes to Lord Shiv.This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.

17. Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

18. You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?

19. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. [O(1) space]

20. [ ** Beauty **] Write an Assembly Level Program [ALP] to find sum of first n natural numbers using the following Instructions

**LDA num **; load Accumulator with num

**DCR R **; decrement Register R

**INR R** ; increment Register R

**MOV x,y** ; move the contents of register y into register x

**JZ label** ; jump to label if A=0

**DJNZ label**; Decrement & Jump if A 0

you can use B & C registers in addition to A register

9.) Maintain 2 hash tables & .

Look for & respectively.

much better approach than this is required I feel. 🙂

1. findLargestSpan(int a[],int n)

{

int i,j,k;

int maxspan;

for(j=n-1,k=n-2;k>=0;k–){

if(a[j]>=a[k]){

if(j-k>maxspan) maxspan=j-k;

}

else j=k;

}

}

18 trie tree or compressed trie tree

16 x=15 y=16

13 traverse the string and in a hashmap stroe the count. now second time traverse the string.. print the character if its count >3 with the count and make make count=0 for that character( so that you dont print it again)

14

reverse the second half and then do bitonic sort..

I very lucky to find this website on bing, just what I was looking for 😀 besides saved to favorites.