Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
private static void findArrayLeaders(int arr[]) {
if (arr == null || arr.length == 0) {
System.out.println("Invalid Inputs");
return;
}
int i = 0, len = 0, leader = 0;
len = arr.length;
leader = arr[len - 1];
System.out.print(leader);
for (i = len - 2; i >= 0; i--) {
if (arr[i] > leader) {
leader = arr[i];
System.out.print(" " + leader);
}
}
}
function findLeader(inputArr) {
var leaderArray = [];
for (var i = 0; i < inputArr.length; i++) {
if (isLeader(inputArr, i)) {
leaderArray.push(inputArr[i]);
}
}
return leaderArray;
}
function isLeader(inputArr, pos) {
for (var j = pos; j < inputArr.length; j++) {
if (inputArr[pos] < inputArr[j]) {
return false;
}
}
return true;
}
public class GetArrLeader {
public static void main(String[] args) {
int[] intArr = {12,14,10,12,2};
// should print 14,12 and 2
printLeaders(intArr);
}
private static void printLeaders(int[] intArr) {
for(int i=0;i<(intArr.length)-1;i++) {
int j = i+i;
boolean bool = false;
while (j<intArr.length) {
if(intArr[i]>intArr[j++])
bool = true;
else {
bool = false;
break;
}
}
if(bool) System.out.println(intArr[i]);
}
System.out.println(intArr[intArr.length-1]); // last one is always considered
}
}
Javascript code, you can run in browser console. just copy and paste it in browser console to see output.
var ele=[13,17,5,4,6,2];
ele=ele.reverse();
var leader_ele=ele[0], leaders=[];
ele.map( function(item) {
if (leader_ele<=item){
leader_ele=item;
leaders.push(leader_ele);
}
})
console.log(leaders.reverse());
Scan from Right for the O(N) Solution.
Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print the same as Leader.
Time Complexity: O(N)
- R@M3$H.N October 03, 2014