Hi5 Interview Questions
- 0of 0 votes
AnswersWe are given a undirected tree with N (1 to N) nodes rooted at node 1. Every node has a value assigned with it, represented by array - A[i] where i:[1:N].
- khatribalak December 03, 2021 in United States
We need to answer Q queries of type : -> V X : longest length of the common prefix between V and any ancestor of X including X, in their binary representation of 62-bit length.
Common prefix between 2 numbers is defined as:
Example :
4: 0..................0100 (62-bit binary representation)
6: 0..................0110
Considering both as 62-bit in it's binary representation.
Longest length of the common prefix is: 60 (as 60 left most bits are same.)
Now we are given the N (num nodes), edges, nodes values (A[i]) and queries, and we need to answer each query in optimal time.
Constrains :
N <= 10^5, number of nodes
A[i] <= 10^9, value of each node
Q <= 10^5 ,number of queries
Edge[i] = (i, j) <= N
Approach :
Create tree and track the immediate parent of each node.
for Each Query : [V, X], traverse each node n(in the path from X to root) and XOR each node's values with V and find the most significant set bit for each of the XOR operation and pick the minimum one among all of them.
So the result for Query : [V, X] : 62 - (1 + Step-2 result).
Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.| Report Duplicate | Flag | PURGE
Hi5 SDE1 - 0of 0 votes
AnswersWe are given a graph of N nodes. (1-N), where each node has exactly 1 directed edge to some node (this node can be the same node).
We need to answer the queries of type : A, B, which asks time required when 2 objects collide if one start at A and other start at B. Both moves 1 hop in 1 sec. If it's not possible for them to collide time would be -1.
Time : from X -> to Y : 1 hop = 1 second.
Constraints :
N, Q <= 10^5 (number of nodes, number of queries).
Example : for given graphA -> B -> C -> D -> E ^ | K <- F
Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.
- tusharrawat831 December 02, 2021 in United States
Query(C, D) : -1 seconds, as they will never collide.
Brute force will take O(Q * N) time. Can we do better than that?| Report Duplicate | Flag | PURGE
Hi5 Software Developer Programming Skills - 1of 1 vote
AnswersGiven a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path from vertex a to b, vertex b to c and vertex c to a there is atleast one edge having red color.
- praveend806 June 19, 2014 in India
It should be noted that (a,b,c), (b,a,c) and all such permutation will be considered as the same triplets.
EXAMPLE : Let N=5 and edges with colors are as follow :
1 2 b
2 3 r
3 4 r
4 5 b
Here answer will be 4.
EXPLANATION : (2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having read color. (2,3,5), (1,3,4) and (1,3,5) are such other triplets.| Report Duplicate | Flag | PURGE
Hi5 Student student Algorithm - 0of 0 votes
AnswerCreate a class Graph, which must represent the graph data structure in java. What will be the difference between directional and unidirectional Graph? How would you represent the weight of the edges?
- Lyubomir December 21, 2012 in United States| Report Duplicate | Flag | PURGE
Hi5 Java Developer - 0of 0 votes
AnswersCode quicksort
- Jon Horseman August 26, 2009| Report Duplicate | Flag | PURGE
Hi5 Accountant Algorithm - 0of 0 votes
AnswersLets say A is a friend of B and B is a friend of C then A and C are two degree friends. So we have to implement a function that takes two friends and return true if they are 2 degree friends. How will you implement this function efficiently.
- gauravk.18 May 04, 2008| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is stack. How do you implement it. Now lets say we want to add a new function called min which return the min element on the stack along with push and pop. Like push and pop this min function should also be a constant time operation how will u do it.
- gauravk.18 May 04, 2008| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm - 1of 0 votes
AnswersBackground:
- gauravk.18 May 04, 2008
For any perimeter of a rectangle, there may be multiple different dimensions that result in that specific
perimeter. When there are multiple dimensions for the same perimeter, there may also be multiple areas. In other words, any one perimeter can result in different areas depending on the possible combinations of dimensions that can make that perimeter.
Definition:
A dimension or instance of dimensions for a rectangle is a pair of length and width values. A dimension with length 5 and width 4 is considered the same as a dimension with length 4 and width 5. The area of a rectangle is the length multiplied by the width. The perimeter of a rectangle is equal to the sum of the lengths of all 4 sides or the sum of 2 multiplied by the width and 2 multiplied by the length.
Requirement:
A finite set of possible perimeters of a rectangle exist given a maximum perimeter, minimum length of any side, and the constraint that all sides are whole numbers; we will call this set U. Find the subset of perimeters in set U where all of the possible dimensions for a perimeter in the subset have areas common with the areas of one or more other perimeters in set U. Your program should take the minimum length of any side and the maximum perimeter, respectively, as command line arguments and output a comma separated list of the perimeters that meet the criteria explained above, sorted from lowest to highest. The program should be submitted in a single Java class with an implemented main function that provides the correct output given the two input arguments.
Example:
javac YourClass.java
java YourClass 1 64
10,14,18,20,22,26,30,34
Please make sure your program can be run with the exact syntax above. You can name the class anything you like, but the class name will be passed to a program that will compile it and then run a set of tests on the resulting program. It is important that your class will compile and run from within a local directory, not a package directory.| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Coding Algorithm - 0of 0 votes
AnswerGiven n cities with their populations, suggest an algorithm to pick up one of the cities randomly such that more the population of city is more chance it stands to be picked. Assume you can use an inbuilt random generator function from the language library.
- gauravk.18 April 04, 2008| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm