Algo Archives - Page 15 of 22

Verify Preorder Serialization of a Binary Tree 4

Mar

12

2016

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

Mar

12

2016

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

Mar

12

2016

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

Mar

9

2016

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

Mar

9

2016

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

Mar

8

2016

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

Maximum Depth of Binary Tree

Mar

8

2016

Title: Maximum Depth of Binary Tree Source: leetcode.com Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Python solution Python ''' https://leetcode.com/problems/maximum-depth-of-binary-tree/ ''' # Definition for a binary tree node. # class TreeNode(object): # ...

Detect Cycle in a Directed Graph 1

Mar

6

2016

Title: Detect Cycle in a Directed Graph Source: www.geeksforgeeks.org Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must ...

Fancy Numbers

Mar

6

2016

Title: Check if a given number is Fancy Source: www.geeksforgeeks.org A fancy number is one which when rotated 180 degrees is the same. Given a number, find whether it is fancy or not. 180 degree rotations of 6, 9, 1, 0 and 8 are 9, 6, 1, 0 and 8 respectively Examples: Input: num = ...

Design a tiny URL or URL shortener 27

Mar

6

2016

Title: How to design a tiny URL or URL shortener? Source: www.geeksforgeeks.org How to design a system that takes big URLs like “http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/” and converts them into a short 6 character URL. It is given that URLs are stored in database and every URL has an associated integer id. One important thing to note is, ...