Skip to content

Instantly share code, notes, and snippets.

@pocha
Last active April 3, 2018 11:48
Show Gist options
  • Save pocha/b6cd987f7fe8c950a9495a8620251c63 to your computer and use it in GitHub Desktop.
Save pocha/b6cd987f7fe8c950a9495a8620251c63 to your computer and use it in GitHub Desktop.
Algo-DS interview prep in a glance. Leetcode questions & their answers compiled in one place.

1. Two Sum

Total Accepted: 372574
Total Submissions: 1273263
Difficulty: Easy
Contributors: Admin

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

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

UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.

Approach #3 (One-pass Hash Table) [Accepted]

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.


2. Add Two Numbers

Total Accepted: 219342
Total Submissions: 843677
Difficulty: Medium
Contributors: Admin

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

3. Longest Substring Without Repeating Characters

Total Accepted: 223827
Total Submissions: 949264
Difficulty: Medium
Contributors: Admin

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

We use HashSet to store the characters in current window [i,j)[i, j)[i,j) (j=ij = ij=i initially). Then we slide the index jjj to the right. If it is not in the HashSet, we slide jjj further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index iii. If we do this for all iii, we get our answer.


4. Median of Two Sorted Arrays

Total Accepted: 133399
Total Submissions: 645867
Difficulty: Hard
Contributors: Admin

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution - for arrays of size m & n, median will be at (m+n)/2 from start of the combined array. Run i & j on each array such that .....


5. Longest Palindromic Substring

Total Accepted: 156595
Total Submissions: 643330
Difficulty: Medium
Contributors: Admin

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−12n - 12n−1 such centers.

You might be asking why there are 2n−12n - 12n−1 but not nnn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as ''abba'' ) and its center are between the two 'b'

s.

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

Serialize & deserialize binary tree

Serialize - preorder traversal . Mark nil children as nil. Root, left, right node order

def serialize (node)
    return "nil" if node.nil?
    string = ""
    string += node.val + ","
    string += serialize(node.left) + ","
    string += serialize(node.right) + ","
end

def deserialize (s)
    node.left = _deserialize(val_array,count++)
    node.right = _deserialize(val_array,count++)
end

def _deserialize(val_array,i)
   if val_array[i].nil?
       return
   else
        
            
end

450. Delete Node in a BST

Steps:

Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree Once the node is found, have to handle the below 4 cases node doesn't have left or right - return null node only has left subtree- return the left subtree node only has right subtree- return the right subtree node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree

def delete_node(node,val)
    if val > node.val
        delete_node(node.right,val)
    elseif val < node.val
        delete_node(node.left,val)
    else #current node need deletion
        if node.left.nil?
            return node.right
        elseif node.right.nil?
            return node.left
        else
            replacement = find_replacement(node.left)
            node.val = replacement.val
            delete_node(node,replacement.val)
        end
    end
 end
 
 def find_replacement(node,val)
    while !node.right.nil?
        node = node.right
    end
    return node
 end

Add Numbers (2)

Given 2 linked list of numbers , add them 7->0->4->3 + 3->8->5 = 7->1->2-> 8

def sum(l1, l2)
    c1 = l1.length
    c2 = l2.length
    count = [c1,c2].max
    out = LL.new(count)
    carry = _sum(l1,l2,count,out)
    if carry == 1
        #create new node & append before out
    end
    out
end

def _sum(l1,l2,count,out)
    return 0 if count == 0
    if c1 >= count
        out.val += l1.val
        l1 = l1.next
    end
    if c2 >= count
        out.val += l2.val
        l2 = l2.next
    end
    out.val += _sum(l1,l2,count--,out.next)
    if out.val > 10
        out.val %= 10
        return 1
    else
        return 0
    end
 end

451. Sort Characters By Frequency QuestionEditorial Solution My Submissions

Total Accepted: 8586 Total Submissions: 17129 Difficulty: Medium Contributors: stickypens Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input: "tree"

Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Build a map of characters to the number of times it occurs in the string Create an array where the index of the array represents how many times that character occurred in the String Iterate from the end of the array to the beginning, and at each index, append each character to the return string that number of times.


Poor Pig

1000 bucks, one has poision. One pig drinks the water & dies in 15 min. How many pigs needed to identify the bucket in 60 min

x * x-1 * x-2 * x-3 = 1000 .. x comes around 8


11. Container With Most Water

Add to List QuestionEditorial Solution My Submissions Total Accepted: 107167 Total Submissions: 297862 Difficulty: Medium Contributors: Admin Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Sol - start from both ends, i & j . Increment i if height[i] < height[j] .. reason j is already greater than i & hence the area calculation is (j-1) * height[j] .. we start at boundaries where (j-i) is max .. then we move the value which is smaller so that height increases but j-i is decreasing .. do this till j converges with i


@pocha
Copy link
Author

pocha commented Jan 6, 2017

  1. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Sol - since array is sorted - two pointer approach starting from beginning & end can be used. if sum of the 2 numbers > given sum => end pointer -- else if sum < given sum => start pointer ++ else we have the answer.

@pocha
Copy link
Author

pocha commented Jan 6, 2017

  1. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Sol - Classic binary search problem.

Looking at subarray with index [start,end]. We can find out that if the first member is less than the last member, there's no rotation in the array. So we could directly return the first element in this subarray.

If the first element is larger than the last one, then we compute the element in the middle, and compare it with the first element. If value of the element in the middle is larger than the first element, we know the rotation is at the second half of this array. Else, it is in the first half in the array.

Follow up - if duplicates are allowed

class Solution {
public:
    int findMin(vector<int> &num) {
        int lo = 0;
        int hi = num.size() - 1;
        int mid = 0;
        
        while(lo < hi) {
            mid = lo + (hi - lo) / 2;
            
            if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else if (num[mid] < num[hi]) {
                hi = mid;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
};

When num[mid] == num[hi], we couldn't sure the position of minimum in mid's left or right, so just let upper bound reduce one.

@pocha
Copy link
Author

pocha commented Jan 10, 2017

  1. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

def max_profit(prices)
    max_profit = 0
    buy = nil
    prices.each_with_index do |val,i|
        if prices[i+1] and val < prices[i+1]
            buy = val
        elsif prices[i+1] and val > prices[i+1] 
            next if buy.nil?
            profit = val - buy
            max_profit = profit if profit > max_profit
            buy = nil
        else #next price is not there
            if buy
                profit = val - buy
                max_profit = profit if profit > max_profit
            end
        end
    end
    return max_profit
end

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment