algorithm Archives - Coddicted

Water and Jug Problem

Title: Water and Jug Problem Source: leetcode.com You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs. If z liters of water is measurable, you must have z ...

Power of Three

Title: Power of Three Source: leetcode.com Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion? Java solution Java /*https://leetcode.com/problems/power-of-three/*/ public class PowerOfThree { public boolean isPowerOfThree(int n) { if(n==0) return false; while(n!=1) { //System.out.println(n); int remainder = ...

Delete Node in a Linked List

Title: Delete Node in a Linked List Source: leetcode.com Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Suppose the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list ...

Decode Ways 2

Title: Decode Ways Source: leetcode.com A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 1234 'A' -> 1'B' -> 2...'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, ...

Verify Preorder Serialization of a Binary Tree 1

Title: Verify Preorder Serialization of a Binary Tree Source: leetcode.com One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #. _9_ / \ 3 2 / \ ...

Implement Reverse DNS Look Up Cache

Title: How to Implement Reverse DNS Look Up Cache? Source: www.geeksforgeeks.org Reverse DNS look up is using an internet IP address to find a domain name. For example, if you type 74.125.200.106 in browser, it automatically redirects to google.in. How to implement Reverse DNS Look Up cache? Following are the operations needed from cache. 1) ...

Knapsack Problem 1

Title: Dynamic Programming | 0-1 Knapsack Problem Source: www.geeksforgeeks.org Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also ...

Remove duplicates from an unsorted linked list

Title: Remove duplicates from an unsorted linked list Source: www.geeksforgeeks.org Write a removeDuplicates() function which takes a list and deletes any duplicate nodes from the list. The list is not sorted. For example if the linked list is 12->11->12->21->41->43->21 then removeDuplicates() should convert the list to 12->11->21->41->43. METHOD 1 (Using two loops) This is the ...

Invert Binary Tree

Title: Invert Binary Tree Source: leetcode.com Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 12345      4   /   \  2     7 / \   / \1   3 6   9 to 4 / \ 7 2 / \ / \ 9 6 3 1 12345      4   /   \  7     ...

Count number of ways to cover a distance

Title: Count number of ways to cover a distance Source: www.geeksforgeeks.org Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps. Java solution Java /* http://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/ */ class CountWaysToCoverDistance { public int count(int dist) { if(dist==0) return 1; if(dist < 0) return 0; return count(dist-1) + ...