Questions d'entretiens - Software engineer new grad

2 k

Questions d'entretien pour Software Engineer New Grad partagées par les candidats

Principales questions d'entretien

Trier: Pertinence|Populaires|Date
Google
On a demandé à un Software Engineer - New Grad...6 octobre 2012

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 réponses

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; } } Moins

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; } Moins

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? Moins

Afficher Plus de réponses
Digital Foundry

Improve this piece of code, loop tracing, very basic printing problem

10 réponses

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? Moins

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. Moins

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. Moins

Afficher Plus de réponses
Google

Given a base 10 number, print the hexidecimal (base 16) representation of that number.

7 réponses

lol, I wonder if this is acceptable printf ("%x",n); //n being the base 10 number Moins

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(); Moins

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(); } Moins

Afficher Plus de réponses
Yelp

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 réponses

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

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. Moins

Afficher Plus de réponses
Stripe

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 réponses

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? Moins

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 Moins

Afficher Plus de réponses
Google

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 réponses

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. Moins

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. Moins

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]) Moins

Afficher Plus de réponses
LinkedIn

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 réponses

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. Moins

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. Moins

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)); } } Moins

Afficher Plus de réponses
Microsoft

He asked me to write a function to detect whether string1 contains all letters in string2

4 réponses

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. Moins

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 Moins

// 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++); } Moins

Afficher Plus de réponses
Google

Given a list of integers that fall within a known short but unknown range of values, how to find the median value?

4 réponses

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. Moins

Afficher Plus de réponses
Meta

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 réponses

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; } Moins

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); } Moins

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. Moins

Afficher Plus de réponses
1 - 10 sur 2 210 Questions d'entretien

Consultez les questions posées en entretiens pour des emplois similaires