Software development engineer Interview Questions in San Jose, CA | Glassdoor

# Software development engineer Interview Questions in San Jose, CA

278

software development engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Jun 12, 2018

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

Jul 13, 2012
 Create a data structure that minimizes time complexity of retrieving median and inserting new element. Getting median should be O(1) and insertion should be O(log(n)).5 AnswersA heap in which the root is the median and it has max heap of the lower half on left and min heap of the rest on right.Can we not use a BST which is kept balance after every insertion using AVL ? The median is always the root of this tree, so median is retrieved in O(1) and insertion/deletion is O(log n) for balanced tree.I guess a Red-Black tree would be a more appropriate data structure to use. Since it is a perfectly balanced tree data structure, the median would always be at the root. The insertion takes time proportional to the height of the tree i.e. O(logn)Show More ResponsesWe can use two heaps, one max heap, one min heap. Large values are pushed into the min heap, and small values are pushed into the max heap. Keep the difference of the number of elements in the two heaps smaller than 2. The median will be the top of the heap with more elements or the average of the tops of the two heaps if they have same number of elements. I think this is easier to implement.array?binary search when do insertion?

### Software Development Engineer at Yahoo was asked...

Nov 12, 2009

Jul 13, 2010

Oct 27, 2017
 Check if a string is a pallindrome Find the longest distance between any two nodes in a binary tree.3 Answerspublic List longestPath(BinaryTreeNode root) { if (root == null) { new ArrayList(); } List longestPath = deepestPath(root.left); longestPath.add(root); longestPath.addAll(deepestPath(root.right)); return longestPath; } private List deepestPath(BinaryTreeNode root) { if (root == null) return new ArrayList(); List left = deepestPath(root.left); List right = deepestPath(root.right); List deepestChildren = left.size() > right.size() ? left : right; deepestChildren.add(root); return deepestChildren; }public boolean isPalindrome(String s) { char cs = s.toCharArray(); for (int i = 0; i < cs.length / 2; i++) { if (cs[i] != cs[cs.length -i - 1] return false; } return true; }public List longestPath(BinaryTreeNode root) { HashMap> cache = new HashMap(); return longestPath(root, cache); } public List longestPath(BinaryTreeNode root, HashMap> cache) { if (root == null) return new ArrayList(); List left = longestPath(root.left, cache); List right = longestPath(root.right, cache); List longest = left.size() > right.size() ? left : right; List current = new ArrayList(longest); current.add(root); cache.put(root, current); List deepestLeft = cache.getOrDefault(root.left, Collections.EMPTY_LIST); List deepestRight = cache.getOrDefault(root.right, Collections.EMPTY_LIST); cache.remove(root.left); cache.remove(root.right); if (deepestLeft.size() + deepestRight.size() + 1 > longest.size()) { List newLongest = new ArrayList(); newLongest.addAll(deepestLeft); newLongest.add(root); newLongest.addAll(deepestRight); return newLongest; } else { return longest; } }

Mar 30, 2010

Jun 24, 2010
 Find the optimal map route between two points on a grid (maze) with some areas blocked out.3 AnswersIs this just testing if you know Djikstra's algorithm?Sounds more like an A* application to meBFS

### Software Development Engineer In Test (SDET) at Microsoft was asked...

Mar 7, 2013
 Find if given number matched sum of two elements in sorted array. 3 AnswersDon't assume array is sorted when testing. Now how your solution fail !!two pointers solves sorted array, hashmap can solve unsorted arraypublic static void findNumsEqualTarget(int[] a,int target) { int leftptr=0; int rightptr=a.length-1; int sum=0; //int[] r=new int[2]; while(leftptr

Apr 13, 2017