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

Count Possible Decodings of a given Digit Sequence

Find number of ways a string can be decoded into, if A=1, B=2, C=3 ... Z=25 and encoding number is 123 ways decoding can be done is
1 2 3 = A B C
1 23  = A X
12 3  = L C

Find the element that appears once others appears thrice

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once.
Expected time complexity is O(n) and O(1) extra space.
Examples:
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

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

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".

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 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.

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.

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

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)

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered. ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Write a function flatten() which flattens this link list with each node down sorted link list to a single link list with all the elements in sorted order

Write a function flatten() which flattens this link list with each node down sorted link list to a single link list with all the elements in sorted order.

We have given Two methods in O(n^2) here.
for different linked list.

Length of the longest substring without repeating characters

Length of the longest substring without repeating characters

Method 1 (Brute Force Method)
We can consider all substrings.
One by one and check for each substring whether it contains all unique characters or not. 
There will be n*(n+1)/2 substrings.