Goldman Sachs interview question

Write a program to find the common characters in two strings. After writing the code they asked to reduce the complexity.

Interview Answer

Anonymous

21 Mar 2010

Let's assume we have the strings: "windows" and "linux". Create a first array of chars that contains the characters of the first string sorted by ascii code. [d,i,n,o, s,w, w]. Let's name this array A Create a second array of chars that contains the characters of the second string sorted by ascii code. [i, l, n, u ,x]. Let's name this array B. The pseudo algorithm will be as follow: posA = 0 posB = 0 while(posA < A.length && posB < B.length) { if (A[posA] == B[posB]) { print "find common character = " + A[posA]; posA++; posB++; } else if (A[posA] < B[posB]) { posA++; } else { posB++; } }