Skip to content

Commit c2446d9

Browse files
awangdevawangdev
committed
added new problems
1 parent 244de15 commit c2446d9

15 files changed

Lines changed: 966 additions & 106 deletions

‎Java/Add Binary.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/*
2+
Given two binary strings, return their sum (also a binary string).
3+
4+
Example
5+
a = 11
6+
7+
b = 1
8+
9+
Return 100
10+
11+
Tags Expand
12+
String Binary
13+
14+
15+
16+
//Thougths:
17+
1. Turn string binary format into integer
18+
2. add integer
19+
3. turn integer into binary string
20+
Note: this just test if we know how to manipulate string/binary/Integer
21+
*/
22+
23+
24+
public class Solution {
25+
/**
26+
* @param a a number
27+
* @param b a number
28+
* @return the result
29+
*/
30+
public String addBinary(String a, String b) {
31+
if (a == null || b == null || a.length() == 0 || b.length() == 0) {
32+
return null;
33+
}
34+
int decimalA = Integer.parseInt(a, 2);
35+
int decimalB = Integer.parseInt(b, 2);
36+
37+
int sum = decimalA + decimalB;
38+
39+
return Integer.toBinaryString(sum);
40+
}
41+
}

‎Java/Convert Sorted Array to Binary Search Tree With Minimal Height.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/*
2+
Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.
3+
4+
Have you met this question in a real interview? Yes
5+
Example
6+
Given [1,2,3,4,5,6,7], return
7+
8+
4
9+
/ \
10+
2 6
11+
/ \ / \
12+
1 3 5 7
13+
Note
14+
There may exist multiple valid solutions, return any of them.
15+
16+
Tags Expand
17+
Cracking The Coding Interview Recursion Binary Tree
18+
19+
Thoughts:
20+
1. Find middle point x.
21+
2. All index before x, goes to left of the tree. Same apply to right tree
22+
build sub array and pass alone: we can pass index start, end.
23+
use parent node and pass along
24+
3. Recur on left side array.
25+
26+
*/
27+
28+
29+
/**
30+
* Definition of TreeNode:
31+
* public class TreeNode {
32+
* public int val;
33+
* public TreeNode left, right;
34+
* public TreeNode(int val) {
35+
* this.val = val;
36+
* this.left = this.right = null;
37+
* }
38+
* }
39+
*/
40+
public class Solution {
41+
/**
42+
* @param A: an integer array
43+
* @return: a tree node
44+
*/
45+
public TreeNode sortedArrayToBST(int[] A) {
46+
TreeNode root = null;
47+
if (A == null || A.length == 0) {
48+
return root;
49+
}
50+
root = helper(0, A.length - 1, A);
51+
return root;
52+
}
53+
54+
public TreeNode helper(int start, int end, int[] A) {
55+
if (start > end) {
56+
return null;
57+
}
58+
//add middle node
59+
int mid = start + (end - start)/2;
60+
TreeNode node = new TreeNode(A[mid]);
61+
//Split and append child
62+
node.left = helper(start, mid - 1, A);
63+
node.right = helper(mid + 1, end, A);
64+
return node;
65+
}
66+
}

‎Java/Count 1 in Binary.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/*
2+
Count how many 1 in binary representation of a 32-bit integer.
3+
4+
Example
5+
Given 32, return 1
6+
7+
Given 5, return 2
8+
9+
Given 1023, return 9
10+
11+
Challenge
12+
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
13+
14+
Tags Expand
15+
Binary Bit Manipulation
16+
17+
Thoughts:
18+
1. break string into char[]
19+
2. convert char[] into integer using Character.getNumericValue()
20+
21+
*/
22+
23+
24+
25+
26+
public class Solution {
27+
/**
28+
* @param num: an integer
29+
* @return: an integer, the number of ones in num
30+
*/
31+
public int countOnes(int num) {
32+
if (num < 0) {
33+
return 0;
34+
}
35+
String bits = Integer.toBinaryString(num);
36+
char[] bitArray = bits.toCharArray();
37+
int sum = 0;
38+
for (int i = 0; i < bitArray.length; i++) {
39+
sum += Character.getNumericValue(bitArray[i]);
40+
}
41+
return sum;
42+
}
43+
};

