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?

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

1
2
3
4
5

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

• The array is only modifiable by the update function.
• You may assume the number of calls to update and sumRange function is distributed evenly.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

Example,

Given the following binary tree,

1
2
3
4
5

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

1
2
3
4
5

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
2
3
4
5

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

1

["1->2->5", "1->3"]

Shuffle a set of numbers without duplicates.

Example:

1
2
3
4
5
6
7
8
9
10
11
12

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

Each letter in the magazine
string
can only
be used
once in
your ransom note.

Note:

You may assume that both strings contain only lowercase letters.

1
2
3

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:

Given num = 16, return true. Given num = 5, return false.

Follow up:

Could you solve it without loops/recursion?

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

• Think of “looking ahead”. You want to cache the next element.
• Is one variable sufficient? Why or why not?
• Test your design with call order of peek() before next() vs next() before peek().
• For a clean implementation, check out Google’s guava library source code.

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

1
2
3
4
5
6
7
8

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();