找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: roommate
收起左侧

[Goldman Sachs] Goldman Sachs新鲜电面

[复制链接]

1195

主题

165

精华

3594

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

Its basically a anagram finding problem. The given solution will have time complexity as O(n) sa you are going through the whole list, sorting the words would be O(nlogn) and compairing is a constant work we are doing. So final complexity would be O(n)

import java.util.ArrayList;
7 X% ?$ N" I' Y% N5 ?% vimport java.util.Arrays;
+ b0 Y( {- S2 v# k+ z2 m- \import java.util.List;- _# }' L+ V# \" z

+ K5 Q/ B# }2 y! S* lpublic class AnagramFinder {
# H5 J7 J' {0 \9 V, J) y8 T7 S7 Z+ Q& b4 `' ]
	public static void main(String[] args) {5 ?, u5 u3 J! M! c
		List<String> listOfWords = new ArrayList<String>();
/ I# F* q7 q# t4 r/ a4 D		listOfWords.add("utid");
7 p/ ]: K" U( |6 L+ }8 D		listOfWords.add("ttid");  @& h3 v6 g( r; A  ?
		listOfWords.add("diut");
( u6 X! `, v- s" Y' o		listOfWords.add("utdi");( P9 h6 h( l7 U, V( s
		
0 k. B% _: e5 z0 b+ U		findAnagramInList(listOfWords,"tdiu");
! L, T0 |: e' O  [* X0 G( j	}9 y/ F$ f* v$ p7 Q  F& f

9 B9 Z0 Q6 _  V5 l. A  ~" F9 [	private static void findAnagramInList(List<String> listOfWords,
% ], d( b9 j/ [. ?! G			String string) {
$ p7 ?: \- F+ Z  H! ~! [		char[] stringArray= string.toCharArray();
- c: Y( A" z" M+ ?& n4 q, s; `, ^. [		Arrays.sort(stringArray);) B$ T0 y/ ^1 E& x0 S
		for(String s :listOfWords){/ J! n7 b- j  d2 f6 @
			char [] arr = s.toCharArray();2 v: g/ Z8 K# \7 a' R
			Arrays.sort(arr);
3 _5 M) d6 F+ B* q9 v) o9 h			% a* F% j9 l# y+ L$ R
			if(String.valueOf(arr).equals(String.valueOf(stringArray))){$ d* h/ ?- O) c, W0 X" m# R
				System.out.println("Angram found :" +s);
1 O: C! t/ l8 f! e			}
, p! n, a, J  N		}
7 F: c7 G( B. [& F) e		
( W# e  F7 n9 j, L. W& e# ^	}
1 M0 Z, A/ y3 @  f5 T7 E+ \
4 A) n. {: K9 O6 N}

1194

主题

195

精华

3819

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

A different approach
- each string could be identified by an array of integers of length 26 (size depended on the set of characters, here we considered only a-z). The integer array is populated by setting the number of occurrence of characters in the input string. For example "cat" will be represented as {1,1,1,0,0,0,0,....0}. In this way we form a unique integer array for strings with same number of characters.
- create a map of integer array versus string list

1174

主题

171

精华

3558

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

package com.cnu.ds.programs;; ^* n0 n: }: P( q2 W3 }3 L
& {7 |6 O0 w- F) T" L! g, c
import java.util.Arrays;
! e9 j$ N( q. B) p0 yimport java.util.HashSet;0 t  ^. L# j9 L" C. s3 E  J
import java.util.LinkedList;4 L% h4 s+ f& X$ g/ o! u
import java.util.List;- B; ~2 d1 }5 K" F' y
import java.util.Set;, E2 I; q. C0 q- }) h4 E

. ~% B  |+ c7 a$ X* ppublic class SetOfAnagrams {& e) l$ I$ ^( @& ^; s6 ]

# M, p) S8 c8 Z9 Z% ]	public List<String> anagrams(String str,List<String> list) {
' ~" z2 p( y; x! k9 {6 H		List<String> anagrams = new LinkedList<>();' `: q  |# x( X) Z- j, s
		for (String string : list) {
( a5 a2 G! {" a: b' n% G8 b			if (anagrams(string, str)) {4 l0 S$ o0 I5 h5 y# ?6 J$ E
				anagrams.add(string);
  I  J$ v! W' S			}
9 F" g5 Q# h. R* Z		}
$ S+ g. w6 O$ t! A0 R		return anagrams;) \/ b3 M* ~3 p6 ?7 q! U" v1 m# Z
	}$ c: f4 a+ X! D& i- X! e( J
	+ Z5 x$ f- k3 ~
	public boolean anagrams(String s1, String s2) {
2 _# ?- H( I2 `' l& p3 X		if (s1 != null && s2 != null) {
' s+ q' u, Y* H0 A. p9 `: l2 d			if (s1.length() == s2.length()) {
- X5 p- d4 ]4 m# Q' }				int[] noOfAlphabetsInS1 = new int[26];% M) @$ R# ^; b/ k* |! Q9 Q
				for (int i = 0; i < s1.length(); i++) {
) x& o* B9 \4 I0 l" O					noOfAlphabetsInS1[s1.charAt(i) - 97]++;
/ Q* L( i( Y1 q0 S5 ^$ e$ u					noOfAlphabetsInS1[s2.charAt(i) - 97]--;
8 c1 D' z5 [$ ~) C				}' S. r. Y! ?% B
				for (int i = 0; i < noOfAlphabetsInS1.length; i++) {
" Y# B" E- B. W0 N$ ~					if (noOfAlphabetsInS1[i] != 0) {* F+ o0 i" t/ Q5 p6 v! B
						return false;
; i7 W9 e$ X( ]$ k7 Z; K- W0 T  s* T6 e					}
) a- J& b- p& v! }0 u				}
+ _1 v; D" d8 x+ J: n: B. o  G				return true;: t7 w* E7 s1 p
			}: L6 _1 D/ Q6 K# _, D6 W& V/ Y  p
		}
. W$ k6 h* m  r# B  k! w		return false;
4 ?" Q, Q% P5 o! @" V4 t) |	}7 y0 z/ V9 M- G2 r1 O; x6 O) Y( l

9 W1 p8 Y; a% K* j; L& f	public static void main(String[] args) {' f* M  |6 ^1 Y) w! C, K5 f( t/ D- h9 ^
0 ]/ R7 v$ \9 _$ X$ r6 d
		String[] strings = { "abc", "cab", "dac", "bed", "few", "deb", "acd" };
% ^5 U* a5 h$ a3 n" o		; u8 h8 p% }5 H
		System.out.println(String.format("List of Anagrams of %s : %s","cad",anagrams.anagrams("cad", Arrays.asList(strings))));
) l( u5 P/ z, Z. u	}( \# _! t& l  \5 L
}

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

本版积分规则

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