找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: roommate
收起左侧

[Goldman Sachs] Goldman Sachs新鲜电面

[复制链接]

1094

主题

162

精华

3335

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3335
发表于 2-8-2017 11:03 PM | 显示全部楼层

1. Iterate over the 1000 words.
Create a multivalue hashmap, put the sorted form of that word as key and actual order as value. So all 'act', 'tca', 'cat' will come under key 'act'.
2. Sort the string to compare i.e. sort 'tca' -> 'act'.
3. Use 'act' as key to find all the values from hashmap.

code :

import java.util.ArrayList;
3 g2 o% p; o: q6 Rimport java.util.Hashtable;
3 O  x: {( V3 T: Y0 o: h8 rimport java.util.List;! ]2 i( t2 a. H* o& Q, [
. p3 B2 n. S, O  U: K% r

* ?- O. V/ e. R+ `9 O9 x" J9 G; Qpublic class Anagrams {
3 Y2 ^8 E2 \' y$ O3 C. J	public static void main(String[] args) {1 [3 \6 q( g6 u% \& `
		String[] source = {"cat","act","tca", "good", "dogo", "waste", "read", "dear"};
" g! ^1 ?# L) N& K		printSameKind(source, "good");  O0 _5 @3 x4 }  c8 N+ \, @3 L0 c
		printSameKind(source, "read");, C, S! S. Z8 \, o) V
		printSameKind(source, "act");/ x4 E/ I' @) T& V8 J
	}7 _2 C5 w( u- Q- m2 B
	public static void printSameKind(String[] source, String str){
( {/ n) a, {* ^! \		Hashtable<String, List<String>> ht = new Hashtable<String, List<String>>();: u) N( E" W3 @& s- ~
		MergeSort sorter = new MergeSort();, Z/ R5 q+ l; n4 n0 M; @
		List<String> values;
" j% x* [8 u6 W  U1 m		char[] chr;" e/ Y+ F0 d, c
		
6 L8 a# n7 G5 V		for(int i=0;i<source.length;i++){8 E+ M: w+ v: I8 r
			chr = source[i].toCharArray();1 O2 [) `' X- t
			sorter.sort(chr);			
( i! s8 L  f- o0 ^7 W5 l0 K0 ]* K7 r9 [			String sortedString = String.valueOf(chr);6 H1 S* R# p! R# z
			if(ht.get(sortedString)==null){
1 H5 t" p1 a) H6 W8 A				values = new ArrayList<String>();
( n0 R7 z' n" H			}else{
; m; y7 F; }) w* z9 K4 P& j6 h				values = ht.get(sortedString);( W4 y: x% ]6 x. E( v. b$ J9 {
			}
/ O3 ?8 S" c$ P			values.add(source[i]);
  E" m1 l* M' k8 M. I" ]3 g6 X			ht.put(sortedString, values);) L% \- @- [' o$ I
		}4 ^* W7 X( u% V7 ^% |
		# d0 c: M! B1 _9 c0 p  D* U& ~4 r
		* Q& K! R/ X& W8 l( E
		chr = str.toCharArray();) r: s6 G1 T: n' P+ G' ?1 ]$ j
		sorter.sort(chr);
: c, r2 Q9 X: W* g. V8 [' W		str = String.valueOf(chr);! W8 [9 y/ t7 S) j2 N
		List<String> result = ht.get(str);% f5 `4 z0 h) f3 `6 v
		System.out.println(result);
. |: {! I+ V/ @	}
2 f1 r1 `, f/ }6 E! B! `" j5 k4 t* S/ G1 l	
5 O, j% X- I1 ~}

(I have used mergesort to sort the string)

public class MergeSort {* K8 {  x1 i# ~3 L# Y& W  Z! I. Y
	private char[] c; 3 m9 |# V2 b. _$ d
	private char[] helper;
7 Q" ~' H& T8 w* e- Q0 B9 N# M  F' `! x- y- b1 ?
	private int number;* E) E; @  ^1 n# H. p/ G. n8 N

: h) |. q+ b1 R) }6 q	public void sort(char[] chr){" g  i# G( K# r0 M* O
		this.c = chr;
' h) x+ o; `; I6 P( O		this.number = chr.length;# S$ I8 e& s7 k) l, I" A" n1 a: u& L
		this.helper = new char[number];
& N  g! p, `- w! L8 S* m		mergesort(0,number-1);& z5 O% z  t/ a: }# q+ i
	}
4 j9 @* D# a* W& Z/ a( {0 l, ?8 R/ n& K- V! n3 k4 l
	private void mergesort(int first, int last){
  C% T& g6 {' z( J		$ ]& k9 G! v" `) d( J( `# I/ p
		if(first<last){
; ?1 M8 M& n# a/ v/ p			int mid = first + (last-first)/2;
: F" Y% f- }" g$ M, j3 G			mergesort(first,mid);* G- x' v5 [, x# ?; ?3 A; w
			mergesort(mid+1,last);. [# W: h8 S! m" j
			merge(first,mid,last);
) @" Q( E- R2 N		}		0 Z& _  \) `) W* |! c
	}4 Q" Z$ B* A! m9 X1 c! f
