Let's create a SnakeNLadder.java class. Define constant WINPOINT with value 100. Each player has to start the journey from 0, roll the dice and try to reach WINPOINT.
Showing posts with label #Algorithms. Show all posts
Showing posts with label #Algorithms. Show all posts
January 07, 2020
Missing Number
You have a list of n-1 integers, and these integers are in the range of 1 to n. One of the integers is missing in the list, write a function which will return that missing number. We can assume there are no duplicates in the list.
Example:
Input: arr[] = {1, 2, 4, 5, 3, 7, 8}
Output: 6
November 24, 2019
#Algorithms Part 3: Shortest Path Algorithms(Bellman-Ford Algorithm)
Bellman-Ford Algorithm
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
- As we have seen in above example that Dijkstra Algorithm not always find the shortest path in case of negative edges. Bellman-Ford always give correct result even in case of negative edges (though it has its own drawback).
- As Dijkstra says relax the vertices's only once, Bellman-Ford says we can relax vertices's for n number of times, so that we can get perfect shortest path to all the vertices's.
- In Bellman-Ford we make list of all the edges and go one relaxing them for v-1 times (where v is the number of vertices) after which we will surely get the shortest path to all the edges even in case of negative edges.
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
-K Himaanshu Shuklaa..
#Algorithms Part 1: Graphs, BFS,DFS, Dijkstra Algorithm, Bellman-Ford Algorithm
Graph Traversal
- Its the process of visiting and exploring a graph for processing.
- In this we visit and explore each vertex and edge in a graph such that all the vertices's are explored exactly once.
- Visiting a node means selecting a node, where as exploring means exploring the children nodes of the node which we have visited.
- Its an algorithm for traversing trees and graphs.
- In BFS we start with the root node, explores all sibling nodes before moving on to the next level of siblings.
- Queue is the main data structure which is used while performing BFS.
- BFS is used as a crawlers in web-engines. It is the main algorithm which is used for indexing the web pages, it starts from the source page and follows all the links associated with that page. In this case each link is considered as a node in the graph.
- BFS is also used in GPS navigation to find the neighboring locations.
- BFS is also used in finding the shortest path
#Algorithms Part 4: Caching Algorithms in Java (LRU and LFU)
What is Cache?
- As its expensive to every-time fetch data from the main storage, we story it in temporary location from where it can be retrieved faster. This temporary location is called Cache.
- A Cache is made of pool of entries and these entries are a copy of real data which are in storage and it is tagged with a tag (key identifier) value for retrieval.
- When an application receives a request to get a particular information, it is first checked in cache. If an entry is found with a tag matching with the request, it will be returned. Else it will be fetched from the main storage, kept in Cache and then returned to the client.
July 28, 2019
How to check if a Tree is subtree of another Tree?
To check if the given tree is subtree of another tree, first we need to undertand if the how can we check if the tree's are identical or not.
Please visit: Check if two Binary Trees are Identical or not?
To verify if a tree is subtree of another, we need to traverse the Tree T in a preorder fashion.For every visited node in the traversal, see if the subtree rooted with this node is identical to another tree S.
Please visit: Check if two Binary Trees are Identical or not?
To verify if a tree is subtree of another, we need to traverse the Tree T in a preorder fashion.For every visited node in the traversal, see if the subtree rooted with this node is identical to another tree S.
How to check of two Binary Trees are Identical?
Two Binary trees are identical when they have same data and structure/arrangement of data is also same. To find if they are identical or not, we need to traverse both the trees simultaneously, and in each iteration we will compare the data of current node and the children of both the trees.
Factorial using recursion in Java
Bottom View of a Binary Tree
Recently I had given interview in Morgan Stanley for Senior Java Developer profile, the intervier asked me, we have a balanced Binary Tree, am trying to throw a light from a particular node, which all nodes will be visible?
I tried my best, but failed to write an algorithm. After the interview I realized he was asking to write an algorithm to see the bottom view of a Binary Tree.
The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.
If we see the tree from bottom from a particular node, which all nodes will be visible is the bottom view of a Binary Tree.
The bottom view of above Binary Tree is: 7, 5, 8, 6
I tried my best, but failed to write an algorithm. After the interview I realized he was asking to write an algorithm to see the bottom view of a Binary Tree.
The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.
If we see the tree from bottom from a particular node, which all nodes will be visible is the bottom view of a Binary Tree.
July 27, 2019
Vertical Order Traversal of a Binary Tree
Let's say we have below Binary Tree
In vertical traversal, we print nodes of a binary tree in vertical order by assuming that the left and right child of a node makes 45 degree angle with the parent.
We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on the same vertical line.
We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on the same vertical line.
Level Order Traversal of a Binary Tree
Let's say we have below Binary Tree
We need to print nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on. All nodes for any level should be printed from left to right.
We need to print nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on. All nodes for any level should be printed from left to right.
July 16, 2019
System Design Interview: Consistent Hashing
What is Hashing?
Hashing is the process of mapping one piece of data to another piece of data of fixed size. A function is usually used for mapping objects to hash code (which is typically an integer) known as a hash function.
Let's say we have fixed buckets numbered from 0-N. We have X number of balls (which is typically greater than or equal to N), and now we want to distribute these balls in the different buckets.
Hashing is the process of mapping one piece of data to another piece of data of fixed size. A function is usually used for mapping objects to hash code (which is typically an integer) known as a hash function.
Let's say we have fixed buckets numbered from 0-N. We have X number of balls (which is typically greater than or equal to N), and now we want to distribute these balls in the different buckets.
July 27, 2018
#Algorithm: Find first non-repeating character from a String
Write a method to find the first non-repeating character from a String?
GIT URL: Java Solution to find the first non-repeating character from a String
Solution 1: Using LinkedHashMap.
1). Create a LinkedHashMap, which will maintain the count.
2). Convert the input string into a char array, start iterating it and add each character in LinkedHashMap. If the character is already present in LinkedHashMap, increment the count.
3). Loop through LinkedHashMap and find the character with the count as 1.
#Algorithm: Generate Fibonacci In Java
Generate the Fibonacci recursively and iteratively in Java
In fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. The first two numbers of fibonacci series are 0 and 1.
There are two ways to generate the fibonacci series: With iteration and with recursion.
In fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. The first two numbers of fibonacci series are 0 and 1.
There are two ways to generate the fibonacci series: With iteration and with recursion.
July 19, 2018
#Algorithm: Detect duplicate elements in Array
How to detect duplicate elements in Array in Java?
1). Brute Force: In this approach we will compare each element of Array to all other elements and returns true if it founds duplicates. FYI, this is not an efficient choice.
2). Using HashSet: If you just need to find if whther the array has duplicates of not, convert that array into Set. Since Set doesn’t allow duplicates, the size of the corresponding Set will be smaller than the original Array if Array contains duplicates otherwise the size of both Array and Set will be the same.
#Algorithm: Implement Stack using two Queues
How can we implement Stack using two Queues?
We are given a queue data structure, and we need to implement Stack using it.
Solution 1:
Queue has FIFO, but Stack is FILO. We will use two queues q1 and q2. We can make sure that newly entered element is always at the front of q1, so that pop operation just dequeues from q1. q2 is used to put every new element at front of q1.
We are given a queue data structure, and we need to implement Stack using it.
Solution 1:
Queue has FIFO, but Stack is FILO. We will use two queues q1 and q2. We can make sure that newly entered element is always at the front of q1, so that pop operation just dequeues from q1. q2 is used to put every new element at front of q1.
July 18, 2017
Part 3: LinkedList Related Algorithm Interview Questions(Union and Intersection)
Create a Union and Intersection of two Linked Lists.
Solution 1: Using Merge Sort.
In this approach you need to sort both the lists,this will take O(mLogm) and O(nLogn) time.
Now we will iterate both the sorted lists to get the union and intersection, it will take O(m + n) time
Time complexity of this method is O(mLogm + nLogn).
Solution 2:Use Hashing
We can use HashTable to find the Union and Intersection of two Linked Lists. Here we are assuming that there are no duplicates in each list. Time Complexity would be O(m+n).
For Union:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the givens lists one by one. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.
For Intersection:
1). Create the result list, initialize it with NULL and create an empty hash table.
2). Start traversing the first list, and insert each element in the hash table.
3). Now traverse the second list. During iteration, look the element in the hash table. If the element is not present, then insert the element to the result list and in the hash table as well. Else if the element is present, then ignore it.
Write a function to get the intersection point of two Linked Lists.
Solution 1: Nested Loop
1). We will use 2 nested loops. In the outer loop will be for each node of the 1st list and inner loop will be for 2nd list.
2). In the inner loop, we will check if any of nodes of the 2nd list is same as the current node of the first linked list.
The time complexity of this approach will be O(M * N), where m and n are the numbers of nodes in two lists.
Solution 2: Node count difference.
1). We will get the count of the nodes in the both the lists, lets say c1 and c2 are the number of nodes on 1st and 2nd list.
2). Now we will get the difference of node counts, d = abs(c1 – c2).
3). We will start traversing the bigger list from the first node till dth node. From here onwards both the lists have equal no of nodes.
4). Now we can traverse both the lists in parallel till we come across a common node.
-K Himaanshu Shuklaa..
Part 2: LinkedList Related Algorithm Interview Questions(Reverse)
How to reverse a linked list using recursion and iteration?
In the iteration approach we reverse linked list using 3 pointers in O(n) time, This is done by creating a new list by reversing direction, and subsequently inserting the element at the start of the list.
We can also reverse a singly linked list by using recursion. We will traverse the linked list until we find the tail, this tail would be the new head for reversed linked list.
-K Himaanshu Shuklaa..
In the iteration approach we reverse linked list using 3 pointers in O(n) time, This is done by creating a new list by reversing direction, and subsequently inserting the element at the start of the list.
We can also reverse a singly linked list by using recursion. We will traverse the linked list until we find the tail, this tail would be the new head for reversed linked list.
-K Himaanshu Shuklaa..
Part 1: LinkedList Related Algorithm Interview Questions(find kth element from end, check if list has loop)
How to find middle element of linked list in one pass?
LinkedList data structure contains a collection of the node and has head and tail. To find the middle element in one pass we can use two-pointer approach.
LinkedList data structure contains a collection of the node and has head and tail. To find the middle element in one pass we can use two-pointer approach.
July 14, 2017
System Design Interview: How to implement TinyURL?
TinyURL shortens the long URL. URL shortening will have below benefits:
- Save space when displayed, printed or messaged.
- Consume less space when tweeted.
- Users are less likely to mistype the shorter URL's.
Why that's the wrong answer? because the person who is taking the interview us not looking for a simple solution where you take a longer url and convert it into a shorter one, store it in a map and returning the long url from the map whenever required.
The interviewer is interested ti test your knowledge on durability and scalability. The above diagram is correct, but sadly its neither durable nor scalable.
Subscribe to:
Posts (Atom)