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
public int changeTree(node root){
if (root==null)return;
int left=changeTree(root.left);
int right=changeTree(root.right);
return root.data=left+right;
}
If node value can only be incremented then I am not sure how to set it to lower value, unless we change the tree, i mean add some constant number to each node.
- OTR March 08, 2014public int replaceNodeWithRightSubtree(Node node){
if(node==null)return 0;
int rightSum=0;
if(node.right!=null){
rightSum=replaceNodeWithRightSubtree(node.right);
}
node.value=node.value+rightSum;
if(node.left!=null){
node.left.value=node.left.value+node.value;
replaceNodeWithRightSubtree(node.left);
}
return node.value;
}
Take each element of array find in each Set, Store the result in a hasmap in form HashMap<SetID,SizeOfMissingNumberOfArrayElement>. Sort the Map based on value in ascending Order. put the missing element in other sets, and if found print the result. there can be many such sets if same value is present in different sets but I am not counting that scenario here. In terms of complexity, if array size is m, and there are k sets having each n elements.O(nk)
- OTR August 22, 2013Based on the description of question, here is my assumption:
Tree has three nodes
a) Left Node
b)Right Node
c)Parent Node
Maximum diameter of tree will be distance between two nodes.
These two nodes will be leaf nodes only.
so, here is pseudo code:
1.Find farthest leaf node in left subtree:
Traverse Left subtree and store all leaf nodes in an array .
Loop through all leaf nodes and use parent pointers to find distance to root node, using a temp varaible. Keep updating temp varaible with Max distance.
2. Find farthest leaf node in right subtree
Find all leaf nodes in right subtree of root node.
Traverse till each leaf node and record the maximum distance.
Diameter will be distance between leaf node in left subtree which is farthest from root , and leaf node in right subtree which is farthest from root.
Please comment your views if My analysis is in correct direction or I am missing something.
This problem is similar to frog jump in an array.But before that we will have to model the problem in that format.
Create an array of size 100 and for each position store 6 if there is no snake or ladder. store jump count . if ladder is present at that point . If snake is present then store -ve jump at that location.
Now we have to solve in how many minimum steps we can reach till end.
Main problem can be solved using dynamic programing in O(n^2) time complexity and O(n ) space. tech-queries.blogspot.com/2011/08/find-optimal-number-of-jumps-to-reach.html
- OTR August 17, 2013Working code:
import java.io.*;
class Node<T>{
T data;
Node<T> left;
Node<T> right;
public Node(T t){
this.data=t;
}
}
class Queue<T>{
QueueNode<T> Head;
class QueueNode<T>{
T data;
QueueNode next;
public QueueNode(T data){
this.data=data;
}
}
public boolean enqueue(T data){
if(Head==null){
Head=new QueueNode<T>(data);
return true;
}
QueueNode temp=Head;
while(temp.next!=null){
temp=temp.next;
}
temp.next=new QueueNode<T>(data);
return true;
}
public T dequeue(){
QueueNode<T> temp=Head;
Head=Head.next;
return temp.data;
}
public boolean isEmpty(){
return Head==null;
}
}
class TestCase{
static Node firstLeaf=null;
static Node prevLeaf=null;
public static void main(String[] args) throws IOException{
BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
String str=buf.readLine();
if(str==null || str.length()<=0){
System.out.println("Invalid Input");
return;
}
String[] inpString=str.split(",");
int[] inp=new int[inpString.length];
for(int i=0;i<inpString.length;i++){
inp[i]=Integer.parseInt(inpString[i]);
}
Node<Integer> rootBST= createBSTFromArray(inp,0,inp.length-1);
printBST(rootBST);
convertBST(rootBST);
Node rnode=firstLeaf;
while(rnode.right!=null){
Node temp=rnode;
while(temp.left!=null){
System.out.print(" "+temp.data+"-->"+temp.left.data);
temp=temp.left;
}
System.out.println(" "+rnode.data+"-->"+rnode.right.data);
rnode=rnode.right;
}
}
public static void printBST(Node node){
Queue<Node> queue=new Queue<Node>();
queue.enqueue(node);
queue.enqueue(null);
while(!queue.isEmpty()){
Node temp=queue.dequeue();
if(queue.isEmpty())break;
if(temp==null){
queue.enqueue(null);
System.out.println(" ");
}else{
System.out.print(" "+temp.data);
if(temp.left!=null)queue.enqueue(temp.left);
if(temp.right!=null)queue.enqueue(temp.right);
}
}
}
public static Node convertBST(Node root){
System.out.println("calling for root"+root.data);
if(root.left==null && root.right==null){
System.out.println("returned leaf"+root.data);
if(firstLeaf==null)firstLeaf=root;
System.out.println("firstleaf is"+firstLeaf.data);
if(prevLeaf==null){
prevLeaf=root;
}else{
prevLeaf.right=root;
System.out.println("prev leaf and new leaf"+ prevLeaf.data+" "+root.data);
prevLeaf=root;
}
return root;
}else{
if(root.left!=null) {
System.out.println("left is"+root.left.data);
convertBST(root.left);
root.left.left=root;
root.left.right=null;
root.left=null;
}
if(root.right!=null) {
System.out.println("right is"+root.right.data);
convertBST(root.right);
root.right.left=root;
root.right.right=null;
root.right=null;
}
}
return root;
}
public static Node<Integer> createBSTFromArray(int[] inp,int from,int to){
//System.out.println("from and to "+from+" "+to);
if(inp.length==0 || from>to)return null;
if(from==to && to-from==0)return new Node<Integer>(inp[to]);
int root=from+(to-from)/2;
Node<Integer> rootNode=new Node<Integer>(inp[root]);
rootNode.left=createBSTFromArray(inp,from,root-1);
rootNode.right=createBSTFromArray(inp,root+1,to);
System.out.println("for node"+ inp[root]);
if(rootNode.left!=null){
System.out.println(" left node is"+rootNode.left.data);}
else{
System.out.print(" left node is null");
}
if(rootNode.right!=null){
System.out.print(" right node is"+rootNode.right.data);}
else{
System.out.print(" right node is null");
}
return rootNode;
}
//fuction for converting BST to new format
}
- OTR August 14, 2013Traverse the BST in in-order and when any leaf node is encountered, point it's left pointer to it's parent . for right pointer, store the leafnode as prevLeafNode and when a new leaf node is found point prevLeafNode to new Leafnode.
Working on the code , will post it soon.
Can you please answer my question here so that I can get some clarity about this problem?
I am not sure whether it is possible to build the tree from level order traversal or not. For ex, consider :
1 --level 0
1 1 --level 1
1 1 1
0 0 0 0 0 0
Now, at level 1 , It can not be found which element has two children and which one has one.
It can not be unique.
First of all, how do i differentiate one number is ending in that given string. is it comma separated in the string? If yes, then there are other methods also which use XOR of given numbers and XOR of all the numbers from start to end. that will give you the missing number.
- OTR August 13, 2013I am not sure whether it is possible to build the tree from level order traversal or not. For ex, consider :
1 --level 0
1 1 --level 1
1 1 1
0 0 0 0 0 0
Now, at level 1 , It can not be found which element has two children and which one has one.
It can not be unique.
if each node in tree has pointer to it's parent, then we can find the LCA even if tree's root is not given. In this case this problem will be similar to finding intersection of two linked list.
keep traversing two nodes separately till parent is null. this way we can find the length of these two lists. get the difference of these two lengths and in bigger list , traverse till this length difference, and after that keep moving forward in these two list and compare the parent nodes.
When parent node is same that node will be LCA.
This can also be solved using two stacks. Keep putting parent node of each given node on stack till parent node is null. pop each node from stack and compare, if they are same then keep popping, when the node is different, then that node is LCA.
1.sort the both string and in one loop compare each character, if each character matches, then both strings are anagram of each other. Time Complexity O(nlogn), Space complexity O(1)
2. Create a hashmap with key as character and value as counter. Traverse the first string and insert character in map if it does not exist, otherwise increment the counter.
Now, for second string, loop through each character, and search in the map and if any character does not exist, then return false, if exists then reduce the value of that key. once looping over second string is over, iterate through hashmap and all values stored in the map should be zero. then return true, otherwise return false.
If I understand it correctly, Given input is about stundent and the subjects which are attended by a particular student. And If focus is to get the query done faster, then a map can be created with string as Key and List as value. Now when any student-subject input is received, get the data using student as key and update the value list with the subject, do the same for subject as key and update the value list containing number of students attending it.
- OTR April 20, 2014When query is done to find how many subjects are attended by a particular student named "ABC" , then get the corresponding list from map suing this student name as key and return the size of list.