Convert a Binary Tree to Linked List

Given a binary tree (or Binary Search Tree), convert it to a doubly-linked list. Can you do it inline?

Input:
                    60
           50             70
      40       55   65      75

Output:
      60 -> 50 -> 70 ->40 -> 55 -> 65 -> 75

Approach
The structure of a Binary Tree Node is similar to Linked List Node. Binary Tree node has left and right. A linked list has prev and next.
Do a Bread-First-Search (BFS) and adjust the pointers as the nodes are read.

Solution

First occurrence of a number in a sorted array

Given a sorted array of numbers where each number is repeated multiple times,  design an algorithm to find the first occurrence of a given number.
for e.g.
input array: {2,2,2,3,4,5,5,5,6,6,6,7,7,7,7,12,12,15,19}
number: 6
Here number 6 is found in position 8,9 and 10 (0-indexed). However, 8 is the first index.

Approach:- Using binary search locate the block of numbers containing the list of target number.
Once the list is found, apply binary search on the block again.

Solution

Implement Mobile T9 using TRIE

T9's objective is to make it easier to type text messages. It allows words to be entered by a single keypress for each letter. T9's objective is to make it easier to type text messages. It allows words to be entered by a single keypress for each letter.  For instance, in English, 4663 matches "good", "home", "gone", "hood", etc. 

This program takes in a dictionary file as input, reads it and creates a Ternary Search Trie (TST). Once the Trie is created, any word can be searched. The matching words for a given sequence are stored in ascending order (instead of word ranking). This code can be modified to accomplish word ranking and machine learning. 

The above code can be implemented with HashMap. However hashing does not provide efficient searching. 

For the purpose of benchmarking, I have enabled the runtime stats in this class. I have tested with 3 types of dictionaries. The biggest dictionary I could get hold off was containing 3.7 million words. The program currently accepts only alphabets. 

Solution

Unimodal array has an increasing sequence followed by decreasing sequence, find the number at which the transition happens

  Unimodal array contains a list of 'N' integers. There exists M < N, such that
  a[0] to a[M] are in increasing series
  a[M+1] to a[N] are in decreasing series
  The problem is to find a[M] in O(Log N)
  E.g. {2, 4, 8, 10, 13, 18, 12, 7, 5, 4}. Here M is 18 as the switch happens after it

 Solution

Pairs of numbers whose sum is "S"

In a given sorted array of integers, print the pairs of numbers which give a sum "S" in O(N) time.

The problem like this can be solved with 2 pointers.

Solution:-

Kth Largest using MaxHeap

Find the Kth largest element in an unsorted array of integers, using MaxHeap

Solution

Median of Medians to find Kth Smallest

Given an array of unsorted integers find the Kth smallest element using "Median of Medians".
This method is guaranteed to work in max linear time

Solution

Kth smallest element in an unsorted array

Given an array of unsorted numbers, find the Kth smallest element in the array.
Input:  10, 8, 5, 7, 14, 3
K = 4
Output: 8

Solution

Count occurrence of an element in a Sorted Array

Given an array of sorted elements, count the number of times a given element is repeated. The solution cannot be linear.

Solution:- Have given 2 solutions, both are modifications to binary search

Algorithm to find the least number of coins

This is a simplest puzzle asked in interviews. You are given coins of denominations 5 Rs, 2 Rs, 1 Re, 50 Paisa, 25 Paisa and 10 Paisa. For any given currency value (assume > 10 Rs), determine the change to be given in coins. While doing this ensure that the number of coins are minimum.

Solution: