# Software Engineer Interview Questions in London

Software engineer interview questions shared by candidates

## Top Interview Questions

### Software Engineer at Accenture was asked...

You have three doors, behind one there is a prize. You choose door A, after that I ll tell you that behind door B there is no prize, do yuo keep your choice or change it ? 7 AnswersChange it. The probability for door A is 1/3, the probability for the set Door C + Door B is 2/3. The interview adds information on the set stating that Door B prob is 0, so the probability for Door C is 2/3 while Door A stays at 1/3 Balls. Once you know that there is no prize behind door B, prob(B) becomes 0. Then, since the prize must be behind A or C, and you don't know anything about them, prob(A) = prob(C) = 1/2. Any of the doors is OK. Sorry Filippo (F?) but u r wrong on this one. U may see also it in this way: in the game You ll never be told that your initial choice is wrong, the information added is only about the other two doors. This breaks the symmetry, the probability that your initial choice stays at 1/3 ( It is secluded by the bit of more information added ) , but now the prob of b goes to zero and because all the probabilities must add up to 1, the prob(c) becomes 2/3. I understand it is not intuitive, but not all the math is :) Show more responses Sorry guys. none of the above is correct. You forgot the check on the sentence, as Interviewer may be lying or not (50% probability for each of the two). If he is NOT lying than there is NO price behind B --> you have 50% it is behind A and 50% it is behind C. If he IS lying than price is behind door B (100% sure) If you draw the brances tree and put it all together, you have that: Probab. = 0,5*[(0.5*A+0.5*C] + 0.5*1*B Ossia: Probab = 0,25*A + 0.25*C + 0.5B which means that both A and C have 25% probabiity of having it right, while B has 50% to be right. Therefore answer is: "you leave door A and choose door B ". Not because this IS behind door B, but because you have a higher probability this is there. :-) my vote is with Rob. this is covered in every basic probability and statistics course. I think Andrea is bringing unneeded complexity to the question Filippo's answer would be correct if he did actually open the door when he chose door A, but because it doesn't say that. So assuming that he telling the truth and that door B does not have a prize i.e probability of a zero, door C must have a probability of 2/3 . Therefore Rob's answer is correct. This is a the Monty Hall problem. Switching yields a win 2/3 of the time, and is preferred. I ran a simulation to confirm :-) https://en.wikipedia.org/wiki/Monty_Hall_problem |

The questions were not very difficult but you really need to have all the concepts crystal-clear and be ready to apply them successfully. One of the questions was "how to count the letters in this string:" "The quick brown fox jumps over the lazy dog"; 11 Answerspublic static int countWords(String str){ if(str == null || str.isEmpty()) return 0; int count = 0; for(int e = 0; e < str.length(); e++){ if(str.charAt(e) != ' '){ count++; while(str.charAt(e) != ' ' && e < str.length()-1){ e++; } }else{ e++; } } return count; } Sorry, the above version has an error!!!!!!!!!!!!!!!!!!!!!!!! concider this one: public static int countWords(String str){ if(str == null || str.isEmpty()) return 0; int count = 0; for(int e = 0; e < str.length(); e++){ if(str.charAt(e) != ' '){ count++; while(str.charAt(e) != ' ' && e < str.length()-1){ e++; } } } return count; } # That's why i love Python: len(re.findall('[a-zA-Z]', s)) Show more responses sorry u need to give input ;) ------ len(re.findall('[a-zA-Z]', "The quick brown fox jumps over the lazy dog")) It depends on what has to be considered a word. For example, if we consider a word any string between spaces, we can write it in a more compact way: public static int countWords(String str){ if(str == null || str.isEmpty()) return 0; return str.split(" ").length; } The question is how to count the characters in the string. If we can assume that the input is ASCII - always clarify first - then we know that the character range is 0-255. void count(char* str, int counts[255]) { if (str == 0) return; if (counts == 0) return; for (char *c = str; c != 0; c++) { counts[*c]++; } } First we assert the input is valid. Note that we take an additional parameter - an array of the count of each ASCII character. We loop through the string until we reach the null terminator, and we iterate a char pointer through each character in the string. For each iteration, we increment the counter in the array. Memory complexity is O(1), runtime complexity is O(n). If the input must be unicode, then we may consider alternatively using a hash table. void count(wchar_t* str, std::unordered_map& counts) { if (str == 0) return; for (char *c = str; c != 0; c++) { counts[*c]++; } } We still arrive at an O(1) memory complexity and O(n) runtime complexity (although it is worth noting that despite a hash table lookup takes O(1) like an array, the fixed cost of each lookup is higher for the hash table due to the hashing function, and in the worst case a lookup can be O(n)). The question asks to count the characters, without using String.length() you can do this: public static Pair countLetters(String s) { //If the string is null or it is empty then it will have no character if (s == null || s.isEmpty()) { //So return the pair with 0 and 0 return new Pair(0, 0); } //If we should still run the loop. boolean run = true; //The count of characters int count = 0; //The count of characters without spaces int countWithoutSpace = 0; //While we are still running (we are at a valid index) while (run) { //Then try to try { //Get the character at the current count char c = s.charAt(count); //Add one to the count as we have a valid character count++; //If the character is not a space if (c != ' ') { //Then add one to the count without spaces. countWithoutSpace++; } //If we get a StringIndexOutOfBooundsException it means that the current count is outside the length of the string. } catch (StringIndexOutOfBoundsException e) { //So stop the loop. run = false; } } //And return the pair with the count and the count without spaces. return new Pair(count, countWithoutSpace); } This returns both the count with and without spaces and does not use a built in length function. Wait..Am I missing something? string.Length will do the job? Yeah i think string.length() will do the job. failed! String.length returns the length of the String. Google asked you how many letters - in other words you cannot count the spaces. String. length returns number of unicode characters -and so includes spaces I would do this: public static int countWords(String sentence){ String noSpace; //REMOVE SPACE noSpace = sentence.replaceAll(" ", ""); return noSpace.length } |

