Bloomberg LP Interview Question for Financial Software Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
8
of 8 vote

Simple trie structure should be good enough for this.
(en.wikipedia.org/wiki/Trie)

Comment hidden because of low score. Click to expand.
0

Some code (python)

``````class Trie:
def __init__(self):
self.root = {}

"""adds a name/number to the Trie"""
node = self.root
for char in name:
if char not in node:
node[char] = {}
node = node[char]

node["NUMBER"] = phone_number

def find(self, prefix):
"""returns node after consuming given prefix"""
node = self.root
for char in prefix:
if char not in node.keys():
return None
node = node[char]

return node

def list_contacts(self, prefix):
sub_trie = self.find(prefix)
_print(sub_trie, prefix)

def _print(subtrie, prefix):
for key in subtrie.keys():
if (key == "NUMBER"):
print("{} : {}".format(prefix, subtrie[key]))
else:
_print(subtrie[key], prefix + key)

T = Trie()
T.list_contacts("J")``````

Comment hidden because of low score. Click to expand.
0

What data structure should we use to find a name through a phone number?

Comment hidden because of low score. Click to expand.
2
of 2 vote

Tries, they are a good way to implement dictionaries. They have a tree like structure with an empty node at the root and as you progress, each node adds one character to make words at the roots.

So, on R, traverse the trie till the node R and then depth first search (! can be optimized) to print all the names that can be reached from this point. Each node will have an object to store contact information.

Comment hidden because of low score. Click to expand.
0

Yeah i also explained him the trie solution but he was concerned about high amount of space that would be consumed (as each node will contain an array of 26 nodes for next character).. i could have have suggested him compressed trie but we were out of time so we couldnt discuss further

Comment hidden because of low score. Click to expand.
0

We can use compact prefix tree (Radix tree)!!

Comment hidden because of low score. Click to expand.
1
of 1 vote

You could use a trieof names and save the phone numbers in the last node of each leaf in trie.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Indeed Trie implementation would consume a lot of space. Therefore, we have succinct data structures, which are compressed TRIE based implementations. This is a very good explanation for using them for T9: stevehanov.ca/blog/index.php?id=120

Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes this is very old Trie Question.. Mostly interviewer was looking for if the candidate can code Trie or not .. else this is known question.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Use Hashtable, make key the first letter of name and each slot contain Linked list which contain Name and phone number and that linked list should be ascending order.

what you guys think?

Comment hidden because of low score. Click to expand.
0

yes..HasMap will contain 26 letters key and each key will contain the linklist ,having name and phone number in each node, starting with key character in Alphabetically sorted.

Comment hidden because of low score. Click to expand.
0

I dont get it ! How would this work when the input is 'ri' ?? or another combination which does not include just the first letter ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

maybe B+ tree, it's used in database for the same purpose

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct s
{
char a[10];
char b[10];
struct s *next;
}node;
node *ptr[26]={NULL};
int issame(char p[],char q[]);
int main(int argc, char const *argv[])
{
FILE *fp;
int i;
node *temp2;
char temp[10];
int response;
char temp1[11];
fp=fopen("phonesim.txt","r");
if(fp==NULL)
{
printf("no such file found\n");
exit(1);
}
while(fscanf(fp,"%s %s\n",temp,temp1)!=EOF)
{
temp2=ptr[temp[0]-'a'];
ptr[temp[0]-'a']=malloc(sizeof(node));
strcpy(ptr[temp[0]-'a']->a,temp);
temp1[10]='\0';
strcpy(ptr[temp[0]-'a']->b,temp1);
ptr[temp[0]-'a']->next=temp2;
}
fclose(fp);
printf("enter response\n");
scanf("%d",&response);
while(response)
{
printf("enter string\n");
getchar();
gets(temp);
if(temp[0]>'z'||temp[0]<'a')
{
printf("wrong i.p\n");
}
else
{
temp2=ptr[temp[0]-'a'];
while(temp2!=NULL)
{
if(issame(temp2->a,temp))
printf("%s %s\n",temp2->a,temp2->b);
temp2=temp2->next;
}
}
printf("enter response\n");
scanf("%d",&response);
}
return 0;
}
int issame(char p[],char q[])
{
int j=0;
int i=strlen(q);
while(j<i)
{
if(p[j]!=q[j])
{
return 0;
}
j++;
}
return 1;
}``````

Comment hidden because of low score. Click to expand.
0