+ F; S9 C5 L. @0 @, A7 r/ N
	public void merge(int start,int mid, int end){
( f& z& c* W1 h
+ s0 U* W! ~$ ~+ v+ S7 c( d		//Copy both parts to helper array2 E! ?/ N% K0 X% L2 L% d" z
		for(int i=start;i<=end;i++){
0 O, b/ F: I* v6 y			helper[i] = c[i];3 r9 ?) v! K$ n* ^1 j. ^+ t
		}
- A7 V$ _1 d) D. r( B		
+ k' O/ j& A* a: y		int i = start;/ [6 b4 H2 K6 w
		int j = mid+1;- U8 P" X/ l" p" k8 }$ U1 u
		int k = start;( E1 }4 ]2 W( B7 a1 i0 W3 T2 v
		while(i<=mid && j<=end){
- q" t5 H! G  P, T  N			if(helper[i]<=helper[j]){5 ]8 x+ ]8 W+ _3 c2 E/ [3 q
				c[k] = helper[i];5 I9 j, |5 A( d( ^' L" p; W/ D
				i++;
' D; O; U! u1 f- b: a& m			}else{
/ F4 P! C- G" W8 n  k# k				c[k] = helper[j];% l" t% H0 i# P
				j++;
* F5 ~* R$ t* k% v! x- J			}+ a# J2 w, l  w! O6 M8 _
			k++;  p" I3 r/ _  L" j. n2 D' a
		}
# F! ]3 G6 r( M/ U5 T5 x		while (i <= mid) {4 L* ]+ O% w/ ]- n, ~/ q- [! X( ?
			c[k] = helper[i];( i1 L- L0 w5 w& n7 u
			k++;
5 O8 p+ Z( G6 O$ x: v' p- o- M) H			i++;* S& R3 f: G/ q: ~, O4 c1 K1 O
		}
; h6 B5 L1 s( }) ?" e8 T		while (j <= end) {/ d0 ^( y. c" M
			c[k] = helper[j];1 y5 K2 L* V0 }/ O! o9 Z1 K9 O6 Z
			k++;
) k+ A  U9 n& H			j++;
4 t7 W+ T1 S+ ?		}
' G  S7 v) T+ _$ N+ j, x1 t7 l9 o% J2 I7 P1 Y
	}
/ }% L  P+ O: ]/ Z/ y: u# h}

1156

主题

173

精华

3582

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3582
发表于 2-8-2017 11:03 PM | 显示全部楼层

1. convert strings to character arrays using toCharArray() 6 U8 v' C; H9 V$ @2 a; [
2. sort the arrays using Arrays.sort()+ ]. \6 Z: [+ h6 w
3. compare the arrays Arrays.equals()

package goldmansachs;, \1 P( s, W% q  N

( ?( p8 g9 p% oimport java.util.Arrays;
' i- I/ ^! P; v/ D( J. f- y5 H. `( L# e- T( C) N
public class anagram {
$ R' Q4 \1 H6 l" n  D$ L1 I$ F4 q  E7 q
	  public static void main(String args[]){
8 j0 |, r% @1 r# a$ N3 ^		  String arr[] ={"cat","tac","act","xyz"};$ l$ l- Q) u- K% l
		    String s = "tac";8 S  ?# q4 x& A) h  G: t
		    for(int i =0;i<arr.length;i++){, O- [) n) M% z
		      if(isAnagram(s,arr[i])){1 y2 v. f3 i4 e: t) k; J* J" e  K
		        System.out.println(arr[i]);9 x. t5 k0 F& R
		      }3 @* ^. J5 F2 J
		    }: I& z7 ^4 m: M7 @
		    
8 A( C( P2 k+ D& [& E& n! \, f		  }5 z$ x+ ~3 J# O( f( m& {+ |! g+ i
		  " `) v1 ^3 _. a0 Z0 f+ x2 ^' f
		  public static boolean  isAnagram(String x,String y){' B) i6 q* @  t6 u8 H
		    8 S+ g3 v4 e2 i+ C2 \- N7 s
		    char a[] = x.toCharArray();# U9 \( y; ?( J+ \  @- v7 p. L
		    char b[] = y.toCharArray();) L) q& J$ i8 `5 b& {. j$ B
		    
/ L2 W, ?$ f) [1 P/ Y7 k		    Arrays.sort(a);
8 u& ?' U+ p" Z$ R* k9 V		    Arrays.sort(b);
7 p0 T# M! E9 @, a6 y7 J& T9 i		    1 |9 N4 C) x8 A1 D$ z* y
		    if(Arrays.equals(a,b)){
2 m  }' {8 D' V		      return true;' Y$ d  j* W& Z, K
		    }3 c+ \1 {  ~; c" F3 i# M+ x
		    return false;
" a+ a" Z# c7 @# v" P) \, Z		  }$ I) f; b0 S& G$ I7 q+ v# M
}

1117

主题

178

精华

3488

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3488
发表于 2-8-2017 11:03 PM | 显示全部楼层

I have tested Its working.

public class MiscDemo {

public static void main(String[] args) {
String []input = {"cat","good","tac","act","odog"};
MiscDemo misc = new MiscDemo();
misc.segragateAnagram(input);
System.out.println();

}

public void segragateAnagram(String input[]){
Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
Set<String> keys = map.keySet();
String word;
for(int i=0; i<input.length;i++){
if(this.matchingAnagramKey(keys, input[i])!=null){
word = this.matchingAnagramKey(keys, input[i]);
map.get(word).add(input[i]);
}else{
map.put(input[i], new ArrayList<String>());
}
}
System.out.println(map.get("cat").size());

}


public String matchingAnagramKey(Set<String> keys, String b){
for(String word:keys){
if(isAnagram(word, b)){
return word;
}else{

}
}
return null;
}
public boolean isAnagram(String a, String b){
// Their length shoud be same \
// Their both String contain same character and same number of character but there order might be diifer.
int m = a.length();
int n = a.length();
if(m!=n){
return false;
}
int []count1 = new int[26];
int []count2 = new int[26];
// using single count array
for(int i=0;i<n;i++){
count1[a.charAt(i)-97]+=1;
}
for(int i=0;i<n;i++){
count1[b.charAt(i)-97]-=1;
}
for(int i=0;i<26;i++){
if(count1[i]!=0){
return false;
}
}
return true;
}
}

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

本版积分规则

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