Software Development Engineer in Test | TutorialHorizon

Sorted Array to Binary Search Tree of Minimal Height

August 31, 2019September 27, 2014 by Sumit Jain

Objective: Given a sorted array with unique elements, Create a binary search tree with minimal height.

Why minimal height is important :

We can do the linear scan to the array and make the first element as root and insert all other elements into the tree but in that case tree will be skewed , which means all the nodes of the tree will be on the one side of the root so the height of the tree will be equal to the number of elements in the array. So here our objective is to keep the tree balanced as much as possible.

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one. To read more about balanced tree, click here

Input: A one dimensional array

Output: Binary Search Tree of Minimal Height

Example:

Delete a Node in the Middle of a linked list, Given only access to that Node

May 21, 2020September 12, 2014 by Sumit Jain

Objective: Write a program to Delete a Node in the Middle of a linked list, Given only access to that Node

Example:

Original List : ->1->2->8->3->7->0->4
After Deleting the mid node (say 7) : ->1->2->8->3->0->4

Input: A Linked List and access to the node which needs to be deleted

Output: Linked list with deleted node

Approach:

Approach is tricky and simple
Copy the value of next node to the node which you want to delete
Delete the next node

Find the n’th Node from the end of a given Linked List

May 21, 2020September 12, 2014 by Sumit Jain

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach:

Check if one string is Rotation of another string

August 14, 2020September 9, 2014 by Sumit Jain

Objective: Write an algorithm to check if one string is Rotation of another string. This question has been asked in the Amazon interview.

Example:

Input Strings : 'sumitjain' and 'tjainsumi'
Output : true

Input String : 'Jaain' and 'ainJ'
Output: false

Input: Two Strings

Output: True or false based on whether strings are rotation of each other.

Approach:

Reverse a Linked List

May 21, 2020August 28, 2014 by Sumit Jain

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Print All Elements of Two Dimensional Array in Spiral

May 21, 2020August 4, 2014 by Sumit Jain

Objective: This question was asked in Amazon interview for the Software development Engineer position, Write an algorithm to print all the elements of two dimensional array in spiral.
Example :

Input: Two dimensional array

Output: All array elements printed in spiral.

Approach:

Find a pair of numbers from an array whose sum equals k

May 21, 2020August 4, 2014 by Sumit Jain

Objective: Write an algorithm to find out whether in a given array there exists or not two numbers whose sum is exactly equals to a given number. This problem has been asked in Amazon and Microsoft interviews.

Input: An array arrA[], A number k

Output: True or false based upon we have found any two numbers in array arrA[] whose sum is equal to k

Approach:

Method 1: Using Binary Search

Find Whether Given String is palindrome or Not.

May 21, 2020July 20, 2014 by Sumit Jain

Objective : Write an algorithm to find Whether Given String is palindrome or Not.

Input: A String,

Output: true or false on whether string is palindrome or not

Approach:

Use recursive approach
Compare first and last characters if they are not same- return false
If they are same make, remove the first and last characters and make a recursive call.

Example:

Jain niaJ => compare ‘J’ with ‘J’ =>returns true

ain nia => compare ‘a’ with ‘a’ =>returns true

in ni => compare ‘i’ with ‘i’ =>returns true

n n => compare ‘n’ with ‘n’ =>returns true

string length <2 => returns true

Find two Missing Numbers in a Sequence of Consecutive Numbers

May 21, 2020July 20, 2014 by Sumit Jain

Objective : Write an algorithm to find two Missing Numbers in a Sequence of Consecutive Numbers

Input: Array, arrA[] with two missing numbers and Range

Output : Two missing numbers

Approach:

- Approach is very simple, Add all the given numbers say S
- Calculate sum of N numbers by formula n(n+1)/2 , say N
- Find sum of two missing numbers a+b = N-S