Software development engineer intern Interview Questions | Glassdoor

# Software development engineer intern Interview Questions

334

software development engineer intern interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Jan 26, 2017

Feb 15, 2012

### Software Development Engineer Intern at Microsoft was asked...

Aug 13, 2013
 Determine if an array from 1..n has a duplicate in constant time and space.14 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array). If an index already contains its corresponding value, there's a duplicate.^^ Sorry, that's linear time *and* at best linear space, you fail.What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates.Show More ResponsesSUM(array) - (N(N+1)/2) = missing number.@Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4}I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated itemsThis cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap.If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate.I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbersI think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbersThey asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1.Obviously this can't be done with constant time or space. At best you could compute a solution in linear time. memoize/cache it once then you could return the solution in O(1) time for subsequent calls.Show More ResponsesI've seen this question posted several places as "Find if an array has duplicates, in constant O(1) space" but no restriction on time. If the array is not sorted, and there is no restriction on the actual values in each item, then there is no O(1) space and O(1) algo. if you sort the array, then you lose O(1) time and obviously can not detect duplicates even in a sorted array in constant time. If its like most other versions of this question, and its only O(1) space, then you could store the duplicate value in the array itself, overwriting earlier elements that you already scanned. You'd only need an index that points just past the last duplicate value written. But this is not constant time. One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.

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

Feb 10, 2013
 I was asked two questions. Q 1. You are given two version numbers of a software, like Version 10.3.4 and Version 10.3.41. Write a program to find out which of the version numbers are the latest. If version 1 is latest output -1, if version number 2 is latest output +1 else output 0 if same version. Both the version numbers are taken as string. He also asks to make the program of minimum time complexity as we can. At the end he also asked the difference between an iterative program and one with recurrence and their advantages and disadvantages. Q 2. Given two files with a list of application IDs (or some kind of data) stored in them , write a program to compare the data in the two files and output all the common data found in each. What data structure would you use and why ? Give a minimum time and space complexity algorithm. Why did you choose the particular data Structure or algorithm ?7 Answers1. This was a little tricky. You have to check for the decimal place in both the versions and then Store that part of the string till the decimal place in a temporary variable and then convert them to integer and check which one is greater. You have to keep on doing that till you reach the end of the version numbers or till when you find the answer 2. In the second question you can use Linked lists and then Binary Search Algorithm. The interviewer will ask you the reason for this.Why not just delimit the string with "." Then you'll have an array of string numbers. Then loop with the array from 0 -> n (depending on how many decimals there was) and compare. Return when one is greater than the other. You will have to check if you get a index out of bounds if one has more decimals than the other. Over all, that should be in n time.As for #2. HashTable it. Also n time.Show More ResponsesIf you are using c++, can't you just use the "compare" method that is built into the string class?Maybe not the best solution... the time complexity is O(n). public static void main(String[] args) { String ver1 = "10.22.7.3"; String ver2 = "10.22.8.4.1"; String split1[] = ver1.split("\\."); String split2[] = ver2.split("\\."); int max = split1.length > split2.length ? split1.length : split2.length; for (int i = 0; i i) { System.out.println(+1); break; } else if (split2.length i) { System.out.println(-1); break; } else { if (Integer.parseInt(split1[i]) > Integer.parseInt(split2[i])) { System.out.println(-1); break; } else if (Integer.parseInt(split1[i]) < Integer .parseInt(split2[i])) { System.out.println(+1); break; } } } }String v1="10.3.4"; String v2="10.3.41; double v12=v1.parseDouble(); double v22=v2.parseDouble(); If(v12>v22) { System.out.print(-1);} else if(v22>v12) {System.out.print(1);} else{ System. out. print(0);}Q:2 List a= new LinkedList(); List b= new LinkedList(); while(a.hasNext()) { ( int =1; i

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

Feb 15, 2012
 To return the 'm' smallest numbers from a file of 'n' numbers8 AnswersI would first create an array holding the first m values of the file, and sort. Then, each value I read from the file, I can compare the the last (largest) value in the array. If its smaller, do a binary search to find the correct spot in the array. Insert the number and shift everything behind it back by 1. Worst case runtime will be O(n lg m)Why cant we simply start with min=INT_MIN. Then, read first number from file, if lower, set min=that number. Seek next number and so on... We dont need to load the whole file. We will go to the disk often though.I will create a min heap with the given numbers and extract 'm' minimums from the heap which will get stored into the resultant arrayShow More ResponsesAnuj, Wont it take time of O((M+N)log N)@spammer, I think it's O(n+m*log n), since you can construct the min heap bottom-up and that only takes O(n)Why don't we just sort the array and return the first m numbers? Takes O(nlogn) for sorting and O(m) to return the first m numbers.Maintain a heap of m numbers and also track a variable which stores the current highest value. So as u go through the n numbers, if the number is higher than the current highest number, ignore it else insert it into the heap and set the current highest value to the newly inserted value One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.

Sep 26, 2012

Jan 6, 2011

Mar 10, 2017