Software engineer iii Interview Questions | Glassdoor.co.uk

# Software engineer iii Interview Questions

9,852

software engineer iii interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

29 Oct 2015

### Financial Software Developer at Bloomberg L.P. was asked...

4 Nov 2014
 Design an algorithm to find the first unique element in an array.8 AnswersOne possibility that comes in mind: * Walk the array, create a hashmap (key is the value in array, value is the count of such values). * Walk the array again and check the count in the hash map, once you hit 1, you have the first unique value. This is O(n) both space and time.Are you sure that this is O(n), it is definitely O(n^2), you go over all items twice.dear utk O(2n) = O(n) != O(n^2)...Show more responsesIts a hashmap. It never guarantees you the order in which you inserted the elements...!!@ankush: this is where LinkedHashMap comes into play.An easier one would be to sort the array and since they are asking for the first unique element return the first element that does not appear more than once in the newly sorted array.@ankush: That does not matter, you do not need to keep the order in the hash map. You go again through the original array, so you definitely find the first unique value. The hashmap is just for bookkeeping.@kabajiegara: No, that will not work, consider array "2 1" - if you sort, you'll have "1 2" and would thus return 1, which is the wrong answer because the first unique is 2.

### Financial Software Developer at Bloomberg L.P. was asked...

22 Dec 2012
 A rabbit wants to climb some stairs and it can do steps of 1 or 2. How many possible paths are there to follow ( e.g 1-1-1... or 2-2-2 ... or 2-1-2-1... etc)6 Answersuse recursion2^n possibility...F(n) = F(n-1)+F(n-2)Show more responsesSummation(i=0,floor(n/2))[(n-i)C(i)]. I'm sure this can be further simplified though.Correction on the above: Summation(i=0,floor(n/2))[(n-i)P(i)].Summation(i=0,floor(n/2))[(n-i)C(i)] is correct. I need to sleep. Sorry.

23 Jul 2010

### Java Developer at IHS Markit was asked...

9 Nov 2010
 How would you measure 4 litres of water if you have 3 litre and 5 litre canisters?7 Answers1) Pour water in 5 litre container 2) Pour 5 litre container into 3 litre until full. You are left with 2 litre in 5 litre container 3) Empty 3 liter container. Pour 2 litre into 3 litre container 4) Fill 5 litre container until full 5) Pour 1 litre into 3 litre container until full. Left with 4 litres in 5 litre container.1. fill half of the 3 litre container 2. fill half of the 5 litre containerhttp://brainteaserbible.com/interview-brainteaser-puzzle-water-jugShow more responsesbit lenghty but 1)both 3 & 5l are empty. 2) fill 3l, pour in 5l, fill 3l again and pour in 5l, you'll have 1 l in 3 l. now pour this 1l somewhere then fill 3l one more time.Add 2 full measures using the 5l, remove 2 full measures with the 3l, you are left with 4l.Fill full water in the 5 litre canister, remove 3 liters of it to the 5 litre to the 3 litre canister. Keep remaining in the 5 litre canister(=2 litre) somwhere. Take another 5 litre water and perform the same procedure.= another 2 litre... 2+2 =4 litre.. done.Fill full water in the 5 litre canister, remove 3 liters of it to the 5 litre to the 3 litre canister. Keep remaining in the 5 litre canister(=2 litre) somwhere. Take another 5 litre water and perform the same procedure.= another 2 litre... 2+2 =4 litre.. done.

29 Jul 2010

### Forward Deployed Software Engineer at Palantir Technologies was asked...

22 Nov 2017
 Merging of Sets: Sets Users which reference other user groups.6 AnswersRecursivelyHello! When did you interview?Beginning of NovemberShow more responsesOkay. Thanks!Hi, can you provide more details about the question? Thanks!Recursively is bad due performance ;-) Iterative is the better way.

5 Jan 2014

