Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.

Examples:

Analysis:

This problem can be solved using DFS algorithm. For example, given the input “123456“, suppose we encounter the last digit “6”, at which we already have the result of solve(“12345“). Then there are three cases:

solve(“123456”) = solve(“12345”) + 6

solve(“123456”) = solve(“12345”) - 6

solve(“123456”) = cal( solve(“12345”) ,

Random ID Generator

From: http://blog.gainlo.co/index.php/2016/06/07/random-id-generator/

Let’s continue our system design interview questions discussion. If you are new to this series, you can check our previous posts. Basically, each week we are going to pick several interesting interview questions and provide in-depth analysis.

It’s worth to note that the post is not about giving you something like a standard answer. Instead, we focus more on analyzing the problem and how to come up with reasonable approaches. This is even more true for system design interviews because the question can be extremely open-ended.

Design a Cache System

from: http://blog.gainlo.co/index.php/2016/04/19/design-facebook-chat-function/

Similar to our previous posts, we would like to select system design interview questions that are popular and practical so that not only can you get ideas about how to analyze problems in an interview, but learn something interesting at the same time.

If you have no idea about system design interviews, I’d recommend you read this tutorial first. In this post, we are addressing the problem – how to design a cache system. Topics covered by this post include:

• LRU cache
• Eviction policy,

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Analysis
This problem can be easily solved using a recursive algorithm. We defined a method with the following signature:

equal(left, right)

then we recursively call equal(left.left, right.right) and equal(left.right, right.left).

The method returns false as long as only one of the two nodes is null,

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, val = 6
Return: 1 -> 2 -> 3 -> 4 -> 5

Analysis

To solve this problem, we keep two pointers pre and cur when scanning the LinkedList. Once the current node’s value equals to the target value, we remove the cur node by set pre.next = cur.next;

To make the implementation easier,

Intersection of Two unsorted Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Analysis

Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays.