## Bloomberg LP Interview Questions

- 0of 0 votes
Q1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))

Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))

Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))

- 0of 0 votes
You are given a vector of integers. You have to delete the odd numbers from it.

Expected complexity is O(N) Time and O(1) space

- 0of 0 votes
One question containing multiple questions

1) Define the structure of a function which takes an array of size n as input and returns True or False.

2) Write a function which takes an array as input and returns a string containing all the elements separated by a comma.

Ex : [0, -45, 9, 10] => "0,-45,9,10";

3) Write a function which takes two arrays ass input, and returns minimum common element in them.

Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45] => 4

4) Now let's say, the function takes an array of arrays, and each array is sorted. now, returns their first common element.

Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45], [-1, -3, -5, -7, 10, 4], [24, 35, 78, -90, 56, 4] => 4

- 1of 1 vote
You are given an array of integers both negative and positive.

Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.

Ex : [-20, -5, -2, -9] :> -2(-2)

Ex : [20, -19, 6, 9, 4] :-> 20(20)

Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)

Thanks velu007 for pointing out the mistake

- 1of 1 vote
Define a graph using Adjacency list where node and graphs are different entities, for example, Node is a struct/class and graph is set of nodes.

The graph is an acyclic directed graph(may be a forest not necessarily connected).

Write an assignment copy constructor for this graph.

Please note that the copy constructor should create a new copy of the graph, including all its edges and vertices. Interviewer called this deep copy.

- 1of 1 vote
Given a list of URLs entered by a user write a program to print unique and most recently used URLs. For example if user entered the following: -

1. google.com

2. yahoo.com

3. wsj.com

4. google.com

The output should be :-

1. google.com

2. wsj.com

3.yahoo.com

- 1of 1 vote
Calculate and replace repeated characters in a string with their number of occurrences.

Example :

aaaggbbbbc

3a2g4b1c

- 1of 1 vote
Sort elements by frequency, print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

- 2of 2 votes
Given points on a plane like (0,0), (1,0), (0,1), (1,1), (0,2), (2,2), (1,2). How many rectangles can be formed ?

- 0of 0 votes
I was asked to design a stock ticker system. Stock ticker is simply the shortened name of company and its current stock size. e.g. for Apple - "AAPL" -> "115"

He asked me to design a data structure to store incoming stream of stock tickers. Stream can contain same company more than once but all the values of it had to be stored. I used HashMap<String, List<Integer>>. Then he was adding more functionalities to system I don't exactly remember the questions now but one of them was related to calculating some ratio in constant time. Some of the questions were challenging.

- 0of 0 votes
Given a set find its power set. (This question is from CTCI) Interviewer then discussed the complexity of my solution. He asked me to explain him how the complexity is 2^n? As per my solution, I was iterating over an arraylist which contained the set elements so the size of list was getting doubled in every iteration. Hence the complexity (2^0 + 2^1 + 2^2 +.....+2^n-1 = 2^n)

- 0of 0 votes
Given a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input -> "ab" output -> "bab" 3) input -> "a" output -> "a"

- 0of 0 votes
You are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.

- 0of 2 votes
Hey guys, I was asked this question on Bloomberg's pre-interview screening exam and I was wondering how to go about it.

Find the tightest asymptotic bound for:

T(n) = n(T(n/2)^2)

so far I was able to get it to look like this (not sure if correct):

T(n) = 1 / (1 + T(n/2)^2)

From then I made a recursion tree which led me to think that T(n) might be exponential in this case. Do you have any idea where could I go from here? Do you think this has no tight asymptotic bound?

- 0of 2 votes
Returns the zero based index of the first occurrence of any character of str2 in str1

Input:

str1="adf6ysh"

str2="123678"

output: 3

I have solved this by taking second string in hashset and then iterating first string one by one but i need more optimized way.

- 5of 5 votes
* Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero

* elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])

- 0of 0 votes
* Implement a tick server the has multiple clients interested in different tickers. Clients have Plotters that are updated

* in real-time with the top 10 tickers that have the most price updates on the top. What data structure would you choose

* for the server and client plotters?