‎Java/Count and Say.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/*
2+
The count-and-say sequence is the sequence of integers beginning as follows:
3+
4+
1, 11, 21, 1211, 111221, ...
5+
6+
1 is read off as "one 1" or 11.
7+
8+
11 is read off as "two 1s" or 21.
9+
10+
21 is read off as "one 2, then one 1" or 1211.
11+
12+
Given an integer n, generate the nth sequence.
13+
14+
Example
15+
Given n = 5, return "111221".
16+
17+
Note
18+
The sequence of integers will be represented as a string.
19+
20+
Tags Expand
21+
String
22+
23+
24+
1. Set up initial value '11'
25+
2. use while loop to build on past variable
26+
3. In each while loop case, break the string into charArray, count and name mark the type
27+
4. In for loop: when different, append string (count+type); when same, count++.
28+
*/
29+
30+
31+
public class Solution {
32+
/**
33+
* @param n the nth
34+
* @return the nth sequence
35+
*/
36+
public String countAndSay(int n) {
37+
if (n <= 1) {
38+
return n + "";
39+
}
40+
String str = "11";
41+
int ind = 2;
42+
while (ind < n) {
43+
StringBuffer sb = new StringBuffer();
44+
char[] arr = str.toCharArray();
45+
int count = 1;
46+
int type = Character.getNumericValue(arr[0]);
47+
for (int i = 1; i < arr.length; i++) {
48+
if (arr[i] == arr[i - 1]) {
49+
count++;
50+
} else {
51+
sb.append(count + "" + type);
52+
type = Character.getNumericValue(arr[i]);
53+
count = 1;
54+
}
55+
}
56+
ind++;
57+
sb.append(count + "" + type);
58+
str = sb.toString();
59+
}
60+
return str;
61+
}
62+
}

‎Java/Delete Node in the Middle of Singly Linked List.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
3+
4+
Example
5+
Given 1->2->3->4, and node 3. return 1->2->4
6+
7+
Tags Expand
8+
Cracking The Coding Interview Linked List
9+
10+
Thoughts:
11+
1. Only have this node, make it look like its next
12+
2. remove next
13+
14+
*/
15+
16+
17+
/**
18+
* Definition for ListNode.
19+
* public class ListNode {
20+
* int val;
21+
* ListNode next;
22+
* ListNode(int val) {
23+
* this.val = val;
24+
* this.next = null;
25+
* }
26+
* }
27+
*/
28+
public class Solution {
29+
/**
30+
* @param node: the node in the list should be deleted
31+
* @return: nothing
32+
*/
33+
public void deleteNode(ListNode node) {
34+
if (node == null) {
35+
return;
36+
}
37+
node.val = node.next.val;
38+
node.next = node.next.next;
39+
}
40+
}

‎Java/Fibonacci.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/*
2+
Find the Nth number in Fibonacci sequence.
3+
4+
A Fibonacci sequence is defined as follow:
5+
6+
The first two numbers are 0 and 1.
7+
The i th number is the sum of i-1 th number and i-2 th number.
8+
The first ten numbers in Fibonacci sequence is:
9+
10+
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
11+
12+
13+
Example
14+
Given 1, return 0
15+
16+
Given 2, return 1
17+
18+
Given 10, return 34
19+
20+
Note
21+
The Nth fibonacci number won't exceed the max value of signed 32-bit integer in the test cases.
22+
23+
Tags Expand
24+
Enumeration Mathematics Non Recursion
25+
26+
Thoughts:
27+
1. If non-recursion, do for loop for that n
28+
2. Note: this specfiic problem is not 0-based. it's 1-based.
29+
3. return fib[n]
30+
*/
31+
32+
class Solution {
33+
/**
34+
* @param n: an integer
35+
* @return an integer f(n)
36+
*/
37+
public int fibonacci(int n) {
38+
if (n <= 1) {
39+
return 0;
40+
}
41+
int[] fib = new int[n + 1];
42+
fib[1] = 0;
43+
fib[2] = 1;
44+
for (int i = 3; i <= n; i++) {
45+
fib[i] = fib[i - 1] + fib[i - 2];
46+
}
47+
return fib[n];
48+
}
49+
}

0 commit comments

Comments
 (0)