Development Engineer I Interview Questions | Glassdoor

# Development Engineer I Interview Questions

326

Development engineer i interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Jan 3, 2013
 Given a string of format '2+3*2-1', calculate and return the result. No parenthesis in the input, just integers and + - * / operators. Operator precedence has to be considered. Linear time complexity and minimal data structure use is preferred.4 AnswersI did 2 pass on input string.I also did two passes on the input string. I created the following helper classes: Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator). InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1". Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it. One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle.I used a different approach by making use of a queue: - parse the string, and push in the operands and operators onto a queue - evaluate the queue My general approach was this: - read in lhs, operator and rhs - if operator is "+" or "-", enqueue lhs and operator > if string is empty, we are done parsing --> enqueue rhs > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further - else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate. (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug) // Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression. string getCurr(string& str); int eval(string str) { if (str.empty()) return -1; // operand / operator queue std::queue q; // construct it char buf[5]; while (!str.empty()) { string lhs = getCurr(str), oper = getCurr(str), rhs = getCurr(str); // evaluate directly if (oper == "*") { int res = atoi(lhs.c_str()) * atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } // evaluate directly else if (oper == "/") { int res = atoi(lhs.c_str()) / atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } else // "+" or "-" { q.push(lhs); q.push(oper); // finished parsing the expression if (str.empty()) q.push(rhs); else // restore the string str = rhs + str; } } // evaluate the queue int res, rhs; string oper; res = atoi(q.front().c_str()); q.pop(); while (!q.empty()) { oper = q.front(); q.pop(); rhs = atoi(q.front().c_str()); q.pop(); if (oper == "+") res += rhs; else // "-" res -= rhs; } return res; } string getCurr(string& str) { if (str.empty()) return ""; string curr(""); // operator if (str[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/') { curr += str[0]; str = str.substr(1); } else // a number { do { curr += str[0]; str = str.substr(1); } while (!str.empty() && str[0] >= '0' && str[0] <= '9'); } return curr; }Show More ResponsesUse 2 stacks. one for operands and one for operators. Keep pushing in operator as long as the newly pushed opertor has higher precedence than the "top of stack " operator. if not, pop out 2 operands and calculate result and again push it on stack

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

Jun 1, 2011
 Complexity of this algorithm. How to improve the complexity?3 AnswersN^2 and can be improved to n logn using binary serach.or could be linear time if you're allowed to use a hash tableI'm pretty sure hash table is the answer they were looking for...

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

Jan 11, 2012
 Remove the nth from last element in a singularly linked list in linear time.3 AnswersThe general idea is to keep a pointer n elements back from the current element as you're traversing the linked list looking for the last node. There are some edge cases when coding it. O(n) time, O(1) space.How about? Traverse once find length. Then find n-kth element. Still linear complexity in time and 0 addl spaceThat works too. The first way you only traverse once though.

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

Jun 4, 2012
 there is an array with 99 length long, each spot will have number from 1-100, number will never repeat on the array. Give as many way as possible to find the missing number. 3 AnswersAdd up all number in the array and find the difference between the sum of 1 to 100.Another way since the interviewer asked for as my solutions as possible 1. Create another array of 100 elements and initialize to 0 2. Traverse through the first array and mark the corresponding spot in the second array 3. Now traverse through the second array and find the spot that is still marked as 0 - that is your missing element Note: You'll have to do a subtract by 1 since the numbers are from 1-100 and your array count will be from 0 to 99.sum of 1 to 100 can be got by using Gauss's formula n(n+1)/2. If we subtract the sum of all numbers in the array with the result we got from formula, it's the answer.

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

Jan 14, 2012
 Write a function that takes an integer and counts the number of bits.3 AnswersThis is a simple bit manipulation problem. If you study before your interviews, this is a common area to study.void count_Bits(int inp){ int count = 0; for (int y = inp; y >=1;y = y /2 ){ count++; } cout<< "number of bits : " << count<< endl; }If you take a simple log base 2 of the integer, that should give you the number of bits, right?

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

May 24, 2011
 Given a set of numbers, partition the set in to two, such that sum of all the candidates in first subset = sum of all the candidate numbers in second subset.2 AnswersSolved by factoring sum of entire set and finding all candidate numbers which sums up to that factor. That is if the set sum = 15. Factorize 15 such as 1+14, 2+13, etc. And find all the candidates in the set which sums up to 1 and 14(and so on). Then subgroup them. Then follow up was how to handle negative values, what if values are largely distributed like {-1M1, -1, 0, 1M} The above method performs miserably. One solution I gave was to reduce numbers by orders of magnitude. That is above set is equivalent to {-11, -1, 0, 10} and while finding out factors of sum, go from -x to +y where x being most negative and y being most positive value in a given set.it's a subset sum problem with the targetted sum equal to half of the sum of elements in the array. It can be solved usin DP.

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

Jun 19, 2011
 Discuss finding the most efficient route in terms of cost and time for moving products through warehouses to customers. Explain algorithm complexity.2 AnswersBreadth-first traversal of a graphshortest path algoritm

Apr 14, 2012