abc
BAN USER- 11of 11 votes
AnswersGiven an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.
- abc in India
Sample input : [1, 2, 3, 4] -- output : 2
Sample input : [900, 2, 901, 3, 1000] -- output: 3| Report Duplicate | Flag | PURGE
Google Applications Developer - 1of 1 vote
AnswersTraveler wants to travel from city “A” to city “D”.
There is a path from city “A” to city “D”.
Path consists of steps, i.e. travel from city “A” to city “B”.
Path is encoded as sequence of steps.
Sequence is in incorrect order.
Your task is to restore order of steps in the path.
Input (unordered sequence):
C -> D
A -> B
B -> C
Output (Correctly ordered list which represents path):
A, B, C, D
Implement following API:
- abc in Indiaclass Step { String start; String finish; }; class Node { String value; Node next; } List<String> findPath(List<Step> steps) { }
| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 10of 10 votes
AnswersGiven a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!).
- abc in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 2 votes
AnswersYou are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.
- abc in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm
Hi Saurabh,
I think your first approach will not work. Consider the same tree you given and search(7, 20).
Search for min element in BST. Get the left and right child counts.
For 7: left count = 0 and right count = 0
Search for max element BST. Get the left and right child counts.
For 20: left count = 2 and right count = 1
Get the left and right child count of the root.
For root: left count = 4 and right count = 4
So the total number of elements between min and max would be
left child count of root + right child count of root - left child count of min node - right child count of max nodes + 1 for root himself
4 + 4 - 0 - 1 + 1 = 8 nodes which is wrong. It should return 3.
Please correct me if I'm wrong.
Hi Neeraj,
In your program, what are the initial values of low and high .?
Suppose my root value is 15 and the min and max are given as 2 and 30 respectively, control will go into else part of the findCount() function., could you please explain what will the condition if(lbound>=low && rbound<=right) evaluate to.!
Correction to the above comment. In the given tree, search (7, 20) should return 5.(ot 3 as mentioned in previous comment)
- abc June 20, 2014