Amazon Interview Question for Backend Developers


Country: United States




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

The input can be combined with the reverse input by summing their ascii values. this string can then be hashed with a standard hash function. in python:

import hashlib

def reversable_hash(s):
    tmp = []
    for i in range(len(s)):
        tmp += [chr((ord(s[i]) + ord(s[len(s) -i -1])) % 255)]
    tmp = ''.join(tmp)
    return hashlib.md5(tmp.encode('utf8')).hexdigest()

yields:

% reversable_hash("banana")
3210b46e29e61d8865edf62e65929b76
% reversable_hash("ananab")
3210b46e29e61d8865edf62e65929b76
% reversable_hash("anaaab")
9009f73b1797b4c5f6851cf4865c5895
% reversable_hash("élève")
7b27c8eb83ab0aaa267352caaf0bea41
% reversable_hash("evèlé")
7b27c8eb83ab0aaa267352caaf0bea41
% reversable_hash("012")
08f8e0260c64418510cefb2b06eee5cd
% reversable_hash("210")
08f8e0260c64418510cefb2b06eee5cd

- tom.hostyn March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if we restrict equality to only the reverse strings?

E.g.

hash("baaann") != hash("banana")

- infoginx March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In general, different permutations will have different hashes.
E.g hash("baaann") != hash("banana")

however, there are indeed corner cases such as
hash ("baanna") == hash ("banana")

btw - edited the code to ensure we modulo the sum, not the last term

- tom.hostyn March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create hash using hash(givenString + reverse(givenString)).

- hprem991 March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well if we are just looking for same hashes for anagrams, and security is not a priority, then just sort both strings.

- asub March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well if security is not a priority and we are just looking at anagrams, just sort both strings.

- asub March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

with +, do you mean string concatination ? That would yield different hash values.

% hashlib.md5("bananaananab".encode('utf8')).hexdigest()
4a7c040bad14e734e3aa0a430c7de397
% hashlib.md5("ananabbanana".encode('utf8')).hexdigest()
5743eb3309a43451ec8a253923437c37

- tom.hostyn March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

string ReverseHash(string s) {
    string hash_str;
    int first = 0;
    int last = s.length()-1;

    while(first <= last) {
        if(first != last) {
            if(s[first] <= s[last]) {
                hash_str.push_back(s[first]);
                hash_str.push_back(s[last]);
            } else {
                hash_str.push_back(s[last]);
                hash_str.push_back(s[first]);
            }
        } else {
            hash_str.push_back(s[first]);
        }
        first++;
        last--;
    }
    return hash_str;
}

- Akash Panda March 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

string ReverseHash(string s) {
    string hash_str;
    int first = 0;
    int last = s.length()-1;

    while(first <= last) {
        if(first != last) {
            if(s[first] <= s[last]) {
                hash_str.push_back(s[first]);
                hash_str.push_back(s[last]);
            } else {
                hash_str.push_back(s[last]);
                hash_str.push_back(s[first]);
            }
        } else {
            hash_str.push_back(s[first]);
        }
        first++;
        last--;
    }
    return hash_str;
}

- Akash Panda March 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int hash(String any) {
        int hash = 23;//any intial value
        hash += any.charAt(0);
        for(int i = 1;i<any.length();i++) {
            hash += any.charAt(i)+Math.abs(any.charAt(i) - any.charAt(i-1));
        }

        return hash;
    }

- Lokesh Malwiya March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int hash(String any) {
        int hash = 23;//any intial value
        hash += any.charAt(0);
        for(int i = 1;i<any.length();i++) {
            hash += any.charAt(i)+Math.abs(any.charAt(i) - any.charAt(i-1));
        }

        return hash;
    }

- Lokesh Malwiya March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int hash(String any) {
int hash = 23;//any intial value
hash += any.charAt(0);
for(int i = 1;i<any.length();i++) {
hash += any.charAt(i)+Math.abs(any.charAt(i) - any.charAt(i-1));
}

return hash;
}

- Lokesh Malwiya March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{int reverseHash(string s)
{
string rev = s;
string toHash = "";
reverse(rev.begin(),rev.end());
hash<string> h;
toHash += s < rev ? s+rev : rev+s;
return h(toHash);
}}}

- Anonymous March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{int reverseHash(string s)
{
string rev = s;
string toHash = "";
reverse(rev.begin(),rev.end());
hash<string> h;
toHash += s < rev ? s+rev : rev+s;
return h(toHash);
}}}

- dandashino March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Swift,

func Hash(_ string: String) -> String {
    let array = string.map({ $0 })
    let reversedArray = string.reversed().map({ $0 })
    var hashSeed = [UInt32]()
    for (chara1, chara2) in zip(array, reversedArray) {
        let val1 = chara1.unicodeScalars.reduce(0, { (result, scalar) -> UInt32 in
            scalar.value
        })
        let val2 = chara2.unicodeScalars.reduce(0, { (result, scalar) -> UInt32 in
            scalar.value
        })
        hashSeed.append(val1 + val2)
    }
    print("\(string) = \(hashSeed)")

    return hashSeed.reduce("", { $0 + String($1) })
}

Hash("banana") == Hash("ananab")
Hash("banana") == Hash("banaaa")

- takecian March 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String revHash(String arr) throws NoSuchAlgorithmException {

        StringBuilder stringBuilder = new StringBuilder();
        int N = arr.length();
        for (int i = 0; i < N / 2; i++) {
            int numericValue = (int) (arr.charAt(i));
            numericValue += (int) (arr.charAt(N - i - 1));
            stringBuilder.append((char) numericValue);
        }

        MessageDigest messageDigest = MessageDigest.getInstance("MD5");
        return printHexBinary(messageDigest.digest(stringBuilder.toString().getBytes()));
    }

- abrahamimohiosen April 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The Pearson hashing function fails to create a unique key for anagrams. It also is one of the simplest. Pseudo: foreach char c in string, key = key xor c

- Shawn Smith April 11, 2019 | Flag Reply


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