#codingexercise
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i]
= [numberOfBoxesi, numberOfUnitsPerBoxi]:
- numberOfBoxesi is the number of boxes of
type i.
- numberOfUnitsPerBoxi is the
number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number
of boxes that can be put on the truck. You can choose
any boxes to put on the truck as long as the number of boxes does not
exceed truckSize.
Return the maximum total
number of units that can be put on the truck.
Example 1:
Input: boxTypes =
[[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation:
There are:
- 1
box of the first type that contains 3 units.
- 2
boxes of the second type that contain 2 units each.
- 3
boxes of the third type that contain 1 unit each.
You
can take all the boxes of the first and second types, and one box of the third
type.
The
total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes =
[[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Constraints:
- 1
<= boxTypes.length <= 1000
- 1
<= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
- 1
<= truckSize <= 106
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
var boxMap = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < boxTypes.length; i++) {
var type = boxTypes[i][0];
var countOfUnits = boxTypes[i][1];
if (boxMap.containsKey(countOfUnits)){
var list = boxMap.get(countOfUnits);
list.add(type);
boxMap.put(countOfUnits, list);
} else {
var list = new ArrayList<Integer>();
list.add(type);
boxMap.put(countOfUnits, list);
}
}
int total = 0;
int totalUnits = 0;
for (var entry : boxMap.descendingMap().entrySet()){
var countOfUnits = entry.getKey();
var types = entry.getValue();
for (var type : types){
if (total + 1 <= truckSize) {
for (int i = 0; i < type && total < truckSize;
i++) {
total += 1;
totalUnits += 1 * countOfUnits;
}
} else {
return totalUnits;
}
}
}
return totalUnits;
}
}
Input
boxTypes =
[[1,3],[2,2],[3,1]]
truckSize =
4
Output
8
Expected
8
Input
boxTypes =
[[5,10],[2,5],[4,7],[3,9]]
truckSize =
10
Output
91
Expected
91
You are given a 0-indexed
integer array nums.
Swaps of adjacent elements are able to be performed on nums.
A valid array meets the
following conditions:
·
The largest element (any
of the largest elements if there are multiple) is at the rightmost position in
the array.
·
The smallest element (any
of the smallest elements if there are multiple) is at the leftmost position in
the array.
Return the minimum swaps
required to make nums a valid array.
Example 1:
Input:
nums = [3,4,5,5,3,1]
Output:
6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd
and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th
and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd
and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd
and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st
and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th
and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum
swaps required to make a valid array.
Example 2:
Input:
nums = [9]
Output:
0
Explanation: The array is already valid, so we return 0.
Constraints:
·
1 <= nums.length <= 105
·
1 <= nums[i] <= 105
class Solution {
public int minimumSwaps(int[] nums) {
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
int count = 0;
while
(nums[0] !=
min && nums[nums.length-1] !=
max && count < 2 * nums.length)
{
var numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
var end = numsList.lastIndexOf(max);
for (int i =
end; i < nums.length-1; i++)
{
swap(nums, i, i+1);
count++;
}
numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
var start = numsList.indexOf(min);
for (int j =
start; j >= 1; j--) {
swap(nums, j, j-1);
count++;
}
}
return
count;
}
public void swap (int[] nums, int i, int j) {
int temp =
nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
Input
nums =
[3,4,5,5,3,1]
Output
6
Expected
6
Input
nums =
[9]
Output
0
Expected
0
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i]
= [numberOfBoxesi, numberOfUnitsPerBoxi]:
- numberOfBoxesi is the number of boxes of
type i.
- numberOfUnitsPerBoxi is the
number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number
of boxes that can be put on the truck. You can choose
any boxes to put on the truck as long as the number of boxes does not
exceed truckSize.
Return the maximum total
number of units that can be put on the truck.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]],
truckSize = 4
Output: 8
Explanation: There are:
- 1
box of the first type that contains 3 units.
- 2
boxes of the second type that contain 2 units each.
- 3
boxes of the third type that contain 1 unit each.
You
can take all the boxes of the first and second types, and one box of the third
type.
The
total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes =
[[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91
Constraints:
- 1
<= boxTypes.length <= 1000
- 1
<= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
- 1
<= truckSize <= 106
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
var boxMap = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < boxTypes.length; i++) {
var type = boxTypes[i][0];
var countOfUnits = boxTypes[i][1];
if (boxMap.containsKey(countOfUnits)){
var list = boxMap.get(countOfUnits);
list.add(type);
boxMap.put(countOfUnits, list);
} else {
var list = new ArrayList<Integer>();
list.add(type);
boxMap.put(countOfUnits, list);
}
}
int total = 0;
int totalUnits = 0;
for (var entry : boxMap.descendingMap().entrySet()){
var countOfUnits = entry.getKey();
var types = entry.getValue();
for (var type : types){
if (total + 1 <= truckSize) {
for (int i = 0; i < type && total < truckSize;
i++) {
total += 1;
totalUnits += 1 * countOfUnits;
}
} else {
return totalUnits;
}
}
}
return totalUnits;
}
}
Given a string s, rearrange the
characters of s so that any two adjacent characters are
not the same.
Return any possible rearrangement
of s or return "" if not possible.
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
Constraints:
- 1
<= s.length <= 500
- s consists of lowercase English letters.
class Solution {
public String reorganizeString(String s) {
String result = "";
Map<Character, Integer> charMap = new HashMap<Character, Integer>();
for(Character c : s.toCharArray()) {
if (charMap.containsKey(c)) {
charMap.put(c, charMap.get(c) + 1);
} else {
charMap.put(c, 1);
}
}
int countOfDuplicates = 0;
TreeMap<Integer, List<Character>> countMap = new TreeMap<Integer, List<Character>>();
for (var entry : charMap.entrySet()) {
if (entry.getValue() > 1){
countOfDuplicates += (int)entry.getValue() - 1;
}
if (countMap.containsKey(entry.getValue())) {
countMap.get(entry.getValue()).add(entry.getKey());
} else {
var list = new ArrayList<Character>();
list.add(entry.getKey());
countMap.put(entry.getValue(), list);
}
}
System.out.println(countMap);
if (countMap.firstEntry().getKey() > 1 && countMap.firstEntry().getValue().size() == 1) {
var firstEntry = countMap.firstEntry();
var secondEntry = countMap.higherEntry(firstEntry.getKey());
if (secondEntry != null) {
int diff = secondEntry.getKey() - firstEntry.getKey();
countMap.remove(firstEntry.getKey());
countMap.remove(secondEntry.getKey());
var list = new ArrayList<Character>();
list.addAll(secondEntry.getValue());
list.addAll(firstEntry.getValue());
countMap.put(firstEntry.getKey(), list);
countMap.put(diff, secondEntry.getValue());
}
}
System.out.println(countMap);
StringBuilder sb = new StringBuilder();
while (countMap.size() > 0) {
var entry = countMap.pollLastEntry();
int occurrence = 0;
while (entry != null && entry.getValue().size() > 1) {
for (int i = 0; i < entry.getKey(); i++) {
occurrence++;
for (int j = 0; j < entry.getValue().size(); j++) {
sb.append(entry.getValue().get(j));
}
}
entry.getValue().clear();
}
while(entry != null && entry.getValue().size() == 1) {
var last = entry.getValue().get(0);
int accounted = 0;
int lastEntryCount = entry.getKey() - occurrence;
System.out.println("occurrence=" + occurrence);
if (countMap.size() == 0 && lastEntryCount > 1) {
return "";
}
while (lastEntryCount > 0){
var lastEntry = countMap.lastEntry();
while (lastEntry != null && lastEntry.getValue().size() > 0) {
int secondLastEntryCount = lastEntry.getKey();
var secondLast = lastEntry.getValue().remove(0);
while (lastEntryCount > 0 && secondLastEntryCount
> 0) {
sb.append(last);
sb.append(secondLast);
lastEntryCount--;
occurrence++;
secondLastEntryCount--;
}
if (secondLastEntryCount > 0) {
var list = countMap.get(secondLastEntryCount);
if (list == null) {
list = new ArrayList<Character>();
}
list.add(secondLast);
countMap.put(secondLastEntryCount, list);
break;
}
}
if (lastEntryCount == 1){
sb.append(last);
lastEntryCount--;
occurrence++;
}
if (lastEntry != null && lastEntry.getValue().size() == 0) {
countMap.remove(lastEntry.getKey());
}
if (lastEntryCount == 0) {
countMap.remove(entry.getKey());
entry.getValue().clear();
}
if (lastEntryCount > 0 && countMap.size() == 0) {
return "";
}
}
}
}
result = sb.toString();
for (int i = 1; i < sb.length(); i++) {
if (sb.charAt(i-1) == sb.charAt(i)) {
return "";
}
}
return result;
}
}
Input
s =
"kkkkzrkatkwpkkkktrq"
Output
"krkrktktkpkakqkwkzk"
Expected
"krkrktktkakpkqkwkzk"
Stdout
{1=[p, a, q, w, z], 2=[r, t], 10=[k]} 10 [k] countMap={1=[p, a, q, w, z],
2=[r, t]} last=k occurrence=0
lastEntry=2=[r, t] kr 2=[t] 9 1 krkr 2=[t] 8 0 secondLastEntryCount=0 and
secondLast=r lastEntryCount=8 krkrkt 2=[] 7 1 krkrktkt 2=[] 6 0
secondLastEntryCount=0 and secondLast=t lastEntryCount=6 lastEntry=1=[p, a, q,
w, z] krkrktktkp 1=[a, q, w, z] 5 0 secondLastEntryCount=0 and secondLast=p
lastEntryCount=5 krkrktktkpka 1=[q, w, z] 4 0 secondLastEntryCount=0 and
secondLast=a lastEntryCount=4 krkrktktkpkakq 1=[w, z] 3 0
secondLastEntryCount=0 and secondLast=q lastEntryCount=3 krkrktktkpkakqkw 1=[z]
2 0 secondLastEntryCount=0 and secondLast=w lastEntryCount=2 krkrktktkpkakqkwkz
1=[] 1 0 secondLastEntryCount=0 and secondLast=z lastEntryCount=1
krkrktktkpkakqkwkzk
