JP Morgan Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
class NtheLargest{
int findNthLargest(int [] input, int n){
int [] nLargestNumbers = new int[n];
//Assume that the first n elements are the largest n numbers
for(int i=0;i<n;i++){
nLargestNumbers[i] = input[i];
}
//Starting from the n+1 elements update the nLargestNumbers if we find any value greater
for(int j=n-1;j<input.lenght;j++){
for(k=0;k<nLargestNumbers.length;k++){
if(input[j] > nLargestNumbers[k]){
updateNLargest(nLargestNumbers,input[j]);
}
}
}
//Find the min in the nLargest numbers which will the nth Largest number in the array.
intNthLargestvalue = 0;
for(int v : nLargestNumbers){
if(v < intNthLargestvalue)
intNthLargestvalue = v;
}
return intNthLargestvalue;
}
updateNLargest(int [] array, int val){
for(int a:array){
if(val > a) {
tmp = array[i];
array[i] = val;
updateNLargest(array,tmp);
}
}
}
}
class NtheLargest{
int findNthLargest(int [] input, int n){
int [] nLargestNumbers = new int[n];
//Assume that the first n elements are the largest n numbers
for(int i=0;i<n;i++){
nLargestNumbers[i] = input[i];
}
//Starting from the n+1 elements update the nLargestNumbers if we find any value greater
for(int j=n-1;j<input.lenght;j++){
for(k=0;k<nLargestNumbers.length;k++){
if(input[j] > nLargestNumbers[k]){
updateNLargest(nLargestNumbers,input[j]);
}
}
}
//Find the min in the nLargest numbers which will the nth Largest number in the array.
intNthLargestvalue = 0;
for(int v : nLargestNumbers){
if(v < intNthLargestvalue)
intNthLargestvalue = v;
}
return intNthLargestvalue;
}
updateNLargest(int [] array, int val){
for(int a:array){
if(val > a) {
tmp = array[i];
array[i] = val;
updateNLargest(array,tmp);
}
}
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class NthLargestNumberInArray {
public static void main(String[] args) {
Integer[] numbers = {1,3,5,3,7,0,20,30,15,2,100};
int position =9;
System.out.println("Largest number on position "+position +" is: " +getNthLargestNumber(position, numbers));
}
public static int getNthLargestNumber(int position, Integer[] numbers){
List<Integer> list = Arrays.asList(numbers);
Collections.sort(list);
for (int i=list.size()-1;i>=0;i--) {
System.out.println("Position "+(list.size()-(i))+" = "+list.get(i));
}
return list.get(list.size()-position);
}
}
---------------------
Output
Position 1 = 100
Position 2 = 30
Position 3 = 20
Position 4 = 15
Position 5 = 7
Position 6 = 5
Position 7 = 3
Position 8 = 3
Position 9 = 2
Position 10 = 1
Position 11 = 0
Larget number on position 9 is: 2
Simple (reverse bubble sort)
function(arr,n){
document.write(" Array is "+ arr + "<p>");
var t;
for(i= 0; i < n ; i++){
for(j=i; j < arr.length; j++){
if(arr[j] > arr[i]){
document.write(arr[j] + " is greater than "+ arr[i]+" index is "+j+"\n <p>");
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
return arr[n-1];
PS: Javascript code snippet
#include <iostream>
#include <queue>
#include <array>
using namespace std;
int nth_largest(vector<int> v, int pos) {
priority_queue<int> q;
int result;
for (auto i : v) {
q.emplace(i);
};
for (int j = 1; j <= pos; j++) {
result = q.top();
q.pop();
if (j == pos)
break;
}
return result;
}
int main()
{
vector<int> v = { 1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67 };
cout << "\t " << nth_largest(v, 2) << "\t" << nth_largest(v, 5) << endl;
return 0;
}
#include <iostream>
#include <queue>
#include <array>
using namespace std;
int nth_largest(vector<int> v, int pos) {
priority_queue<int> q;
int result;
for (auto i : v) {
q.emplace(i);
};
for (int j = 1; j <= pos; j++) {
result = q.top();
q.pop();
if (j == pos)
break;
}
return result;
}
int main()
{
vector<int> v = { 1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67 };
cout << "\t " << nth_largest(v, 2) << "\t" << nth_largest(v, 5) << endl;
return 0;
}
public class NthLargest {
public static void main(String[] args) {
Integer[] array={1,8,4,5,9,7,2,10,55,67,3};
findNthLargest(array, 5);
//System.out.print(nthLargest);
}
static void findNthLargest(Integer[] array, int n){
int counter=0;
List<Integer> newList= new ArrayList(Arrays.asList(array));
Collections.sort(newList);
System.out.print("This is "+newList.get(newList.size()-n));
//return newList.get(newList.size()-1);
}
}
public class FindSecondLargestInArray {
public static void main(String[] args) {
int array[] = {1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67};
int largest = array[0];
int secondLargest = array[0];
int thirdLargest = array[0];
int fourthLargest = array[0];
int fifthLargest = array[0];
for(int i=0; i<array.length;i++){
if(array[i]>largest){
fifthLargest = fourthLargest;
fourthLargest = thirdLargest;
thirdLargest = secondLargest;
secondLargest = largest;
largest = array[i];
}
else if(array[i]>secondLargest){
secondLargest = array[i];
}
else if(array[i]>thirdLargest){
thirdLargest = array[i];
}
else if(array[i]>fourthLargest){
fourthLargest = array[i];
}
else if(array[i]>fifthLargest){
fifthLargest = array[i];
}
}
System.out.println("Second Largest Number in Array: "+secondLargest);
System.out.println("Fifth Largest Number in Array: "+fifthLargest);
}
}
public class FindSecondLargestInArray {
public static void main(String[] args) {
int array[] = {1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67};
int largest = array[0];
int secondLargest = array[0];
int thirdLargest = array[0];
int fourthLargest = array[0];
int fifthLargest = array[0];
for(int i=0; i<array.length;i++){
if(array[i]>largest){
fifthLargest = fourthLargest;
fourthLargest = thirdLargest;
thirdLargest = secondLargest;
secondLargest = largest;
largest = array[i];
}
else if(array[i]>secondLargest){
secondLargest = array[i];
}
else if(array[i]>thirdLargest){
thirdLargest = array[i];
}
else if(array[i]>fourthLargest){
fourthLargest = array[i];
}
else if(array[i]>fifthLargest){
fifthLargest = array[i];
}
}
System.out.println("Second Largest Number in Array: "+secondLargest);
System.out.println("Fifth Largest Number in Array: "+fifthLargest);
}
}
package org.test;
import java.util.Scanner;
//{1,2,4,5,7,8,9,10,44,55,67}
public class Test1 {
public static void main(String[] args) {
int n ;
int i,temp;
Scanner scanner= new Scanner(System.in);
System.out.println("Enter number of elements : ");
n= scanner.nextInt();
int a[] = new int[n];
System.out.println("Enter Elements :");
for(i = 0; i < n; i++)
{
a[i] = scanner.nextInt();
}
for(int k =0;k<n;k++)
{
for(int l=k+1;l<n;l++)
{
if(a[k]>a[l]){
temp =a[k];
a[k]=a[l];
a[l]=temp;
}
}
}
System.out.print("Ascending Order:");
for (int r = 0; r < n - 1; r++)
{
System.out.print(a[r] + ",");
}
int result =nth_largest(a, 2);;
System.out.println("Result is :"+result);
}
public static int nth_largest(int[] a , int pos)
{
return a[pos+1];
}
}
package org.test;
import java.util.Scanner;
//{1,2,4,5,7,8,9,10,44,55,67}
public class Test1 {
public static void main(String[] args) {
int n ;
int i,temp;
Scanner scanner= new Scanner(System.in);
System.out.println("Enter number of elements : ");
n= scanner.nextInt();
int a[] = new int[n];
System.out.println("Enter Elements :");
for(i = 0; i < n; i++)
{
a[i] = scanner.nextInt();
}
for(int k =0;k<n;k++)
{
for(int l=k+1;l<n;l++)
{
if(a[k]>a[l]){
temp =a[k];
a[k]=a[l];
a[l]=temp;
}
}
}
System.out.print("Ascending Order:");
for (int r = 0; r < n - 1; r++)
{
System.out.print(a[r] + ",");
}
int result =nth_largest(a, 2);;
System.out.println("Result is :"+result);
}
public static int nth_largest(int[] a , int pos)
{
return a[pos+1];
}
}
public static void main(String[] args) {
int[] nums = { 3, 11, 55, 22, 33, 2 };
System.out.println("kth largest ==> " + findKthLargest(nums, 4));
}
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
for (int i : nums) {
q.offer(i);
if (q.size() > k) {
q.poll();
}
}
return q.peek();
}
classical quick select
- Scott March 03, 2016