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

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

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 order. Distance can be upwards or downwards. Example start node = 18, k = 2 , then output = 2, 19, 25 [Read More]
Binary Tree  BT  kodeknight  K-Distance  distance 

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

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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 example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree. [Read More]
Binary Tree  BT  K-Distance  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

cant the solution be simply distance of n1 and n2 …

Rohit Yadav - Feb 0, 2016

cant the solution be simply distance of n1 and n2 from lca.
dist(n1,n2)= dist(lca,n1)+dist(lca,n2)? correct me if i am wrong.

You are absolutely correct. What is being done in the above solution is, dist(n1,n2) = dist(root,n1) + dist(root,n2) - 2*dist(root,lca) as root is point of reference. Thanks.

Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

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) = 3 Dist(2,-4) = 1 Solution The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2\*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree. [Read More]
Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

 Posted on July 29, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Example Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1 Solution Method 1 (Simple but Inefficient) [Read More]
Algorithms  kodeknight  sorting  array  distance 

Shortest distances between two words in a file

 Posted on July 23, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution? OR Find the minimum distance between 2 numbers in the array? Example File contains: as was is the as the yahoo you me was the and [Read More]
kodeknight  hard  distance  CrackingTheCodingInterview  min 

Minimum Distance Between Two Elements in an Array

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Question Given an unsorted array and two elements, find the minimum distance between the elements in the array. The array may have duplicates. Example For example, if the Input array is (2, 1, 3, 4, 0, 2, 5) and the two elements are 4 and 5, then the min distance is 3 because 4 is at index 3 and 5 is at index 6. Solution Method 1 - Brute force [Read More]
kodeknight  array  distance  min 

Hirschberg’s linear space algorithm in C++

 Posted on August 4, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

It should work on any container type which supports forward and reverse iteration. It’s similar to the Python implementation, but note: rather than copy slices of the original sequences, it passes around iterators and reverse iterators into these sequences rather than recursively accumulating sums of sub-LCS results, it ticks off items in a members array, xs_in_lcs /\* C++ implementation of "A linear space algorithm for computing maximal common subsequences" D. [Read More]
Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring  distance  programCPP  programs 

Hirschberg's algorithm

 Posted on August 4, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Hirschberg’s algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string to the other. Hirschberg’s algorithm is simply described as a divide and conquer version of the Needleman-Wunsch algorithm. The Needleman-Wunsch algorithm finds an optimal alignment in O(nm) time, using O(nm) space. [Read More]
StringAlgo  Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring  distance