Count number of ways to reach a given score in a game

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.

Examples:

Input: n = 20
Output: 4

Mirror of Tree

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

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”

Find if a binary tree is height balanced ?

A Height Balanced Tree is tree where for each node this condition is true.
- The difference between heights of left subtree and right subtree for any node is not more than 1.

So we can say that a tree T is Height Balanced when
- Left Sub Tree of T is height balanced
- Right Sub Tree of T is height balanced
and for each node this above condition is true :P

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)

Word Break Problem

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.

Consider the following dictionary 
{ i, like, go, hired, gohired, site, sweet,fruit, man, go, mango}

Input:  ilike
Output: Yes 
The string can be segmented as "i like".

Input:  ilikemango
Output: Yes
The string can be segmented as "i like mango" or "i like man go".

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

Amazon Interview Experience - SDE Chennai

Recently I have participated in Amazon SDE interview for Chennai location Kindle team.
Kindle team has arrived Bangalore location to take drive.
I have given 8 rounds
Questions- Answers are as below

R-1)  Written Test 1 :
Three codes were asked :
1) Find whether given LinkedList is Palindrome or not
2) Find Whether given Binary Tree is Binary Search Tree or not
Code : www.gohired.in/2014/07/check-binary-tree-is-binary-search-tree.html
3) Create Regular expression and String Matching program for ? and *, where. * means any null or character may appear instead *. and ? means one or more previous character may appear in string.
example
input :
AM*AZO?N*, AMAZON
AM*AZO?N*, ABAZOO
Both are matching as per rules of ? and *.

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.

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.

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.

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.

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.