Reverse the doubly linked list

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

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). [Read More]
reverse  Doubly Linked List  DLL 

Doubly linked list ADT

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

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. [Read More]
kodeknight  Doubly Linked List  DLL 

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

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

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 [Read More]
sub-array  Dynamic Programming  DP  incomplete  array  sum 

Einsteen's 5 house riddle

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

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. [Read More]

Find the maximum distance covered using n bikes

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem There are n bikes and each can cover 100 km when fully fueled. What is the maximum amount of distance you can go using n bikes? You may assume that all bikes are similar and a bike takes 1 litre to cover 1 km. Solution There are couple of ways. Lets find the right solution. Say n = 50. Naive Solution: The most naive solution would be to just make all the bikes go together. [Read More]
kodeknight  Puzzles 

Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

 Posted on November 21, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a binary tree, find out if the tree can be folded or not. A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable. Examples Consider the below trees: (a) and (b) can be folded. (c) and (d) cannot be folded. (a) 10 / \\ 7 15 \\ / 9 11 (b) 10 / \\ 7 15 / \\ 9 11 (c) 10 / \\ 7 15 / / 5 11 (d) 10 / \\ 7 15 / \\ / 9 10 12 Solution Method 1 (Change Left subtree to its Mirror and compare it with Right subtree) [Read More]
Binary Tree  BT  kodeknight 

Given a node in binary tree - Check if left and right subtree are mirror of each other

 Posted on October 18, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples. Example 1 / \ 2 2 ```TRUE 1 / \ 2 2 \ 3 1 / \ 2 2 / \ / \ 4 3 3 4 1 / \ 2 2 / \ / \ [Read More]
Binary Tree  BT  kodeknight  Amazon 

Queue ADT

 Posted on October 17, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Definition :- A queue is a collection of same type of entities, which ensures that all entities in collection will have a sequential storage structure that permits access only at the two ends of the sequence. We refer to the ends of the sequence as the front and rear. The first element in queue have the position as front and value or pointer or front changes according to the solution of the given problem. [Read More]
queue  abstract-data-type  ADT 

Maximum number of chickens you cannot order

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

Problem There is a non vegetarian restaurant which sells chicken in orders of 6, 9 and 20. Calculate the maximum number of chicken pieces you cannot order from that restaurant ? Solution 43 If you analyze, then you will find that all the 6 numbers divisible by 3 can be ordered. Why? Because you can break them own as the sum of 6 and 9. Now after 26, all the numbers that are divisible by 3 if subtracted by 40 can be obtained. [Read More]
jabong  Puzzles