fenghaolw

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. The intuitive approach is to use a hash map to store the mapping between the original nodes and the copied nodes. The following code requires O(2n) in time and O(n) in space. If we do not want to use extra memory, the following approach could be applied:  Copy the list nodes and insert the copied node right after the original node. For example, A->B->C->... becomes A->copyA->B->copyB->C->copyC->... If A has a non-null random pointer, we can simply set A->next->random = A->random->next . Split the list into two separate lists. O(3n) in time and O(1) in space.

There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. 1. If the sum of gas[i] is less than the sum of cost[i], for sure we should return -1. However, is it possible that we cannot travel around the circuit from any starting gas stations, even if the sum of gas[i] is greater than the sum of cost[i]? The answer is no since we have unlimited gas tank. 2. If we cannot travel from station i to station j, is it possible that the available starting point is located between i and j?

Given an array of integers, every element appears  twice  except for one. Find that single one. Could you implement it without using extra memory? Intuitive answer: using hash set Without extra space: use bit XOR. All numbers which occur twice will be cancelled out by themselves.

Clone an undirected graph. Each node in the graph contains a  label  and a list of its  neighbors . OJ's undirected graph serialization: Nodes are labeled uniquely. We use  #  as a separator for each node, and  ,  as a separator for node label and each neighbor of the node. As an example, consider the serialized graph  { 0 ,1,2# 1 ,2# 2 ,2} . The graph has a total of three nodes, and therefore contains three parts as separated by  # . First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 . Second node is labeled as  1 . Connect node  1  to node  2 . Third node is labeled as  2 . Connect node  2  to node  2  (itself), thus forming a self-cycle. Visually, the graph looks like the following: 1 / \ / \ 0 --- 2 / \ \_/ BFS

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words. For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16. Return the formatted lines as: [    "This    is    an",    "example  of text",    "justification.  " ] Note: Each word is guarante

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy.  Children with a higher rating get more candies than their neighbors.  What is the minimum candies you must give?