This week's interview questions were prepared for candidates with a background in algorithms in bioinformatics and a few years of C++ experience, with an academic background in statistics. The last two questions in probability are due to Shmuel Fomberg.
.A.
Let S1 and S2 be strings over the same alphabet. The edit distance between S1 and S2 is the smallest number of changes sufficient to transform a substring of S1 into S2, where the changes may be:
1. Substitution --two corresponding characters may differ: KAT -> CAT
2. Insertion -- we may add a character to S1 that is in S2: CT -> CAT
3. Deletion – we may delete from S1 a character that is not in S2: CAAT -> CAT
The cost for every operation is 1, regardless of the operation. Suggest an efficient algorithm for calculating the edit distance between two strings. Suggest a design for an efficient implementation (data structures)
.B.
You have a very large and static text T that you have available a-priory, and a set of strings S that you receive in run-time. Describe a data structure and an algorithm that facilitate efficient multiple queries on the same text. What is the required time complexity for executing a query and getting the result?
.C.
Describe an algorithm for searching the existence of a string S in a text T. Write an implementation in a programming language of your choice. What is the time and space complexity of your solution?
.D.
Describe an algorithm for searching the existence of any string from a set of strings {S1 S2, …, Sn} in a text T What is the time and space complexity of your solution? How will your solution change if you want to know which settings exactly from your set of strings was matched in the text?
.E.
Write an implementation of a function that receives a string containing an arithmetic expression (that has numbers, the +-*/ operators and the parentheses () for precedence ordering) and returns the result of the expression.
.F.
How would you copy a class instance in C++? How would you implement a function that receives the source instance and cloned instance and determines that the two are copies?
.G.
Please suggest an object oriented design for a database layer. So that a developer can write code using an object oriented interface and does not need to know anything about database tables, SQL, etc.
.H.
You have three roads that form a triangle. In every node of the triangle (in every intersection of two roads) there’s one car. At a certain point in time every cars chooses a direction and starts moving. They all start moving at the same time and drive. What’s the probability for a collision? A collision is defined as a meeting where at least one car is headed in one direction and at least one other car is heading in the opposite direction.
.I.
There’s a 95% chance that a car drives by your house within 30 minutes. What is the probability that a car drives by your house within 10 minutes.