### Software Engineer at Google was asked...

Write a function that takes the ordinal number of a column in a spreadsheet and returns the label of that column: i.e. 1 -> A 2 -> B, 26 -> Z, 27->AA 7 Answers!!!! There can be some bugs not fully tested use at your own risk =)... import java.util.ArrayList; public class OrdinalToColumn { public static void main(String[] args) { // TODO Auto-generated method stub int valueToConvert = 64; System.out.println(ordinalToColumnConversion(valueToConvert)); } private static char[] ordinalToColumnConversion(int valueToConvert) { // TODO Auto-generated method stub ArrayList numbersReverse = new ArrayList(); int sizeOfArr; int curIndex, rollBackIndex; while(valueToConvert>0){ // base conversion numbersReverse.add(valueToConvert % 26); valueToConvert /= 26; } sizeOfArr = numbersReverse.size(); curIndex = rollBackIndex = 0; while(curIndex rollBackIndex){ // borrowing can lead some cascading operation we have to roll back until all digits are more than 0 int barrowNumber = numbersReverse.get(tempIndx); // barrow from previous barrowNumber--; numbersReverse.set(tempIndx, barrowNumber); tempIndx--; int nextNumber = numbersReverse.get(tempIndx); // add to the current one nextNumber += 26; numbersReverse.set(tempIndx, nextNumber); } } else { curIndex++; } } if(sizeOfArr > 0 && numbersReverse.get(sizeOfArr-1) == 0){ // remove the highest significant bit if it is 0 numbersReverse.remove(sizeOfArr-1); sizeOfArr--; } char [] returnNumbers = new char [sizeOfArr]; for(int i = sizeOfArr-1, n=0; i>=0; --i, ++n){ returnNumbers[n] = (char)(numbersReverse.get(i)+64); // converting to capital letter } return returnNumbers; } } Here my solution in Java: public class SpreadSheetLabel { private static char LABEL[] = new char[] {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; private static void printLabel(int n) { if (n = 26) { n /= 26; str.append(LABEL[(n-1) % LABEL.length]); } System.out.println(str.reverse()); } public static void main(String[] args) { for(int i = 1; i <= 2600; i++) { printLabel(i); } } } I haven't tried interwee's solution, but that code is so complex and long for such a simple problem I don't even wish to try and understand it :) Anyways, here is my simple and elegant solution in Java: // Precondition: i >=1 public static String excelNumbering(int i){ if(i >=1 && i<= 26) return ""+(char)(i+64); else return excelNumbering((i-1)/26) + excelNumbering((i-1)%26+1); } Show more responses In C++: string excelNumber(int i) { string excelStr = ""; int numAs = i / 26; int rest = i % 26; for (int j = 0; j < numAs; ++j) { excelStr += "A"; } return excelStr + (char) (rest + 64); } Not sure what is meant to happen for error cases (e.g. 0). void calc_ord(int ord, char* out) { if (ord == 0) return; int tmp = ord; char *ptr = out; while (tmp <= 26) { *ptr++ = 'A'; tmp -= 26; } *ptr++ = 'A' + tmp; } public String getName(int n) { String ret=""; while(n>0) { char c='A'+(n%26); ret=c+ret; n/=26; } return ret; } here in OBJC. Is interesting that no one in the previous answers, is calculating the base system..everyone is hardcoding 26. - (NSString *)lettersFromOrdinal:(NSUInteger)ordinal { NSMutableString *letters = [NSMutableString new]; NSUInteger base = 'Z'-'A'+1; NSUInteger labelLength = ceil(customLog(base, ordinal)); for (NSInteger i = labelLength-1; i >= 0; i--) { NSUInteger pow_ = pow(base, i); NSUInteger res = ordinal/pow_; char letter = 'A' + res - 1; [letters appendFormat:@"%c", letter]; ordinal -= res*pow_; } return [letters copy]; } |

Given a list of words, right a function to return a list of pairs of palindromes 5 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 responses std::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. |

### Software Engineer at Google was asked...

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 responses package 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 |

Assuming you have a large cube shaped by small cubes together, their number is 1000 How many cubes will be visible? 4 Answers8+(8*12)+((8*8)*6) A cube will have n^3 sub cubes. With some guessing you get to 10^3 = 1000. Now the cube that fits within the 10^3 cube is a 8^3 cube (take off one layer from each side). So the total number of outer faces is 10^3 - 8^3 = 488. right another way of solving it which I think is better Thanks, Kiki Show more responses 10 x 10 + 9 x 10 + 9 x 9 = 271 |

### Software Engineer at Google was asked...

Find if there are two members of an array that sum to 10 (10 and 0 count, but 10 alone does not). 4 AnswersMy first guess is something like the following, where 10 would be passed as the sum parameter: int[] findSum(int[] nums, int sum){ int[] pair = null; for(int i = 0; i < nums.length; i++){ int a = nums[i]; int target = sum - a; for(int j = 0; j < nums.length; j++){ if(nums[ j ] == target){ pair = new int[2]; pair[0] = a; pair[1] = target; return pair; } } } return pair; // returns null if no suitable pair found } } I would use a hash to count how often the numbers between 0 and sum/10 show up. then go through the has to see if we have two that match. it is O(n^2) also, and doesn't work if sum is large. int[] findSum(int[] nums, int sum) { int[] hash = new int[sum+1]; //count how many numbers for (int i=0; i 0) && (hash[sum-i]>0)) { return new int[] {i, sum-i}; } } return null; } Basically sort the elements in n log n . Then for every element k search for (Sum - k) in the array using a binary search. Hence total complexity is n log n. Show more responses You can use a hashmap from value to # of occurrences of the number in the hashmap. Enter all numbers to a the hashmap (O(n)), go through the array and calculate 10 - n for each member and determine whether that number has occurrences > 0 in the hashmap. If so, you have a match, don't forget to decrease the occurrence by 1 (O(n)). Total O(n). Note that if duplicate is allowed (such that 5+5=10 is possible), you may need to check whether n = Sum - n, if so you must make sure the # of occurrences is > 1 and then reduce the occurrences by 2 instead. |

### Software Engineer at Facebook was asked...

Given two unsorted arrays, one with event start times and one with end times, find out if any two events overlap. 5 Answersarray S; array E; for(int o=1; o S[i] && S[o] S[i]) || (S[o] == S[i] && E[o] == E[i])) print "Event " + o + " intersect event " + (i+1); } } I'm sorry, the condition in the second for cycle is: i Best I could figure out (algorithm): 1. Sort the two arrays (using heap sort), while keeping the correlation between the start and end date. 2. Traverse the start date array, checking neighbouring intervals for any overlap (left, right or inside). time O(n log n); space O(1) Show more responses // NOTE: I haven't tested in an editor, may not compile. // Please think as a pseudo code public static void main(String[] args){ // we assume the lists are populated // and there is a correlation between arrays ArrayList eventstart; ArrayList eventend; printInterlappingEvents(eventstart, eventend); if(anyOverlap == false){ System.out.println("Good! There is no overlap!"); } } public static void printInterlappingEvents(ArrayList eventstart, ArrayList eventend){ // assumption : arrays have same size for(int index1 = 0; index1 event1start && event2start event1start && event2start < event1end) ){ // then there is an overlap System.out.println(event1start + ":" + event1end + " overlaps with " + event2start + ":" + event2end); } } } return anyOverlap; } http://www.geeksforgeeks.org/merging-intervals/ |

