Oracle Interview Question
Software ArchitectsCountry: India
Interview Type: In-Person
Exactly what I was thinking. However if we need functions like name like 'a%' or name like '%a%' or name like '%a' I would have a Map<Character, NameInfo>. Where NameInfo has 3 binary trees. Tree 1 has entry for all IDs with names starting with that Character, Tree 2 has all ending with it and Tree 3 with all names containing it. This is a lot of space I know but makes the retrieval faster.
We can have three different hash tables based on ID, name and salary. Also, each table is like a bucket, which contains a list of all employees with same ID (or name or salary).
In this case each query will be answered in O(L) in which L is the number of result items, which is the most efficient time complexity we could have.
Note that for inserting an employee we should insert it in three different tables, which causes to have space complexity of 3*N(N is number of all employees) which is O(N) in total.
Create an interface with method called IEmployee
with method declaration :
FindAllEmployee();
FindEmployeeById(int employeeId);
UpdateEmployee(int employeeId);
DeleteEmployee(int employeeId);
----------------
Now implement the interface in a class
(using C#)
EmployeeRepositoryClass : IEmployee
{
now define all the methods
}
Now wherever we are using the employee object
Employee = new Employeee();
List<Employee> empList = FindAllEmployee();
Write one method with with query string and value array.
public void pojoToSQL(String query, String[] values) {
//Create a hashmap with Key as pojo field and value as corresponding db field.
//parse the query string and replace pojo fields with corresponding db columns
//make db connection and execute query in statement.
}
We can implement this using reflection.
1) Write a query parser which will parse the query.
2) The from clause contains class name. Load it using forName
3) The select clause contains few or all fields of the class mentioned in from clause.
4) Query may contain where clause or may not. If contains, then where clause may use "=" or like or >= or <= or > or <.
5) Using reflection we can extra the fields and compare the value with the where clause field values. If matches, then add it in some data structure which we want to return. Else ignore that record and move one.
I would create like below,
1) One hashmap with ID as key and Employee Object as value
2) Create a BST for Name and it has id. (so that search can be faster) - another gentleman suggested three trees for %a, %a%,a%...that's nice too..
3) Create a BST for Salary and ID. or B+ Tree in case they are looking for range queries on Salary.
Assume that employees are stored in array Employee[] employeeArr
1. Implement comparator interface using fields (ID,Name,Salary, Manager.. ) of the class.
2. Use Arrays.binarySearch( employeeArr, "searchField","SearchComparator") to search employee using specific information. E.g if searchField is ID then use comparator for ID field and pass appropriate information to binarySearch call.
3. You will be able to search values in O(log n).
This solution give good performance while keeping memory footprint low.
DATASTRUCTURE:
- BST or Hash Maps.
COMPLEXITY:
- O(1) for searching for an employee Id using Id as a Key in a hash map (Id will be unique. So, makes more sense to use a hash map).
ONE WAY:
- O(N)..Worst case if all the employees have the same name. Then there will be just one key and a list of employee objects associated with it. But if you simply want to print all the employee objects with the searched name, then it will be O(1). This will be exactly like querying.
- O(N)..Worst case if all the employees have the same salaries. Then there will be just one key and a list of employee objects associated with it. But if you simply want to print all the employee objects with the searched salary, then it will be O(1). This will be exactly like querying.
SECOND WAY (We won't need hash map for this alternative):
-Load all the employee objects into 2 binary search trees. The criteria for loading the two BSTs will be Name and Salary respectively (alphabetically for name and value-based for salary). That way the search would be O(logn).
-Moreover, we can also have searches such as "a%","%a" or "%a%" (where 'a' can be any charater or string of characters) using the BST which will fetch us the data in O(logn)....(AS ALREADY HIGHLIGHTED BY SOMEONE ELSE).
DESIGN:
- Create an Interface "IEmployee".
public Interface IEmployee{
public Employee getUsingId(int Id);
public Employee getUsingName(String nm);
public Employee getUsingSalary(int sal);
}
Implement the above interface in the Employee class.
Create a hashmap with key as id and value as Employee object.
- Anonymous August 26, 2015Create two more hashmap as below
1. First HashMap with key as name and value as id
2. Second HashMap with key as salary and value as id.
Now, when getEmployeeByName(String name) is called, it get the employee id corresponding to the name by looking up in the first hashmap. Use the key to get Employee from master hashmap
Similarly for getEmployeeBySalary.