Walmart Labs Interview Question
Java DevelopersCountry: United States
Interview Type: In-Person
Example 1 is wrong. '2' only occurs ones and example counter it twice. It should be 4 arrows:
5-4-3-2-1
3
1
1
This is the code maybe it helps, i am new to CC
public static void main(String[] args) throws IOException {
// Scanner scanner = new Scanner(System.in);
// 5 4 3 3 2 1 1 1
int count = 0;
// int[] nums = {5, 4, 3, 3, 2, 1, 1, 1};
int[] nums ={5,4,2,1};
int mazx = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > mazx) {
mazx = nums[i];
}
}
int[] newNums = new int[nums.length];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
int a = nums[i];
if ((nums[i + 1] == a + 1) && (nums[i + 1] < nums.length - 1)) {
count++;
} else if (nums[i + 1] == a) {
i++;
} else if (nums[i + 1] != a + 1) {
count++;
}
}
System.out.println(count);
}
}
O(n) time O(1) space
#include <bits/stdc++.h>
using namespace std;
int min_c(vector< int > &A){
int ans = 0;
int p_c = 0;
int c_c = 0;
int n = A.size();
for(int i = 0; i < n; ++i){
if(i > 0 and A[i - 1] - A[i] > 1){
ans += max(0, c_c - p_c);
p_c = 0;
c_c = 0;
} else if(i > 0 and (A[i] != A[i - 1])){
ans += max(0, c_c - p_c);
p_c = c_c;
c_c = 0;
}
++c_c;
if(i == n - 1){
ans += max(0, c_c - p_c);
}
}
return ans;
}
int main(){
vector< int > test_1 {5, 4, 3, 3, 2, 2, 1, 1, 1};
vector< int > test_2 {5, 4, 2, 1};
cout << min_c(test_1) << endl;
cout << min_c(test_2) << endl;
return 0;
}
public class BalloonsProblem {
public static void main(String[] args) {
int[] arr1 = { 5, 4, 3, 3, 2, 2, 1, 1, 1 };
int[] arr2 = { 5, 4, 2, 1 };
System.out.println(findSol(arr1));
}
private static int findSol(int[] arr) {
if (arr.length == 0)
return 0;
int sameNo = 0;
int seq = 1; // if array is not empty then there will be 1 sequence by default
int prev = 0; // to keep track of number of repeated numbers.
for (int i = 1; i < arr.length; i++) {
// when there is break b/w numbers.
if (arr[i - 1] - arr[i] > 1) {
seq++;
}
// when number or equal its the same number, hence we can form another set with this.
if (arr[i] == arr[i - 1])
sameNo++;
if (arr[i] != arr[i - 1])
sameNo = 0;
if (prev < sameNo)
prev = sameNo;
}
// combine both break in sequence and same numbers.
return (seq + prev);
}
}
public class BallonsProblem {
public static void main(String[] args) {
int[] arr1 = { 5, 4, 3, 3, 2, 2, 1, 1, 1 };
int[] arr2 = { 5, 4, 2, 1 };
System.out.println(findSol(arr1));
}
private static int findSol(int[] arr) {
if (arr.length == 0)
return 0;
int sameNo = 0;
int seq = 1; // if array is not empty then there will be 1 sequence by default
int prev = 0; // to keep track of number of repeated numbers.
for (int i = 1; i < arr.length; i++) {
// when there is break b/w numbers.
if (arr[i - 1] - arr[i] > 1) {
seq++;
}
// when number or equal its the same number, hence we can form another set with this.
if (arr[i] == arr[i - 1])
sameNo++;
if (arr[i] != arr[i - 1])
sameNo = 0;
if (prev < sameNo)
prev = sameNo;
}
// combine both break in sequence and same numbers.
return (seq + prev);
}
}
public class BallonsProblem {
public static void main(String[] args) {
int[] arr1 = { 5, 4, 3, 3, 2, 2, 1, 1, 1 };
int[] arr2 = { 5, 4, 2, 1 };
System.out.println(findSol(arr1));
}
private static int findSol(int[] arr) {
if (arr.length == 0)
return 0;
int sameNo = 0;
int seq = 1; // if array is not empty then there will be 1 sequence by default
int prev = 0; // to keep track of number of repeated numbers.
for (int i = 1; i < arr.length; i++) {
// when there is break b/w numbers.
if (arr[i - 1] - arr[i] > 1) {
seq++;
}
// when number or equal its the same number, hence we can form another set with this.
if (arr[i] == arr[i - 1])
sameNo++;
if (arr[i] != arr[i - 1])
sameNo = 0;
if (prev < sameNo)
prev = sameNo;
}
// combine both break in sequence and same numbers.
return (seq + prev);
}
}
public class BallonsProblem {
public static void main(String[] args) {
int[] arr1 = { 5, 4, 3, 3, 2, 2, 1, 1, 1 };
int[] arr2 = { 5, 4, 2, 1 };
System.out.println(findSol(arr1));
}
private static int findSol(int[] arr) {
if (arr.length == 0)
return 0;
int sameNo = 0;
int seq = 1; // if array is not empty then there will be 1 sequence by default
int prev = 0; // to keep track of number of repeated numbers.
for (int i = 1; i < arr.length; i++) {
// when there is break b/w numbers.
if (arr[i - 1] - arr[i] > 1) {
seq++;
}
// when number or equal its the same number, hence we can form another set with this.
if (arr[i] == arr[i - 1])
sameNo++;
if (arr[i] != arr[i - 1])
sameNo = 0;
if (prev < sameNo)
prev = sameNo;
}
// combine both break in sequence and same numbers.
return (seq + prev);
}
}
package com.test.src;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BallonBustingAlgo {
public static void main(String... args) {
List<Integer> sortedList = Arrays.asList(args[0].split("")).stream().map(str -> Integer.parseInt(str.trim()))
.sorted((i1, i2) -> i2.compareTo(i1)).collect(Collectors.toList());
Integer noOfArrows = countArrowsToBurstBalloons(sortedList, 0);
System.out.println(noOfArrows);
}
public static Integer countArrowsToBurstBalloons(List<Integer> bList, Integer noOfArrows) {
if (bList == null || bList.isEmpty())
return noOfArrows;
noOfArrows++;
// burst 1st balloon
bList.remove(0);
bList = bList.stream().map(ballon -> {
if (ballon > 1)
return ballon - 1;
else
return null;
}).filter(ballon -> ballon != null).collect(Collectors.toList());
return countArrowsToBurstBalloons(bList, noOfArrows);
}
}
package com.test.src;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BallonBustingAlgo {
public static void main(String... args) {
List<Integer> sortedList = Arrays.asList(args[0].split("")).stream().map(str -> Integer.parseInt(str.trim()))
.sorted((i1, i2) -> i2.compareTo(i1)).collect(Collectors.toList());
Integer noOfArrows = countArrowsToBurstBalloons(sortedList, 0);
System.out.println(noOfArrows);
}
public static Integer countArrowsToBurstBalloons(List<Integer> bList, Integer noOfArrows) {
if (bList == null || bList.isEmpty())
return noOfArrows;
noOfArrows++;
// burst 1st balloon
bList.remove(0);
bList = bList.stream().map(ballon -> {
if (ballon > 1)
return ballon - 1;
else
return null;
}).filter(ballon -> ballon != null).collect(Collectors.toList());
return countArrowsToBurstBalloons(bList, noOfArrows);
}
}
/**
* Complexity is O(n)
* @author Omid Ghiasi Tarzi
*/
static int arrowCount(List<Integer> list){
int arrow=list.get(0);
int arrows=1;
int pararelArrows=0;
int max=0;
for(int i=0; i<list.size();i++){
int diff=list.get(i)-arrow;
if(diff==0){
arrow--;
pararelArrows=0;
continue;
}
else if(diff==1){
pararelArrows++;
if(max<pararelArrows){
max=pararelArrows;
arrows++;
}
}
else {
max=0;
arrows++;
}
arrow=list.get(i)-1;
}
return arrows;
}
public static int minArrows(int arr[])
{
if (arr.length == 0)
return 0;
int arrows = 1;
int lastRepeatedNo = -1;
int lastRepeatations = 0;
int currrepeatations = 0;
for (int i = 1; i < arr.length; i++)
{
if (arr[i] == arr[i-1])
{
currrepeatations++;
}
else
{
if (arr[i] - arr[i-1] > 1)
{
arrows += 1;
}
if (currrepeatations != 0)
{
if (lastRepeatations != 0)
{
if (lastRepeatedNo - arr[i-1]!= 1)
{
arrows += lastRepeatations;
}
else if (lastRepeatations > currrepeatations)
{
arrows += (lastRepeatations - currrepeatations);
}
}
lastRepeatations = currrepeatations;
lastRepeatedNo = arr[i-1];
currrepeatations = 0;
}
}
}
return arrows + (currrepeatations == 0 ? lastRepeatations: currrepeatations);
}
//after sorting the array in descending order
//if 2 consecutive elements difference is greater than 1 than they are in 2 different continent
// in each continent find the max occurence of same number
// summing the all max occurence in each continent is the ans
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll x,i,j,k,n,p,f,t;
cin>>n;
ll a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n,greater<int>());
ll ma=0,same=1,arrow=0;
f=0;
for(i=0;i<n-1;i++)
{
if(a[i]-a[i+1]>1)
{
if(f==2)
{
if(same>ma)
ma=same;
}
arrow+=ma;
ma=0;
same=1;
f=1;
}
else
{
if(a[i]==a[i+1]){
same++;
f=2;
}
else
{
if(ma<same)
ma=same;
same=1;
f=3;
}
}
}
if(f==1)arrow++;
else if(f==2)
{
if(ma<same)
ma=same;
arrow+=ma;
}
else if(f==3)arrow+=ma;
cout<<arrow<<"\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
int a[N];
int main() {
int n;
cin >> n;
for (int i=0;i<n;i++) {
cin >> a[i];
}
unordered_map<int, int> mp;
mp.clear();
for (int i=0;i<n;i++){
mp[a[i]]++;
}
int ans = 0;
for (int i = 0; i < n; i++){
if(mp[a[i]] > 0) {//Frequency is +ve
++ans;
int x = a[i];
while(mp[x] > 0) {
if(mp[x] == 1)
mp.erase(x);
else
mp[x]--;
x--;
}
}
}
cout << ans;
return 0;
}
- nelavelli.c@gmail.com June 30, 2019