19 Jun 2010
 Given the pre-order and in-order traversing result of a binary tree, write a function to rebuild the tree.5 AnswersHere is the algorithm (I am too lazy to write the whole program). Let's number the nodes of in-order traversing sequentially (1,2,3, etc.). Then take the list of nodes of pre-order traversing. The first one is the root. While their numbers (from in-order list) decreasing, connect them as left-hand children, one by one. If the next number is greater, find the node with the max number (less than this one) and connect this one to it as right-hand child. Etc.I think they meant any "binary tree" not a binary search tree; but ALL values must be different (imagine a tree with n 1's; it has a Catalan(n) configurations and the same pre- and in-order traversals). So here is a solution: node* rec(const std::vector& PRE, const std::vector& IN) { node * r = new node(0,PRE[0]); // root node * v = r; // what we want to return bool l = PRE[0] != IN[0]; // do I go left? std::set path; // ancestors path.insert(PRE[0]); for(int p=1, i=l ? 0 : 1; p!=(int)PRE.size(); ++p) { node * n = new node(r,PRE[p]); r = l ? r->_left = n : r->_right = n; l = true; // revert to left if (PRE[p] == IN[i]) { // must go right or up ++i; while(i _v); r = r->_up; if (r->_v == IN[i]) { ++i; break; } } } } } path.insert(PRE[p]); } return v; } The idea is that the pre-order is basically a depth-first search order, which is convenient to build the tree (it is always connected at every interim stage). The in-order is used to decide whether to move right or up. BTW, you can guess the definition of "node".I have done something in Java. Maybe this might help: import java.util.Arrays; import java.util.TreeMap; import javax.management.RuntimeErrorException; public class BinaryTrees { public static class Node { Node right; Node left; char value; // preorder // public String toString() { // return (value + " ") + (this.left == null ? "" : this.left) // + (this.right == null ? "" : this.right); // // } // in order // public String toString() { // return (this.left == null ? "" : this.left) +(value + " ") + // (this.right == null ? "" : this.right); // // } // post order public String toString() { return (this.left == null ? "" : this.left) + "" + (this.right == null ? "" : this.right) + (value + " "); } } private static final char[] preOrderStr = new char[] { 'u','f','A','C','M','h','s','9','6' }; private static final char[] inOrderStr = new char[] { 'A','f','C','u','s','h','M','9','6' }; public static void main(String... args) { BinaryTrees trees = new BinaryTrees(); Node root = trees.rebuildTree(inOrderStr, preOrderStr); System.out.println(root); } public Node rebuildTree(char[] inOrderS, char[] preOrderS) { Node root = new Node(); root.value = preOrderS[0]; int index = getIndex(inOrderS, root.value); char[] leftInOrderS = new char[index]; char[] rightInOrderS = new char[inOrderS.length - index - 1]; char[] leftPreOrderS = new char[index]; char[] rightPreOrderS = new char[preOrderS.length - index - 1]; System.arraycopy(inOrderS, 0, leftInOrderS, 0, index); System.arraycopy(inOrderS, index + 1, rightInOrderS, 0, inOrderS.length - index - 1); System.arraycopy(preOrderS, 1, leftPreOrderS, 0, index); System.arraycopy(preOrderS, index+1, rightPreOrderS, 0, preOrderS.length - index -1); if (leftInOrderS.length != 0 && leftPreOrderS.length != 0) root.left = rebuildTree(leftInOrderS, leftPreOrderS); if (rightInOrderS.length != 0 && rightPreOrderS.length != 0) root.right = rebuildTree(rightInOrderS, rightPreOrderS); return root; } public int getIndex(char[] chars, char ch) { for (int i = 0; i < chars.length; i++) if (ch == chars[i]) return i; throw new RuntimeException("No char " + ch + " in the vector"); } }Show more responsespackage datastructures.trees; public class BuildTreeInorderPreorder { public static void buildTree(int[] inorder, int[] preorder) { TreeNode root = createNode(preorder,inorder,0,preorder.length-1,0,inorder.length - 1); printPostOrder(root); } private static TreeNode createNode(int[] preorder, int[] inorder, int ps, int pe, int is, int ie) { if(ps > pe || is > ie) { return null; } TreeNode newNode = new TreeNode(preorder[ps]); int i; for(i = is; i <= ie; i++) { if(preorder[ps] == inorder[i]) { break; } } newNode.left = createNode(preorder, inorder, ps + 1, ps + i - is, is, i - 1); newNode.right = createNode(preorder, inorder, ps + i - is + 1, pe, i + 1, ie); return newNode; } private static void printPostOrder(TreeNode node) { if(node == null) { return; } printPostOrder(node.left); printPostOrder(node.right); System.out.print(node.x + ""); } public static void main(String[] args) { int[] preorder = {1,2,4,7,8,5,3,6,9,10,11,12}; int[] inorder = {7,4,8,2,5,1,3,9,6,10,12,11}; buildTree(inorder,preorder); } } class TreeNode { int x; TreeNode left, right; public TreeNode(int x) { this.x = x; } }Here is a compact solution using recursion. Assume your pre-ordering is given in "pre", and in-ordering is given in "in", in the form of integers from 1 to n, representing nodes. "p" is an indicator showing which of the pre-order nodes we're currently procesing, and "ind" is used to quickly find where a node is in "in". class Node { int value=-1; Node left=null, right=null; public Node(int val){value=val;} public Node(int val, Node l, Node r){value=val;left=l;right=r;} } public class Rebuild { int[] pre, in,ind; int p=-1; public Node reconstruct(int st, int ed) { p++; //go to next root if(st==ed)return new Node(pre[p]); Node lr=reconstruct(st,ind[p]-1); Node rr=reconstruct(ind[p]+1,ed); return new Node(pre[p],lr,rr); } public static void main(String[] args) { //input "pre" and "in" however you want, initialise ind for(int i=0;i

### Software Engineer at Jane Street was asked...

4 Mar 2012
 Given a list of words, right a function to return a list of pairs of palindromes5 AnswersPresume you mean pairs of ANAGRAMS? Otherwise why would palindromes come in pairs? Simple O(n^2) implementation in Python: for left in words: for right in words: if (not left==right and sorted(left)==sorted(right)): print (left, right)from itertools import combinations def find_anagrams(words): return [(a, b) for a, b in combinations(set(words), 2) if sorted(a) == sorted(b)]A simple C++ solutions. O(nlogn). void reverse(string &s) { int len = s.length(); for(int i = 0, j = len-1; i palindromes(vector words) { if(words.empty()) return words; vector pal; sort(words.begin(), words.end()); vector::iterator it = words.begin(); for(; it != words.end(); ) { string tmp = *it; reverse(tmp); if(binary_search(++it, words.end(), tmp)) { pal.push_back(tmp); cout<Show more responsesstd::vector getPalindromePairs(std::vector words) { std::vector pairs; for (auto word : words) { std::string str = word; std::reverse(str.begin(), str.end()); if (word == str) { pairs.push_back(word); } } return pairs; } Worst case is O(nm) where m is the longest string length.1. Build a HashMap key -> current string, value -> reversed string. 2. Traverse the hashmap, add the strings to a list, where key == Value. 3. return list.
110 of 9,852 Interview Questions