- 0of 0 votes
* Royal titles consist of name followed by space and a Roman numeral. Example: Richard IV. The Roman numeral in the title

* can go to L (50). You are given the roman numerals from 1 to 10:

* I II III IV V VI VII VIII IX X. And you are given the 10 multiples up to 50: XX XXX IL L. Numbers between 10 and 50 that

* are not given can be formed from 10 multiples and a numeral b/w 1 and 9. Example: 48 is XLVIII wichi is XL (40) plus

* VIII (8).

* <p>

* You are given an array of Roman titles sort it as follows: sort it on the name unless the names are equal, in which

* case you have to sort it on the ordinal of the numerals.

* Examples:

* Henry II, Edward VIII => Eward VII, Henry II

* Richard V, Richard II, Richard X => Richard II, Richard V, Richard X

- 0of 0 votes
Find out the output. Or Correct it if something is wrong.

`#include <iostream> #include<typeinfo> using namespace std; class base{ public: int a; base():a(0) {} int getA(){return a;} }; class der:public base { public: int b; der():b(1) {} int getB(){return b;} }; void display(base *obj, int ele) { for(int i = 0; i < ele; i++) { cout << (obj+i)->getA() <<endl; } } int main() { int i = 3; base arrb[i]; display(arrb, 3); der arrd[i]; display(arrd, 3); return 0; }`

The output is looking like

`0 0 0 0 1 0`

To me the output should be

`0,0,0,0,0,0 //6 0's`

But, how come

`1`

is coming in?

- 0of 0 votes
Given a string find biggest palindrome substring. For example for given string "AABCDCBA" output should be "ABCDCBA" and for given string "DEFABCBAYT" output should be "ABCBA".

- 0of 0 votes
THERE ARE SEVERAL LOG FILES COMING BY DATE WITH PRODUCT IDS AND I NEED TO REPORT THE TOP 10 (PRODUCT IDS) DURING A MOVING PERIOD OF 1 MONTH. DISCUSSED ABOUT THE DATA STRUCTURES NEEDED TO IMPLEMENT THE SOLUTION.

- 0of 0 votes
SSUME YOU HAVE A LARGE FILE WITH LINES OF TIMESTAMPS AND IP ADDRESSES . TIMESTAMPS ARE ORDERED, BUT MAY REPEAT AND MAY SKIP. HOW DO YOU DETERMINE WHETHER

THERE IS A TIME WINDOW THAT HAS A CERTAIN IP ADDRESS APPEARING MORE THAN K TIMES? HOW WOULD YOU SOLVE THIS IF INSTEAD YOU RECEIVED A STREAM.

- 1of 1 vote
Image an airport with the control tower having a constantly rotating radar scanning for airplanes. The radar's coordinates in the 2-d plane are (0,0). The radar has an API: void scan(const Plane &P) that is called periodically whenever the radar detects a plane. You can imagine that the Plane structure has x,y coordinates for that plane. You should fill in the function Scan, such that at any given time you are able to return the 100 closest planes to the tower (0,0).

- 0of 0 votes
Find summation of n records added in past 60 secs

Items of the type`struct { int i; time_t timestamp; }`

needs to be stored in a C++ container. One of the requirement is to calculate summation of 'i' s of these items added in past 60secs.

What container/datastructure will you use. (number of items can be in the order of 10s of thousands.

- 1of 3 votes
Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs from that array A that sums up to N. You should print each pair once.

- 0of 0 votes
Given an array A [0, 1, 3, 4,9,5,7,6] and number N.

This means that the array consists of the numbers from 0 ... N. However, as you see, 8 is missing in A. Print the missing number.

Think about the case N = 10^6

- 0of 0 votes
How do you decide whether we should use Java or C++ for a particular project . what are pros and cons

- 0of 0 votes
How does garbage collector work ? In mark and sweep , how does gc know which objects it needs to mark , how are references stored for objects for gc to understand that its reference is null or it is no more referenced anywhere j

- 0of 0 votes
Implement hashtable put function in C++ without using STL stuff.

- 0of 0 votes
A client wants to build a software phone book that contains everyone in the world (7 billion people). Every person has only the first name and the name is unique. What data structure would you use to store the data?