Interview Question for Analysts


Country: India
Interview Type: In-Person




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

Hi saurabh.
I hope i didnt explain the question properly. this is more like for a huge data (lets say for a org like tcs where ppl count is too huge) , and while inserting data , we will have name , id , contact , designation. etc . this record should be searchable using name / id / designation.. whenever multiple records are possible (like name designation) , need to print them all.

- gopi.komanduri July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Ok. It seems then you are looking for a Btree data structure and which will help create something like the Lucene Index.

Here a document will be indexed by tokenizing each word in the document and an inverted index will be created for each word found in the document against the document information. With this setup, the document (in this case the employee information) will be searchable with any key.

Here is an example:
Employee records:

DOC / ID /Name / Designation
DOC1: 100 / Perry / Program Manager
DOC2:101 / John / .NET Developer
DOC3:102 / Mark / Lead
DOC4:103 / Larry / Project Manager
DOC5:104 / Tim / Java Developer

Now here the expectation is to search by id, name or designation and in return get back the entire employee information

While saving the document, the doc can be tokenized and for each word in the document an inverted index can be created like

100: {"100,Perry,Program Manager"}
101: {"101,John,.NET Developer"]
...
104: {"104,Tim,Java Manager"}
"Program": {("100,Perry,Program Manager")}
"Manager": {("100,Perry,Program Manager"),("103,Larry,Project Manager)}
"Developer": {("101,John,.NET Developer"),("104,Tim,Java Developer")}
....
"Perry":{("100,Perry,Program Manager")}
....


This way when a query is fired for say Manager, it brings back 2 employee information for Perry and Larry
Searching by Employee ID brings back information / document about only that employee.

The actual index does have multiple fields though. If this logic sound right, Lucene implementation of BTree is what the interviewer is then looking for.

- Saurabh July 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think saurabh's answer is correct, even if its a big data structure, we only have multiple key, the value reference will only be duplicated.

- Gourab July 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java:
We wont need to create our own data structure. Existing java DS would work good. We will have to come up with our own logic of storing information in the DS though.This is what I can think of.


Lets say the requirement is to store and retrieve student address. The data structure should be searchable using
a. student id (100,101 etc)
b. student name (Larry, Perry etc)
c. student education level (high school, grad school etc)

Now student name and education level can be added later also.

So I will create a Map of Objects

Data Structure:
Map<Object, Object> student = HashMap<Object, Object>();


Populating Map:
-----------------------
Key: Student ID
Value: Student Address

student.put(100,"hillview ave");
student.put(101,"Pennsylvania Ave");

Later we need to store student using their names. Now instead of duplicating address against names, we can store names against student ids (as there can be more than 1 student with same name)

Key: Student Name
Value: ArrayList [ Student Ids ]

With Education Levels:
Key: Education Level.
Value: ArrayList [ Student Ids ]

Retrieval of information from the Map:
------------------------------------------------------
When retrieving information from the Map
Input: Student ID
Return: Return student address

Input: Student Name
Return: Get all the student Ids first from the same Map and then return arraylist of student addresses.

Code snippet:
--------------------

Map<Object, Object> student = HashMap<Object, Object>();



Object getStudentAddress(Object input){
	if(input instanceof Integer && input.startsWith("ID")){
		//id is given in the input. return the address directly
		return student.get(input);
	}
	else if(input instanceof String && input.startsWith("NAME")){
		//Name of the student is given, find all the ids and return their addresses
		List<String> addList = new ArrayList<String>();
		List<Integer> idList = (ArrayList) student.get(input);
		if(idList != null)
			for(int id: idList){
				addList.add((Integer)student.get(id));
			}
		}
		return addList;
	}
}

The solution is not very pretty but it should get the job done with variable keys added any time later.

- Saurabh July 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey Gopi
I don't understand why this has to be only implemented using hashmap. The current databases use the concept of indexes (Btree, Bitmap etc) to solve such problems and I guess thats the best way forward.

- kr.neerav July 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not my requirement , the interviewer asked this. However initially he said he is open to use any datastructure,. after later narrowed down to hashmap.

- gopi.komanduri July 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.Latest.customHashMap;

import java.util.ArrayList;
import java.util.List;

public class CustomHashMap {

List<Map> list = new ArrayList<Map>();

//method to add key
public void put(String key, Object value) {
Map m = new Map();
m.setKey(key);
m.setValue(value);
list.add(m);
}

//method to get key
public Object get(String key) {
Object o = new Object();
for (Map m : list) {
if (m.getKey().equalsIgnoreCase(key))
;
o = m.getValue();
break;
}
return o;
}
}

-------------------------------------------------

package com.Latest.customHashMap;

public class Map {
private String key;
private Object value;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}

}

--------------------------------------------

package com.Latest.customHashMap;

public class Test {

public static void main(String[] args) {
CustomHashMap m=new CustomHashMap();
m.put("Sushant", "Is a good Boy");
m.put("Sumit", "Is a bad boy");

System.out.println("getting value for key Sushant--->"+m.get("Sushant"));
System.out.println("getting value for key Sumit--->"+m.get("Sumit"));
}
}

- Anonymous July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use 4 array list for performing the same. Lets take arraylist like doc, id, name and designation. Each will have value of every column returned. Based on the position we can rearrange each of the item. say doc(1)=DOC1, and id(1)=100, Name(1)=perry and Designation(1)=Program Manager.
So, Like this every data can be accessed without wastage of memory.

- Pawan July 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You missed a tag.

- Anonymous July 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Map<Map<String,Object>, Object> multikeyMap

All passed Key match - 2 loops - one for all n entries and other for comparing that all keys match
Any Key match - 2 loops - same as above

To improve this structure - build a compact representation of the Key - ( as all the possible key fields are defined - the hashcode for every key can
be built from a combination of all keys that form a part of the keys for each record.
For example
Record 1:
Key = (Id:20, Name: "X") - Record 1
KeyHash = ("ID-Name").hashcode();
Key = (Id:20, Name: "X",Grade:A) - Record 1
KeyHash = ("ID-Name-Grade").hashcode();

So for the map, the records with same number of keys can be found in the same bucket.

- Anonymous August 18, 2014 | 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