angshu1986
BAN USER- 0of 0 votes
AnswersDesign a rules engine. It should run in at least linear time and should efficiently handle repetitive attributes in different rules. E.g.,
- angshu1986 in India
Attributes:
1. Digit check
2. Character check
Rule:
1. Rule 1 - input should be digit
2. Rule 2 - input should be digit and = 3
3. Rule 3 - input should be digit and between 2 and 5
4. Rule 4 - input should be character and value should be 'A'
5. Rule 5 - input should be character and value should be 'B'
Design rule matrix and process a stream of inputs. More than one rule may be applicable for a given input.| Report Duplicate | Flag | PURGE
JP Morgan Java Developer Algorithm Object Oriented Design - 1of 1 vote
AnswersYou are given two objects, Student and Course, and there exist a many to many relation between them. One student can be enrolled for more than one course and there can be many students enrolled for a single course. Design an effective data structure to store such data keeping in mind that the time complexity for search should be optimum. A search can be for the list of students enrolled for a single course, or for the list of courses a single student is enrolled.
- angshu1986 in India| Report Duplicate | Flag | PURGE
Morgan Stanley Java Developer Data Structures Java - 0of 0 votes
AnswersGiven a class Employee
class Employee { int age; String fName; String lName; }
An UI searches for employees using either 'FirstName LastName' or 'LastName FirstName'. Give a solution that will return the employee details, in O(1) time.
- angshu1986 in India
e.g. FirstName - John LastName - Walker
both John Walker and Walker John should work in O(1). Tried using a hashmap, but search would be O(2).| Report Duplicate | Flag | PURGE
Symantec Java Developer - 1of 1 vote
AnswersHow can you determine if an array is pre order representation of a binary tree. I started with the logic of creating binary tree using a pre order array and failure to create the tree will mean that the array is not a pre order representation, but got stuck in middle.
- angshu1986 in India| Report Duplicate | Flag | PURGE
Symantec Java Developer Data Structures
Use external sorting. There are two basic algorithms for this, a two way merge and multi way merge.
- angshu1986 May 12, 2015Use BFS approach. Print all nodes of a given level in the same line, then print a new line
for i = 1 to height of tree {
call the recursive function breadthFirst below
System.out.println("*****");
}
private void breadthFirst(Node<V> node, int level) {
if (node == null) {
return;
}if (level == 0) {
System.out.print(node.value + " ");
} else if (level >= 1) {
breadthFirst(node.leftChild, level - 1);
breadthFirst(node.rightChild, level - 1);
}
}
I came up with this approach without extra space:
1. take the first element, arr[0], as root.
2. For i=0 to length of array
i. find i where arr[i] > arr[0].
3. Split up arr into two sub arrays, 1 to (i-1) and i to length, the first being the left tree of root and the second the right tree.
4. Check if any element in second sub array has a value less than arr[0]. If found, return false indicating the tree cannot be formed.
5. Recursively call 1 to 4 for the two sub arrays.
Well, I suggested map based approach but was rejected in the first place, just as you mentioned, because of huge memory usage.
- angshu1986 May 03, 2015XOR approach works only when there is a single number that is repeated odd number of times. In your example, 5 and 7 both occur three times. So the final result is displayed as XOR of 5 and 7.
5 ^ 7 = 2.
My mistake. It is O(1). The interviewer was looking for a solution with one comparison only.
- angshu1986 April 25, 2015It will be O(1). What I meant is the number of comparisions.
- angshu1986 April 25, 2015It is a BST. IBut the question was to validate the array and not create the tree. Bit confused here.
- angshu1986 April 21, 2015In pre order, the first element is always the root.
- angshu1986 April 21, 2015Xor all the numbers. The result will be the number appearing odd number of times. It is because when we XOR the same number with itself, the result is zero. Complexity O(n)
- angshu1986 April 17, 2015
I tried two answers but both were rejected
- angshu1986 May 19, 20151. storing firstname+lastname and lastname+firstname in hashmap: will consume extra space.
2. tried something similar to @Karthikeyan's approach, creating unique key using characters, by adding up the ascii values. But the scenario failed. The following example will explain:
Employee 1:
First name : Abc
Last name: Def
Employee 2:
First name: Dbc
Last name: Aef
Both employees will have same ascii value sum, and on sorting, will yield the same result.