Friday, March 1, 2019

Finding All Permutations of a given String

Problem: Find all permutations of a given string and display them in lexicographically increasing order.

GFG Link: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

GFG Practice Link: https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string/0

My Solution:

1. Use recursion to get the strings.
2. Use a TreeMap to get order.

Java:


Time Complexity:
O(n * n!) not considering the time for lexicographical sort.

Using MergeSort to sort a LinkedList

Task: Sort a linked list using Merge Sort Algorithm.

GFG Link: https://www.geeksforgeeks.org/merge-sort-for-linked-list/

Why Merge Sort for Linked List Sorting?

The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Java:

Time Complexity : O(nlogn)
Space Complexity : O(n)