mission-peace / interview Goto Github PK
View Code? Open in Web Editor NEWInterview questions
License: Apache License 2.0
Interview questions
License: Apache License 2.0
In SegmentTree file, while using "rangeQuery" method to find the minimum of a range in array, return value, when there is no overalap, should a very high value and not "0" otherwise rangeQuery result always be "0".
Please make some edits in the class "SegmentTree" and "MinOperation" to accomodate for the same.
private int rangeQuery(int segmentTree[],int low,int high,int qlow,int qhigh,int pos, Operation operation){
if(qlow <= low && qhigh >= high){
return segmentTree[pos];
}
if(qlow > high || qhigh < low){
return 0;
}
int mid = (low+high)/2;
return operation.perform(rangeQuery(segmentTree,low,mid,qlow,qhigh,2*pos+1, operation),
rangeQuery(segmentTree,mid+1,high,qlow,qhigh,2*pos+2, operation));
}
Happy Programming!!!!!
the input variable y does not contain sorted arrray
I would like know if it will be helpful if I contribute some unit tests.
Thank you
Farid
while (i <= j)
, because if we have one character input and this character is a dictionary word, then restore answer will produce an empty string.Tushar keep an high level context table for lookup. It is difficult to navigate through the whole Wiki page.
For example : if i want to go to dynamic programming i have to scroll through the entire page to reach there. Instead if you have index lookup it will be easy to go to that index. Just a though. You have written a lot of code. It is pretty cool.
could you post the code for determining the path?
The algorithm will result false for 1,1,1,1,2,2 ( n =6 , m= 2) since count of 1 i.e 4 is greater then n/m ( 3) although there is a solution : 1,1,2,1,1,2 .
Some modifications will correct it :
1)return false when
C > N- (N/m+1)
2)when distributing data instead of start = start + m , it should be start = start + m +1.
Please have a look
The graph you have implemented doesn't adds vertex to Hashmap naming allVertex if addEdge function in Graph class is called for two non declared vertices.
So when you have invoked addEdge in Graph Traversal (BFS and DFS) with main function it gives no response .Since none of the vertices are added
Thank you for your solution of N-Queen on LeetCode, but when I post your code to test the speed of this solution, the LeetCode return Status: Time Limit Exceeded
. So, maybe this solution now is out of the time limit.
The class BellmanFordShortestPath is not detecting negative cycles
Hi,
for addition of two array program, it fails when you think on the below example
for ex: int arr1[] = {99,2,3,4,5};
int arr2[] = {1,3,5,3,2};
so c= 10 hence it is now two digits how do you increase the new array and insert the value.
Regards
Anand
Hi,
I have tested your implementation of the Suffix Tree data structure. The validation step fails when using:
SuffixTree st = new SuffixTree("GGACTACGATTTGTGTTCATATTAGTTCA".toCharArray());
st.build();
System.out.println(st.validate());
And the output is:
Mismatch found $ T
Failed validation
false
Do you know where is the problem?
Emilio
if(k == m){
cout << i - m + 1 << "\n";
k = longestPrefix[k - 1];
/* whats the need for this statement when we display the output?
shouldn't we break here ?
or if the last character or the pattern doesn't match with the string only then this statement should be called.
Please explain this */
}
I think the code gives output as kth "smallest" element in two sorted array instead of giving the kth "largest" element.
Any specific reason for not using a parmeterized constructor and using a static function instead for new node creation.
Thanks.
Hi ,
The "size" property is not required & not used anywhere in the AVLTree.java class.
Not sure why it is calculated/kept in the class then. Please advise.
https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/AVLTree.java
Thanks,
Mayank
Test case
@Test
public void testDeleteLongerWordOnly() {
final Trie trie = new Trie();
trie.insert("Craploader");
trie.insert("Crap");
trie.delete("Craploader");
assertFalse(trie.search("Craploader"));
assertTrue(trie.search("Crap")); // Fails here
}
Solution
Add checking for leaf node in line 143 of Trie.java
So instead of
return current.children.size() == 0;
Do
return !current.endOfWord && current.children.isEmpty();
https://github.com/mission-peace/interview/blob/master/src/com/interview/array/DuplicateNumberDetection.java
What if the numbers in the are bigger than the size of the array? It results in array out of bounds exception.
Try to add two words like "ciao" and "ciaone" and delete "ciaone"
The Tries will be empty
for example
int arr[] = {1,1000001,1};
for matrix chain multiplication java,
I have raised a pull request as a fix for the same
#195
Why can't this be solved using same technique as in undirected graph using parent reference and visited set only . Why we need 3 sets. node v will be Adjacent of node u in directed graph only if there is a direct edge from u to v.
A lot of programmers prefer to code interview questions in C++. Please add a C++ folder so that we can contribute.
The Bellman-Ford algorithm doesn't seem to be compatible with the graph implementation. It fails when the graph is undirected.
Since the Bellman-Ford algorithm iterates through all the edges, it has no notion of which vertex is adjacent. It treats the edges as directed and doesn't take into account the edge v->u when the graph is undirected.
Vertex<Integer> u = edge.getVertex1();
Vertex<Integer> v = edge.getVertex2();
//relax the edge
//if we get better distance to v via u then use this distance
//and set u as parent of v.
if (distance.get(u) + edge.getWeight() < distance.get(v)) {
distance.put(v, distance.get(u) + edge.getWeight());
parent.put(v, u);
}
I encountered this problem when Dijkstra and Bellman-Ford returned different results for the following graph:
Graph<Integer> graph = new Graph<>(false);
graph.addEdge(1, 2, 7);
graph.addEdge(1, 3, 9);
graph.addEdge(1, 6, 14);
graph.addEdge(2, 3, 10);
graph.addEdge(2, 4, 15);
graph.addEdge(3, 6, 2);
graph.addEdge(3, 4, 11);
graph.addEdge(4, 5, 6);
graph.addEdge(5, 6, 9);
Within the addEdge method of Graph.java, the current implementation is:
Edge<T> edge = new Edge<T>(vertex1,vertex2,isDirected,weight);
allEdges.add(edge);
vertex1.addAdjacentVertex(edge, vertex2);
if(!isDirected){
vertex2.addAdjacentVertex(edge, vertex1);
}
A potential fix could be:
Edge<T> edge = new Edge<T>(vertex1,vertex2,isDirected,weight);
allEdges.add(edge);
vertex1.addAdjacentVertex(edge, vertex2);
if(!isDirected){
edge = new Edge<T>(vertex2,vertex1,isDirected,weight);
allEdges.add(edge);
vertex2.addAdjacentVertex(edge, vertex1);
}
This answer will fail if the array has negative integers.
int input[] = {-1,-2,-3,-4};
I have noticed from some source files that you do not comment so much your code. Since, as far as I have understood, this project is mostly for educative purposes, it would be nice to include some comments in the source code or at least at the beginning of the source code that explains the purpose of the program/algorithm.
It would be nice also to include a link to corresponding video where you explain the algorithm.
Example :
Try to have the first string as : "mary"
and the second string as "aralea" - The output should be false but according to your logic it is true since you have the CurrentLength to be (curlen-index).
kD-trees and similar computational geometry data structures.
Your videos are great!
Just try insert in the order 1, 3, 2 and notice that tree isn't balancing itself
output for this {2,5,7,8} price array is 10 instead of 12, why so?
len of rod is 5.
Regarding: interview/src/com/interview/dynamic/BreakMultipleWordsWithNoSpaceIntoSpace.java
I think the solution you wanted to write should provide all the possible Strings
.
BTW, I really like your Youtube channel, it would really awesome if you could create a video for this change request as well.
//expect false
System.out.println(rm.matchRegex("aba".toCharArray(), "c*a.*".toCharArray()));
Could ylu help analyze what is the time complexity and storage complexity?
output is not correct for 10 9 8 7 8 9 5
https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/CircularBinarySearch.java
From your YouTube video, Optimal Strategy Game Pick from Ends of array Dynamic Programming
I came here looking for the source code because you linked to it in the vid, and I believe you haven't actually written an example. I looked under dynamic...
Solution given in the python file seems incorrect. Here is the correct sulution
def coin_changing_num_ways(coins, total):
cols = total + 1 # 1 for value 0 in total
rows = len(coins)
T = [[1 if col == 0 else 0 for col in range(cols)] for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if j >= coins[i]:
T[i][j] = T[i - 1][j] + T[i][j - coins[i]]
else:
T[i][j] = T[i - 1][j]
return T[rows - 1][cols - 1]
total = 5
coins = [1,2,3]
ways = coin_changing_num_ways(coins, total)
print(ways)
fix...
private static int setHeight(Node root) {
if (root == null) {
return 0;
}
return Math.max((root.getLeft() != null ? 1+root.getLeft().getHeight() : 0), (root.getRight() != null ? 1+root.getRight().getHeight() : 0));
}
private static int getHeight(Node root) {
if (root == null) {
return -1;
} else {
return root.getHeight();
}
}
Typo in
https://github.com/mission-peace/interview/wiki/Graph
BSF and DFS graph traversal - GraphTraversal.java
BSF -- Found when I tried to search for BFS! ๐
At first, I would like to thank you for this project, it helped me a lot.
And I'd like to know if it would be helpful if I contribute to some algorithm implementations in Python Language.
Thank you
Ahmed Henteti
I went through the solution given by you. it seems the solution is to search the minimum number in the circular array. Could you please explain the relation of the question with the solution?
Test case
@Test
public void testDeleteLongerWordOnly() {
final Trie trie = new Trie();
trie.insert("Craploader");
trie.insert("Crap");
trie.delete("Craploader");
assertFalse(trie.search("Craploader"));
assertTrue(trie.search("Crap")); // Fails here
}
Solution
Add checking for leaf node in line 143 of Trie.java
So instead of
return current.children.size() == 0;
Do
return !current.endOfWord && current.children.isEmpty();
In the Wiki, the largest increasing subsequence run time is given as O(Logn). It should be O(nLogn).
Hi (:
I think, I found a problem in your matrix multiplication implementation using dynamic programing:
https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MatrixMultiplicationCost.java
On the very first iteration, the field temp[0][1]
get's set to 1000000
, but it never get's updated, as the next for loop checks for k=i+1
(which is 1
) to be smaller than j
, which is 1
too.
The guys at geeksforgeeks.org have a pretty decent version of the problem on their site, maybee you could have a look there and fix your code accordingly (your Youtube explanation is great though!)
When one of the input lists is of length 1 the code is not returning the correct value
First of all, what you are doing with this project is really amazing, and making all this code open-source is really kind of you. Now, as far as I have understood, you have used only Java to implement your algorithms, but it would be nice to provide implementations also for other programming languages, in case someone didn't know Java. I was thinking I could contribute with some Python implementations, but since I have not so much time, I would be a little bit slow doing it alone. I hope you like this idea, and that someone could start contributing to it.
I think Readme.md file should be modified and improved so that any new contributor or user can understand the process of installation and know what he should do.
Hi,
You have done a wonderful job in the implementation. However, when I try to insert a large String (I can provide the test string) It throws the following exception. It never completed inserting the full string.
Exception in thread "main" java.lang.NullPointerException
at SuffixTree.nextChar(SuffixTree.java:426)
at SuffixTree.startPhase(SuffixTree.java:322)
at SuffixTree.build(SuffixTree.java:143)
at SuffixTree.main(SuffixTree.java:101)
The string I was trying to insert was 63027 in length. However, another large string with a length of 63067 inserted without any errors (I can provide this test string as well).
However, the second large string failed at your validation function;
Failed at 58 for index 56
Failed validation
false
I was trying to debug it but couldn't track it down. Wanted to bring it to your attention. Thanks.
Hi,
I was going through the implementation of the BinaryTree in tree source repository. I could not see how this logic(below) make this as Binary Tree?
if(head.data < data){
head = head.right;
}else{
head = head.left;
}
Isn't this logic is related to BST?
Thanks
Nitin
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.