Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

759

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

Mar 29, 2010

### Software Development Engineer at Amazon was asked...

Jun 8, 2009

May 8, 2010

May 15, 2010

Feb 7, 2011
 Implement a power function to raise a double to an int power, including negative powers.11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills.#include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv); int b = atoi(argv); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } }c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; }Show More Responsesint power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; }C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); }double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; }I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation...I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; }Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact?TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution.public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; }

Feb 9, 2013

### Software Development Engineer at Amazon was asked...

Feb 27, 2010

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;iShow More Responsesto the last two - just use a boolean array instead of a map or list like Interview Candidatepublic class Duplicates { public static String removeDuplicates(String str){ int[] chars = new int; StringBuffer sb = new StringBuffer(); for(int i = 0; i < str.length(); i++){ int val = (int)str.charAt(i)-97; if(chars[val]==0){ chars[val]=1; sb.append(str.charAt(i)); } } return sb.toString(); } public static void main(String[] args){ String res = removeDuplicates("faaabook"); System.out.println(res); } }each char has ASCII code number, so just XOR all those numbers together, duplicates will eliminate each other.void remove_duplicate(char * str, int len) { bool appeared[NUM_CHARS]; memset(appeared, 0, sizeof(appeared)); int i = 0, j=0; while(i < n) { if(!appeared[str[i]]) { str[j] = str[i]; j ++; appeared[str[i]] = true; } i ++; } str[j] = '\0'; }store each characted in hashset and them combineI mean combine them