As I tend to do from time to time; Here is another good set of interview questions to toy with (These particular ones are in C#):
private static char FindLongestRun(string str)
{
Dictionary<char, int> runs = new Dictionary<char, int>();
char last = str[0];
runs.Add(last, 1);
for(int i = 1; i < str.Length; i++)
{
if (last == str[i])
{
int oldCount = runs[last];
runs.Remove(last);
runs.Add(last, oldCount + 1);
}
else
{
runs.Remove(str[i]);
runs.Add(str[i], 1);
}
}
char longest = last;
foreach (char c in runs.Keys)
{
if (runs[c] >= runs[longest])
longest = c;
}
return longest;
}
private static int BinSearch(int[] arr, int seek)
{
return BinSearch(arr, 0, arr.Length - 1, seek);
}
private static int BinSearch(int[] arr, int min, int max, int seek)
{
if (min > max)
return -1;
else if (min == max)
return (arr[min] == seek ? min : -1);
else
{
int partIdx = min + ((max - min) / 2);
int left = BinSearch(arr, min, partIdx, seek);
int right = BinSearch(arr, partIdx + 1, max, seek);
if (left != -1)
return left;
if (right != -1)
return right;
return -1;
}
}
private static int Atoi(string number)
{
int result = 0;
int multiplier = 1;
for (int idx = number.Length - 1; idx >= 0; idx--)
{
char digitChar = number[idx];
int digitValue = digitChar - '0';
result += (digitValue * multiplier);
multiplier *= 10;
}
return result;
}
private static string ReverseString(string str)
{
char[] strChars = str.ToCharArray();
for (int idx = 0; idx < strChars.Length / 2; idx++)
{
char tmp = strChars[str.Length - 1 - idx];
strChars[str.Length - 1 - idx] = strChars[idx];
strChars[idx] = tmp;
}
return new String(strChars);
}
private static int BitCount(int number)
{
int bits = 0;
while (number > 0)
{
bits += (number % 2);
number /= 2;
}
return bits;
}
This is a fairly common interview question. Here is one possible solution using recursion:
int getMaxDepth(node n)
{
if(n == null)
return 0;
l = 1 + getMaxDepth(n.left);
r = 1 + getMaxDepth(n.right);
return (l > r ? l : r);
}
Another mental exercise:
public static T[] FindIntersection<t>(T[] a, T[] b) where T : IComparable
{
LinkedList<t> answer = new LinkedList<t>();
Array.Sort(a);
Array.Sort(b);
int aptr = 0;
int bptr = 0;
while (aptr < a.Length && bptr < b.Length)
{
if (a[aptr].Equals(b[bptr]))
{
answer.AddFirst(a[aptr]);
aptr++;
bptr++;
}
else if (a[aptr].CompareTo(b[bptr]) < 0)
{
aptr++;
}
else
{
bptr++;
}
}
return answer.ToArray<t>();
}
The latest in this series makes a shift from C++ to Java since that’s what I’ve been mucking about with lately. I’m in a little bit of a time squeeze at the moment so explanations will have to come later (though this code should be fairly readable and obvious what its doing).
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
public class Program
{
public static void main(String[] args)
{
doMatrixSearch();
doMissingNumberSearch();
doFirstUnrepeated();
}
public static void doFirstUnrepeated()
{
String testString = "nnnnnnnnxxnnpnn";
char[] testStringChars = testString.toCharArray();
class EntryInfo
{
int count;
int firstPos;
}
HashMap<character, EntryInfo> stuff = new HashMap<character, EntryInfo>();
for(int i = 0; i < testStringChars.length; i++)
{
EntryInfo thisInfo;
if(stuff.containsKey(testStringChars[i]))
{
thisInfo = stuff.get(testStringChars[i]);
thisInfo.count++;
}
else
{
thisInfo = new EntryInfo();
thisInfo.count = 1;
thisInfo.firstPos = i;
}
stuff.put(testStringChars[i], thisInfo);
}
int minPosition = testStringChars.length - 1;
Collection<character> coll = stuff.keySet();
Iterator<character> iter = coll.iterator();
while(iter.hasNext())
{
Character thisChar = iter.next();
EntryInfo thisInfo = stuff.get(thisChar);
if(thisInfo.count == 1 && thisInfo.firstPos < minPosition)
minPosition = thisInfo.firstPos;
}
System.out.println("doFirstUnrepeated():\t First non-repeater: " + testStringChars[minPosition]);
}
public static void doMissingNumberSearch()
{
int minInclusive = 1;
int[] arr = {1,2,5,6,7,8,9};
int[] missingNums = new int[2];
int missingNumsPtr = 0;
int shouldExist = minInclusive;
for(int i = 0; i < arr.length && missingNumsPtr < 2; i++)
{
if(arr[i] != shouldExist)
{
missingNums[missingNumsPtr] = shouldExist;
missingNumsPtr++;
}
shouldExist++;
}
System.out.println("doMissingNumberSearch():\t Missing nums: " + missingNums[0] + " and " + missingNums[1]);
}
public static void doMatrixSearch()
{
int numRuns = 1000;
int numSteps = 0;
for(int z = 0; z < numRuns; z++)
{
Random rnd = new Random();
int[][] arr = new int[5][5];
int last = 0;
for(int y = 0; y < 5; y++)
{
for(int x = 0; x < 5; x++)
{
int newval = rnd.nextInt(5) + last;
arr[x][y] = newval + 10;
last = newval;
}
}
int toFind = 30;
numSteps += matrixSearch(arr, toFind);
}
double averageSteps = (double)numSteps / (double)numRuns;
System.out.println("doMatrixSearch():\t Average steps: " + averageSteps);
}
public static int matrixSearch(int[][] arr, int toFind)
{
int numSteps = 0;
int x = arr[0].length - 1;
int y = 0;
while(x >= 0 && y < arr.length)
{
numSteps++;
if(toFind < arr[y][x])
x--;
else if(toFind > arr[y][x])
y++;
else if(toFind == arr[y][x])
break;
}
return numSteps;
}
}
Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:
- Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
- Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
- ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.
Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ‘smart’ pointer.):
void LinkedList::reverse()
{
if((_head == NULL) || (_length == 1))
{
return;
}
else
{
NodePtr previous = NodePtr();
NodePtr current = _head;
NodePtr next = NodePtr();
while(current)
{
next = current->next;
current->next = previous;
previous = current;
current = next;
}
_head = previous;
}
}
