New Grad Software Engineer Interview Questions
2K
New Grad Software Engineer interview questions shared by candidates
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?
11 Answers↳
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; } } Less
↳
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; } Less
↳
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? Less
Improve this piece of code, loop tracing, very basic printing problem
10 Answers↳
Did they ask salary expectations? Do you think you might have been rejected because you asked for too much $? And you say you answered everything correctly you think? Less
↳
We didn't even get to salary expectations actually. Yea I'm very confident I answered everything correctly. It was definitely not a difficult assessment at all. I know it's kinda tough but try not to be discouraged, unfortunately it's not uncommon for you to ace a technical but still get rejected. All we did was have the technical thing on a google doc, then afterwards they explained what the company does, which is build custom software essentially, and then asked if I had questions. Hopefully you guys have better luck than I did. Less
↳
I have an interview with them this upcoming next week, I am sorry it did not work out I am sure you did great. Makes me a bit nervous you aced it and didnt get a call back. Less
Given a base 10 number, print the hexidecimal (base 16) representation of that number.
7 Answers↳
lol, I wonder if this is acceptable printf ("%x",n); //n being the base 10 number Less
↳
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(); Less
↳
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(); } Less
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 Answers↳
cat log | sort | uniq -c | sort -k2n | head 100
↳
I would add a min-heap of size 100 to BetterSolution's answer (in order to get the top 100). Less
↳
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. Less
Given a list of compare orders and keys (directions), find the hashmap that matches the directions. If the first direction gives equal, then go to the second. And so on.
4 Answers↳
Can you talk a bit about how you prepped for the onsite interview? Especially for system / API design, do you brush up on UML diagrams? Less
↳
Can you elaborate the question? What is the meaning of direction here?
↳
The key in these questions is to cover the fundamentals, and be ready for the back-and-forth with the interviewer. Might be worth doing a mock interview with one of the Stripe or ex-Stripe Software Engineer New Grad experts on Prepfully? They give real-world practice and guidance, which is pretty helpful. prepfully.com/practice-interviews Less
Question1 /** * Given a nested list of integers, returns the sum of all integers in the list weighted by their depth * For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1) * Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)
4 Answers↳
Solve by recursively entering lists within lists: void printLevel(List l){ int level = 0; System.out.println(recurse(l, level)); } int recurse(List l, int level){ int sum = 1; for(int i = 0; i < list.length; i++){ if( isInteger(list.get(i))){ int val = list.get(i) * level; sum = sum + val; }else{ // recurse and increment depth level sum = sum + recurse(l.get(i), level+1); } } return sum; } I typed this up fast so will have to go back through and check for errors. Less
↳
void printLevel(List l){ int level = 1; System.out.println(recurse(l, level)); } int recurse(List l, int level){ int sum = 0; for(int i = 0; i < list.length; i++){ if( isInteger(list.get(i))){ int val = list.get(i) * level; sum = sum + val; }else{ // recurse and increment depth level sum = sum + recurse(l.get(i), level+1); } } return sum; } whoops meant to swap level and sum. Sum should 0 and level should start at 1. Less
↳
public class SumOfNestedLists { public static int getSum(List list) { int sum = 0; for(Object o : list) { if(o.getClass() == Integer.class) sum += (int)o; else if(o.getClass() == LinkedList.class) sum += getNestedSum(o, 2); } return sum; } private static int getNestedSum(Object o, int level) { if(o.getClass() != LinkedList.class) return -1; List list = (List)o; int tempSum = 0; for(Object io : list) { if(io.getClass() == Integer.class) tempSum += (level*(int)io); else if(io.getClass() == LinkedList.class) tempSum += getNestedSum(io, level+1); } return tempSum; } public static void main(String[] args) { // TODO Auto-generated method stub List l3 = new LinkedList(); l3.add(6); List l2 = new LinkedList(); l2.add(4); l2.add(l3); List l1 = new LinkedList(); l1.add(1); l1.add(l2); System.out.println(SumOfNestedLists.getSum(l1)); List l6 = new LinkedList(); l6.add(1); l6.add(1); List l5 = new LinkedList(); l5.add(l6); l5.add(2); l5.add(l6); System.out.println(SumOfNestedLists.getSum(l5)); } } Less
Mostly the concepts of array and string manipulation. You are given an array with distinct numbers between 1 to 100. You have to return You have to return a string which says the number's range which are not in the given array separated by comma. Eg: Input: [50,75] Output: (0-49,51-74,76-100)
4 Answers↳
This is a variation of counting sort. To solve, create an array 'hits' of size 100 and initialize all elements to 0. Iterate through the list. Every time you encounter a number n, set hits[n-1] = 1. Then, iterate through hits and make the ranges. O(n) work, O(n) space. Less
↳
Easiest way would be to sort using any method (counting sort could be used to give linear time or the other answer could also work) once the numbers are sorted you can just go through and find any gaps and write them down. Clarification might be needed beyond what's given here. So you might want to ask for example if the range you should return should be inclusive, exclusive or something else. Also dealing with single gaps might be strange. Less
↳
def givemeval[N): from itertools import groupby m=[] for i in range(101): if(i not in N): m.append(i) #print m n=[] for i,j in groupby(enumerate(m),lambda(a,x):a-x): n.append(map(lambda x:x[1],j)) for i in n: print (min(i),max(i)) givemeval[[50,75]) Less
He asked me to write a function to detect whether string1 contains all letters in string2
4 Answers↳
Traverse string2 and create a map where the characters of string2 are used as keys. Then traverse string1. If the the character in string1 exists in the map, remove the key from the map. At the end if your map has anything in it, string1 did not contain all of the characters. Less
↳
def hasAllLetters(str1,str2): if str2 == "": return True else: dict = {} for ch2 in str2: if ch2 in dict: dict[ch2] += 1 else: dict[ch2] = 1 for ch1 in str1: if ch1 in dict: if dict[ch1] > 0: dict[ch1] -= 1 else: del dict[ch1] else: return False return True Less
↳
// Assume S1 and S2 are non-null pointers bool hasChar(char *s1, char *s2) { int ret=false; char *tmp; if (*s2 == '\0') return true; tmp = s1; while ((*tmp != '\0') && (*tmp != *s2)) tmp++ if (*tmp == '\0') return false; return hasChar(s1, s2++); } Less
Given a list of integers that fall within a known short but unknown range of values, how to find the median value?
4 Answers↳
median finding algorithm. Works in O(n) time.
↳
It can be done using Selection algorithm
↳
Given the range is small, create an array of size 100; Iterate once and insert the values AT the array indexes; count each insert. Then iterate from the start of the array (skipping most blanks) up to the count/2 indexed value. Less
Given an input array like [1,2,3] and a target like 5, find all combinations of array that sum up to target. [2,3] and [3,2] counts for only 1 combination.
4 Answers↳
Question is not clear as to whether we need find pairs or any combination. For pairs below is a solution. vector>findpairs(vector vec, int target) { vector> ans; map m; for(int i = 0; i p = make_pair(target-vec[i], vec[i]); if(std::find(ans.begin(), ans.end(), p)==ans.end()) ans.push_back(p); } else{ m[vec[i]]++; } } return ans; } Less
↳
List>GetCombination(int[]arr, int sum) { var res=new List>(); Generate(arr,sum,0,i,res, new List()); return res; } void Generate(int[]arr, int sum, int currentSum, int index, List curr) { if(currentSum==sum) { res.Add(curr); } if(index==arr.Length)return; curr.Add(arr[index]); Generate(arr,sum,currentSum+arr[index],index+1,curr); curr.RemoveAt(curr.Count-1); Generate(arr,sum,currentSum,index+1,curr); } Less
↳
Bill's answer is not correct I think. When I run it it returns "[0 8, 1 7, 2 6, 3 5, 4 4]" so it only returns pairs and not all k-combinations, for his example it should also return [1, 2, 2, 3] as these also sum to 8. Less