Bloomberg LP Interview Question Financial Software Developers
Country: United States
Interview Type: In-Person
Some code (python)
class Trie:
def __init__(self):
self.root = {}
def add(self, name, phone_number):
"""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.add("Joe", 1234567868)
T.add("James", 4483455747)
T.add("Samantha", 4454443947)
T.list_contacts("J")
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.
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
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?
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.
#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;
}
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 {
PB.add("Riana",2222222)
PB.add("Riza",33333)
PB.add("Gza",334343)
PB.add("reve",44444)
PB.add("ODB",0)
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)
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());
}
}
}
}
// 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");
}
}
Simple trie structure should be good enough for this.
- deadman February 08, 2013(en.wikipedia.org/wiki/Trie)