How work you work out all the prime numbers up to a given range? 3 AnswersStore all the prime numbers in an array and compare the next number with the array to find out whether it is prime or not. Sieve of Eratosthenes algorithm. create an array of the numbers, set them all to the value 1. Start at 2, set every second number after 2 to 0. move to the next number (3). change every third number after three to zero. stop when there's no more numbers set to 1 or you reach the end of the array. At the end, the numbers marked 1 are the primes. Interview candidate - did you give that answer in the interview? If so, what did they say? |

### Software Engineer at Bloomberg L.P. was asked...

What is 'deadlock'? 3 AnswersThreading process When two competing threads/processes need to acquire a resource which the other one has they are said to be deadlocked. Both want what the other has to perform a task but neither will release what they have until they get what the other has. A timeout on the held resources would help deadlock avoidance in this instance. Thread A has resource 'X' locked, and needs to access resource 'Y' before releaseing 'X' but 'Y' currently locked. Meanwhile its Thread B that has 'Y' locked, but needs to access 'X' before releasing 'Y'. Without a timeout its a dead lock. |

**1**–

**10**of

**968**Interview Questions

## See Interview Questions for Similar Jobs

- Software Developer
- Senior Software Engineer
- Intern
- Technology Analyst
- Software Development Engineer
- Graduate Software Engineer
- Java Developer
- Analyst
- Senior Software Developer
- Associate Software Engineer
- Consultant
- Graduate Software Developer
- Business Analyst
- Associate
- Financial Software Developer
- Software Engineer III
- Developer
- Product Manager
- Project Manager