Walmart Labs Interview Question Software Developers
Country: India
Interview Type: In-Person
package com.eb.corealgo;
public class AfterBiggest {
public int[] getNextBigCount(int [] input){
int l=input.length;
int output[]=new int[l];
for(int i=0;i<l;i++){
int c=input[i];
int co=0;
for(int j=i;j<l;j++){
if(input[j]>c){
co++;
}
}
output[i]=co;
}
return output;
}
public static void main(String args[]){
AfterBiggest big=new AfterBiggest();
int inp[]={5,3,9,8,2,6};
int out[]=big.getNextBigCount(inp);
for(int i:out){
System.out.println(i);
}
}
}
package com.eb.corealgo;
public class AfterBiggest {
public int[] getNextBigCount(int [] input){
int l=input.length;
int output[]=new int[l];
for(int i=0;i<l;i++){
int c=input[i];
int co=0;
for(int j=i;j<l;j++){
if(input[j]>c){
co++;
}
}
output[i]=co;
}
return output;
}
public static void main(String args[]){
AfterBiggest big=new AfterBiggest();
int inp[]={5,3,9,8,2,6};
int out[]=big.getNextBigCount(inp);
for(int i:out){
System.out.println(i);
}
}
}
As mentioned before we can get an average case of O(N*LogN) but still a O(N^2) in the worst case.
The idea is to based on which direction you move in the BST you'll cache the number of values more than.
I think there might be better way to do this but so far I though about using the BST.
For simplicity I'll assume that the numbers are unique.
class Node
{
int Data;
int RightCount = 0;
int MoreThanCount = 0;
Node Left = null;
Node Rigth = null;
}
public IEnumerable<int> FindMorethanAfter(int[] A)
{
if(A.Length == 0) yield break;
var root = new Node() { Data = A[A.Length -1] };
var map = new Dictionary<int,
for(int i = A.Length - 2; i >= 0; i--)
{
var cur = root;
var node = new Node() { Data = A[i] };
while(true)
{
if(cur.Data < node.Data)
{
cur.RightCount++;
if(cur.Rigth == null)
{
cur.Right = node;
map.Add(node.Data, node);
break;
}
cur = cur.Right;
}
else if(cur.Data > node.Data)
{
node.MoreThanCount += cur.RightCount;
node.MoreThanCount++;
if(cur.Left == null)
{
cur.Left = node;
map.Add(node.Data, node);
break;
}
cur = cur.Left;
}
}
}
foreach(var a in A)
{
yield return map[a].MoreThanCount;
}
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k,x;
cin>>n>>k;
int a[n];
int ans[n];
multiset<int> st;
for(int i=0;i<n;i++)
{
cin>>a[i];
st.insert(a[i]);
}
for(int i=0;i<n;i++)
{
ans[i]=st.size()-distance(st.begin(),st.find(a[i]))-1;
st.erase(st.find(a[i]));
}
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
Simply try this
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k,x;
cin>>n>>k;
int a[n];
int ans[n];
multiset<int> st;
for(int i=0;i<n;i++)
{
cin>>a[i];
st.insert(a[i]);
}
for(int i=0;i<n;i++)
{
ans[i]=st.size()-distance(st.begin(),st.find(a[i]))-1;
st.erase(st.find(a[i]));
}
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
Theres a way to make it O(NlogN) even in the worst case.
Compress the data using a mapping of the array to a range of [0...N].
Insert from left to right into a segment tree, each time querying the number of elements in the segment tree from the range [map[a[i]], N].
Each query is O(logN), we perform N queries, for a total complexity of O(NlogN)
#include <stdio.h>
void main()
{
int a[]={5,3,9,8,2,6};
int count=0;
int i=0;
int j=0;
int total_elements=sizeof(a)/sizeof(a[i]);
printf("\n Total_elements=%d \n",total_elements);
int b[total_elements];
for( i = 0 ; i < total_elements; i++ )
{
b[i]=0;
}
for(i=0;i<total_elements-1;i++)
{
for(j=i+1;j<=total_elements-1;j++)
{
printf("\n comparision between a[i]=%d a[j]=%d \n",a[i],a[j]);
if(a[i]<a[j])
{
count++;
b[i]=count;
}
}
count=0;
}
for( i = 0 ; i < total_elements; i++ )
{
printf("%d ", b[i]);
}
printf("\n");
}
#include <stdio.h>
void main()
{
int a[]={5,3,9,8,2,6};
int count=0;
int i=0;
int j=0;
int total_elements=sizeof(a)/sizeof(a[i]);
printf("\n Total_elements=%d \n",total_elements);
int b[total_elements];
for( i = 0 ; i < total_elements; i++ )
{
b[i]=0;
}
for(i=0;i<total_elements-1;i++)
{
for(j=i+1;j<=total_elements-1;j++)
{
printf("\n comparision between a[i]=%d a[j]=%d \n",a[i],a[j]);
if(a[i]<a[j])
{
count++;
b[i]=count;
}
}
count=0;
}
for( i = 0 ; i < total_elements; i++ )
{
printf("%d ", b[i]);
}
printf("\n");
}
#include <stdio.h>
void main()
{
int a[]={5,3,9,8,2,6};
int count=0;
int i=0;
int j=0;
int total_elements=sizeof(a)/sizeof(a[i]);
printf("\n Total_elements=%d \n",total_elements);
int b[total_elements];
for( i = 0 ; i < total_elements; i++ )
{
b[i]=0;
}
for(i=0;i<total_elements-1;i++)
{
for(j=i+1;j<=total_elements-1;j++)
{
printf("\n comparision between a[i]=%d a[j]=%d \n",a[i],a[j]);
if(a[i]<a[j])
{
count++;
b[i]=count;
}
}
count=0;
}
for( i = 0 ; i < total_elements; i++ )
{
printf("%d ", b[i]);
}
printf("\n");
}
#include <stdio.h>
void main()
{
int a[]={5,3,9,8,2,6};
int count=0;
int i=0;
int j=0;
int total_elements=sizeof(a)/sizeof(a[i]);
printf("\n Total_elements=%d \n",total_elements);
int b[total_elements];
for( i = 0 ; i < total_elements; i++ )
{
b[i]=0;
}
for(i=0;i<total_elements-1;i++)
{
for(j=i+1;j<=total_elements-1;j++)
{
printf("\n comparision between a[i]=%d a[j]=%d \n",a[i],a[j]);
if(a[i]<a[j])
{
count++;
b[i]=count;
}
}
count=0;
}
for( i = 0 ; i < total_elements; i++ )
{
printf("%d ", b[i]);
}
printf("\n");
}
#include <stdio.h>
void main()
{
int a[]={5,3,9,8,2,6};
int count=0;
int i=0;
int j=0;
int total_elements=sizeof(a)/sizeof(a[i]);
printf("\n Total_elements=%d \n",total_elements);
int b[total_elements];
for( i = 0 ; i < total_elements; i++ )
{
b[i]=0;
}
for(i=0;i<total_elements-1;i++)
{
for(j=i+1;j<=total_elements-1;j++)
{
printf("\n comparision between a[i]=%d a[j]=%d \n",a[i],a[j]);
if(a[i]<a[j])
{
count++;
b[i]=count;
}
}
count=0;
}
for( i = 0 ; i < total_elements; i++ )
{
printf("%d ", b[i]);
}
printf("\n");
import java.util.Scanner;
public class NumberCount {
public static void numbercount(){
Scanner s = new Scanner(System.in);
int k=0;
System.out.print("Enter n");
int n = s.nextInt();
System.out.println("Enter Array:");
int a[] = new int[n];
for(int i =0;i<n;i++){
a[i] = s.nextInt();
}
/* for(int i =0;i<n;i++){
System.out.print(a[i]);
}*/
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++) {
if (a[i] < a[j]) {
k++;
}
}
System.out.print(k+" ");
k=0;
}
}
public static void main(String[] args) {
numbercount();
}
}
Have a look at this solution by Binary Indexed Tree : -
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc1(a,b) scanf("%lld%lld",&a,&b)
#define sc2(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define pc(a) printf("%lld\n",a)
#define pc1(a) printf("%lld ",a)
const int MOD=1e9+7;
ll n;
void update(ll idx,ll val,ll bit[])
{
for(;idx<=n+1;idx+=(idx&-idx))
bit[idx]+=val;
}
ll query(ll idx,ll bit[])
{
ll ans=0;
for(;idx>0;idx-=(idx & -idx))
ans+=bit[idx];
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
ll ar[n];
vector<pair<ll,ll>> v;
for(ll i=0;i<n;++i)
cin>>ar[i],v.pb({ar[i],i});
sort(v.begin(),v.end());
for(ll i=0;i<n;++i)
{
ar[v[i].second]=i+1;
}
ll bit[n+1];
memset(bit,0,sizeof(bit));
ll ans[n];
for(ll i=n-1;i>=0;i--)
{
ans[i]=query(n,bit)-query(ar[i]-1,bit);
update(ar[i],1,bit);
}
for(ll i=0;i<n;++i)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
- NoOne October 06, 2016// ZoomBA : Dance with it def count_bigger_right( arr ){ arr_len = #|arr| rfold( [0: arr_len] , list() ) as { cur = arr [ $.o ] num_greater = sum ( [$.o+1: arr_len ] ) as { arr[$.o] > cur ? 1 : 0 } $.p.add ( 0 , num_greater ) $.p } }