Find the smallest window in a string containing all characters of another string

Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.

For Example:

Input string1: “this is a test string”
Input string2: “tist”

Output string: “t stri”

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Given LinkedList and K=2, N=4

1->2->3->4->5->6->7->8->9

so Partitioned LinkedList will be

1->2->3->4->5->6->7->8->9

Now delete first K nodes from each subpart and return linked list

3->4->7->8

Here first 2 nodes are deleted from each subparts.

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

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.

Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance k from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

           [1]
          /   \
       [2]     [3]
      /  \     /  \
    [4]  [5] [6]  [7]
    /
  [8]

Here Output should be 1, and 2 for K=2 as both are at 2 distance from leaf nodes.
1 is at K=2 distance from 5 and  2 is K=2 distance from 8.

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.

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.

Find if two rectangles overlap

Given two rectangles, find if the given two rectangles overlap or not.

Note that a rectangle can be represented by two coordinates, top left and bottom right. So mainly we are given following four coordinates.

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.

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:

CodeChef Code SGARDEN

This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand.
Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.
Now the Sheriff asks the question: How many times has he whistled?

CodeChef' RRCOPY

Def: 
You had an array of integer numbers. You also had a beautiful operations called "Copy-Paste" which allowed you to copy any contiguous sub-sequence of your array and paste it in any position of your array. For example, if you have array [1, 2, 3, 4, 5] and copy it's sub-sequence from the second to the fourth element and paste it after the third one, then you will get [1, 2, 3, 2, 3, 4, 4, 5] array. You remember that you have done a finite(probably zero) number of such operations over your initial array and got an array A as a result. Unfortunately you don't remember the initial array itself, so you would like to know what could it be. You are interested by the smallest such array. So the task is to find the minimal size(length) of the array that A can be obtained from by using "Copy-Paste" operations.

Wrong Directions given find minimum Moves so that he can reach to the destination

A person wants to go from origin to a particular location, he can move in only 4 directions(i.e East, West, North, South) but his friend gave him a long route, help a person to find minimum Moves so that he can reach to the destination.
Input – NESNWES
Output – E

Find the kth number with prime factors 3, 5 and 7

Find the kth number with prime factors 3, 5 and 7

Design an algorithm such that we have to find the k th element in the array such that their only prime factors are 3,5 an 7.
Example: Array will contain 1,3,5,7,9,15,21,25,...
We have to return the kth element in array

Print vertical sum of all the axis in the given binary tree

Print Vertical Sum of all the axis in the given binary Tree.

Most of times in written test , you will encounter this very good question.

given a binary tree.

(most of times a complete binary tree with all leaf node at same height will be given)