How to prepare for an interview - 13

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

121. Divide two numbers a and b.

122. Sort a binary tree and give the complixty of that.

123. Find all sub sets of size k from given set.

124. Given a sorted array and number x, return the index of this number in the array and if not exist return the index it should be inserted in.

125. Implement a read/write lock, given a mutex that has lock() and trylock() interface.

126. Prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 10 + 10 + 1 + 1 + 1 + 1 (6 coins), and we take the average of these coins, we would see that the average comes out to ~4.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.

127. Implement a stack using only queue(s).

128. Print a bst in a sorted order.

129. Write a function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1].

130. Given a m*n grid starting from (1, 1). At any point (x, y), you have two choices for the next move:
     1) move to (x+y, y);
     2) move to (x, y+x);

From point (1, 1), how to move to (m, n) in least moves? (or there's no such a path).

Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 12

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

111. Check if 3 points are collinear.

112. Given coins of values 1, 5, 10, 25 and Sum S, give the min number of coins that can represent S.

113. Given an array of integers, return the number of longest increasing subsequence.

114. A table composed of N x M cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.

115. 0-1 Knapsack problem.

116. Fractional Knapsack problem.

117. Matrix multiplication.

118. Given a sorted array with duplicates, search for the start index and end index of an element using binary search.

119. Find different combinations of all the digits of an integer number with some conditions like sum < k and they can be grouped together to form a combination.

120. Given two sorted arrays, no duplicates, could be any size, return the median number in faster than O(n) time.

 Done.

Read next post. Share this post to your Facebook, Twitter, LinkedIn.

How to prepare for an interview - 11

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

101. Given an array of distinct integers, and a target integer t, compute all of the subsets of the array that sum to t, where order matters.

102. Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.

103. Reverse an array.

104. Two texts are considered to "match" if they have a common substring of at least length n. Describe an algorithm to determine if two strings are matches.

105. Given N credits cards, determine if more than half of them belong to the same person/owner. All you have is an array of the credit card numbers, and an api call like isSamePerson(num1, num2).

106. Compress a string.

107. Given an integer, return all sequences of numbers that sum to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1)).

108. Given an unsorted array, extract the max and min value using the least number of comparison.

109. Max sum of adjacent value combination in an array.

110. Provided a phone number (654-876-0987), return all possible strings that the phone number could represent if 2 -> {A, B, C}, 3 -> {D, E, F}, and so on.

Done.

Read the next post. Share it on Facebook, Twitter, LinkedIn.

How to prepare for an interview - 10

Back to a new set of problems. If you didn't read previous posts start from here. Read previous post here.

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

Problems

92. Combinations(n, k).


93. Write a program to sum two binary numbers represented as strings.


94. Compute the cubic root.


95. You have two lists with meetings scheduling (start time, end time) Meetings in single list don't intersect. Find all intersecting meetings across the two lists.


96. Given a binary search tree, write an algorithm to find the kth smallest element.


97. Given a string, return true if it's a palindrome. Only alphanumeric characters considered. Do this in one pass through the string.


99. Write a function that calculates input strings with operators +,-,*,/ eg. "5+5*6" should output 35.


100. Longest common substring between two strings A and B.


101. Find the predecessor of a binary search tree.


Now we finished this post, Read next post. Please share this post on your Facebook, Linkedin, and Twitter.

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").

Now we finished this post, Read next post. If you liked this post please share it on Facebook, Linkedin, and Twitter.

How to prepare for an interview - 8

Welcome back with a new post and new problem set. You may need to read previous posts from here. Or read previous post from here.

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

Problems

72. Given an array of integers, find the sub array with the largest sum.

73. Palindromes possible from a string without extra space.

74. Prime factors of a given number.

75. Implement strstr().

76. Convert a binary number to its gray code.

77. Convert a gray code to its binary representation.

78. Given two unsorted arrays, one with event start times and one with end times, find out if any two events overlap.

79. Reverse double linked list.

80. Given a bipartite graph, separate the vertices into two sets.

81. Given two strings representing integer numbers ("123" , "30") return a string representing the sum of the two numbers ("153").

Now we finished today's set of problems, Read next post. Please share the post on your Facebook, Linkedin, and Twitter.

How to prepare for an interview - 7

Welcome to the seventh post in the How to prepare for an interview series. If you didn't read previous post please read it from here.

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

Problems

62. Given a List structure where each node contains a Next node and optionally a pointer to another list, flatten that list.

Input:

 L1 --> L2 --> L3 --> L7 --> L8
                          |
                         v
                         L4 --> L5-->L6

Output: 

L1 --> L2 --> L3 -->L4 -->L5-->L6-->L7-->L8

63. Interleave two linked lists (e.g. {1, 2, 3} & {4, 5, 6} would return {1, 4, 2, 5, 3, 6}).

64. Write a simple regular experession parser using ., *, +, ?.

65. Given a list of strings, return a list of lists, where each list consists of words that are anagrams." Example: Given ["cab", "cz", "abc", "bca", "zc"] the output should be: [ [ "abc", "bca", "cab"] , [ "zc", cz"]].

66. Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions for example if they give you "abc" you print out {a, ab, abc, ac, b, bc, c}.

67. Method to return sqrt of a number.

68. Program "atof", which means convert a string float (e.g. "345.44E-10") to an actual float without using any existing Parse Float functions. This is not hard but gets messy.

69. Function to check if any 3 numbers sum to x.

70. Merge two sorted arrays together.

71. Given an array, remove the duplicates and return a unique array keeping the first occurrence of the duplicates and the order. [@2, @1, @3, @1, @2] --> [@2, @1, @3].

Now we finished this post, Read next post. Please share the post in case you liked it.