anshulzunke
BAN USER- 0of 0 votes
AnswersHow many types of class loaders do you know in java
- anshulzunke in India| Report Duplicate | Flag | PURGE
Tribal Fusion Software Engineer / Developer Java - 0of 0 votes
AnswerWhat is request forwarding and request redirect
- anshulzunke in India| Report Duplicate | Flag | PURGE
Tribal Fusion Software Engineer / Developer - 0of 0 votes
AnswerYou have two hashmaps HM1 and HM2 where key = Id(long) value = timestamp. You need to give a program to return a list of Ids combined from both the hashmaps such that they are sorted as per their timestamps
- anshulzunke in India| Report Duplicate | Flag | PURGE
Tribal Fusion Software Engineer / Developer Java - 0of 0 votes
AnswersHow will you make your own Hashmap class?
- anshulzunke in India| Report Duplicate | Flag | PURGE
Tribal Fusion Software Engineer / Developer Java - 0of 0 votes
AnswersPreOrder traversal without recusion
- anshulzunke in -| Report Duplicate | Flag | PURGE
Myntra Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhich is greated 3^20 or 2^30
- anshulzunke in India| Report Duplicate | Flag | PURGE
Urban Touch Software Engineer / Developer Brain Teasers - 0of 0 votes
AnswerDifference between MYISAM and NoDB Mysql
- anshulzunke in India| Report Duplicate | Flag | PURGE
Urban Touch Software Engineer / Developer Database
if i got ur question correctly. The problem is: we got a dictionary with some words inserted in the dictionary. Now given a String str we need to find if str or any of its anagram is part of the dictionary.
For the problem stated above, i think trie will be the best suited DS.
Suppose i got a dictionary(trie) and a string "same" and in my dictionary i have the anagram "emas". So my algorithm will start traversal from root and check if any of the chars from the string is a valid child of the root. If so we then move to next the child node and keep on checking for remaining characters till all the characters r completed else return false.
nice approach for level order traversal :)
- anshulzunke September 30, 2014This can be solved using Trie.
Assuming we have a Trie data structure with all the dictionary words in it
Basic idea is for each character keep on tracking whether the prefix it covered is a valid word or not. If it is then we have 2 subproblems
a. substring upto i is valid but need to check validity of i+1 to length subsequence.
b. ignore validity of substring 0 to i instead keep on checking validity of the subsequence from 0 to i+1
if any of the two subproblems give a result true. Overall result will be true.
public static boolean isValidSequence(Trie trie, String sequence){
boolean rslt = false;
int length = sequence.length();
TrieNode node = trie.getRoot();
int i = 0;
for( i = 0; i < length; i++){
char ch = sequence.charAt(i);
int charIdx = ch - 'a';
TrieNode[] children = node.getChildren();
TrieNode charNode = children[charIdx];
if(charNode == null){
rslt = false;
break;
}
if(charNode.isEndsWord()){
String subSeq = sequence.substring(i+1);
boolean rsltOfNextSeq = isValidSequence(trie, subSeq);
if(rsltOfNextSeq){
rslt = true;
break;
}
}
node = charNode;
}
if((i == length) && (node.isEndsWord()))
rslt = true;
return rslt;
}
Queue of size n and a variable storing SUM. Queue[0 to (n-1)] elements will store the last numbers in FIFO order and when ever a number is entered SUM will be modified accordingly. In this way getting avg in O(1) operation
- anshulzunke October 09, 2013Why not an ArrayList
- anshulzunke August 04, 2013This code still has issues since we are not modifying the start of the linked list which will get modified too in case of swapping 1st and 2nd node of the linked list
procedure(Node start){
if(start == null) return;
boolean startNodeModifed = false;
Node x = start;
Node y = x.next;
while(x!= null and y != null)
{
x.next = y.next;
y.next = x;
if(!startNodeModifed)
start = y;
x = x.next;
if(x == null) return;
y = x.next;
}
}
procedure(Node start){
if(start == null) return;
Node x = start;
Node y = x.next;
while(x!= null and y != null)
{
x.next = y.next;
y.next = x;
x = x.next;
if(x == null) return;
y = x.next;
}
}
Just iterate through all the nodes
for each node find x = height of right subtree + height of left subtree + 2 if both subtrees r not null
if any1 of them is null x = height (right or left subtree ) + 1
else 0
and diameter = max(x) when u calculate x for each node
some part would have been
Node temp1 = head;
while(N.value<=temp.value)
{
temp1 = temp;
temp = head.Next; // since this is circular tail will point to head
}
temp1.Next = N;
N.Next = temp; // correct
Jayram your code has lot of problem
1.temp = head.Next; insteam you should write temp = temp.next
2.while(N<=temp) instead while(N.value<=temp.value)
3. If N.value is > all the values in the list, it will invoke infinite loop
4.head.Next = N; I dont know wht are you doing here by inserting on head. you should rather insert it jst before temp by having another variable temp1 = temp b4 doing temp=temp.next; so temp1.next = N nd N.next=temp would hv done the trick
R u suggesting an array of 1million boolean data? I dont think tht will be feasible
- anshulzunke September 04, 2012My Idea is get the length of both the trees and whoever is larger could surely be the Super tree and another will be subtree if they one of them is part of the other and to find whether the smaller tree is part of larger tree we will recursively check if the left and right subtrees are exactly same if the respective is not null in the smaller tree
function isSubTree(Node root1, Node root2)
{
int length1 = lengthOfTree(root1);
int length2 = lengthOfTree(root2);
if(length 2 > length1)
{
root2 = findNodeInTree(root2, root1); // find root1 in tree2(root2)
return isSubTreeOf(root2, root1)
}
else{
root1 = findNodeInTree(root1, root2); // find root2 in tree1(root1)
return isSubTreeOf(root1, root2)
}
}
function isSubTreeOf(Node rootOfSuperTree, Node rootOfSubTree)
{
boolean isleftChildSubTree = true;
boolean isRightChildSubTree = true;
if(rootOfSubTree.value == rootOfSuperTree.value)
{
if(rootOfSubTree.leftChild != null)
{
isleftChildSubTree= isSubTreeOf(rootOfSuperTree.leftChild , rootOfSubTree.leftChild);
}
else{
isRightChildSubTree= isSubTreeOf(rootOfSuperTree.rightChild , rootOfSubTree.rightChild)
}
return isRightChildSubTree && isleftChildSubTree;
}
else
return false;
}
I will go with an array of linked lists.
Lets say my browser stores history of last 7 days then there will be array of length 7 and each element of the array is a linked list which is nothing but all the urls it had accessed that day. So the array will be used like a queue and every day 1 linked list would be deleted from top to create a new linked list on the bottom for that particular day.
buble sort on linked list
- anshulzunke September 02, 2012but you aint taking the advantage of the cond mentioned by interviewer of sorted lists.
+ you are using the help of DS libraries
+ how can you say the complexity would be O(N) when you are using functions like hm.containsKey. Do you think these functions are implemented in O(1) time complexity.
always remember, never use the java api calls in algorithm interviews.
Modified code
function myFunc(){ // func start
List l1;
List l2;
List l3;
Node currentNode1 = l1.head;
Node currentNode2 = l2.head;
Node currentNode3 = l3.head;
while(currentNode1 != null || currentNode2 != null)
{// 1st while loop starts
while(currentNode2.value < currentNode1.value)
{ // 2nd while loop starts
if(currentNode2.next ! = null)
{
currentNode2 = curentNode2.next;
}
else{
// below func will apend nodes from L1
// starting from currentNode1 into L3
L3.appendAllRemainingNodes(L1, currentNode1)
return L3;
}
}// 2nd while loop ends here
if(currentNode1.value != currentNode1.value)
{ // if starts
Node newNode = createNewNode();
if(currentNode3 == null)
{
L3.head = newNode;
currentNode3 = newNode;
}
else
{
currentNode3.next = newNode;
currentNode3 = newNode;
}
} // if ends
currentNode1 = currentNode1.next;
}//1st while loop ends here
// below func will apend nodes from L1
// starting from currentNode1 into L3
return L3;
/ /func ends
}
Jack in that case 2nd sorted list will be traversed only once since
if(currentNode2.next ! = null)
{
currentNode2 = curentNode2.next;
}
else{
return L3;
will take care of it.
Now after your comment i again checked and found I cond is still missing in the algo particularly in your case
I should have added all the remaining nodes of List1 should be appended to resultant List L3 before returning L3
dont u think u r taking too much extra memory
- anshulzunke September 01, 2012The idea is since both are sorted compare elements of 1st list with 2nd list only till 2nd list element is smaller or equal to 1st list and for comparing next element of 1st list do it from the node where the search of prev node stopped.
function myFunc(){ // func start
List l1;
List l2;
List l3;
Node currentNode1 = l1.head;
Node currentNode2 = l2.head;
Node currentNode3 = l3.head;
while(currentNode1 != null || currentNode2 != null)
{// 1st while loop starts
while(currentNode2.value < currentNode1.value)
{ // 2nd while loop starts
if(currentNode2.next ! = null)
{
currentNode2 = curentNode2.next;
}
else{
return L3;
}
}// 2nd while loop ends here
if(currentNode1.value != currentNode1.value)
{ // if starts
Node newNode = createNewNode();
if(currentNode3 == null)
{
L3.head = newNode;
currentNode3 = newNode;
}
else
{
currentNode3.next = newNode;
currentNode3 = newNode;
}
} // if ends
}//1st while loop ends here
return L3;
//func ends
}
your soln is better. Many ppl suggested on ur lines but the thing you pointed is most recent used will be placed on the head of the list and least recent used on tail of the list. Most of the time you need to work with modification of head of the list only when you dont find your match then you need to traverse down the tail
- anshulzunke August 15, 2012for 2D array ineed to get 135 * 135 continuous space which i think should be avoided
- anshulzunke August 15, 2012nice questio though taking the help of binary search it will still be O(nlogn) worst case
1. using binary search find the 1(index i) which has 0 at index i + 1. Once you got that move to 2. next row and check if newRow(index) == 0 then move to next row // this has less 1st than earlier row
3. else apply binarySearch on newRow from index to nth index as shown in step 1 // this has more or equal 1s than earlier row
eventually you will find the row which has max number of 1s
Though worst case it will be O(NlogN)
worst case is
row1 has one 1
row2 has two 1
row3 has three 1.
eventually it will go to complexity o(n logn)
btw hrday could you please elaborate which company had asked you the question
- anshulzunke August 15, 2012I think database and all comes afterwards when we want to persist the data which is obvious we need to.
Talking about RAM datastructure i dont think we should go for 2D array. Rather i will prefer nodes of all the from stations and from there there wll b an array of 135(including the from station) destinations. Now all these from station nodes will be accessed through a hash table.
So in short if i have to define the Ds it should be
Datastrucutre NodeStation(){
int stationId
float Array destStationFare[];
}
hashTable<stationId, NodeStation>
so from the hash table we will get the from station node and from that node we will get the fare through the destStationFare array
If i count the number of 0s(say m) and number of 1s(say n) and then make last m nodes as 1 and remaining as 0s. That too solves my problem with O(N) time complexity
- anshulzunke August 13, 2012Sorry there is a problem in the above algo havent taken the case if tree is nt complete binary tree. In that case for each node need to check whether it has 2 or 1 child node(s)
- anshulzunke August 12, 2012Please let me know if the sol has some flaw.
- anshulzunke August 12, 2012see i have tried to write an algo for this
my idea is i have divided the tree nodes into 5 modes 1. either node is a root 2. node is a leaf node 3. node lies in the left circumference wrt root 4. node lies in the right circumference 5. nodes are intermediate nodes and based on that i have written a simple level wise traversal
function printCircumference(Node node, Mode mode){
if(isLeafNode(node))
print node.value;
else if(mode == root)
{
print node.value
printCircumference(node.leftChild, left)
printCircumference(node.rightChild, rigt)
}
else if(mode == left)
{
print node.value
printCircumference(node.leftChild, left)
printCircumference(node.rightChild, intermediate)
}
else if(mode == right)
{
print node.value
printCircumference(node.leftChild, intermediate)
printCircumference(node.rightChild, right)
}
else{
//intermediate nodes
printCircumference(node.left, intermediate)
printCircumference(node.right, intermediate)
}
}
naveen i dont think question meant any calculation we just had to print the circumference
- anshulzunke August 12, 2012I think we can have a trie datastructure which will help us in maintaining a key value pair and it will also help in giving prefix search capability.
Now how the client side interaction takes place, we can have ajax calls but i am not too supporter of ajax calls it will take an ajax call per keypress
isnt this a prob of finding min dist b/n 2 nodes in a graph?
- anshulzunke May 20, 2012Yes we can but the method the above guy used is morec efficient and i think interviewer was expecting tht efficient algo only
- anshulzunke September 23, 2011The person nodes of 1 group could be arranged as an array or linked list. I personally would prefer as an array since the application might require accessing any person at a time.
- anshulzunke September 23, 2011// basically a node(Person) having his name and an array of pointers pointing to the Person object of other group if it has punched that guy. So basically a graph.
Person{
String Name;
Person punchedPerson[];
}
Why cant i have 2 way hash table
?
I did it by using a shared variable(state).
initially state = 0, when J1 is starts state = 1 and when J1 completes state = 2.
for thread T2 -->
if(state != 2)
{
Thread.currentThread().wait();
}
Do J2
for T1 --->
state = 1
Do J1
state = 2
notifyAll();
Trie would be better. But instead of having count of urls we should have the index of the string in the list. Whenever we encounter the url again make the index = -1. So now the trie will give indexes in each node of trie as Null(never got set) or -1(set more than once) or +ve index value of the url in the list(set only once). now getting all the non null and +ve indexes find the min index you will get first unique URL.
- anshulzunke September 18, 2011millions of url i dont think hash is a good idea
- anshulzunke September 18, 2011i forgot to add this. I am sorry but interviewer has explicitly said without using join method
- anshulzunke September 18, 2011i think hash would b a nice for time complexity
- anshulzunke September 18, 2011One int variable storing current position of user. Hash Table for snake such that key = Snake'Mouth and Value = Snake Tail. So if user_position == x and if (SnakeHT.get(x) != null) then user_position = SnakeHT.get(x). Similarly another hash table for Ladder. User everytime dices, a random Number [1 6] gets generated and x = x + Random_Number and the snake and ladder position is checked as descibed above
- anshulzunke September 17, 2011Kamal's answer seems perfect.
- anshulzunke September 17, 2011Hashing aint the sol for everything. Could you imagine the space complexity behind hashing.
- anshulzunke September 17, 2011External sort is the ans. It uses merge sort as the base
- anshulzunke September 17, 2011Sorry i had misinterpreted ur line "Mapping". Yes ur solution seems good
- anshulzunke September 17, 2011Nice answer but though the space complexity is O(n)
- anshulzunke September 17, 2011I guess we had discussed the solution above. The solution will have O(N) space complexity
- anshulzunke September 17, 2011check the above replies it wont work for all cases
- anshulzunke September 16, 2011I think Wrapper classes were part of java even before generics
- anshulzunke September 16, 2011
- anshulzunke December 17, 2014