Intermediate

Add two numbers represented by a linked list, Numbers are Stored in REVERSE order

by

We have similar post – Two numbers represented by a linked list, Number Stored in FORWARD order

Objective: Two numbers represented by a linked list where each node contains single digit. The digits are stored in REVERSE order, means head is pointing to the first digit of the number.

Input: Two numbers represented by Linked Lists

Output: Addition of two numbers represented by a Linked List.

Example: 

First Number in REVERSE order: 5957
Second Number in REVERSE order : 59
Addition in REVERSE order : 0967
Actual Result in FORWARD ORDER : 9670

Approach:

Read more

Swap Every Kth Node in a LinkedList

by

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10

Approach:

Read more

Replace all spaces in a String with ‘%20’

by

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and the true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

Example: 

Input String :

I am Sumit Jain    

Output String :

I%20am%20Sumit%20Jain 

 

Approach:

Read more

Find Intersection Point in Two Linked List

by

Objective: Given Two linked lists, check whether both lists intersect each other, if yes then find the starting node of the intersection.

An intersection point means the end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List

Output: Intersection Node or point

Example:

Find Intersection Point in Two Linked List
Find Intersection Point in Two Linked List

Approach:

Read more

Find the Loop in a Linked list, find its length and Break the Loop

by

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Input: A Linked List

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example: 

Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop
Loop in a Linked List
Loop in a Linked List

Approach:

Read more

Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

by

Objective: Count all the paths from left top corner to the right bottom corner in two-dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

The recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub-problems that will be solved again and again to get the final solution. read this: “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Create two-dimensional resultCount array to store the number of paths from top left corner.

Read more

Print All Paths from Top left to bottom right in Two Dimensional Array

by

Objective: Print all the paths from left top corner to right bottom corner in two dimensional array.

Input: Two Dimensional array

Output: Print all the paths.

Note: At the End of the article you will know what needs to be included if you want to print the diagonal paths as well.

Example:

Print All Paths - Example

Approach:

As we need to explore all the paths from top left corner to bottom right corner, we will either travel down OR travel right. so every time either we increase the row or column.

Read more

Merge or Combine Two Sorted Linked Lists

by

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example: 



List a : 


->2->6->18




Listb: 


->1->3->17->19




Merged List: ->1->2->3->6->17->18->19


 


Approach:

Without Recursion:


Read more
 













Print All Elements of Two Dimensional Array in Spiral
 

 by  













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 :


Print 2D array in Spiral
Print 2D array in Spiral


Input: Two dimensional array


Output: All array elements printed in spiral.


Approach:


Read more
 













Quick Sort Implementation
 

 by  













Objective: Write an algorithm to sort an array in increasing or decreasing order using Quick Sort.


Input:  An Array arrA[]

Output: A sorted array.


Approach:


  • Choose any element from the array and call it as pivot element, Example here we have selected middle element as pivot
  • Place all the elements smaller than pivot in the left side of pivot.
  • Place all the elements greater than pivot in the right side of pivot.
  • Sort left side and right side recursively.


Example:


Read more
 













Valid or Well Formed Parentheses | Part – 1
 

 by  













Objective: You have been asked to write an algorithm to find Whether Given the Sequence of parentheses is well-formed. This question was asked in the Amazon Interview.


Input: A String contains a sequence of parentheses


Output: true or false on whether parentheses are well-formed or not


Approach:


  • Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
  • Read one character at a time and increment one of the counters
  • If any given point of time count of close parentheses is greater than the open one, return false
  • If at the end both counters are equal, return true


Example: { { } { } } – Well-formed


{ { } { = Not well-formed



Code:



Read more
 













Find an Element in 2 dimensional sorted array
 

 by  













Objective: Write an algorithm to find an element in 2-dimensional array where rows and columns are sorted respectively.


Input: A two dimensional sorted array, arrA[][].


Sorted 2D array


Output: True or false based on whether the element exists and its location


Approach:


Read more
 













Merge Sort – Updated – Most Efficient ways to Implement
 

 by  













Objective : Write Merge Sort algorithm to sort elements in an array


Input: A unsorted array, arrA[].


Output : A sorted array.


Approach:


Divide and Conquer: In this approach we divide the main problems into smaller problems, solve them and merge the results to get the final result.


How Divide and conquer works in Merge Sort:


We divide the elements into two half’s by middle of the array. We solve the left half and right half recursively and merge the results.


Merging:

Once the sorting is done individually on both the half’s, our next task will be merge them. To merge we start with both the arrays at the beginning, pick the smaller one put into array and then compare the next elements and so on.


Read more