1. Find if there is a loop in a single linked-list and if yes, remove it.
Approach-1: Take a slow and fast pointer and see if they ever meet.
Time Complexity: O(n)
Space Complexity: O(1)
Approach-2: Go on storing all the addresses and if a stored address is met.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-3: Reverse the linked-list. And then again reverse the linked-list.
Time Complexity: O(n)
Space Complexity: O(1)
2. Given an array of integers, find the pair of integers that add up to a given number.
Approach-1: Store the integers in a hash-table and see if the difference is present in the hash-table.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-2: Find all the possible pairs in the array.
Time Complexity: O(n-square)
Space Complexity: O(1)
Approach-3:
a) Sort all the numbers (Time: nlogn Space: O(1)).
b) At each element, search for the difference using binary search in the same array (Time: nlogn Space: O(1))
Total time-complexity: O(nlogn)
3. Given a single linked-list, find out if it is a palindrome or not.
Approach-1: Push half the nodes in a stack and traverse the rest of the linked-list, while popping the elements from the stack. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-2: Reach the mid element of the linked-list. And reverse the rest of the linked-list. Then traverse both the linked lists in parallel. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(1)
4. Given a string S and a number n, rotate the string the given number of times.
Example input: S: abcdef, n: 2
Example output: efabcd
Approach-1: Start a loop at twice the given number from the end of the string. Swap the next n characters with the nth character from current position. Repeat this till the starting point reaches the beginning of the string.
Time Complexity: O(n)
Space Complexity: O(1)
Approach-2: Reverse the entire string. Then reverse the characters between 0 to n. And then reverse the characters between n+1 to length of string.
Time Complexity: O(n)
Space Complexity: O(1)
Approach-1: Take a slow and fast pointer and see if they ever meet.
Time Complexity: O(n)
Space Complexity: O(1)
Approach-2: Go on storing all the addresses and if a stored address is met.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-3: Reverse the linked-list. And then again reverse the linked-list.
Time Complexity: O(n)
Space Complexity: O(1)
2. Given an array of integers, find the pair of integers that add up to a given number.
Approach-1: Store the integers in a hash-table and see if the difference is present in the hash-table.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-2: Find all the possible pairs in the array.
Time Complexity: O(n-square)
Space Complexity: O(1)
Approach-3:
a) Sort all the numbers (Time: nlogn Space: O(1)).
b) At each element, search for the difference using binary search in the same array (Time: nlogn Space: O(1))
Total time-complexity: O(nlogn)
3. Given a single linked-list, find out if it is a palindrome or not.
Approach-1: Push half the nodes in a stack and traverse the rest of the linked-list, while popping the elements from the stack. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(n)
Approach-2: Reach the mid element of the linked-list. And reverse the rest of the linked-list. Then traverse both the linked lists in parallel. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(1)
4. Given a string S and a number n, rotate the string the given number of times.
Example input: S: abcdef, n: 2
Example output: efabcd
Approach-1: Start a loop at twice the given number from the end of the string. Swap the next n characters with the nth character from current position. Repeat this till the starting point reaches the beginning of the string.
Time Complexity: O(n)
Space Complexity: O(1)
Approach-2: Reverse the entire string. Then reverse the characters between 0 to n. And then reverse the characters between n+1 to length of string.
Time Complexity: O(n)
Space Complexity: O(1)
No comments:
Post a Comment