Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

785

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

Apr 16, 2013

Apr 24, 2011
 Given a string, remove all the duplicate characters (not necessarily consecutive)9 Answersvoid removeDuplicates(char *in, char *out) { bool seen[NUM_CHARS] = {false}; while (*p != 0) { if (seen[*p] == 0) { *out++ = *p; } seen[*p] = true; } }public class StringRemove { private final String baseString = "abcdefghijklmnopqrstuvwxyz12345678910"; private final List finalMap = new ArrayList(); private StringBuffer sb = new StringBuffer(); private void findDup(){ for(int i=1 ; i <= baseString.length() ; i++) { String sLocal = baseString.substring(i-1, i); if(finalMap.contains(sLocal)){ finalMap.remove(sLocal); }else{ finalMap.add(sLocal); } } String s = finalMap.toString(); s = s.replace('[',' ').replace(']',' ').replace(',', ' ').replace(',', ' ').trim().replaceAll(" ", ""); System.out.println(s); } public static void main(String s[]){ StringRemove sr = new StringRemove(); sr.findDup(); }void RemoveDuplicates(char[] arr, int length) { Map charMap = new Map(); int currenPosition = 0; for (int i=0;i

Jan 27, 2012
 Describe a routine which returns the set of integers in {1..100} divisible without remainder by 3 but not by 9.12 AnswersI'm assuming the question wants us to find integers that are divisible by 3 but not by 9. This can be easily obtained using a mod function inside the following if statement: if(number % 3 == 0 && number % 9 != 0) Here is a short program I wrote in c++ to show how to solve this problem. Instead of returning the set of integer, I just printed them out on the screen: #include #include using namespace std; int main(int argc, char** argv) { int i = 0; vector list; vector::iterator it; for(i = 1; i <= 100; i++) { if(i%3 == 0 && i%9 != 0) { list.push_back(i); } } for(it = list.begin(); it != list.end(); it++) { cout << *it << endl; } return 0; } If I missed anything, please let me know. Happy coding and problem solving!That'll certainly work, Tyler, but the OP indicated he was interviewing for a Ruby On Rails - not C++ - gig.put those integers into an array, pick every third element, out of which discard every third element.Show More Responsespython [x for x in range(0,100) if x % 3 == 0 and x % 9 != 0]1) start from number = 3 Loop while(number <= 100) 2) display number 3) number = number+3, display number 4) number = number+6 Loop(1..100).map { |i| (i % 3).zero? && !(i % 9).zero? ? i : nil }.compact(1..100).select { |x| x%3 == 0 && x%9 != 0matt has the best answerA variation on Matt's answer: (1..100).select { |n| n % 3 == 0 }.reject { |n| n % 9 == 0 }The requirement doesn't say if the input has to be a Range. If it doesn't have to be, then we don't need to traverse each element but to simply calculate it. def get_nums_by_3_not_by_9(max) arr = [] x = max.to_i / 3 x.times do |i| next if i % 3 == 0 arr << i * 3 end return arr end(1..100).select do |n| n%3 ==0 and n%9 != 0 end(1..100).to_a.delete_if{|x| !(x%3==0 && x%9>0)} or (1..100).to_a.select{|x| x%3==0 && x%9>0} or (1..100).to_a.map{|x| x%3==0 && x%9>0 ? x : nil}.compact or (1..100).to_a.reject{|x| !(x%3==0 && x%9>0)}

Apr 24, 2011

Apr 24, 2011

Mar 26, 2012
 Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. Output the result on iteration y10 AnswersThe description of the problem was very fussy at first. Hi didn't mention the "see and tell" algorithm, just started to show some example inputs and outputs on collabedit and asked to code a function to generate those outputs.FYI : http://en.wikipedia.org/wiki/Look-and-say_sequenceHere is a quick solution in PHP: 0){ \$seed = str_split(\$seed); \$output = ""; \$last = \$seed[0]; \$count = 1; for(\$i=0;\$i

Aug 16, 2010
 There are n pots with different # gold coins in them. Two players play a game, where each player can select a pot at either ends. maximize the gold7 AnswersUse dynamic programming to solve the same. Could explain the logic, but again did not find the time to code it up.What does "maximize the gold" mean in this game? If it means to keep the heavier pots for the end of the game and keep the two sides balanced, then I think you need to sort the N pots and redistribute so that the heaviest is in the middle and the two sides are balanced. Since a pot can contain only a limited number of gold, I would use a count sort algorithm for an average time of O(N+k). When re-distributing, I would balance the two sides starting by the heaviest pot, according to the individual sides's weight. For example: 1, 4, 10, 2, 3, 4, 2 Counting sort: 1:. 2:.. 3:. 4:.. 5: 6: 7: 8: 9: 10:. Sorted list: 1, 2, 2, 3, 4, 4, 10 If K is odd, remember the heaviest = 10 Re-distributing by weights: 4, 3, 1 4, 2, 2 Final list: 1, 3, 4, 10, 4, 2, 2To maximize the gold means, each player wants to maximize the amount of gold the player gets by selection of one pot at a time (either leftmost or rightmost). Player 1 selects a pot, followed by player 2, followed by player 1 etc. How does the player select picking Left or right one ? Maximize gold means sum of the gold coins of all the pots selected by a player. I did not follow how sorting helpsShow More ResponsesHow about take differences and get the side that gives you a better gain. For example: 8 7 4 6 Take 6 Then take 7I think the idea is that each person takes turns choosing the currently leftmost or rightmost pot and tries to maximize the sum of all the pots they take. You can't be greedy because of situations like this: 10, 100, 10, 5 If you were greedy, you would take 10 first, and the other person would take 100. If you instead took 5, they would be forced to take one of the 10's, leaving the 100 available for you to take. The recursive idea here is minimax. The maximum I get from X to Y is the maximum of either the gold at X + what's left over when the other player takes from X+1 to Y, or the gold at Y + what's left over when the other player takes from X to Y-1. As an implementation note, we should keep track of the amount both players get over each interval. If the other player gets R gold, with T gold leftover for me, when choosing from the subrange X+1 to Y, then from the range X to Y, I can easily say that if I choose to take the gold from X, I get T + gold[X] gold, leaving R gold for the other person. This makes the code much simpler. Since each case is based only on subcases of a smaller length (e.g. from X to Y, which is length Y - X, only depends on X to Y-1 and X+1 to Y, both of length Y-X-1), we can build up the cases in order of length. C++ DP implementation would look something like this: pair dp[n][n]; for (int i = 0; i L = dp[i + 1][i + len]; pair R = dp[i][i + len - 1]; if (gold[i] + L.second > gold[i + len] + R.second) dp[i][i + len] = make_pair(gold[i] + L.second, L.first); else dp[i][i + len] = make_pair(gold[i + len] + R.second, R.first); } } The amount of gold I get is dp[0][n - 1].firstUse induction: Suppose that I know how to play best with N arbitrary pots. What's my best move with N+2 pots? Trivial cases: N=0 and N=1. With N+2 pots, I can chose L or R. After that my opponent chooses L or R. Then it's my turn again, but this time, with N pots, I know how to play, by induction hypothesis. So what's the best move? It's the one that maximizes the worst case scenario (that is, my opponent playing her best). What's the worst if I pick the left? It's the value of the left pot plus the minimum of two scenarios: 1. the opponent picks L and I do my best with what's left and 2. the opponent picks R and I do my best with what's left. I do the same calculation assuming that I take the right first. The best of the two worst scenarios maximizes my goal. Here's the code in C++: enum Move ( L, R, E }; // left, right, end of game Move BestMove(int const * left, int const * right, int & minGain) { if (left == right) // there's nothing left in between { minGain = 0; return E; } if (right - left == 1) // just one left { minGain = *left; return L; // arbitrary choice } // I take left, she takes right int xLL; BestMove(left + 2, right, xLL); // I take the left, she takes the right, or vice versa int xLR; BestMove(left + 1, right - 1, xLR); // I take the right, she takes the right int xRR; BestMove(left, right - 2, xRR); // my worst if I take left int wLeft = *left + std::min(xLL, xLR); // my worst if I take right int wRight = *(r-1) + std::min(xLR, xRR); // the better of the two minGain = std::max(wLeft, wRight); return (wLeft >= wRight)? L: R; } void main() { int pots[] = { 2, 4, 10, 2, 3, 1 }; int minGain; Move m = BestMove(a, a + 6, minGain); }Dynamic programming public class GoldPots { public static int max(int a, int b) { return a < b ? b : a; } public static int solve(int[] a, int player) { int n = a.length; int[][] m = new int[n][n]; int[] sums = new int[n]; sums[0] = a[0]; for(int i = 1; i < n; i++) { sums[i] = sums[i-1] + a[i]; } for(int i = 0; i < n; i++) { m[i][i] = a[i]; } int sumij; for(int k = 1; k < n - 1; k++) { for(int i = 0; i < n - k; i++) { for(int j = i + k; j < n; j++) { sumij = sums[j] - sums[i] + a[i]; m[i][j] = max(sumij - m[i + 1][j], sumij - m[i][j-1]); } } } return m[0][n-1]; } public static void main(String[] args) { int[] a = {1,9,5,3,6,2}; System.out.println(solve(a,0)); } }

Dec 24, 2011