Interview Questions | Learn for Master

Leetcode Sliding Window Maximum

September 2, 2016 Author: david

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see thek numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

1

2

3

4

5

6

7

8

9

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

[Read More...]

LeetCode Recover Binary Search Tree (java)

August 28, 2016 Author: david

No comment yet

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Java Solution

We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,

[Read More...]

Leetcode Path Sum

August 26, 2016 Author: david

No comment yet

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

1

2

3

4

5

6

7

8

5

/ \

4 8

/ / \

11 13 4

/ \ \

7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == sum;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public boolean hasPathSum(TreeNode root, int sum) {

if (root == null) return false;

if (root.left == null && root.right == null) return root.val == sum;

return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

}

[Read More...]

Leetcode Permutation Sequence

August 26, 2016 Author: david

No comment yet

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”
“132”
“213”
“231”
“312”
“321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Java solution:

public class Solution {
    public String getPermutation(int n, int k) {
        if ( n ==  1) return "1";
        int factor = 1;
        //cause time limit error
        // ArrayList<Integer> res = new ArrayList<>();
        int[] res = new int[n];
        for(int i = 1; i <= n; i++) {
            // res.add(i);
            factor *= i;
            res[i - 1] = i;
        }
        int index = 0;
        // StringBuilder sb = new StringBuilder();
        char[] ary = new char[n];
        k--;
        for(int i = 0; i < n ; i++) {
            factor /= (n - i);
            index = k / factor;
            k = k % factor;
            ary[i] = (char)(res[index] + '0');
            // sb.append(res[index]);
            // res.remove(index);
            for(int j = index; j < n - i - 1; j++) {
                res[j]= res[j + 1];
            }
        }
        return String.valueOf(ary);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

public class Solution {

public String getPermutation(int n, int k) {

if ( n == 1) return "1";

int factor = 1;

//cause time limit error

// ArrayList<Integer> res = new ArrayList<>();

int[] res = new int[n];

for(int i = 1; i <= n; i++) {

// res.add(i);

factor *= i;

res[i - 1] = i;

}

int index = 0;

// StringBuilder sb = new StringBuilder();

char[] ary = new char[n];

k--;

for(int i = 0; i < n ; i++) {

factor /= (n - i);

index = k / factor;

k = k % factor;

ary[i] = (char)(res[index] + '0');

// sb.append(res[index]);

// res.remove(index);

for(int j = index; j < n - i - 1; j++) {

res[j]= res[j + 1];

}

return String.valueOf(ary);

}

Refernce:

https://leetcode.com/problems/permutation-sequence/

http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html

[Read More...]

Leetcode Flatten Nested List Iterator (Java)

August 24, 2016 Author: david

No comment yet

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

[Read More...]

LeetCode Shuffle an Array (Java)

August 23, 2016 Author: david

No comment yet

Shuffle a set of numbers without duplicates.

Example:

// 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();

1

2

3

4

5

6

7

8

9

10

11

12

13

// 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();

Java Solution

public class Solution {
    int[] origin;
    int[] res;
    Random r;
    public Solution(int[] nums) {
        origin = nums;
        res = Arrays.copyOf(nums, nums.length);
        r = new Random();
    }
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        res = Arrays.copyOf(origin, origin.length);
        return res;
    }
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int right = res.length - 1;
        int j;
        while(right > 0) {
            j = r.nextInt(right + 1);
            swap(res, j, right);
            right--;
        }
        return res;
    }
    void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

public class Solution {

int[] origin;

int[] res;

Random r;

public Solution(int[] nums) {

origin = nums;

res = Arrays.copyOf(nums, nums.length);

r = new Random();

}

/** Resets the array to its original configuration and return it. */

public int[] reset() {

res = Arrays.copyOf(origin, origin.length);

return res;

}

/** Returns a random shuffling of the array. */

public int[] shuffle() {

int right = res.length - 1;

int j;

while(right > 0) {

j = r.nextInt(right + 1);

swap(res, j, right);

right--;

}

return res;

}

void swap(int[] A, int i, int j) {

int tmp = A[i];

A[i] = A[j];

A[j] = tmp;

}

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* int[] param_1 = obj.reset();

* int[] param_2 = obj.shuffle();

*/

[Read More...]

LeetCode Linked List Cycle (java)

August 22, 2016 Author: david

No comment yet

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Java Solution

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode fastP = head.next;
        ListNode slowP = head;
        while(fastP != null && fastP != slowP) {
            if(fastP.next == null) return false;
            fastP = fastP.next.next;
            slowP = slowP.next;
        }
        return fastP == slowP;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

*/

public class Solution {

public boolean hasCycle(ListNode head) {

if(head == null || head.next == null) return false;

ListNode fastP = head.next;

ListNode slowP = head;

while(fastP != null && fastP != slowP) {

if(fastP.next == null) return false;

fastP = fastP.next.next;

slowP = slowP.next;

}

return fastP == slowP;

}

[Read More...]

LeetCode Ransom Note (Java)

August 22, 2016 Author: david

No comment yet

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.

Note:
You may assume that both strings contain only lowercase letters.

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

1

2

3

4

canConstruct("a", "b") -> false

canConstruct("aa", "ab") -> false

canConstruct("aa", "aab") -> true

Java Solution

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // if(ransomNote == null && magazine == null) return true;
        // if(ransomNote == null) return true;
        // if(magazine == null) return false;
        // if(ransomNote.length() == 0 && magazine.length() == 0) return true;
        // if(ransomNote.length() > magazine.length()) return false;
        Map<Character, Integer> freq = new HashMap<>();
        for(char c: magazine.toCharArray()) {
            if(freq.containsKey(c)) {
                freq.put(c, freq.get(c) + 1);
            } else {
                freq.put(c, 1);
            }
        }
        for(char c: ransomNote.toCharArray()) {
            if (freq.containsKey(c)) {
                if(freq.get(c) > 1) {
                    freq.put(c, freq.get(c) - 1);
                } else {
                    freq.remove(c);
                }
            }else{
                return false;
            }
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

public class Solution {

public boolean canConstruct(String ransomNote, String magazine) {

// if(ransomNote == null && magazine == null) return true;

// if(ransomNote == null) return true;

// if(magazine == null) return false;

// if(ransomNote.length() == 0 && magazine.length() == 0) return true;

// if(ransomNote.length() > magazine.length()) return false;

Map<Character, Integer> freq = new HashMap<>();

for(char c: magazine.toCharArray()) {

if(freq.containsKey(c)) {

freq.put(c, freq.get(c) + 1);

} else {

freq.put(c, 1);

}

for(char c: ransomNote.toCharArray()) {

if (freq.containsKey(c)) {

if(freq.get(c) > 1) {

freq.put(c, freq.get(c) - 1);

} else {

freq.remove(c);

}

}else{

return false;

}

return true;

}

[Read More...]

Leetcode Jump Game I & II (Java)

August 22, 2016 Author: david

No comment yet

Jump Game I

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Analysis:
We maintain the max step can be reached so far. If an index i is larger than the current max step that can be reached, it returns false.

Java Solution:

public class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        if (size == 0) return true;
        int curMax = nums[0];
        for(int i = 1; i < size; i++) {
            if( i <= curMax) {
                curMax = Math.max(curMax, nums[i] + i);
            }else{
                return false;
            }
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

public class Solution {

public boolean canJump(int[] nums) {

int size = nums.length;

if (size == 0) return true;

int curMax = nums[0];

for(int i = 1; i < size; i++) {

if( i <= curMax) {

curMax = Math.max(curMax, nums[i] + i);

}else{

return false;

}

return true;

}

Jump Game II

Given an array of non-negative integers,

[Read More...]

Leetcode mini parser

August 22, 2016 Author: david

No comment yet

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

1

2

3

4

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

1

2

3

4

5

6

7

8

9

10

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.

2. A nested list containing two elements:

i. An integer containing value 456.

ii. A nested list with one element:

a. An integer containing value 789.

Analysis

Define num to store the current number,

[Read More...]

Leetcode Sliding Window Maximum

LeetCode Recover Binary Search Tree (java)

Leetcode Path Sum

Leetcode Permutation Sequence

Leetcode Flatten Nested List Iterator (Java)

LeetCode Shuffle an Array (Java)

LeetCode Linked List Cycle (java)

LeetCode Ransom Note (Java)

Leetcode Jump Game I & II (Java)

Leetcode mini parser

Get $35 Toward a New Fire TV 4K Device

Shop Amazon Gift Cards. Any Occasion. No Expiration

Best books to master algorithms

Search

Category List

Featured Categories

Rss Feeds

Categories

Subscribe

Contact US

Popular Posts

learn4master.com 2016 Accelerated by keyCDN

Get $35 Toward a New Fire TV 4K Device

Shop Amazon Gift Cards. Any Occasion. No Expiration

Best books to master algorithms

Search

Category List

Featured Categories

Tags

Categories

Subscribe

Categories

Contact US

Tags

Popular Posts

learn4master.com 2016 Accelerated by keyCDN