找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2683|回复: 12
收起左侧

[Amazon] 亚麻测试工程师面经

[复制链接]

1159

主题

170

精华

3549

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3549
发表于 2-1-2017 10:32 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-6-2017 09:49 AM 编辑 , a' }3 u  [: z5 U, T( @. k5 p
( H2 E8 a1 q2 A( z. \- i) |3 m8 O
You are given an array of integers. Find the minimum difference between two prime numbers(Positive or negative) in the array when present with minimum time complexity and provide the test data to test the this code.

1144

主题

184

精华

3626

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3626
发表于 2-1-2017 10:32 PM | 显示全部楼层

I donot know whaat you answered but for my solution the complexity is n2 + logn
here is the solution

public class MinimumDiffPrimeNumbers {& g: C6 C% n; o' [) I: n9 n
	! i  q6 Q& D+ w" c& w
	public static void main(String[] args) {
$ b! W% V) K# a; }& i* Q9 U		int[] numbers = {101,-113,1,45,78,-2,-3,7};  o: d: V/ x  X4 K& h
		new MinimumDiffPrimeNumbers().findPrimes(numbers);	6 r4 {- V. D+ E+ P" V  d
		; U5 X3 b: m! n9 O. U7 w0 @
	}/ c! W, A3 X# x' W) S6 T
	
4 V7 P5 C3 V' B: y6 _  N	private int[] findPrimes(int [] numbers) {$ _2 P& [( y$ j3 y
		int [] returnArray = new int[2];
; W0 J# E6 G: K' I$ @) P		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
5 E: f! N. H5 A/ I/ T8 c5 l		
* x; `0 D$ s5 {9 x2 ~5 U& s; D		for(int i=0;i<numbers.length;i++){& n9 d/ I5 J7 o  F
			if(isPrime(numbers[i]))
& p* k) Y1 d. F' B! W1 l				map.put(numbers[i], numbers[i]);- S; K; r) T6 q  W. c2 A
		}
' h, o& @# J" b$ L# X		+ C7 Q; \4 }3 s+ X  D* @
		returnArray[0]= map.firstKey().intValue();
6 N) H+ S# k% t' V6 G# L) }7 |		returnArray[1]= map.lastKey().intValue();
' m0 r6 P+ F- s* n2 S		return returnArray;2 ^+ D5 n& }; s! `
	}
' s' p% w- E( c5 g	# Z' i; Z1 n* v% G0 U4 l% a
	private boolean isPrime(int n){" _- D0 m) D! z( |4 x: d3 o
			
- |" u6 i, O2 {& `  r& J2 A# i" S		if(n<0)
% D7 W# \! Q# x; u/ q" T 			n = 0 - n;  //just convert n to positive for simplicity; n# T( Y/ S* _( E4 e
		for(int i = 2;i<n/2;i++){( n# P. P2 W7 v3 l& h% M
			if(n%i==0)
) D' j: {8 f, X, q( x				return false;( `0 E. S4 ]" X) Z$ i3 V, z
		}( s2 l( M! R( n6 x
		return true;" J& B( X% ^" G* j
	}
0 Q! y. T3 z( X3 p' S}

回复 支持 反对

使用道具 举报

1132

主题

171

精华

3488

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3488
发表于 2-1-2017 10:32 PM | 显示全部楼层

Sorry I got the question wrong .. I thought the two numbers needs to be returned.. This solution returns the minimum difference

import java.util.HashMap;5 i5 p5 y: k+ T- V% G
import java.util.TreeMap;+ V* j4 j0 d+ s5 d# \, |6 r

3 L- W9 j0 J7 ^/**4 N; ?! u4 p3 S, C5 [( @  y
 * You are given an array of integers. Find the minimum difference between two prime numbers(Positive or negative) # x% j; C( B- O2 |! C8 J, S
 * in the array when present with minimum time complexity and provide the test data to test the this code.
3 m9 g) `! n/ t1 U2 A% i. h */( p2 E) X0 _" s( X1 U
public class MinimumDiffPrimeNumbers {/ ^9 U0 K- W/ g" A4 i( x
	2 l" \1 r5 [6 y- P) |0 ]" x
	public static void main(String[] args) {4 \" W  k3 Y$ {
		int[] numbers = {101,-113,1,45,78,-2,-3,7};2 K' L. u& P2 g' M8 I
		System.out.println(new MinimumDiffPrimeNumbers().findPrimes(numbers));	) U# A* |2 I) ~# h
		
) \7 p4 F/ I9 R! u	}
# ~4 k9 u9 h# R" {2 X3 q6 z( C	* m, q( ~1 u9 b- p% h2 T4 C
	private int findPrimes(int [] numbers) {
. i, y: t+ x2 b		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
0 @* \" _! o$ |		
! i. X9 P. M  F# q7 m; T, B& m		for(int i=0;i<numbers.length;i++){
% y+ r5 r2 x. h( ^& M. `			if(isPrime(numbers[i]))
9 c$ d9 ^1 g) U, N6 A				map.put(numbers[i], numbers[i]);) a* }  `3 e0 e6 ?
		}' Y, K7 y) ^& {  T& K
		# E! C5 p" S. u! H: t7 F, b8 J
		return map.firstKey().intValue() - map.lastKey().intValue();4 G1 C) c/ e! u8 G! H
	}" W" G2 D1 Q* U! T- @
	
6 B! }  \# {6 ]0 l	private boolean isPrime(int n){' B) ?/ |) J+ p* z# ^  t, C
			
+ A, q  I* K& r' [: A$ X7 F		if(n<0)
0 C9 @4 T0 b1 ]0 G( ` 			n = 0 - n;  //just convert n to positive for simplicity
3 x" J  d5 ]3 p& T8 {/ w& ], n		for(int i = 2;i<n/2;i++){
' z) n) L8 k: [: v! e" Z			if(n%i==0)* a' S$ C' ?4 B; S1 c# w: ~
				return false;9 k' y* |* J) s0 j0 g; a* o
		}, j' r2 M- B! o  `& m! @
		return true;
) r; w& p+ J- H8 D$ ^	}
) r5 t4 w+ d  F" d' [) p: ]7 D- I}

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表