correct me if i am wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think using Suffix Tree is a good choice

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ternery Tree with prefix matching

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````object PB {
private var pb = Map[String,Int]()
def add(n:String, num:Int) { pb += (n -> num) }
def find(l:String) = pb filterKeys { _.toLowerCase() startsWith(l) }
}

object Bloomberg extends App {

println (PB.find ("r"))
println (PB.find ("ri"))
println (PB.find ("o"))
}``````

Output:

``````Map(reve -> 44444, Riza -> 33333, Riana -> 2222222)
Map(Riza -> 33333, Riana -> 2222222)
Map(ODB -> 0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using regex given a flat file if space is the issue:

grep ^[Rr][Ii] <filename> | cut -d " " f2

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class phonebookDictionary {

public static void main(String[] args) {

Hashtable<String,Integer> phonebook = new Hashtable<String,Integer>();
String value,userIp,key;

phonebook.put("Rihana",233222232);
phonebook.put("Ricky", 134242444);
phonebook.put("Peter",224323423);
phonebook.put("Ron", 988232323);
System.out.println("Enter char to be searched:");
Scanner input = new Scanner(System.in);
userIp = input.next();
Set s = phonebook.entrySet();
Iterator it = s.iterator();
boolean flag = true;
while(it.hasNext()){
Map.Entry me = (Map.Entry)it.next();
key = (String)me.getKey();
for(int i =0;i<userIp.length();i++){
flag = true;
if(userIp.charAt(i) != key.charAt(i)){
flag = false;
}
}
if(flag){
System.out.println(key);
System.out.println(me.getValue());
}
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ would be something like

``````auto p = map.lower_bound("R");
while(p->second.name.substr(0,1) == "R")
{
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// source leetcode Implement Trie, I have added display method and modified insert

public class Trie {

private class TrieNode {
Map<Character, TrieNode> children;  // for children
boolean endOfWord;   // specifies end of word
int contact;
public TrieNode() {
children = new HashMap<>();
endOfWord = false;
}
}

private final TrieNode root;  // root doesnt change so final
public Trie() {
root = new TrieNode();  // root is also a TrieNode, construct Trie using TrieNodes
}

/**
* Iterative implementation of insert into trie
*/
public void insert(String word, int PhoneNumber) {
TrieNode current = root;  // start with root, point curr to root
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i); // for each character
TrieNode node = current.children.get(ch); // check if it is in children
if (node == null) {
node = new TrieNode();  // if not create a new node
current.children.put(ch, node);
}
current = node; // point curr to new node, there by incrementing curr
}
//mark the current nodes endOfWord as true
current.endOfWord = true;
current.contact=PhoneNumber;
}

/**
* Iterative implementation of search into trie.
*/
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
//if node does not exist for given char then return false
if (node == null) {
return false;
}
current = node;
}
//return true of current's endOfWord is true else return false.
return current.endOfWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
TrieNode node = current.children.get(ch);
//if node does not exist for given char then return false
if (node == null) {
return false;
}
current = node;
}
//return true of current's endOfWord is true else return false.
return true;
}

public void display(String prefix) {

TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
TrieNode node = current.children.get(ch);
//if node does not exist for given char then return false
if (node == null) {
System.out.println("Name doesnt exist in the contacts");
}
current = node;
}
//return true of current's endOfWord is true else return false.

if(current!=null) {
for(Character child: current.children.keySet()) {
TrieNode node=current.children.get(child);
helper(node,prefix+child);
}
}
}

public void helper( TrieNode node, String name) {

if(node==null) return;
if(node.endOfWord) {
System.out.println(name);
System.out.println(node.contact);

}
for(Character child: node.children.keySet()) {
TrieNode temp=node.children.get(child);
helper(temp,name+child);
}

}

/*
* For instance
Rihana 233222232
Ricky 134242444
Peter 224323423
Ron 988232323

If you give R as input it should list
Rihana Ricky and Ron with their contact numbers

If you give ri as input it should list
Rihana, Ricky with their contact numbers
* */
public static void main(String[] args) {

Trie phone = new Trie();
phone.insert("Rihana",233222232);
phone.insert("Ricky",134242444);
phone.insert("Peter",224323423);
phone.insert("Ron",988232323);

//System.out.println(phone.startsWith("R"));
//System.out.println(phone.startsWith("Ri"));
phone.display("K");

}

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use 26 buckets

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.