## Sunday, February 2, 2014

### How to prepare for an interview - 9

Welcome back with a new set of problems. If you didn't check previous posts please start from here. Also if you didn't read previous post read it here.

Remember you should discuss these solutions with me, and refer if there are mistakes or other good solutions.

Problems

82. Search a word in a character matrix.

83. Levenshtein Distance - Edit distance: Given two strings and you can only delete, insert, replace a character - return the minimum number of operations to make s1 = s2.

84. Solve the skyline problem, http://uva.onlinejudge.org/external/1/p105.pdf.

85. Sort an array of 3 numbers.

86. Write a function to calculate the hamming distance between two binary numbers.

87. Write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair -> O(n) solution.

88. Return the value of a roman number given a string.

89. Print out the paths to all leaves of a binary tree.

90. Given a set of n jobs with [start time, end time] find a subset so that no 2 jobs overlap and the length is maximum?

91. You are given a string with each English character translated to its alphabetical position (e.g., the string "ABC" --> "123"). Provide a function that, when provided the string as an argument, will return the maximum number of strings the encoded string could represent (for example, "123" could represent "ABC", "LC", or "AW").