Software Engineer New Grad Interview Questions
Software engineer new grad interview questions shared by candidates
Top Interview Questions
| Implement division without using multiplication or division. It should work most efficient and fast. 11 Answersexp(ln(a)-ln(b))=a/b What if one or both of a,b is less than zero. ln(x) for x < 0 is not defined. we can use bit shift operator. e.g. 4 is 100 in binary we want to divide 4 by 2 so right shift 4 by 1 bit 4>>1, so we get 010 which is 2. Show More Responses This solution rounds down to the nearest signed integer // Implement division without using multiplication or division. It should work most efficient and fast. int Divide(int divisor, int dividend) { int divisionCount; int tmp = dividend; if (tmp - divisor > 0) { tmp = tmp - divisor; divisionCount++; } // This will apply the correct sign to the quotient if ((divisor & 8) ^ (dividend & 8) != 0) { divisionCount = divisionCount | 8; } return divisionCount; } // correcting previous answer int Divide(int divisor, int dividend) { int divisionCount; int tmp = dividend; if (tmp - divisor > 0) { tmp = tmp - divisor; divisionCount++; } // This will apply the correct sign to the quotient if ((divisor & 0x80000000) ^ (dividend & 0x80000000) != 0) { divisionCount = divisionCount | 80000000; } return divisionCount; } can anyone post solution in java? public class Solution { public static void main(String[] args){ int top=32; int bottom=4; int count=0; boolean negative=(top*bottom)=bottom){ top=top-bottom; count++; } System.out.print((negative)?"-":""+String.valueOf(count)+"..."+top); } } Obviously the interviewer would not allow us to use Math functions like exp, log etc. We are supposed to use the Long division method or the Newton Raphson method to find the quotient. Newton Raphson is the fastest but uses operator * (multiplication) though. http://stackoverflow.com/a/5284915 Python version that gives you an idea how it works: i = 0 while divisor = 0: if dividend >= divisor: dividend -= divisor result |= 1 >= 1 i-=1 plus some code to check for 0 and support negative values #Write a program to do division without division or multiplication 2 3 def division(dividend, divisor_initial): 4 divisor_final = divisor_initial 5 quotient = 1 6 while dividend - divisor_final > divisor_initial: 7 quotient += 1 8 divisor_final = divisor_final + divisor_initial 9 number = divisor_final - divisor_initial 10 remainder = dividend - divisor_final 11 return quotient,remainder 12 13 14 def main(): 15 print division( 101, 3) 16 17 18 if __name__ == "__main__": 19 main() |
| Write a function that finds the median of a set of three numbers, also find the Big O. Can it be done with only 2 comparisons, or do you need 3? 10 AnswersPick two numbers: A and B, Add the third number to each of the first two : (A+C), (B+C). Compare these two numbers and take the lesser of the two. Now compare C with the other member of the less number. The greater of these two is the median. I'm not following. Is this: say, B+C is less than A+C, then the larger of B and C is the median? If so, isn't this a counterexample: A = 2, B = 1, C = 3? Actually the answer is the next one: we could have an answer using only two comparisons. The main idea is that we need to examine one of the numbers to get into the segment created by the other two numbers. And another important thing is that one comparison could be used to definitely determine for both two segments created by two numbers. For example we are trying to examine number A and we have two segments formed by B and C numbers: [B; C] and [C; B]. But considering that for determining if A is in the segment created by B an C we need to make the following comparison: (A - B) * (C - A) >= 0. It is easy to notice that if A is in segment [B; C] (B is less or equals to C) we have both multipliers are positive but in an opposite case when A is in segment [C; B] (C is less or equals to B) we have both that multipliers are negative. If former comparison is negative - then number A is not in any of segments [B; C] or [C; B]. And here is a code of function on C/C++: int medianOfThreeNums(int A, int B, int C){ if ((A - B) * (C - A) >= 0) { return A; } else if ((B - A) * (C - B) >= 0) { return B; } else { return C; } } Show More Responses if (B-A) > 0 if (C-B) then B else C else if (C-A) > 0 then A else C a=b=c ? First get two numbers: x = a - b y = a - c now there are four possible cases for x and y if x & y are both positive => a is bigger than both b and c.=> choose bigger of b & c if x & y are both negative => a is smaller than b and c => choose smaller of b & c if x is positive and y is negative => a is bigger than b but smaller than c => choose a if x is negative and y is positive => a is smaller than b but bigger than c => choose a void GetMedian(int a, int b, int c) { int small, large; if (a < b) { small = a; large = b;} else {small = b; large = a;} // Check where c lies: if (large < c) return large; else if (c < small) return small; else return c; } @Moy: if the answer turns out to be small, then haven't you done 3 compares? Running Vitalii's code with a = 1, b = 7, and c = 3 produces a median == 7, which is incorrect. Suggestions? Vitalii's solution works for me. def find_median(a, b, c): ab = b - a bc = c - b if -ab * (ab + bc) >= 0: return a if ab * bc >= 0: return b return c |
Software Engineer - New Grad at Google was asked...
| Given a base 10 number, print the hexidecimal (base 16) representation of that number. 7 Answerspublic void printHex(int d) { string s = ""; int m = 0; int next = d; int a[16]; a[10] = "a"; a[11] = "b"; a[12] = "c"; a[13] = "d"; a[14] = "e"; a[15] = "f"; while (next > 15) { m = next % 16; if (m > 9 && m < 16) s = a[m] + s; else s = m + s; next = next / 16; } system.out.println(s); } B's answer doesn't work. I think a quick fix (besides all of the issues like incorrect array initialization, setting int to string, etc) would be to change while loop to a do while and the conditional to next > 0. Here is a generic solution passing radix which also handles negative numbers: public static String intToStr(int val, int radix) { char[] digits = new char[36]; for (int i = 0; i < 10; i++) { digits[i] = (char)('0' + i); } for (int i = 10; i < 36; i++) { digits[i] = (char)('A' + i); } String result = ""; boolean negative = false; if (val < 0) { negative = true; } val = Math.abs(val); do { result = digits[val%radix] + result; val = val/radix; } while (val != 0); if (negative) { result = "-" + result; } return result; } String buffer = new StringBuffer(); while (n > 0) { int base = n% 16; buffer.append((base<10 ? base : (Char)('a'+base-10)); n /= 16; } String result = buffer.toString().reverse(); Show More Responses lol, I wonder if this is acceptable printf ("%x",n); //n being the base 10 number To any base. private static String toBase(int number, int base, boolean literal){ String baseResult=""; while(number > 0){ int n = number % base; if(base == 16 && n > 9 && n < 16){ baseResult += getBase16Char(n); }else{ baseResult =n + baseResult; } number /=base; } return literal ? baseToLiteral(base).concat(baseResult) : baseResult; } private static String baseToLiteral(int base){ switch(base){ case 2: return "b"; case 8: return "o"; case 10: return "d"; case 16: return "x"; default: return "("+base+")"; } } private static char getBase16Char(int digit){ char[] base16char = new char[16]; base16char[10] ='a'; base16char[11] = 'b'; base16char[12] = 'c'; base16char[13] = 'd'; base16char[14] = 'e'; base16char[15] = 'f'; return base16char[digit]; } To any base. private static String anyToBase(int number, int base, boolean literal){ String baseResult=""; while(number > 0){ int n = number % base; if(base == 16 && n > 9 && n < 16){ baseResult = getBase16Char(n) + baseResult; }else{ baseResult =n + baseResult; } number /=base; } return literal ? baseToLiteral(base).concat(baseResult) : baseResult; } private static String baseToLiteral(int base){ switch(base){ case 2: return "0b"; case 8: return "0o"; case 10: return "0d"; case 16: return "0x"; default: return "0("+base+")"; } } private static char getBase16Char(int digit){ char[] base16char = new char[16]; base16char[10] ='a'; base16char[11] = 'b'; base16char[12] = 'c'; base16char[13] = 'd'; base16char[14] = 'e'; base16char[15] = 'f'; return base16char[digit]; } public String toHex(int num) { if(num == 0) return "0"; char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}; String result = ""; while(num != 0){ System.out.println((num & 15)+ " "+ result); result = map[(num & 15)] + result; num = (num >>> 4); } return result.toString(); } |
Software Engineer New Grad at Yelp was asked...
| We have a fairly large log file, about 5GB. Each line of the log file contains an url which a user has visited on our site. We want to figure out what's the most popular 100 urls visited by our users. 6 AnswersPossible Solution: not necessary the right one. Notes: Will recommend use non recursive version of quick sort since 5GB log file could be considered to generate URL data to 500 MB ball park and worst estimate. That would blow the below solution. Also keeping the file open all the time while reading rather than putting it in buffer, since 5GB is a large file size and that may not hold in the memory provided for the program. Will have to ensure that file remains untouched in those moments. # Program to find the URLS that have been most referenced and used from a log file. import sys # Function that will quicksort the list of tuples that have occurence number as first # element in tuple and the URL as the second element in the list. The list is sorted # from the least referenced to most referenced as done in classical quicksort. # From: www.algolist.net/Algorithms/Sorting/Quicksort def sortDict(impurllist, left, right): i, j = left, right - 1 pivot = impurllist[int((left + right) / 2)] while (i pivot[0]): j = j - 1 if (i len(urllist): for element in reversed(urllist): print(str(element[1]), '\t', str(element[0])) else: j = -1 for i in range(num): print(str(urllist[j][1]), '\t', str(urllist[j][0])) j = j - 1 # Definition of main. def main(): try: int(sys.argv[1]) except ValueError: print('Please input a integer for the number of URLs you want to view.') return # Terminate program execution if the arguments provided are not right. if len(sys.argv) != 3: print('Usage: python3.2 HighURLFinder.py #URLs_you_want Log_file') return else: logdict = readLogFile(sys.argv[2]) if logdict is None: return # Terminate execution since the file read program encountered error. else: impurllist = sortLogDict(logdict) showUrlLast(impurllist, int(sys.argv[1])) # The starting point of the program main() Quick Sort is O ( n log n ) avg case, so we could do better O (n) Now, onto design : Do the lines have other information other than URL? If so, we need to filter them out using Regular Expressions. Possible O (n) solution: A hashmap with URL's as keys and number of hits as values would yield a O(n) run-time to populate it. Algo: while input from file getURL (or filter out URLs from line) if URL exists in hashmap, increment its count else add URL to hashmap Ofcourse, being a large data set, we might get a ton of random disk seeks due to paging of memory. After profiling, if we really find that to be a problem then we could do something like encode the urls into something smaller that takes less space and hence has a lesser probability of causing paging. I can think of few more solutions but I think this should be sufficient. I would add a min-heap of size 100 to BetterSolution's answer (in order to get the top 100). Show More Responses cat log | sort | uniq -c | sort -k2n | head 100 Well, I believe, we can create a HashMap with as the key and visit times as Value. Once we get all the values(i.e. URL visited), we can do a Min Heap Sort. Its like saying I have n number in an array and I need to find top k number (n>>k) ,So applying Min Heap would cost O(nlog k), whereas if we use the best sorting technique, we get O(n log n). But Hey @ David Response is a smart one in relevance to FrontEnd Engg position. If you don't need 100% accuracy, which in this case you probably don't, you can use a Count-Min-Sketch data structure to come up with a pretty accurate estimate ( with some acceptable degree of error ) in a streaming fashion. Very little memory needs to be used in this approach. |
| Write a function that takes in an integer and returns the number of ones set in the binary representation. 4 Answerscount = 0 while(num) { num &= num-1; count++; } return count; I thought the question was asking how to convert the integer to binary code and output it. function getOnes($int) { return substr_count(decbin($int), '1'); } Show More Responses __builtin_popcount(num) :D |
| If you had a savings account with $1, at a 100% interest rate, at what year would you have 15 billion dollars? 4 AnswersUse the power of 2's to get to the answer. Log base 2 of 15 billion You should know offhand that 2^10 is 1024, so 2^20 = 1024^2 is approx a million, 2^30 is approx a billion, then you need four more years to get to 16 billion. Remember that you started with 1, not 2, so the answer is 35 years, not 34. Show More Responses After 34 years you would have 16 billion. That is to say, you would have 15 billion in the 34th year. |
Software Engineer - New Grad at Yahoo was asked...
| None I could think of, I prepared everything from careercup yahoo questions and programming interviews book. I dint had an offer during the time I was writing this. 1. find right cousin of a given node. 2. simple oop and data structure questions. and lots of simple questions checking my ability to handle things in log(n) complexity. 3. binary search - took me into situation I wrote code in 3 diff, prog. lang's 3 AnswersDid you finally hear from them? I too am waiting for a response from 2 weeks. I did try to call them around 50 times may be and 20 emails..finally the answer was NO. But just might be common sense thing, if the recruiter hasnt contacted, then the candidate was rejected. I hope I dint even believe my common sense, and dragged the situation. However the situation will not always be same for everyone. Good luck Samir, Hope you have a chance at Yahoo Thanks Vakshu. After seeing your response, I called up the HR (already sent a couple of emails). She says "I was good at the interviews. But the position was filled with another candidate. And they are finding another position for me." God knows. Whats the matter. If the position was already filled, why did they call me then? They should really stop playing with the sentiments of candidates. All of us prepare so hard to finally know that we are being turned down. I am not saying rejecting a candidate is hurting him/her. But delaying the result certainly hurts. I am no more hopeful !!! |
| Isomorphic trees 3 Answers(print a tree, level by level) public static void printTree(Tree t) { int treeDepth = findDepth(t); for (int i = 0; i 0) { printLevel(t.left, level-1); printLevel(t.right, level-1); } } (a^3 + b^3 = c^3 + d^3) public static void a3b3c3d3() { Hashtable> h = new Hashtable>(); for (int a = 0; a prev = h.get(lhs); if (null == prev) prev = new ArrayList(); for (String s : prev) { System.out.println(a + " " + b + " = " + s); } prev.add(a + " " + b); h.put(lhs, prev); } } } (profit maximization) partition prices into non-decreasing sequences; buy at start of sequence of each sequence and sell at end; can be done iteratively by peeking ahead to next day's closing price |
Software Engineer - New Grad at Google was asked...
| Given a list of integers of at least length 7, print the average of each consecutive 7 number long subsequence (sliding window). 4 Answerspublic static void slidingAvg(int[] vals, int everyN) { int total = 0; for (int i = 0; i = everyN) { System.out.printf("%f\n", (double)total/(double)everyN); total -= vals[i-everyN]; } if (i < vals.length) total += vals[i]; } } public static void averageOf7InList(List list){ int last = 0; // just for range tracking int i = 0; do{ if(i+6 < list.size()) i += 6 ; else // i += list.size()-i; not requested :) break; double average = 0.0; int j = last; for(;j < i; j++){ average += list.get(j); } System.out.println("Result : i: "+ i +" Range: from "+last + " to : "+i+" Average: " +(double) (average/j)); last = i; }while(i < list.size()); } static void printAveragesForWindow(list ints, int windowSize) { // need at least windowSize elements per specification if((int)ints.size() ::const_iterator iter = ints.begin(); iter != ints.end(); ++iter) { // reminder: static variables only initialized on first pass static int windowSum = 0; static int pos = 1; static list::const_iterator windowStart = ints.begin(); windowSum += *iter; if(pos >= windowSize) { cout << windowSum / windowSize << endl; windowSum -= *windowStart; ++windowStart; } ++pos; } } Show More Responses def slide(s): if len(s) = 7: avg = sum(s[:7]) l.append(avg) s = s[1:] return l a=[0,1,2,1,2,3,4,1,3,5,2,6] print slide(a) |
| Find the first letter in a string that does not have a pair. 3 AnswersCreate a histogram and do a two time pass. function findSingle($str) { $arr = str_split($str); foreach ($arr as $char) { if (1 == substr_count($str, $char)) { echo "first letter that doesnt have a pair: " . $char . "\n"; return; } } echo "no such letter\n"; } findSingle("lala"); findSingle("lalas"); #include char getFirstNonRepChar(std::string& input) { int str_Len = input.length(); // Build a Hash Map Table std::map char_map; for(int i=0; i(input[i],1)); } for(int i=0; i< str_Len; i++) { if(char_map[input[i]] == 1) return input[i]; } } int main() { std::string input = "teeter"; char result = getFirstNonRepChar(input); std::cout << result <<std::endl; } |
See Interview Questions for Similar Jobs
- Software Engineer
- Software Engineer Intern
- Intern
- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Software Engineer New Grad
- Data Scientist
- Software Engineering
- Software Engineering Intern
- Product Manager
- Software Engineer III
- Analyst
- Software Engineer I
- Member of Technical Staff
- Engineer
- Recruiter