LeetCode - Longest Substring Without Repeating Characters - O(n) - Java

Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring

Solution


LeetCode - Two Sum O(n) Solution in Java


Problem

[Original Link]

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Solution:

The idea is to maintain a hash map to store the elements that you have seen as we iterate over the array. For every number we try to see if we have a complement i.e (target-current no) in our hash map. If we find the number in our hash map, we have our answer.

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


Must do questions for software engineering interviews - LeetCode

These questions are in no particular order. Every question will give you enough exposure to strategies and techniques required to solve most of the problem solving & data structures related questions in the interviews.

Some of the techniques used in these problems are two pointers, invariant windows, binary search, DFS/BFS, recursion, interval scheduling related, simple DP and bit manipulation, heaps, data structure design etc.

  1. Two Sum
  2. 3Sum
  3. Combination Sum
  4. Minimum Window Substring
  5. Maximum Subarray
  6. Longest substring without repeating characters
  7. Longest Palindromic Substring
  8. Longest repeating character replacement
  9. Search in a rotated sorted array
  10. Maximum Subarray
  11. Spiral Matrix
  12. Rotate Image
  13. Container with most Water
  14. Best Time to Buy and Sell Stock
  15. Remove Nth Node from end of a list
  16. Maximum Product Subarray
  17. Reverse LinkedList
  18. Product of Array Except Self
  19. Find minimum in rotated sorted array
  20. Valid Parenthesis
  21. Merge two sorted lists
  22. Merge K sorted lists
  23. Group Anagrams
  24. Merge Intervals
  25. Meeting Rooms
  26. Meeting Rooms ||
  27. Minimum Number of arrows to burst balloons
  28. Insert Interval
  29. Unique Paths
  30. Jump Game
  31. Climbing Stairs
  32. Set Matrix Zeros
  33. Word Search
  34. Word Search ||
  35. Validate Binary Search Tree
  36. Binary Tree Level Order Traversal
  37. Maximum Depth of a Binary Tree
  38. Binary Tree from Preorder and Inorder traversals
  39. Binary Tree Maximum Path Sum
  40. Invert Binary Tree
  41. Kth Smallest Element in a BST
  42. Lowest Common Ancestor in a BST
  43. Serialize and deserialize binary tree
  44. Subtree of Another Tree
  45. Number of connected components in an undirected graph
  46. Clone Graph
  47. Valid Palindrome
  48. Longest Consecutive Sequence
  49. Word Break
  50. Decode Ways
  51. Linked List Cycle
  52. Reorder List
  53. Reverse Bits
  54. Number of 1 Bits
  55. House Robber
  56. House Robber ||
  57. Number of Islands
  58. Implement Trie
  59. Add and Search Word - DS Design
  60. Contains Duplicate
  61. Course Schedule
  62. Valid Anagram
  63. Group Valid Tree
  64. Missing Number
  65. Alien Dictionary
  66. Encode And Deode Strings
  67. Find Median from data stream
  68. Longest Increasing Subsequence
  69. Coin Change
  70. Counting Bits
  71. Top K frequent elements
  72. Sum of Two Integers
  73. Pacific Atlantic Water flow
  74. Non Overlapping Intervals



CodeFights - Cat Walk - Solution

Problem
You've been working on a particularly difficult algorithm all day, and finally decided to take a break and drink some coffee. To your horror, when you returned you found out that your cat decided to take a walk on the keyboard in your absence, and pressed a key or two. Your computer doesn't react to letters being pressed when an unauthorized action appears, but allows typing whitespace characters and moving the arrow keys, so now your masterpiece contains way too many whitespace characters.
To repair the damage, you need to start with implementing a function that will replace all multiple space characters in the given line of your code with single ones. In addition, all leading and trailing whitespaces should be removed.
Example
For line = "def      m   e  gaDifficu     ltFun        ction(x):",
the output should be
catWalk(line) = "def m e gaDifficu ltFun ction(x):".
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] string line
    One line from your code containing way too many whitespace characters.
    Guaranteed constraints:
    5 ≤ line.length ≤ 125.
  • [output] string
    line with unnecessary whitespace characters removed.
Solution


def catWalk(code):
    return " ".join(code.strip().split())

CodeFights - Simple Sort - Solution

Problem
To understand how efficient the built-in Python sorting function is, you decided to implement your own simple sorting algorithm and compare its speed to the speed of the Python sorting. Write a function that, given an array of integers arr, sorts its elements in ascending order.
Hint: with Python it's possible to swap several elements in a single line. To solve the task, use this knowledge to fill in both of the blanks (...).
Example
For arr = [2, 4, 1, 5], the output should be
simpleSort(arr) = [1, 2, 4, 5].
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] array.integer arr
    Guaranteed constraints:
    1 ≤ arr.length ≤ 100,
    -105 ≤ arr[i] ≤ 105.
  • [output] array.integer
    The given array with elements sorted in ascending order.
Solution

We just have to swap the elements which are out of order. The line in bold does just that. Its called tuple unpacking.


def simpleSort(arr):

    n = len(arr)

    for i in range(n):
        j = 0
        stop = n - i
        while j < stop - 1:
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            j += 1
    return arr

CodeFights - Count Bits - Solution

Problem
Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
Implement a function that, given an integer n, uses a specific method on it and returns the number of bits in its binary representation.
Note: in this task and most of the following tasks you will be given a code snippet with some part of it replaced by the ellipsis (...). Only this part is allowed to be changed.
Example
For n = 50, the output should be
countBits(n) = 6.
5010 = 1100102, a number that consists of 6 digits. Thus, the output should be 6.
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] integer n
    A positive integer.
    Guaranteed constraints:
    1 ≤ n ≤ 109.
  • [output] integer
    The number of bits in binary representation of n.
Solution
It is expected to only replace the ellipsis with the code that would give you the bit length of the given integer. 

def countBits(n):
     return n.bit_length()

CodeFights - Comfortable Numbers - Solution

Problem

Let's say that number a feels comfortable with number b if a ≠ b and b lies in the segment [a - s(a), a + s(a)], where s(x) is the sum of x's digits.
How many pairs (a, b) are there, such that a < b, both a and b lie on the segment [L, R], and each number feels comfortable with the other?
Example
For L = 10 and R = 12, the output should be
comfortableNumbers(L, R) = 2.
Here are all values of s(x) to consider:
  • s(10) = 1, so 10 is comfortable with 9 and 11;
  • s(11) = 2, so 11 is comfortable with 91012 and 13;
  • s(12) = 3, so 12 is comfortable with 910111314 and 15.
Thus, there are 2 pairs of numbers comfortable with each other within the segment [10; 12](10, 11) and (11, 12).
Input/Output
  • [time limit] 500ms (cpp)
  • [input] integer L
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [input] integer R
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [output] integer
    The number of pairs satisfying all the above conditions.

Solution

The problem is pretty straightforward due to constraints of the problem. We need to look at 1000C2 pairs in the worst case. We look at all the pairs in the range [L, R] and check if the pair of integers in a given pair are comfortable to each other.

Code

int digitSum(int n){
    int _sum = 0;
    
    while (n){
        _sum += (n%10);
        n = n/10;
    }
    
    return _sum;
}

int comfortableNumbers(int L, int R) {
    int total_pairs = 0;
    
    for(int i=L; i<=R; i++){
        for(int j=i+1; j<=R; j++){
            int s_a = digitSum(i);
            int s_b = digitSum(j);
            if (j>= (i-s_a) and j<= (i+s_a) and 
                  i>= (j-s_b) and i<= (j+s_b)
               ) {
                total_pairs++;
            }
        }
    }
    return total_pairs;
}