Goldman Sachs Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
9
of 9 vote

private static void anagram(String[] str1,String searchString) {
		// TODO Auto-generated method stub
		for(String s:str1)
		{
			if(sort(searchString).equals(sort(s)))
			{
				System.out.println(s);
			}
		}
	}

- Vir Pratap Uttam May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Create a HashMap<Integer, List<String>> that will hold every String from your array of strings using as Key the sum of each char Integer value.

2. Iterate over your list and insert each string using as key a transformation function that will calculate the sum of every char on that string, thus strings with same chars will have exact same sum. Append the Strings with same sum into the List of Strings for that particular sum.

3. for your String as input, just get it's sum value using the same transformation function, once you have the sum use it as key to print the resulting List<String> of the HashMap, that will print all Strings with same chars.

- O(n * n) to build list, O(1) to print String list
- O(n) space

- guilhebl January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Almost.

Let's define ascii values:

A= 65
B = 66
C = 67
D = 68
E = 69
... etc.

If we have two strings "BE" and "DC", they both sum to the same value, but they have different characters.

I think instead of transforming based on the sum of characters, when you iterate over the list, the hash code should be the hashcode produced when the particular string is lexicographically ordered.

so if you have the following strings:

"BAC", "CAB"

we would first find the lexicographically sorted version of the string , (for both this is "ABC") and in the hash location for "ABC", we would add both of them

- Skor January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You are right, definitely missed that detail, your solution would cover that issue.

- guilhebl January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

def anagramQuestion(list1, input):
	dict1 = {}
	for x in range(0,len(list1)):
		key = ''.join(sorted(list1[x]))
		if key in dict1:
			dict1[key].append(list1[x])
		else:
			dict1[key] = [list1[x]]
	result = []
	for x in dict1:
		inputsorted = ''.join(sorted(input))
		if x == inputsorted:
			dict1[x].remove(input)
			result.append(dict1[x])

	return result

- Anonymous January 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Multimap. Use the sorted value of a string as Key.

So for tac. The key will be act.
Also for atc. The key will be act.

- Abhi January 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.careercup;

public class FuzzyStringSearch
{
    
    public static void main(String[] args)
    {
       String input[] = new String[]{"cat","lion","act","dog"};
       String toSearch = "tac";
       searchWord(toSearch,input);
    }

    private static void searchWord(String toSearch, String[] input)
    {
        for (int i = 0; i < input.length; i++)
        {
            if (input[i].length() == toSearch.length())
            {
                if(fuzzySearch(input[i],toSearch))
                {
                    System.out.println(input[i]);
                }
            }
        }
    }

    private static boolean fuzzySearch(String string, String toSearch)
    {
        boolean result = false;
        char text[] = toSearch.toCharArray();
        
        for (int i = 0; i < text.length; i++)
        {
            for (int j = 0; j < string.length(); j++)
            {
                if(text[i] == string.charAt(j))
                    result = true;
                
            }
        }
        return result;
    }
    
}

- Anonymous January 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the body of IF condition result=true does not always implies that the strings are anagrams.

- Mani January 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def anagrams(word, some_list):
    letters = list(word)
    matches = []
    
    for value in some_list:
        if sorted(list(value)) == sorted(letters):
            matches.append(value)
    return matches
    

bank = ['cat', 'tac', 'act', 'trick', 'bad']

print(anagrams('tca', bank)) #returns ['cat','tac','act']

- Anonymous January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.util.regex.Pattern;
public class AllMatchedletters {
	
	ArrayList<String> al=new ArrayList<String>();
	ArrayList <String>matches=new ArrayList<String>();
	public void insertChar()
	{
		al.add("cat");
		al.add("tac");
		al.add("tas");
		al.add("act");
		al.add("bct");
		al.add("bat");
	}
	public void matchAll(String str)
	{
		Pattern p=Pattern.compile(str);
		for(String s:al)
		{
			if(p.matcher(s).matches())
			{
				matches.add(s);
			}
					}
		
		System.out.println(matches);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		AllMatchedletters match=new AllMatchedletters();
		match.insertChar();
		String str="[cat]+";
		match.matchAll(str);
			}

}

- sulavasingha February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved by sorting the words and then compairing it with given word. This is basically a problem of finding anagrams from list of words.

<pre>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AnagramFinder {

public static void main(String[] args) {
List<String> listOfWords = new ArrayList<String>();
listOfWords.add("utid");
listOfWords.add("ttid");
listOfWords.add("diut");
listOfWords.add("utdi");

findAnagramInList(listOfWords,"tdiu");
}

private static void findAnagramInList(List<String> listOfWords,
String string) {
char[] stringArray= string.toCharArray();
Arrays.sort(stringArray);
for(String s :listOfWords){
char [] arr = s.toCharArray();
Arrays.sort(arr);

if(String.valueOf(arr).equals(String.valueOf(stringArray))){
System.out.println("Angram found :" +s);
}
}

}

}

</pre>

- Varun April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
import java.util.Arrays;
import java.util.List;

public class AnagramFinder {

