OTR
BAN USER- 0of 0 votes
AnswersGiven an array which has prime numbers, find all duplicates elements of array.
- OTR in India| Report Duplicate | Flag | PURGE
iLabs Tech Lead Algorithm Arrays - 0of 0 votes
AnswersFrom a given input array, for each element, find next higher element present in each array. for example {40,50,11,32,55,68,75} output should be {50,55,32,55,68,75,-1} for element if no higher element is present, print -1. complexity should be less than O(n^2) . you can use datastructure and no constraint on space complexity.
- OTR in India| Report Duplicate | Flag | PURGE
iLabs Java Developer Algorithm
Here is what i can think of, let me know if you replied differently.
sort the data provided as input , and start inserting the data in binary tree from heightest input value so that all top values will be at low level and low values of input will be at high level. Insertion in tree should be done by traversing the tree in level order and left tree should be inserted before right tree. Total time to sort the input data O(nlogn)+building tree[O(n)]+calculating weight[O(n)]= Total TimeComplexity[O(nlogn)] ..
Here is the right answer, but could not think of when i was asked this question
Put plane on a ship which is in water and mark the hull immersed in water, then remove the plane from ship and start loading ship with known weights and the weight with which ship's hull comes to same marked position is the weight of plane.
I was also asked same question by GS, but interview kept on asking what else other approach can you think of. But i couldn't give the answer he was looking for.
I searched on internet and found the solution, which was put plane on a ship which is in water and mark the hull immersed in water, then remove the plane from ship and start loading ship with known weights and the weight with which ship's hull comes to same marked position is the weight of plane.
It can be done in O(n) time complexity and O(1) space complexity.
public int findSecondMax(int[] nums){
if(nums.length<=1){
System.out.println("invalid input");
}
int lower =nums[0];
int higher =nums[1];
for(int j=2;j<nums.length;j++){
if(nums[j]>lower && nums[j]<higher){
lower=nums[j];
}else if(nums[j]>higher){
higher=nums[j];
}
if(lower<=higher){
System.out.println("2nd lowest"+lower);
}else{
System.out.println("2nd lowest"+lower);
}
}
}
I can think of two things here:
- OTR August 07, 20131. we have to maintain the property that last node is pointing to middle node, so when any node is deleted, change the last node pointer to one node in backward direction.
2. Delete the node and reset the pointers, for this we need to traverse the linked list and keep two pointers prevNode and currentNode. Once we find the node to be deleted then delete that node and reset the pointers.