# Interview questions in London, England

Bloomberg L.P. Interviews in London

www.bloomberg.com / HQ: New York, NY

826 Interviews in London (of 4,636)

## Interview Questions in London

### Trader at Jane Street was asked...

was asked this question today...you want buy a car at an auction whos price is uniformly distributed between 0-1000 if you bid more than the car you win it at the price you bid.if you bid less that the cars proce you dont win it but dont lose anything. you can sell the car for 1.5 time the value of which you bought it. what should you bid on the car to maximumise your profit? 11 Answersi told the interviewer that the expected value is negitve so you should bid 0 to maximum your profit.(0 is greater that any negitive number) but the answer which i was guided towards wasE(X)= X-(X/2)*1.5 letting X = your bid so if you bid 500 E(x) = 500 - 250(1.5) = 125 pretty weird question if you ask me. comming up with a formula for expected value when i was orgionaly asked what would be my bid to maxiumise my profit. any1 have an thoughts? maybe this was obvious? If you bid X then your expected gain is (X/2)*1.5 So (X/2)*1.5 - X should be your profit... I.E. negative expected value. Could it be the interview just wanted to see how you can mathematically back up your original statement? yeah good point! that is most likely what he was testing. i suppose i just assumed it was obviously neg EV. Show More Responses im sorry but can u guys explain why is it X/2 *1.5 and not x*1.5 Also, where have you guys taken into acct that the gain is only when your bid is successful. If its not successful u gain ntn. Hence in my opinion it should be E(X) = (X/1000) * (1.5*X - X) its x/2 because the expected value of all the other possible outcome when you win is x/2.the expected profit is negative. say you bid 500 and win then the expected value is 0(1/501) + 1(1/501).....500(1/501) that where the x/2 come from Shouldn't it be bid 1000? then you will win the car for sure, and you can make a 1000*50%=$500 profit. (theoretically, assuming you can sell the car for 1.5 times the purchase price no matter what the purchase price is, you should bid as large as possible, then your profit is purchase price*50%) Looks like an options contract. I agree with "e". This doesn't seem like it should be more complicated than it is. if you can sell the car for 1.5 times the value of which you bid for, then no matter what the bid is, your profit will be 50%. You want to maximize profit, which implies the fact that you "want to win the bid" so that you can then sell it for more. Bidding less wins you nothing, and so you might as well bid the largest amount, i.e. $1000, to ensure you win, so you can then spin it off for a 50% profit. Granted, this explanation is only valid if it's a "sure" thing that no matter what you pay for the car, you can 100% sell it for 1.5 times the price you paid. Thoughts? You dont sell it for 1.5 times you paid you sell it for a 1.5 times it's true value (a number uniformly distributed between 0 and your bid (which expected value 0.5 times your bid). assuming the question is wrongly worded, and we can sell it for 1.5 * its actual value. bid x dollars, between 0 and 1000: expected profit = probability you get the car * (1.5 * expected value of car - bid) p = (x/1000) * (1.5 * 500 - x) maximise w.r.t x to get p = 140.6 at x = 375 a=actual price b=bidding price ------------------ If profit = 1.5b - a answer is easy, bid 1000 ------------------- If question was wrongly worded & profit = 1.5a - b to win, b>a to make profit, b<1.5a so to win and make profit: a |

### Assistant Trader at Jane Street was asked...

We consider numbers from 1 to 1 million. How many digits 2 are there?? 10 Answers600 000 940951 654321: The total number of digits 1-999,999 is 5888889 Total 1-9 = 9 10-99 = 2*9*10 and so on so number of 2s is 5888889/9 Show More Responses 654321: The total number of digits 1-999,999 is 5888889 Total 1-9 = 9 10-99 = 2*9*10 and so on so number of 2s is 5888889/9 Each time you fix a digit 2 (in units, tens...), then you change the other 5 digits. So you'll have 100 000 number. Having that for the six placements, the result would be 600 000. 600,000 6C6 with 6 digits, 9(6C5) with 5, (9^2)(6C4) with 4...etc. Add them up 600,000. 111111 10^6-9^6 observe the recurrence relation. 1-9 there is 1 from 1-99 there is 10 1-9 intervals plus 10 digits from 2x. and then it continuous in exactly the same fashion add one 0 you get 10 times as many plus 10^(n-1) from the nth digit you add. (((((10+10)*10+100)*10+1,000)*10+10,000)*10+100,000)=600,000 Consider from 0000000 to 9999999, the number of 0,1,2,3,4,5,6,7,8,9 present must be the same since they are all symmetric. prove: the position can be filled with 0 can be filled with 1, so the number of 0=the number of 1; the number of 1=the number of 2 for the same reason. ... so the number of 0-9 are all the same. There are 6*1million positions in total, thus 6 million positions, divided by 10, is 600,000. |

You roll two die: What is the probability of rolling a 10 and an 11 before rolling a 7? 8 Answers17/132 How did you get that? Individually 10 comes up 3/11 (4+6, 5+5, 6+4), 11 comes up 2/11, 7 comes up 6/11. Consider 10 first: Then only interested in 7,11: Probability 11 is 2/8, 7 is 6/8. Consider 11 first: Then only interested in 7,10: Probability 10 is 3/9, 7 is 6/9. Consider 7 first: Busted. So add 10 then 11, and 11 then 10: (3/11)*(2/8)+(2/11)*(3/99)=17/132. Show More Responses 5/11 let's say d is the probability that 10 or 11 comes up before 7. probability of rolling 10: (6+4,4+6,5+5) = 3/36 probability of rolling 11: (6+5,5+6): 2/36 probability of rolling 7: (6+1,1+6,5+2,2+5,4+3,3+4): 6/36 d = you roll 10 or you roll 11 or (you roll something other than 10,11,7 and roll 10 or 11 before 7) d = (3/36) + (2/36) + (25/36)*d (11/36)*d = (5/36) d= 5/11 Anonbyfar is correct, 5/11 is the right answer but for the wrong question doesnt the answer by 'Anonbyfar' (17/132) give you the probability of rolling a 10 and 11 within two rolls? Shouldnt this be then related to the probability of rolling a 7 (6/11). I.e 17/72? P(10 or 11 before 7) = P(10 or 11 | 10 or 11 or 7) = [P(10) + P(11)]/[P(10)+P(11)+P(7)] P(10) = 3/36 4,6 5,5 6,4 P(11)= 2/36 5,6 6,5 P(7) = 6/36 1,6 2,5, 3,4 4,3 5,2 6,1 Answer: 5/11 roll 10 or 11: 5 cases roll 7: 6 cases roll others: 25 in total: 36 cases So Pr = 5/36 + 25/36 *Pr Pr = 5/11 |

### Trader at Jane Street was asked...

If I write down all of the numbers from 1 to 1,000,000 on a page, how many times do I write down the digit 2? 9 Answers(base 10 )log(x)/10*x I got 468599 600000 (verified through brute force) Show More Responses imagine the numbers written as 000001 000002 000003.....999998 999999, then we 1 million numbers containing 6 digits, each digit of 10 digits we have, is used as much as any other number. Therefore, you write down the digit 2 10% * 6 million - 600,000 the minus must be an equal sign on the end, so 600,000 is the right number [1 x 10 x 10 x 10 x 10 x 10] + [10 x 1 x 10 x 10 x 10 x 10] - 1 + (bcos 222222 covered above) [10 x 10 x 1 x 10 x 10 x 10] - 2 + (bcos 222222 & 22222 covered) [10 x 10 x 10 x 1 x 10 x 10] - 3 [10 x 10 x 10 x 10 x 1 x 10] - 4 [10 x 10 x 10 x 10 x 10 x 1] - 5 = 600000 - 15 = 599985 Continuation from above from 1 upto 1 with n 'zeros' (e.g. 10 has 1 zero, 100 has 2 zero, etc), answer = n(10^[n-1]) - 0.5n(n-1) So upto 1000000 would give 6 x 10 ^ 5 - 0.5 x 6 x 5 = 599985 The idea is to exploit the symmetry among 0,1,2...9. Instead of 1->10^6, one should think of 000000 -> 999999, where 0-9 occurs with the same probablity . Altogether 000000 -> 999999 has 10^6 numbers, 6*10^6 digits; divided by 10 this is 600,000. The idea is recursion, let x_n be number of times that digit 2 appear in 0 to the largest n digit number. For example, x_1 = number of times that 2 appears in 0-9. x_2 is up until 99, etc. you work out to see x_1 = 1. x_2 = 10*x_1 + 10 etc. finally, I think you will get 600000 |

### Assista at Jane Street was asked...

2nd Round: You have a deck of cards, 26 red, 26 black. These are turned over, and at any point you may stop and exclaim "The next card is red.". If the next card is red you win £10. What's the optimal strategy? Prove this is the optimal strategy. 6 AnswersThe simplest strategy is not to wait until any card is open and say the next one is red, than you have 26/52 chance of success. All other strategies require conditional probabilities, so when multiplying by the probability of that condition the overall probability is not going to be greater than 1/2. Regardless of your strategy, your probability of winning is 1/2 Nope the optimal strategy is to count the amount of black cards that come up until you hit 26 and obviously the next one is red Show More Responses Adrian is wrong, because the strategy only work 50% of the time, when the last card is not black. So you still get 1/2. The idea here is A LEAP OF FAITH: that is we have found the optimal strategy when there is X red and Y black left in the deck. let Strategy(X,Y) be that strategy: it is either "Wait" or "Say it now". Let P(X,Y) be the probability that we are right by following this strategy. now Strategy(X, 0) is definitely "say it now" and P(X, 0) = 1. what about Strategy(1, 1)? half the time it will show black and we win for sure; half the time it will show red and we are doomed. Both action, "wait" and "say it now" have the same expected chance of winning, which is 1/2. so P(1,1) = 1/2. What about Strategy(2, 1)? if it is "wait", 2/3 time we go to (1, 1) and 1/3 time we go (2, 0). the chance of winning if we wait is 2/3*1/2 + 1/3*1 = 2/3. if it "say it now", the chance of winning is 2/3 as well. so P(2, 1) = 2/3. As you can see, we basically have the following relationships: P(X, 0) =1 for any X. P(X, Y) = max( X/(X+Y), X/(X+Y) * P(X-1,Y) + Y/(X+Y) * P(X, Y-1)) and you can probably guess that P(X, Y) = X/(X+Y) so P(26, 26) = 1/2. That means calling out on first card or wait both gives you optimal strategy. always 1/2 |

### Analyst at J.P. Morgan was asked...

puzzle 9 balls, identical in appearance. 8 are of same weight. 1 is heavier. Identify this heavier ball by using a scale twice. 5 Answersput 9 balls in groups of 3. Split them into two sets of 4 and 1 individual ball. Place the two sets on each side of the balance. If the sets balance out, then the individual ball is the heavier one. If the sets don't balance, then take the heavier set and split it up into two sets of two and repeat. I believe that an explanation to the solution that Interview Candidate is suggesting can be found here: http://brainteaserbible.com/snooker-balls-weighing-scales Show More Responses Split the balls into groups of three, compare two of the groups. If the sets balance then the heavy ball is in the third group, otherwise it is in the group left out. Whichever it is, take two balls from that group to weigh. If they balance, you know it is the third ball, if they don't, you have the heavier ball. http://brainteaserbible.com/snooker-balls-weighing-scales |

write a function that returns the first unique element in an array 5 AnswersWhat the type of elements in the array? If character, set up the hash table, and scan the array. the hash table stores the index of each element. If the element appears more than once, update the table as a negetive value. After scanning, find the smallest index value from the hash table, which would be the first uniqure element. The time complex gonna be O(n), where n is the length of array. I wrote a sample program here. (I use map container here to replace hash_map. The doesnot work on my computer) #include "stdafx.h" #include #include using namespace std; static int find_unique_ele(char*,int); int _tmain(int argc, _TCHAR* argv[]) { char test[6] = {'a','b','c','b','c','a'}; int min_index = find_unique_ele(test,6); if (min_index store_table_value; map store_table; while(i ::const_iterator test_it = store_table.find(*test); if(test_it != store_table.end()){ store_table[*test] = -1; } else{ store_table.insert(map::value_type(store_table_value(*test,i))); } i++; test++; } map::const_iterator table_it = store_table.begin(); store_table_value temp_value = *table_it; int min_index = temp_value.second; while(++table_it != store_table.end()){ temp_value = *table_it; if(temp_value.second < min_index || min_index < 0){ min_index = temp_value.second; } } return min_index; } I think in the above solution you have to scan the original array twice making it order (2n) or O(n). The 2nd scan is needed to determine the corresponding entry in the hash table whether it is unique or not. We need this to determine the first unique element in the array. Show More Responses Sort the list then scan the list looking for a data item that does not match the previous item or the next item. very easy with c++ stl using unique() function or use hashtable for O(1) look -up HashTable mm = new HashTable(myArray.count()); for(int i =0; i |

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

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 } |

### Options Trader at Liquid Capital was asked...

If there was a drawer in front of me containing 4 socks, either black or white, and I know that I have a 50% probability of pulling out two white socks in a row, then what is the probability of pulling out two black socks? 5 AnswersThere is zero probability of pulling two black socks. Assuming there are 2 whites and 2 blacks then getting 2 socks of the same colour is the same Above meant to say: Has the same probability Show More Responses You can't assume there are two white socks and two black socks. This problem is an easy enumeration problem actually. From the problem, you have at least 2 white socks, otherwise it would be impossible to take out 2 in a row. So you have either 2 white socks, 3 or 4. Just compute the three prob of getting two white socks in a row for all case and see which is 50%. P(two w in a row| 2 white socks) = (2/4) * (1/3) = 1/6 => not two socks. P(two w in a row| 3 white socks) = (3/4) * (2/3) = 1/2 => this is our answer. Obviously, if there were 4 socks, we would have a 100% chance of getting two whites in a row. So as calculated, there must be 3 white socks. The probability is 0 as there is only 1 black sock. Solution: Assume there are k white socks and 4-k black ones in the drawer. => 0.5 = P(2 white socks in a row) = k/4 * (k-1)/3 => k^2 - k - 6 = 0 => k = 3 is the number of white socks. qed. |

### 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]; } |