Google Interview

Colorful Numbers

by

Objective: Given a number, find out whether its colorful or not. Colorful Number: When in a given number, product of every digit of a sub-sequence are different. That number is called Colorful Number. See Example Example: Given Number : 3245 Output : Colorful Number 3245 can be broken into parts like 3 2 4 5 … Read more Colorful Numbers

Print All the Subsets of a Given Set (Power Set)

by

Objective: Given a set of numbers, print all the posssible subsets of it including empty set. Power Set: In mathematics, PowerSet of any given set S, PS(S) is set of all subsets of S including empty set. Example: S ={1,2,3} PS(S): {{ᵩ}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Approach: … Read more Print All the Subsets of a Given Set (Power Set)

Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

by

Objec­tive: – Given “n”, generate all valid parenthesis strings of length “2n”.
Example:

Given n=2

Output:
(())
()()

Approach:

Read morePrint All Possible Valid Combinations Of Parenthesis of Given ‘N’

Implement Queue Using Stacks

by

Objective: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objective is to implement queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used a back of the Queue and stack2 will be used as front of the Queue. Push() operation will be done on … Read more Implement Queue Using Stacks

Merge Sort in a Linked list

by

Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … Read more Merge Sort in a Linked list

Construct a binary tree from given Inorder and Level Order Traversal

by

Objective: – Given a inorder and level order traversal, construct a binary tree from that. Input: Inorder and level order traversal Approach: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 }; First element in the levelorder [] will be the … Read more Construct a binary tree from given Inorder and Level Order Traversal

Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

by

Objective: – Given a preorder traversal, construct BST from that, without using recursion. Input: Preorder traversal Similar Problem : This problem is similar to the Construct Binary Search Tree from a given Preorder Traversal using Recursion. Approach: Example: int[] preOrder = { 20, 10, 5, 1, 7, 15, 30, 25, 35, 32, 40 }; Use … Read more Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

Construct Binary Search Tree from a given Preorder Traversal using Recursion

by

Objective: – Given a preorder traversal, construct BST from that. Input: Preorder traversal Similar Problem : This problem is similar to the – Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion) Approach: Solution to the problem is similar to isBST Max-Min Solution. “Your root value can have any value between … Read more Construct Binary Search Tree from a given Preorder Traversal using Recursion

Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

by

Objective: Given an array arrA[], find the maximum j – i such that arr[j] > arr[i]. Example: int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 }; Output: Max(j-i) where j>i and A[j]>A[i] is : 7 Approach: Create 2 Auxilary Arrays say Lmin[] and Rmax[] of the same size as … Read more Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

by

Objective: Given an array of size of N and number k. Find all elements in an Array which appears more than N/K times.

Input: Array [] and number k.

Example: 

int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 };

K = 4

N/k = 14/4 = 3

Output will be [3,4] they appear 5, 4 times respectively.

Approach:

Read moreFind All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Print All The Nodes Which are X distance from the Given Node

by

Objective: – Given Binary Tree, Print All The Nodes Which are X distance from the Given Node.

Example :

Approach:

Quite Tricky solution, i will explain using the example given in the picture.

Read morePrint All The Nodes Which are X distance from the Given Node

Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree).

by

Objective: – Find the Lowest Common Ancestor of two given nodes in a Binary Tree

What is Lowest Common Ancestor

In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.

Similar Problem: Lowest Common Ancestor in a Binary Search Tree.

Example:

Lowest Common Ancestor Example

Input: A binary Tree and two nodes n1 and n2.

Appraoch:

Read moreLowest Common Ancestor in a Binary Tree (Not Binary Search Tree).

Lowest Common Ancestor in a Binary Search Tree.

by

Objective: – Find the Lowest Common Ancestor of two given nodes in a Binary Search Tree

What is Lowest Common Ancestor

In a given binary tree, The lowest common ancestor of two nodes n1 and n2 will be a node X such that node X will be the lowest node who has n1 and n2 as its descendants.

Similar Problem: Lowest Common Ancestor in a Binary Tree ( Not Binary Search Tree).

Example:

Lowest-Common-Ancestor-BST
Lowest-Common-Ancestor-BST

Input: A binary Search Tree and two nodes n1 and n2.

Appraoch:

Read moreLowest Common Ancestor in a Binary Search Tree.

Make a Binary Tree from Given Inorder and Preorder Traveral.

by

Objective: – Given a inorder and preorder traversal, construct a binary tree from that.

Input: Inorder and preorder traversals

Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal

Approach:

int [] inOrder = {2,5,6,10,12,14,15};

int [] preOrder = {10,5,2,6,14,12,15};

    • First element in preorder[] will be the root of the tree, here its 10.
    • Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
    • See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

    Read moreMake a Binary Tree from Given Inorder and Preorder Traveral.