Skip to content

Commit 496cbf6

Browse files
EdwardTangYongbing Tang
EdwardTang
and
Yongbing Tang
authored
C3ai (#5)
* c3ai add c3ai phone interview question * autonomic phone interview Co-authored-by: Yongbing Tang <yongbing@lumity.com>
1 parent 9088b34 commit 496cbf6

File tree

5 files changed

+345
-0
lines changed

5 files changed

+345
-0
lines changed

‎src/main/java/com/company/autonomic/phone/MaxDistinctElements.java

+79
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package com.company.autonomic.phone;
2+
3+
import java.util.Collections;
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
import java.util.PriorityQueue;
7+
8+
public class MaxDistinctElements {
9+
10+
/**
11+
* Maximum distinct elements after removing k elements
12+
*
13+
* <p>Given an array arr[] containing n elements. The problem is to find maximum number of
14+
* distinct elements (non-repeating) after removing k elements from the array. Note: 1 <= k <= n.
15+
*
16+
* <p>Examples:
17+
*
18+
* <p>Input : arr[] = {5, 7, 5, 5, 1, 2, 2}, k = 3 Output : 4 Remove 2 occurrences of element 5
19+
* and 1 occurrence of element 2.
20+
*
21+
* <p>Input : arr[] = {1, 2, 3, 4, 5, 6, 7}, k = 5 Output : 2
22+
*
23+
* <p>Input : arr[] = {1, 2, 2, 2}, k = 1 Output : 1
24+
*
25+
* <p>Approach: Following are the steps:
26+
*
27+
* <p>Create a hash table to store the frequency of each element. Insert frequency of each element
28+
* in a max heap. Now, perform the following operation k times. Remove an element from the max
29+
* heap. Decrement its value by 1. After this if element is not equal to 0, then again push the
30+
* element in the max heap. After the completion of step 3, the number of elements in the max heap
31+
* is the required answer.
32+
*
33+
* <p>High level: Reducing the most frequent elements to get max distinct element number. Mid
34+
* -level: Insert the frequencies of each, do K times of reducing the frequency on the top of the
35+
* max heap.
36+
*/
37+
public static int maxDistinctElementNumber(int[] input, int k) {
38+
Map<Integer, Integer> freqMap = new HashMap<>();
39+
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
40+
41+
// Init the frequency map
42+
for (int num : input) {
43+
Integer freq = freqMap.get(num);
44+
if (freq == null) {
45+
freq = 0;
46+
}
47+
freq++;
48+
freqMap.put(num, freq);
49+
}
50+
51+
for (Map.Entry<Integer, Integer> e : freqMap.entrySet()) {
52+
maxHeap.offer(e.getValue());
53+
}
54+
55+
for (int i = k; i > 0; i--) {
56+
Integer freq = maxHeap.poll();
57+
freq--;
58+
if (freq > 0) {
59+
maxHeap.offer(freq);
60+
}
61+
}
62+
return maxHeap.size();
63+
}
64+
65+
public static void main(String[] args) {
66+
int[] arr1 = {5, 7, 5, 5, 1, 2, 2};
67+
int k1 = 3;
68+
int[] arr2 = {1, 2, 3, 4, 5, 6, 7};
69+
int k2 = 5;
70+
int[] arr3 = {1, 2, 2, 2};
71+
int k3 = 1;
72+
System.out.println(
73+
"For arr1 and k1 Maximum distinct elements = " + maxDistinctElementNumber(arr1, k1));
74+
System.out.println(
75+
"For arr2 and k2 Maximum distinct elements = " + maxDistinctElementNumber(arr2, k2));
76+
System.out.println(
77+
"For arr3 and k3 Maximum distinct elements = " + maxDistinctElementNumber(arr3, k3));
78+
}
79+
}

‎src/main/java/com/company/c3ai/phone/CounterVirus.java

+64
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.company.c3ai.phone;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
public class CounterVirus {
8+
9+
public static void main(String[] args) {
10+
int[] tcpPacket = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
11+
System.out.println(Arrays.toString(tcpPacket));
12+
iAmVirus(tcpPacket);
13+
System.out.println(Arrays.toString(tcpPacket));
14+
findComplementIndex(tcpPacket).forEach(i -> System.out.print(i + " "));
15+
System.out.println();
16+
changeMeBack(tcpPacket);
17+
System.out.println(Arrays.toString(tcpPacket));
18+
}
19+
20+
private static void iAmVirus(int[] tcpPacket) {
21+
int n = tcpPacket.length;
22+
for (int i = 0; i < n; i++) {
23+
for (int j = 0; j < n; j++) {
24+
if ((i + 1) * (j + 1) <= n) {
25+
tcpPacket[(i + 1) * (j + 1) - 1] = complement(tcpPacket[(i + 1) * (j + 1) - 1]);
26+
// System.out.print(Arrays.toString(tcpPacket));
27+
// System.out.print(" ");
28+
// System.out.println((i + 1) * (j + 1));
29+
} else {
30+
break;
31+
}
32+
}
33+
}
34+
}
35+
36+
private static int complement(int i) {
37+
return i == 0 ? 1 : 0;
38+
}
39+
40+
private static List<Integer> findComplementIndex(int[] tcpPacket) {
41+
List<Integer> res = new ArrayList<>();
42+
for (int i = 0; i < tcpPacket.length; i++) {
43+
if (tcpPacket[i] == 1) {
44+
res.add(i);
45+
}
46+
}
47+
return res;
48+
}
49+
50+
/**
51+
* Complement the digit at 0,3,8,15,24.....
52+
* @param tcpPacket given tcp packet
53+
*/
54+
private static void changeMeBack(int[] tcpPacket) {
55+
// write your code here
56+
int index = 0;
57+
int i = 1;
58+
while (index < tcpPacket.length) {
59+
tcpPacket[index] = complement(tcpPacket[index]);
60+
index += i * 2 + 1;
61+
i++;
62+
}
63+
}
64+
}

‎src/main/java/com/company/servicenow/phone/SliceMatrix.java

+75
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.company.servicenow.phone;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
public class SliceMatrix {
7+
8+
/**
9+
* Write a function to slice the matrix with given row numbers and given columns numbers
10+
*/
11+
public static void main(String[] args) {
12+
int[][] test =
13+
new int[][] {
14+
new int[] {1, 1, 1, 1},
15+
new int[] {0, 0, 0, 0},
16+
new int[] {2, 1, 3, 3},
17+
new int[] {1, 2, 4, 4}
18+
};
19+
int[] rows = new int[] {0, 1};
20+
int[] cols = new int[] {1, 2};
21+
// rows
22+
// 0 [1 1 1 1
23+
// 1 0 0 0 0
24+
// 2 1 3 3 ==> [2 3
25+
// 1 2 4 4] 1 4]
26+
// cols 1 2
27+
int[][] result = findSlicedMatrix(test, rows, cols);
28+
for (int[] r : result) {
29+
for (int num : r) {
30+
System.out.print(num + " ");
31+
}
32+
System.out.println();
33+
}
34+
}
35+
36+
/**
37+
* Assumption: M, rows, cols are not null nor empty.
38+
* High level: use set to check if current row or column should be skipped. Use pointer to create new result 2D-array
39+
* Time: (N*M), Space(rows.length + cols.length)
40+
*/
41+
public static int[][] findSlicedMatrix(int[][] M, int[] rows, int[] cols) {
42+
// todo: validate input
43+
int totalRows = M.length;
44+
int totalCols = M[0].length;
45+
int remainRows = totalRows - rows.length;
46+
int remainCols = totalCols - cols.length;
47+
int[][] res = new int[remainRows][remainCols];
48+
49+
// find the remaining row index and col index in rows and cols,
50+
Set<Integer> slicedRows = new HashSet<>();
51+
Set<Integer> slicedCols = new HashSet<>();
52+
53+
for (int row : rows) {
54+
slicedRows.add(row);
55+
}
56+
for (int col : cols) {
57+
slicedCols.add(col);
58+
}
59+
60+
for (int i = 0, curRow = 0; i < totalRows; i++) {
61+
if (!slicedRows.contains(i)) {
62+
for (int j = 0, curCol = 0; j < totalCols; j++) {
63+
if (!slicedCols.contains(j)) {
64+
if (curRow < remainRows && curCol < remainCols) {
65+
res[curRow][curCol] = M[i][j];
66+
}
67+
curCol++;
68+
}
69+
}
70+
curRow++;
71+
}
72+
}
73+
return res;
74+
}
75+
}

‎src/main/java/com/laioffer/dfs/StringPermutationWithDupChars.java

+34
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.laioffer.dfs;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/*
7+
Assumption: (1) given input is char array ahd not null, not empty (2) output is a list of all permutation Strings
8+
High level: use DFS to traverse all permutations. (1) N levels of recursion tree, each level represents one position. (2) at each level, we need traverse each node with remaining unused letters: i-th level, each node: (n - i) branches
9+
Recursion tree:
10+
root = aab
11+
/ | \
12+
i = 0, 1, 2 swap(0,0). swap(0,1) swap(0, 2)
13+
position 0 **a**ab ~~**a**ab~~ **b**aa n = 3
14+
/ \ / \ / \
15+
i = 1, 2 swap(1,1) swap(1,2) swap(1,1) swap(1,2)
16+
position 1 a**a**b a**b**a ~~a**a**b a**b**a~~ b**a**a. ~~b**a**a~~ * (3-1)
17+
| | | | | |
18+
i = 2 swap(2,2) swap(2,2)
19+
position 2 aa**b** ab**a** ~~aa**b** ab**a**~~ ba**a** ~~ba**a**~~ * (3 - 2)
20+
clone each string at position 2: O(n) * O(n!) brances
21+
Time: O(N!*N), Space(the height of the recursion tree) = O(N)
22+
*/
23+
public class StringPermutationWithDupChars {
24+
public static List<String> findPermutations(char[] input) {
25+
List<String> result = new ArrayList<>();
26+
dfs(input, 0, result);
27+
return result;
28+
}
29+
30+
public static void dfs(char[] input, int index, List<String> result) {
31+
32+
}
33+
}
34+

‎src/main/java/com/laioffer/dfs/_99Cents.java

+93
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package com.laioffer.dfs;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class _99Cents {
7+
8+
/**
9+
* Given a number of different denominations of coins (e.g., 1 cent, 5 cents, 10 cents, 25 cents),
10+
* get all the possible ways to pay a target number of cents.
11+
*
12+
* <p>Arguments
13+
*
14+
* <p>coins - an array of positive integers representing the different denominations of coins,
15+
* there are no duplicate numbers and the numbers are sorted by descending order, eg. {25, 10, 5,
16+
* 2, 1} target - a non-negative integer representing the target number of cents, eg. 99
17+
* Assumptions
18+
*
19+
* <p>coins is not null and is not empty, all the numbers in coins are positive target >= 0 You
20+
* have infinite number of coins for each of the denominations, you can pick any number of the
21+
* coins. Return
22+
*
23+
* <p>a list of ways of combinations of coins to sum up to be target. each way of combinations is
24+
* represented by list of integer, the number at each index means the number of coins used for the
25+
* denomination at corresponding index. Examples
26+
*
27+
* <p>coins = {2, 1}, target = 4, the return should be
28+
*
29+
* <p>[
30+
*
31+
* <p>[0, 4], (4 cents can be conducted by 0 * 2 cents + 4 * 1 cents)
32+
*
33+
* <p>[1, 2], (4 cents can be conducted by 1 * 2 cents + 2 * 1 cents)
34+
*
35+
* <p>[2, 0] (4 cents can be conducted by 2 * 2 cents + 0 * 1 cents)
36+
*
37+
* <p>]
38+
*/
39+
public static void main(String[] args) {
40+
int[] coin = new int[] {25, 10, 5, 1};
41+
findCoinCombination(coin, 99, 0, new int[4]);
42+
List<List<Integer>> result = combinations(99, coin);
43+
}
44+
45+
public static List<List<Integer>> combinations(int target, int[] coins) {
46+
List<List<Integer>> result = new ArrayList<List<Integer>>();
47+
List<Integer> cur = new ArrayList<Integer>();
48+
helper(target, coins, 0, cur, result);
49+
return result;
50+
}
51+
52+
private static void helper(
53+
int target, int[] coins, int index, List<Integer> cur, List<List<Integer>> result) {
54+
if (index == coins.length - 1) {
55+
if (target % coins[coins.length - 1] == 0) {
56+
cur.add(target / coins[coins.length - 1]);
57+
result.add(new ArrayList<Integer>(cur));
58+
cur.remove(cur.size() - 1);
59+
}
60+
return;
61+
}
62+
int max = target / coins[index];
63+
for (int i = 0; i <= max; i++) {
64+
cur.add(i);
65+
helper(target - i * coins[index], coins, index + 1, cur, result);
66+
cur.remove(cur.size() - 1);
67+
}
68+
}
69+
70+
public static void findCoinCombination(int[] coin, int moneyLeft, int index, int[] sol) {
71+
if (index == 3) {
72+
sol[index] = moneyLeft;
73+
printSol(sol, coin);
74+
return;
75+
}
76+
77+
for (int i = 0; i <= moneyLeft / coin[index]; i++) {
78+
sol[index] = i;
79+
findCoinCombination(coin, moneyLeft - i * coin[index], index + 1, sol);
80+
}
81+
}
82+
83+
private static void printSol(int[] sol, int[] coin) {
84+
StringBuilder sb = new StringBuilder();
85+
for (int i = 0; i < sol.length; i++) {
86+
sb.append(sol[i]);
87+
sb.append('x');
88+
sb.append(coin[i]);
89+
sb.append(" cent ");
90+
}
91+
System.out.println(sb.toString());
92+
}
93+
}

0 commit comments

Comments
 (0)