mission-peace / interview

Interview questions

Please visit my wiki link for full list of questions

https://github.com/mission-peace/interview/wiki

Like my facebook page for latest updates on my youtube channel

https://www.facebook.com/tusharroy25

Contribution

Please contribute to this repository to help it make better. Any change like new question, code improvement, doc improvement etc. is very welcome. Just send me a pull request and I will review the request and approve it if it looks good.

How to use this repository

Softwares to install

* Install JDK8 https://docs.oracle.com/javase/8/docs/technotes/guides/install/install_overview.html * Install Git https://git-scm.com/book/en/v2/Getting-Started-Installing-Git * Install either Intellij https://www.jetbrains.com/idea/download/ * If you like eclipse instead of intellij install eclipse https://eclipse.org/downloads/

Set up your desktop

* Pull the git repository. Go to command line and type git clone https://github.com/mission-peace/interview.git * Go to root directory of checked out project. * Run ./gradlew idea to generate idea related classes * Fire up intellij. Go to Open. Go to git repo folder and open interview.ipr . On file menu go to project structure. Update language level support to 8 * If you use eclipse, do ./gradlew eclipse . This will generate eclipse related files. Go to eclipse and open up folder containing this repo. * Go to any program and run that program * Go to any test and run the junit test. * Run ./gradlew build to create classes, run tests and create jar.

interview's Issues

Adding source code for other programming languages?

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.

Trie.java is deleting all shorter leaves

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();

BinaryTree Implementation

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

Coin change solution fails simple test cases

Contribution to some algorithm implementations in Python Language

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

Does MinCostPath need to look at diagonal value as well?

Your code for next power of 2 will not work for numbers not power of 2 themselves

interview/src/com/interview/tree/SegmentTreeMinimumRangeQuery.java

Line 42 in 259077b

int nextPowOfTwo = np2.nextPowerOf2(input.length);

Optimal Strategy Game Pick from Ends of array Dynamic Programming

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...

Graph Traversal has an issue

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

Adding more comments to improve readability and understanding of the code

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.

CheckIfArrayElementsAreConsecutive.java

This answer will fail if the array has negative integers.

https://github.com/mission-peace/interview/blob/master/src/com/interview/array/CheckIfArrayElementsAreConsecutive.java#L19

int input[] = {-1,-2,-3,-4};

path code

could you post the code for determining the path?

output incorrect for rod cutting problem.

output for this {2,5,7,8} price array is 10 instead of 12, why so?
len of rod is 5.

Given a circle with N defined points and a point M outside the circle, find the closest point.

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?

QUESTION: Any specific reason for not using a parmeterized constructor.

interview/src/com/interview/tree/BinaryTree.java

Line 31 in aa7e650

public static Node newNode(int data){

Any specific reason for not using a parmeterized constructor and using a static function instead for new node creation.

Thanks.

RegexMatching.java fails on such case

//expect false

System.out.println(rm.matchRegex("aba".toCharArray(), "c*a.*".toCharArray()));

KthLargestInTwoSortedArray

I think the code gives output as kth "smallest" element in two sorted array instead of giving the kth "largest" element.

AVLTree isn't working as expected

Just try insert in the order 1, 3, 2 and notice that tree isn't balancing itself

Exception when trying to insert a large String

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.

Group Elements In Size M such that the group doesn't contain same integers giving incorrect results

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

Add an organized folder for C++ code as well.

A lot of programmers prefer to code interview questions in C++. Please add a C++ folder so that we can contribute.

N-Queens Problem: Status: Time Limit Exceeded on LeetCode

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.

MinOperation Segment Tree

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!!!!!

Complexity Analysis

https://github.com/mission-peace/interview/blob/master/src/com/interview/string/RemoveConsecutiveDuplicate.java

Could ylu help analyze what is the time complexity and storage complexity?

AnagramOfFirstAsSubstring - Doesn't satisfy all conditions.

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).

DuplicateNumberDetection

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.

Bug in if-condition

interview/src/com/interview/dynamic/BreakMultipleWordsWithNoSpaceIntoSpace.java

Line 95 in 259077b

while(i < j){

It seems this condition should be 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.

Problem in DynamicPrograming - MatrixMultiplicationCost

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!)

Trie.java delete method is deleting all shorter leaves

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();

Keep an Index for the High Level Approches

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.

Why not return all the possible Strings in word break problem

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.

KMP.cpp

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 */
}

MedianOfTwoSortedArrayOfDifferentLength with lists of length 1

When one of the input lists is of length 1 the code is not returning the correct value

AVLTree

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();
    }
}

Compatibility issue with Graph and BellmanFordShortestPath

Problem

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);

Solution

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);
}

Size is not required & not used anywhere in the class.

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

Largest increasing sub sequence

In the Wiki, the largest increasing subsequence run time is given as O(Logn). It should be O(nLogn).

Simplification

interview/src/com/interview/graph/CycleInDirectedGraph.java

Line 11 in 259077b

public boolean hasCycle(Graph<Integer> graph) {

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.

Doubt it CircularBinarySearch

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

The class BellmanFordShortestPath is not detecting negative cycles

The class BellmanFordShortestPath is not detecting negative cycles

Trie.java delete does not correctly work

Try to add two words like "ciao" and "ciaone" and delete "ciaone"
The Tries will be empty

Video / code request

kD-trees and similar computational geometry data structures.

Your videos are great!

Incorrect input for median of two sorted arrays

the input variable y does not contain sorted arrray

Improve Readme.md

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.

Unit Tests for improved test coverage

I would like know if it will be helpful if I contribute some unit tests.

Thank you
Farid

issue with existing prog

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

Typo https://github.com/mission-peace/interview/wiki/Graph

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! 😄

Suffix tree: validation fails

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

Coin changing - find the number of ways

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)

Matrix multiplication default value is incorrect for cases where the value exceeds 1000000

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