Two Sigma Interview Question: You are to write a method get... | Glassdoor

Interview Question

Financial Analyst Interview New York, NY

You are to write a method getMissingLetters, which takes a

  String, sentence, and returns all the letters it is missing (which prevent it from being a pangram)
Answer

Interview Answer

9 Answers

3

First you have to know that a pangram is a string, sentence, that uses every letter of the alphabet at least once. Comes from the greek, Pan (every) and gramma (letter).
If you didn't know that, couldn't figure out the derivation of the word, or weren't told it in the interview - you might be screwed.

Otherwise, getMissingLetters should allocate a string (or pointer to an array of chars if C/C++) in which to return the result, a static string which basically just holds the letters of the alphabet, and an array of 27 single ints to hold the count of the number of times a particular letter appears in the sentence. Then create two loops, the outer loop will move through the alphabet (index 0 to 26) on the static string/array, the inner loop will index into (or moving a pointer along) the string holding the input sentence (exiting if you've reached the end of the string (in C/C++ this is '\0' the null char). Within that inner loop you want to check the current letter being pointed to in the alphabet against the current letter being pointed to in the sentence (be careful if writing C/C++ code as to how the sentence is stored in memory). If the value of the characters being pointed to for each array are equal, then increment the value of the integer at the array position with the same index as the current letter being counted. After each inner loop completes, the outer loop counter will move the index into each array for you (or you can increment the pointers to the alphabet and alphabet count arrays).

After these two arrays complete, you need to finalize the results. To do this you need one last loop to cycle once more through the alphabet string and alphabet counter.
Within this loop you will check the value of the letter count. If it is greater than 0 you move to the next letter, if it is 0, then you want to copy the value of the letter into the current character pointed to in the result string (which should have at least 26 characters assuming a sentence is at least 1 character).

Once this loop completes just return the return string (or a pointer to it)

In C++ you might be able to utilize some of the STL Classes to do all of this, but if you do it in straight C with lots of pointer arithmetic it will execute much more quickly.

alphaG77 on Sep 4, 2009
9

Strong no hire

DJ on Sep 18, 2009
0

Assuming ASCII string:

void
PrintMissingCharacters(char *InputString)
{
UINT32 foundChars = 0xFC000000;
char* stringChar = InputString;
int bitIndex;

while (stringChar != '\0')
{
if (stringChar >= 'a' && stringChar = 'A' && stringChar <= 'Z')
{
bitIndex = stringChar - 'A';
BitSet(&foundChars, bitIndex);
}
}

for (int i = 0; i < 26; i++)
{
if (!BitTest(&foundChars, i))
{
printf("%c, ", ('a' + i));
}
}

Manav on Jan 25, 2010
1

Using Haskell to keep things terse:

    include Data.Char

    getMissingLetters sentence = filter (`notElem` map toLower sentence) ['a'..'z']

or for the more internationally inclined, who might be less biased towards English.

    generalizedGetMissingLetters sentence alphabet = filter (`notElem` map toLower sentence) alphabet

    Main> getMissingLetters "hello"
    "abcdfgijkmnpqrstuvwxyz"

Edward Kmett on Jan 25, 2010
2

#!/usr/bin/perl

$s='The good brown fox, hi.';
print join '', map {$s!~/$_/?$_:''} a..z;

Anonymous on Jan 25, 2010
2

#!/usr/bin/python
"""\
Example solution using Python
"""
import string

def getMissingLetters(sentence):
    """Use sets to find unused characters from the alphabet """
    return ''.join(set(string.lowercase)-set(sentence.lower()))

Nederhoed on Jan 27, 2010
0

Why were you asked this question for a financial analyst interview?

Jeffery on Jul 7, 2014
0

#include
#include

using namespace std;

string CheckPangrams(const string str)
{
    string s = str;
    string result = "";
    int hist[26] = {};

    for (int i=0; i<str.length(); i++) {
        if (isalpha(s[i])) {
            s[i] = tolower(s[i]);
            hist[s[i]-'a']++;
        }
    }

    for (int i=0; i<26; i++) {
        if (!hist[i])
            result += (char) (i+'a');
    }
    return result;
}

int main()
{

    string s = "";

    cout<<"Enter a sentence to check: ";
    std::getline(cin, s);

    cout<<"Input: "<<s<<endl;

    string result = CheckPangrams(s);

    if ("" == result)
        cout<<"Input sentence is a pangrams"<<endl;
    else
        cout<<"Missing characters: "<<result<<endl;

    return 0;
}

HL on Aug 7, 2014
0

import java.util.*;

public class PangramChecker {
    private final Character[] charSet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
                                            'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    private Set alphabetSet = new TreeSet(Arrays.asList(charSet));
    private Set inputSet = Collections.emptySet();

    public PangramChecker(String s) {
        if (s == null) {
            s = "";
        }
        inputSet = new HashSet(s.toCharArray().length);
        for (Character c : s.toCharArray()) {
            inputSet.add(c);
        }
    }

    public Set check() {
        alphabetSet.removeAll(inputSet);
        System.out.printf("\n Missing chars are: " + alphabetSet);
        return alphabetSet;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        PangramChecker pangramChecker = new PangramChecker(s.toLowerCase());
        pangramChecker.check();
    }
}

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import static org.junit.Assert.*;

public class PangramCheckerTest {

    @Before
    public void setUp() throws Exception {

    }

    @Test
    public void testCheck(){
        String s = "Hello World!";
        PangramChecker pangramChecker = new PangramChecker(s.toLowerCase());
        Set result = pangramChecker.check();
        Character[] charArray = {'a','b', 'c', 'f', 'g', 'i', 'j', 'k', 'm', 'n', 'p', 'q', 's', 't', 'u', 'v', 'x', 'y', 'z'};
        List l = Arrays.asList(charArray);
        Set expectedOutput = new TreeSet(l);
        assertTrue(result.equals(expectedOutput));

    }
}

although this does not check the char boundary "a" to "z"

sen on Mar 11, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.