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)

- deadman February 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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")

- O.o December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- interpreterjacksun February 10, 2015 | Flag
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.

- Anonymous February 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vik February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- prasannavenkatesh0 March 12, 2013 | Flag
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.

- aj__ February 08, 2013 | Flag Reply
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

- Second Attempt March 12, 2013 | Flag Reply
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.

- hprem991 February 08, 2013 | Flag Reply
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?

- Geet February 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sonu February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chan1450 May 31, 2013 | Flag
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

- zyfo2 February 09, 2013 | Flag Reply
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;
}

- mani 4m sklm February 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct me if i am wrong

- mani 4m sklm February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think using Suffix Tree is a good choice

- Suffix Tree February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ternery Tree with prefix matching

- Samr March 17, 2013 | Flag Reply
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 {
  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)

- The Rza March 19, 2013 | Flag Reply
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

- Wolverine September 23, 2013 | Flag Reply
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());
			}
		}
	}

}

- karpagaganesh March 08, 2014 | Flag Reply
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")
{
	addresses.push_back(*p);
}

- sokane@bowmain.com August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use 26 buckets

- mani 4m sklm February 08, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More