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

Find the maximum distance covered using n bikes

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. Hence, the maximum distance travelled will be 100km. Better Solution: Move all the bikes 50km, so that each bike has half tank empty. Now pour the fuel of...

Read More