	public static void main(String[] args) {
		List<String> listOfWords = new ArrayList<String>();
		listOfWords.add("utid");
		listOfWords.add("ttid");
		listOfWords.add("diut");
		listOfWords.add("utdi");
		
		findAnagramInList(listOfWords,"tdiu");
	}

	private static void findAnagramInList(List<String> listOfWords,
			String string) {
		char[] stringArray= string.toCharArray();
		Arrays.sort(stringArray);
		for(String s :listOfWords){
			char [] arr = s.toCharArray();
			Arrays.sort(arr);
			
			if(String.valueOf(arr).equals(String.valueOf(stringArray))){
				System.out.println("Angram found :" +s);
			}
		}
		
	}

}

- Varun April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.cnu.ds.programs;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class SetOfAnagrams {

	public List<String> anagrams(String str,List<String> list) {
		List<String> anagrams = new LinkedList<>();
		for (String string : list) {
			if (anagrams(string, str)) {
				anagrams.add(string);
			}
		}
		return anagrams;
	}
	
	public boolean anagrams(String s1, String s2) {
		if (s1 != null && s2 != null) {
			if (s1.length() == s2.length()) {
				int[] noOfAlphabetsInS1 = new int[26];
				for (int i = 0; i < s1.length(); i++) {
					noOfAlphabetsInS1[s1.charAt(i) - 97]++;
					noOfAlphabetsInS1[s2.charAt(i) - 97]--;
				}
				for (int i = 0; i < noOfAlphabetsInS1.length; i++) {
					if (noOfAlphabetsInS1[i] != 0) {
						return false;
					}
				}
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {

		String[] strings = { "abc", "cab", "dac", "bed", "few", "deb", "acd" };
		
		System.out.println(String.format("List of Anagrams of %s : %s","cad",anagrams.anagrams("cad", Arrays.asList(strings))));
	}
}

- cnu1438 July 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class FindNumOfWordsFromList {

static String[] array = {"act","tca","asd","cat"};

public static void main(String[] args){

searchwords("act");
}

private static void searchwords(String string) {

for(String word:array){
if(!word.equals(string) && word.length()==string.length()){
char[] stringCh =string.toCharArray();
char[] wordCh =word.toCharArray();
Arrays.sort(stringCh);
Arrays.sort(wordCh);
if(Arrays.equals(stringCh, wordCh)){
System.out.println(word);
}
}

}
}
}

- omi August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class FindNumOfWordsFromList {

	static String[] array = {"act","tca","asd","cat"};
	
	public static void main(String[] args){
		
		searchwords("act");
	}

	private static void searchwords(String string) {

		for(String word:array){
			if(!word.equals(string) && word.length()==string.length()){
				char[] stringCh =string.toCharArray();
				char[] wordCh =word.toCharArray();
				Arrays.sort(stringCh);
				Arrays.sort(wordCh);
				if(Arrays.equals(stringCh, wordCh)){
					System.out.println(word);
				}
			}
			
		}
	}
}

- omi August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
String[] arr={"abc","cab","fdg","sbc","bac","bsc"};
String inputKey="cba";
System.out.println(getAllPaatern(arr,inputKey));
}

static List<String> getAllPaatern(String[] inputArray, String searchKey){
List<String> wordList= new ArrayList<String>();
for(int i=0;i <inputArray.length;i++){
if(getSortedString(inputArray[i].toLowerCase()).equals(getSortedString(searchKey.toLowerCase()))){
wordList.add(inputArray[i]);
}
}
return wordList;
}

static String getSortedString(String str){
char [] c = str.toCharArray();
Arrays.sort(c);
return new String(c);
}

- prmd89 November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
import java.util.Hashtable;
import java.util.List;


public class Anagrams {
	public static void main(String[] args) {
		String[] source = {"cat","act","tca", "good", "dogo", "waste", "read", "dear"};
		printSameKind(source, "good");
		printSameKind(source, "read");
		printSameKind(source, "act");
	}
	public static void printSameKind(String[] source, String str){
		Hashtable<String, List<String>> ht = new Hashtable<String, List<String>>();
		MergeSort sorter = new MergeSort();
		List<String> values;
		char[] chr;
		
		for(int i=0;i<source.length;i++){
			chr = source[i].toCharArray();
			sorter.sort(chr);			
			String sortedString = String.valueOf(chr);
			if(ht.get(sortedString)==null){
				values = new ArrayList<String>();
			}else{
				values = ht.get(sortedString);
			}
			values.add(source[i]);
			ht.put(sortedString, values);
		}
		
		
		chr = str.toCharArray();
		sorter.sort(chr);
		str = String.valueOf(chr);
		List<String> result = ht.get(str);
		System.out.println(result);
	}
	
}

(I have used mergesort to sort the string)

public class MergeSort {
	private char[] c; 
	private char[] helper;

	private int number;

	public void sort(char[] chr){
		this.c = chr;
		this.number = chr.length;
		this.helper = new char[number];
		mergesort(0,number-1);
	}

	private void mergesort(int first, int last){
		
		if(first<last){
			int mid = first + (last-first)/2;
			mergesort(first,mid);
			mergesort(mid+1,last);
			merge(first,mid,last);
		}		
	}

	public void merge(int start,int mid, int end){

		//Copy both parts to helper array
		for(int i=start;i<=end;i++){
			helper[i] = c[i];
		}
		
		int i = start;
		int j = mid+1;
		int k = start;
		while(i<=mid && j<=end){
			if(helper[i]<=helper[j]){
				c[k] = helper[i];
				i++;
			}else{
				c[k] = helper[j];
				j++;
			}
			k++;
		}
		while (i <= mid) {
			c[k] = helper[i];
			k++;
			i++;
		}
		while (j <= end) {
			c[k] = helper[j];
			k++;
			j++;
		}

	}
}

- Joey November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. convert strings to character arrays using toCharArray()
2. sort the arrays using Arrays.sort()
3. compare the arrays Arrays.equals()

package goldmansachs;

import java.util.Arrays;

public class anagram {

	  public static void main(String args[]){
		  String arr[] ={"cat","tac","act","xyz"};
		    String s = "tac";
		    for(int i =0;i<arr.length;i++){
		      if(isAnagram(s,arr[i])){
		        System.out.println(arr[i]);
		      }
		    }
		    
		  }
		  
		  public static boolean  isAnagram(String x,String y){
		    
		    char a[] = x.toCharArray();
		    char b[] = y.toCharArray();
		    
		    Arrays.sort(a);
		    Arrays.sort(b);
		    
		    if(Arrays.equals(a,b)){
		      return true;
		    }
		    return false;
		  }
}

- Neethi Elizabeth Joseph March 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Anonymous August 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- rathor.rajeev August 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<map>
#include<string.h>
typedef unsigned int UINT;
UINT IsProperWord(const char* str);
int main(int argc, char* argv[]){
if(argc < 3){
printf("\nUsage ./a.out <number of words> <word1> <word2> <word3> ... \n");
printf("\n Example : ./a.out 5 cat act hat god dog\n");
return -1;
}

int numOfWords = atoi(argv[1]);
if(numOfWords != (argc -2)){
printf("\n number of words and words count are not matching !!!\n");
return -1;
}
numOfWords = argc - 2;
std::map<UINT, std::vector<int> > valueToWordIndexMap;
std::map<UINT, std::vector<int> >::iterator mapIter;
std::vector<int>:: iterator vecIter;
int i = 2;
while(i < argc){
UINT key = IsProperWord(argv[i]);
if(key){
//printf("\nKey:%u Word:%s",key,argv[i]);
mapIter = valueToWordIndexMap.find(key);
if(mapIter != valueToWordIndexMap.end()){
mapIter->second.push_back(i);
}else{
std::vector<int> indexVec;
indexVec.push_back(i);
valueToWordIndexMap.insert(std::pair<UINT,std::vector<int> >(key,indexVec));
}
}else{
return -1;
}
i++;
}

for(mapIter = valueToWordIndexMap.begin(); mapIter != valueToWordIndexMap.end(); ++mapIter){
for(vecIter = (mapIter->second).begin();vecIter != (mapIter->second).end(); ++vecIter){
printf("%s ",argv[*vecIter]);
}
printf("\n");
}
return 0;
}

UINT IsProperWord(const char* str){
int size = strlen(str);
bool alphabets[26] = { };
UINT key = 0;
//Convert to lower case
//97 - a 122 - z
int i = 0;
while(i < size){
int alphaIndex = 0;
if( *(str +i) >= 'a' && *(str+i) <= 'z'){
alphaIndex = *(str+i) - 97;
// do nothing
}else if(*(str+i) >= 'A' && *(str+i) <= 'Z'){
alphaIndex = *(str+i) - 65 ;
}else{
return 0;
}

// check the duplicate of characters
if(alphabets[alphaIndex]){
printf("\nDuplicate characters in word : %s\n",str);
return 0;
}else{
alphabets[alphaIndex] = true;
}
i++;
}

// convert the bool to decimal value
i = 0;
while(i < 26){
if(alphabets[i]){
key += (2 ^ i);
}
i++;
}
return key;
}

- venkat August 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.sumit;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution15 {
	public static void main(String[] args) {
		String[] dict = { "abc", "cab", "dac", "bed", "few", "deb", "acd" };
		String input = "cad";
		Map<String, List<String>> dictMap = new HashMap<>();
		for (int i = 0; i < dict.length; i++) {
			String[] carr = dict[i].split("");
			Arrays.sort(carr);
			String key = Arrays.toString(carr);
			if (dictMap.containsKey(key)) {
				List<String> lst = dictMap.get(key);
				lst.add(dict[i]);
				dictMap.put(key, lst);
			} else {
				List<String> lst = new ArrayList<>();
				lst.add(dict[i]);
				dictMap.put(key, lst);
			}
		}
		//System.out.println(dictMap);
		String[] carr = input.split("");
		Arrays.sort(carr);
		String key = Arrays.toString(carr);
		System.out.println(dictMap.get(key));
	}

}

- Sumit March 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is it your homework?????

- autoboli January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No it is a interview question

- Anonymous January 11, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More