Interview Experience 20

##First Skype:

• Given a number N. Find the number of numbers having N bits which don't have two consecutive zeros in their binary representation. He was expecting Log(n) time complexity solution.
• Discussion on how to solve linear equations using matrix exponentiation method and how to design transformation matrix for that.

##Second Skype:

• There are M subjects. Given a matrix of M*N. Any cell score(i,j) represents the score you will get after spending j hours on ith subject. You have T hours. Maximize the score you can get in T hours. It is guaranteed that score[i][j]<=score[i][j+1]. You can read any subject at most once.

##Third Skype:

• Discussion on projects.
• What happens when you hit an URL in browser? Does browser try only once to open an URL? Does browser make more than one http requests to open a page?
• What is process? What is thread? There is one very CPU intensive task given. You have to run it on single core highly prallelable CPU. What would you prefer to use thread or process? Why?
• You have to print "foo" with probability 1/50 and "bar" with probabilty 1/20. how will you do it?
• You have a bucket of size K. A stream of infinite numbers is coming. At a given time bucket will contain those k elements which have a probability of being in that bucket is 1/N. N is the number of numbers that have already come.
• Design a twitter app such that if you are at a location, you can find all the tweets within the 2 Kms radius from your location.
• An employee table is given which contains employee id, employee first name, employee last name. When we make query of type: "where last_name=variable", it searches all the data to get that. How can you optimize it using another sql query?
• What is the solution for critical section problem? Is there any other technique except semaphore to solve the critical section problem? If a resource has multiple instances, then how will you solve critical section problem?
• You are given a file which contains k distinct words w1, w2, w3,...,wk. For each word you are given the occurence positions for that word. You need to find the smallest range in which each word has occurred at least once.