Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Analysis

We can use a bounded queue to record the last n integers in the window, and define a variable sumN to record the sum of the numbers in the window.

Each time when a new number is registered,

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1,

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

Analysis

I will use an example to illustrate how to generate all the permutation of an array.

Given a list [1, 2, 3, 4], all the permutations consists of the four sets:
the permutations starts with 1: {1} + {permutations of array [2, 3, 4]}
the permutations starts with 2,
the permutations starts with 3,
the permutations starts with 4,

Suppose we have a function called search to generate permutations for the subarray nums[start .. end].

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:

This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array.

For instance, given a sorted array [1,

Here are some good resources to prepare a technical interview about programming, software engineering, algorithms, data structures, machine learning, and data science.

Popular websites to prepare a technical interview

GeeksforGeeks.org: A famous website for detailed explanation for essential algorithms and data structures.

CareerCup.com The website built by the author of the one of the most famous book CC150. You can find many interview questions of big companies.

Glassdoor.com : A platform to rate companies. For each company, you can find some interview questions posted by its users.

LeetCode - Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Analysis

This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array.

Leetcode: Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Analysis

We defined two indexes: pre and cur.

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.
   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Analysis:

The key to solve this problem is to use two pointers: pre and cur. The pre pointer moves N steps in the first place,

Longest common prefix

Write a function to find the longest common prefix string amongst an array of strings.

Pay attention to the corner case: strs can be empty.

Analysis

We define cur to record the char at current round that is recorded by si.

If si equals to the current string’s length, we return the substring from 0 to si.

At the beginning of each round, cur is set as null.

So when cur is null, we know this is the first string to check in current round. We set cur as the letter of the current string at index si

For the following string,

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis

The rules to transfer a roman to an integer can be understood using the following examples:

So for any two Roman letters in the form: Left Right

if the left is smaller than the right, the result will be right - left.

if the left is larger or equal to the right, the result will right + left.

See this link for more examples of the roman numbers.