Given a BST with 2 nodes swapped, fix it

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/recover-binary-search-tree-problem/. Problem Given a BST with 2 nodes swapped fix it. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8 and 20, and BST is changed. Input Tree: 10 / \ 5 8 / \ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree....

Read More

Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/given-a-binary-search-tree-with-2-nodes-swapped-find-number-of-pairs-not-following-bst-properties/. Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8...

Read More

For a Given node of a binary tree, print the K distance nodes.

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/all-nodes-distance-k-in-binary-tree/. Problem You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted...

Read More

Print all nodes that are at distance k from a leaf node

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/nodes-at-distance-k-from-leaf-nodes-in-binary-tree/. Problem Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For...

Read More

Find the distance between 2 nodes in Binary Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/distance-between-two-nodes-in-binary-tree/. Problem Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Example Dist(-4,3) = 2, Dist (-4,19) = 4 Dist(21,-4) =...

Read More

Program to count leaf nodes in a binary tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/count-number-of-leaf-nodes-in-binary-tree/. Problem Count leaf nodes in a binary tree Solution Method 1 - Recursive Here is the logic: If node is NULL then return 0. Else If left and right child nodes are NULL return 1. Else recursively calculate leaf count of the tree using below formula.Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree Here is the recursive solution: int...

Read More

Friend Circle - Hackerrank

Problem Reference - Hackerrank This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/number-of-provinces/. Problem There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends. You are given a N×N−matrix M which consists of characters Y...

Read More

Lazy Caterer's sequence

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/lazy-caterer-s-sequence/. Problem Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that. Solution The solution to this is very simple, if you know mathematics. :P Number of pieces p p = ( n^2+n+2)/2 p = C(n+1,2) + 1   More on wikipedia - http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence. Proof When...

Read More

Lego Blocks Problem

Problem statement - https://www.hackerrank.com/challenges/lego-blocks solution - http://stackoverflow.com/questions/15424945/lego-blocks-dynamic-programming http://stackoverflow.com/questions/913566/has-anyone-seen-a-programming-puzzle-similar-to-this Code - Thank...

Read More

K reverse a linked list with increasing K

Problem Reverse k elements in the linked list such that k goes on increasing Example Eg.        1 - 2 - 3 - 4 - 5 - 6 - 7 output - 1 - 3 - 2 - 6 - 5- 4 - 7 Solution You can take this problem here. Here we are just increasing k. public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) { ListNode<Integer> nextNode = headerNode.next; ListNode<Integer> startNode = null; ListNode<Integer> endNode = null; ...

Read More

Convert Binary Tree to Doubly linked list in level order

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below: The output will be a double linked list like this: Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list. For traversing the tree, we'll...

Read More

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

Problem Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position. Example Example 1 Input s1 = abcd s2 = bacd Output Ans = 1 Reason, just move b forward and we get it. Example 2 Input A = (a)b(cd)e(f)g(hij)B = ahdjcifbeg Output Ans =7 Explanation A = (a)b(cd)e(f)g(hij)B = ahdjcifbeg Characters b,e,g are in the order, rest characters have to brought first. Solution This is a DP problem,  LCS of the 2 strings is adf, and rest of the character are moved forward, and rest...

Read More

Maximize the number of magical gems by passing through array of house

Problem There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even. Example Gem array = 1 2 0 4 5 6 2 3 color array = 0 0 1 1 1 0 0 1 (r=1,b=0) o/p = 20 (4*5) Solution This is similar...

Read More

Find the least wastage in cutting the Trees?

Problem You are given n Trees with their heights in an array. and you are given a value k units , that much wood you need to collect. You can have an axe of any height you want but you can use only 1 axe when you choose. Assume height to be integral value. Solution So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k. It is always possible to choose an axe height such that chopping all trees above this height will...

Read More

Implement a function similar to diff command in linux

Problem Give logic for implementing "diff" command in Linux. Consider various test cases and explain what will happen in each. The two files are source code and are huge.. For e.g. File 1: 1-2-3-4 File 2: 1-3-4-2 Solution The operation of diff is based on solving the longest common sub-sequence problem. In this problem, you have two sequences of items: a b c d f g h j q z a b c d e f g i j k r x y z and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new...

Read More

Maximum single sell profit from stock

Problem Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit. OR Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. Example Input = {5        10         4        ...

Read More

Reverse the doubly linked list

Problem Reverse the doubly linked list Input 10 - 8 - 4 - 2 Output 2 - 4 - 8 - 12 Solution Method 1 - Reversing the prev and next references Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references  in all the nodes of the list and need to make head point to the last node of original list (which will be the first node in the reversed list). void reverseDLL(Node head) { while(head!=null) { // Swapping the prev & next pointer...

Read More

Doubly linked list ADT

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two  fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes previous and next  links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized...

Read More

Find the largest subarray with sum of 0 in the given array

Problem An array contains both positive and negative elements, find the largest subarray whose sum equals 0. Example int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2} int output = {4,  6,  3, -9, -5, 1} of length 6 Solution Method 1 - Brute force This is simple. Will write later (incomplete) Method 2 - Storing the sum upto ith element in temp array Given an int[] input array, you can create an int[] tmp array where   tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Example int[]...

Read More

Einsteen's 5 house riddle

Problem Einstein wrote this riddle early during the 19th century. He said 98% of the world could not solve it.  "There are 5 houses in 5 different colors. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage." The question is: Who owns the fish? Hints: The Brit lives in the red house. The Swede keeps dogs as pets. The Dane drinks tea. The...

Read More