Predict the Number
Programming challenge description:
The example sequence 011212201220200112 ... is constructed as follows:
1. The first element in the sequence is 0.
2. For each iteration, repeat the following action: take a copy of the entire current sequence, replace 0 with 1, 1 with 2, and 2 with 0, and place it at the end of the current sequence. E.g.
0 -> 01 -> 0112 -> 01121220 -> ...
Create an algorithm which determines what number is at the Nth position in the sequence (using 0-based indexing).
Input:
Your program should read lines from standard input. Each line contains an integer N such that 0 <= N <= 3000000000.
Output:
Print out the number which is at the Nth position in the sequence.
Test 1
Test Input
Download Test 1 Input
5
Expected Output
Download Test 1 Output
2
Test 2
Test Input
Download Test 2 Input
25684
Expected Output
Download Test 2 Output
0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
public class Main {
private static int getDigitAt(long position) {
StringBuilder sb = new StringBuilder("0");
int result = -1;
long start = 1;
for (long i = 0; i < Long.MAX_VALUE && start-1 <= position; i++) {
String candidate = sb.toString();
candidate = candidate.replace("0", "X").replace("1", "Y").replace("2","Z").replace("X","1").replace("Y", "2").replace("Z", "0");
start += candidate.length();
sb.append(candidate);
}
result = Integer.parseInt(String.valueOf(sb.charAt((int)position)));
return result;
}
public static void main(String[] args) throws IOException {
InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
BufferedReader in = new BufferedReader(reader);
String line;
while ((line = in.readLine()) != null) {
long position = Long.MAX_VALUE;
try {
position = Long.parseLong(line);
} catch (NumberFormatException e) {
}
if (position != Long.MAX_VALUE) {
int digit = getDigitAt(position);
System.out.println(digit);
}
}
}
}
Running test cases... Done
– – – – – – – – – – – – – –
Test 1
Passed Collapse
Test Input:
5
Expected Output:
2
Your Output:
2
Test 2
Passed Collapse
Test Input:
25684
Expected Output:
0
Your Output:
0
Problem 2:
You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
• Every post must be painted exactly one color.
• There cannot be three or more consecutive posts with the same color.
Given the two integers n and k, return the number of ways you can paint the fence.
Example 1:
Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.
Example 2:
Input: n = 1, k = 1
Output: 1
Example 3:
Input: n = 7, k = 2
Output: 42
Constraints:
• 1 <= n <= 50
• 1 <= k <= 105
• The testcases are generated such that the answer is in the range [0, 231 - 1] for the given n and k.
Solution:
class Solution {
public int numWays(int n, int k) {
int[] dp = new int[n+2];
dp[0] = 0;
dp[1] = k;
dp[2] = k + k*(k-1);
for (int i = 3; i <=n; i++) {
dp[i] = dp[i-1] * (k-1) + dp[i-2]*(k-1);
}
return dp[n];
}
}
Accepted
Runtime: 0 ms
Case 1
Case 2
Case 3
Input
n =
3
k =
2
Output
6
Expected
6
Input
n =
1
k =
1
Output
1
Expected
1
Input
n =
7
k =
2
Output
42
Expected
42
Problem #3:
Make Array Zero by Subtracting Equal Amounts
You are given a non-negative integer array nums. In one operation, you must:
• Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
• Subtract x from every positive element in nums.
Return the minimum number of operations to make every element in nums equal to 0.
Example 1:
Input: nums = [1,5,0,3,5]
Output: 3
Explanation:
In the first operation, choose x = 1. Now, nums = [0,4,0,2,4].
In the second operation, choose x = 2. Now, nums = [0,2,0,0,2].
In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].
Example 2:
Input: nums = [0]
Output: 0
Explanation: Each element in nums is already 0 so no operations are needed.
Constraints:
• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
import java.util.*;
import java.util.stream.*;
class Solution {
public int minimumOperations(int[] nums) {
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
var nonZero = list.stream().filter(x -> x > 0).collect(Collectors.toList());
int count = 0;
while(nonZero.size() > 0) {
var min = nonZero.stream().mapToInt(x -> x).min().getAsInt();
nonZero = nonZero.stream().map(x -> x - min).filter(x -> x > 0).collect(Collectors.toList());
count++;
}
return count;
}
}
Input
nums =
[1,5,0,3,5]
Output
3
Expected
3
Input
nums =
[0]
Output
0
Expected
0
SQL Schema
Table: Books
+----------------+---------+
| Column Name | Type |
+----------------+---------+
| book_id | int |
| name | varchar |
| available_from | date |
+----------------+---------+
book_id is the primary key of this table.
Table: Orders
+----------------+---------+
| Column Name | Type |
+----------------+---------+
| order_id | int |
| book_id | int |
| quantity | int |
| dispatch_date | date |
+----------------+---------+
order_id is the primary key of this table.
book_id is a foreign key to the Books table.
Write an SQL query that reports the books that have sold less than 10 copies in the last year, excluding books that have been available for less than one month from today. Assume today is 2019-06-23.
Return the result table in any order.
The query result format is in the following example.
Example 1:
Input:
Books table:
+---------+--------------------+----------------+
| book_id | name | available_from |
+---------+--------------------+----------------+
| 1 | "Kalila And Demna" | 2010-01-01 |
| 2 | "28 Letters" | 2012-05-12 |
| 3 | "The Hobbit" | 2019-06-10 |
| 4 | "13 Reasons Why" | 2019-06-01 |
| 5 | "The Hunger Games" | 2008-09-21 |
+---------+--------------------+----------------+
Orders table:
+----------+---------+----------+---------------+
| order_id | book_id | quantity | dispatch_date |
+----------+---------+----------+---------------+
| 1 | 1 | 2 | 2018-07-26 |
| 2 | 1 | 1 | 2018-11-05 |
| 3 | 3 | 8 | 2019-06-11 |
| 4 | 4 | 6 | 2019-06-05 |
| 5 | 4 | 5 | 2019-06-20 |
| 6 | 5 | 9 | 2009-02-02 |
| 7 | 5 | 8 | 2010-04-13 |
+----------+---------+----------+---------------+
Output:
+-----------+--------------------+
| book_id | name |
+-----------+--------------------+
| 1 | "Kalila And Demna" |
| 2 | "28 Letters" |
| 5 | "The Hunger Games" |
+-----------+--------------------+
SELECT DISTINCT b.book_id, b.name
FROM books b
LEFT JOIN Orders o on b.book_id = o.book_id
GROUP BY b.book_id, b.name,
DATEDIFF(day, DATEADD(year, -1, '2019-06-23'), o.dispatch_date),
DATEDIFF(day, b.available_from, DATEADD(month, -1, '2019-06-23'))
HAVING SUM(o.quantity) IS NULL OR
DATEDIFF(day, DATEADD(year, -1, '2019-06-23'), o.dispatch_date) < 0 OR
(DATEDIFF(day, DATEADD(year, -1, '2019-06-23'), o.dispatch_date) > 0 AND DATEDIFF(day, b.available_from, DATEADD(month, -1, '2019-06-23')) > 0 AND SUM(o.quantity) < 10);
Case 1
Input
Books =
| book_id | name | available_from |
| ------- | ---------------- | -------------- |
| 1 | Kalila And Demna | 2010-01-01 |
| 2 | 28 Letters | 2012-05-12 |
| 3 | The Hobbit | 2019-06-10 |
| 4 | 13 Reasons Why | 2019-06-01 |
| 5 | The Hunger Games | 2008-09-21 |
Orders =
| order_id | book_id | quantity | dispatch_date |
| -------- | ------- | -------- | ------------- |
| 1 | 1 | 2 | 2018-07-26 |
| 2 | 1 | 1 | 2018-11-05 |
| 3 | 3 | 8 | 2019-06-11 |
| 4 | 4 | 6 | 2019-06-05 |
| 5 | 4 | 5 | 2019-06-20 |
| 6 | 5 | 9 | 2009-02-02 |
| 7 | 5 | 8 | 2010-04-13 |
Output
| book_id | name |
| ------- | ---------------- |
| 2 | 28 Letters |
| 1 | Kalila And Demna |
| 5 | The Hunger Games |
Expected
| book_id | name |
| ------- | ---------------- |
| 1 | Kalila And Demna |
| 2 | 28 Letters |
| 5 | The Hunger Games |
