K’th Largest Element in BST when modification to BST is not allowed

Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

      [20]
      /  \     
    [8]  [22] 
    /  \
  [5]  [10]
       /  \
     [9]  [12]

For example, in the following BST, if
if k = 3, then output should be 12
if k = 5, then output should be 9.

Mirror of Tree

Write a code to construct a Mirror of Binary Tree as below.

Check if an array has duplicate numbers in O(n) time and O(1) space

We have array  a[ ]= {1, 2, 3, 4, 5, 6, 7, 8, 4, 10};
And we need to find a number which is duplicate in O(n) and Space complexity O(1)

Find two non repeating elements in an array of repeating elements

Given an array in which all numbers except two are repeated once.
(i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once).
Find those two numbers in the most efficient way.
example :
Arr = [1,2,3,1] => 2, 3 occurring once
Arr = [2, 3, 7, 9, 11, 2, 3, 11] => 7, 9 occurring once

Sort Stack in place

Question is to sort a Stack in place without using extra Stack or other Data Structure.

Answer :
Basic solution which comes in mind is to pop all element and sort and push into Stack again.
but as we don't have extra space or Data Structure to sort stack.
We need to use inplace sorting, and to do so we need to have all elements out of stack.
One way to do so is to use "Recursion" .
It will use internally memory stack to store recursion values. but we can implement without initializing extra stack or memory.

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Given a sorted array and a number x, find a pair in array whose sum is closest to x.

Examples:

Input: arr[] = {10, 22, 28, 29, 32, 40}, x = 54
Output: 22 and 32

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Example : 00001111
Output : 4

Method 1 : in O(n) we can do it . with sequential search.

Method 2 : Binary search.
Yes binary search is useful, as data is sorted.
Just we need to change its conditions for 0 and 1.
lets have a look at Function firstOccurance.

Common Ancestor in a Binary Tree or Binary Search Tree

Binary tree with structure as

struct node {
    int data;
    struct node *left;
    struct node *right;
};

need to find out common ancestor of two nodes.

Password Predictor

Danny has a possible list of passwords of Manny’s facebook account. All passwords length is odd. But Danny knows that Manny is a big fan of palindromes. So, his password and reverse of his password both should be in the list.
You have to print the length of Manny’s password and it’s middle character.
Note : The solution will be unique.

Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3 
Output:  3->2->1->6->5->4->8->7->NULL. 

Solution : Reverse a LinkedList keeping counter, to keep node count along with it.

Generate next palindrome number

Several Companies like MS, Amazon and Flipkart has started asking this question to generate next number which is palindrome.

Say K is given, Generate N such that N is palindrome and N > K.

Max Sum in circularly situated Values

This question was asked first in FACEBOOK On Campus for Internship.

There are N trees in a circle. Each tree has a fruit value associated with it.  

A bird can sit on a tree for 0.5 sec and then bird have to move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. 

We are given N and M (the number of seconds the bird has), and the fruit values of the trees. We have to maximize the total fruit value that the bird can gather. The bird can start from any tree.

Search element in a matrix with all rows and columns in sorted order

Given a matrix containing unique numbers in which all rows and columns are in sorted order.
And You have to search an element output its location row,column number .
If no such element the just print ”-1 -1”.

Example:

5  5                               //size of matrix
 -10   -5   -3    4     9     //matrix
-6     -2     0    5    10
-4     -1     1    6    12
  2      3     7    8    13
100  120 130 140 150

Implement LRU Cache

Generally Interviewer can ask you simply to implement LRU cache, first explain which data structure you will use and why.

Its well known coding question being asked by all Tech giants like Amazon , Flipkart, Microsoft. 

LRU (Least Recently Used) Cache holds Page numbers which are recently used and throws out old or least recently used page number or entries.

Given Set of words or A String find whether chain is possible from these words or not

You are given N strings or N words. You have to find whether a chain can be formed with all the strings given namely n ?

Chain : A chain can be formed between 2 strings if last character of the 1st string matches with the first character of the second string.

Example : cat ,eng, galactic, tree

These words Create chain as  ...  TREE,ENG,GALACTIC,CAT or CAT, TREE, ENG, GALACTIC

Try to think as its simple solution.

Memory Efficient LinkedList

Memory efficient linked list is also called XOR Linked List.
To use lesser memory in doubly link list, such data structure is used.

An ordinary doubly linked list stores addresses of the previous and next list items in each list node, requiring two address fields:

...  A       B         C         D         E  ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

An XOR linked list compresses the same information into one address field by storing the bitwise XOR (here denoted by ⊕) of the address for previous and the address for next in one field:

...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

Sort an array according to the order defined by another array

Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.

Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
       A2[] = {2, 1, 8, 3}
Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}

The code should handle all cases like number of elements in A2[] may be more or less compared to A1[]. A2[] may have some elements which may not be there in A1[] and vice versa is also possible.

Given Code in: O(m*count + n) Space complexity O(m)
where m=size of A1,n=size of A2 count= maximum occurrence of any element of A1.

Company Asked : Amazon

Connect n ropes with minimum cost

There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.

Get Minimum element in O(1) from input numbers

Question : Get Minimum element in O(1) from input numbers..

- With any traditional way we can't get minimum element in O(1)
- so we need to come up with different data structure.
- As its very old and famous question We are directly explaining logic

Find min element in Sorted Rotated Array (With Duplicates)

Problem: Find the minimum element in a sorted and rotated array if duplicates are allowed:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2}   output: 0
Algorithm: