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