Adam Smith
BAN USERdiaphone@gmail.com
I know you meant to write DAG for directed acyclic graph, and this is the solution I would take also. If the set of words you are given demonstrates the ordering of all possible letter combinations, the DAG has a unique topological sort which is the alphabet order. If you don't have all possible relationships, you can make a dummy "root" node for your graph, from which you build edges to any letter node with no input edges. In this case, there will be multiple valid topological sorts, one of which is the correct alphabet order, but you won't have enough information to know which one.
Depth-first, post-ordered traversal of the graph, then reversed, is indeed a good way to generate the topological sorts. If you don't have all letter relationships, you have to exhaustively do all possible traversal permutations to be sure one is the correct solution. The question is worded a little weird, since it asks for "one valid ordering", but really should say "one possible ordering from what is known" if they don't require the solution to necessarily be correct in the event of not enough input--the word "valid" is a bit ambiguous here since we can assume there is only one true ordering.
This moves non-zero elements to the opposite end of the array than what is asked for. Also, just be aware it does not preserve order of the non-zero elements, and upon seeing this, the interviewer might say this is fine, or might ask you to solve it again with a stable solution.
- Adam Smith November 28, 2014I've made one that's quite tight and also stable:
#include <iostream>
//Solution
void MoveNonZerosToTheLeft(int array[], int size)
{
int insertPoint = 0;
for (int i = 0; i < size; ++i)
{
if (array[i] == 0) continue;
array[insertPoint] = array[i];
if ( i > insertPoint++ ) array[i] = 0;
}
}
// Test Code
int main(int argc, const char * argv[])
{
int testArray[] = { 0,0,0,1,2,3,4,5,0,6,7,8,9,0,10,0 };
MoveNonZerosToTheLeft(testArray, 16);
for (int i = 0; i < 16; ++i) std::cout << testArray[i] << " ";
std::cout << std::endl;
return 0;
}
This code appears to fail to recognize any of the following as single-edits:
xyz xz //middle char removed
xyz ayz //first char replaced
xyz yyz //first char replaced
xyz zyz //first char replaced
xyz xayz // insertion at [1]
xyz xyaz // insertion at [2]
xyz xxyz // insertion of dupe at [1] or [2]
xyz xyyz // insertion at dupe [2] or [3]
Here is a way to do it. I've included what I believe is a thorough set of unit test cases, and I've noticed some of the previously posted solutions don't handle them all correctly. If you have a solution to this, I encourage you to run it against all of the cases I've included below. Are there any test cases I missed?
One minor point that warrants a clarification question: None of the example cases show an insert growing the string to 4 characters. This leaves it ambiguous as to whether a change such as xyz --> axy can be considered a single edit (i.e. single insertion at beginning of a fixed 3-character buffer) or whether it is two edits (insertion of 'a' and deletion of 'z').
//
// main.cpp
// OffByOneEdit
//
// Created by Adam Smith on 11/27/14.
//
#include <iostream>
#include <string>
bool AreStringsOneEditDifferent(const std::string& str1, const std::string& str2)
{
unsigned long l1 = str1.length();
unsigned long l2 = str2.length();
// Exit early if length of strings differs by more than 1 character
// string.length() returns unsigned long, this is why absolute value function is not used.
if (((l1 > l2) && ((l1-l2) > 1))
|| ((l2>l1) && ((l2-l1) > 1))) return false;
// Special case for equal-length strings
if (l1 == l2)
{
bool bDiffFound = false; // Difference detected in equal-length strings
for (int i = 0; i < l1; ++i)
{
if (str1[i] != str2[i])
{
if (bDiffFound) return false;
bDiffFound = true;
}
}
return bDiffFound;
}
// Case for strings that differ in length by 1
int offset = 0;
const std::string &shorter = (l1 < l2) ? str1 : str2;
const std::string &longer = (l1 < l2) ? str2 : str1;
for (int i = 0; i < shorter.length(); ++i)
{
if (shorter[i] != longer[i+offset])
{
if (offset > 0) return false; // We found a second difference, fail.
offset = 1;
--i;
}
}
return true;
}
int main(int argc, const char * argv[])
{
std::cout << "Success Cases:" << std::endl;
//Single removal true test cases
std::cout << "xyz yz " << AreStringsOneEditDifferent("xyz", "yz") << std::endl;
std::cout << "xyz xz " << AreStringsOneEditDifferent("xyz", "xz") << std::endl;
std::cout << "xyz xy " << AreStringsOneEditDifferent("xyz", "xy") << std::endl;
//Single replacement with new character true test cases
std::cout << "xyz ayz " << AreStringsOneEditDifferent("xyz", "ayz") << std::endl;
std::cout << "xyz xaz " << AreStringsOneEditDifferent("xyz", "xaz") << std::endl;
std::cout << "xyz xya " << AreStringsOneEditDifferent("xyz", "xya") << std::endl;
//Single replacement with duplicate character true test cases
std::cout << "xyz yyz " << AreStringsOneEditDifferent("xyz", "yyz") << std::endl;
std::cout << "xyz zyz " << AreStringsOneEditDifferent("xyz", "zyz") << std::endl;
std::cout << "xyz xxz " << AreStringsOneEditDifferent("xyz", "xxz") << std::endl;
std::cout << "xyz xzz " << AreStringsOneEditDifferent("xyz", "xzz") << std::endl;
std::cout << "xyz xyx " << AreStringsOneEditDifferent("xyz", "xyx") << std::endl;
std::cout << "xyz xyy " << AreStringsOneEditDifferent("xyz", "xyy") << std::endl;
//Single insertion of new character true test cases
std::cout << "xyz axyz " << AreStringsOneEditDifferent("xyz", "axyz") << std::endl;
std::cout << "xyz xayz " << AreStringsOneEditDifferent("xyz", "xayz") << std::endl;
std::cout << "xyz xyaz " << AreStringsOneEditDifferent("xyz", "xyaz") << std::endl;
std::cout << "xyz xyza " << AreStringsOneEditDifferent("xyz", "xyza") << std::endl;
//Single insertion of duplicate true test cases
std::cout << "xyz xxyz " << AreStringsOneEditDifferent("xyz", "xxyz") << std::endl;
std::cout << "xyz xyyz " << AreStringsOneEditDifferent("xyz", "xyyz") << std::endl;
std::cout << "xyz xyzz " << AreStringsOneEditDifferent("xyz", "xyzz") << std::endl;
std::cout << std::endl << "Failure Cases:" << std::endl;
// Removal and replacement failure cases
std::cout << "xyz az " << AreStringsOneEditDifferent("xyz", "az") << std::endl;
std::cout << "xyz ya " << AreStringsOneEditDifferent("xyz", "ya") << std::endl;
std::cout << "xyz xa " << AreStringsOneEditDifferent("xyz", "xa") << std::endl;
std::cout << "xyz ay " << AreStringsOneEditDifferent("xyz", "ay") << std::endl;
// Removal and insert failure cases (that are not equivalent to one replace)
std::cout << "xyz yaz " << AreStringsOneEditDifferent("xyz", "yaz") << std::endl;
std::cout << "xyz yza " << AreStringsOneEditDifferent("xyz", "yza") << std::endl;
std::cout << "xyz axz " << AreStringsOneEditDifferent("xyz", "axz") << std::endl;
std::cout << "xyz xza " << AreStringsOneEditDifferent("xyz", "xza") << std::endl;
std::cout << "xyz axy " << AreStringsOneEditDifferent("xyz", "axy") << std::endl;
std::cout << "xyz xay " << AreStringsOneEditDifferent("xyz", "xay") << std::endl;
// Replace and insert failure cases
std::cout << "xyz aayz " << AreStringsOneEditDifferent("xyz", "aayz") << std::endl;
std::cout << "xyz ayaz " << AreStringsOneEditDifferent("xyz", "ayaz") << std::endl;
std::cout << "xyz ayza " << AreStringsOneEditDifferent("xyz", "ayza") << std::endl;
std::cout << "xyz axaz " << AreStringsOneEditDifferent("xyz", "axaz") << std::endl;
std::cout << "xyz xaaz " << AreStringsOneEditDifferent("xyz", "xaaz") << std::endl;
std::cout << "xyz xaza " << AreStringsOneEditDifferent("xyz", "xaza") << std::endl;
std::cout << "xyz axya " << AreStringsOneEditDifferent("xyz", "axya") << std::endl;
std::cout << "xyz xaya " << AreStringsOneEditDifferent("xyz", "xaya") << std::endl;
std::cout << "xyz xyaa " << AreStringsOneEditDifferent("xyz", "xyaa") << std::endl;
return 0;
}
I was assuming the matrix would be a 2D array in memory, with random access to all elements. Conventionally, the 'n' in what's given for big-O notation for searching data structures is the number of elements in the structure (i.e size of the data set). For the example, n=25. You could call it O(N*M) if you make it clear that you're talking about an N-by-M matrix, but you wouldn't call this O(n^2) because people would misinterpret you. An example of an O(n^2) operation on this puzzle would to be compare every letter to every other.
- Adam Smith November 05, 2014I was mentally picturing option 3 with early exit cases.
1. Check each circle for intersection with each side of the box. If you encounter a circle that divides the box (intersects top or left side, AND intersects bottom or right side) exit out reporting no path from (0,0) to (x,y). In this same linear pass, all circles you find that touch the left or top sides you add to a list of starting nodes. As you mention, you can think of these as the second level of a tree, all connected to a root node that represents "top or left side".
2. For each of the nodes, check against all remaining (i.e. not yet part of the tree) circles for intersection. Any circles that intersect the current node become new nodes off that one in the next level of the tree. Each time a new circle is added to the tree, check to see if it intersects the right or bottom of the box, if so, you exit reporting there is no path from (0,0) to (x,y)
3. Repeat step 2 for each newly added node. This recursion continues until the exit condition is encountered (returning no path) or all N circles are visited without hitting the exit condition, in which case you return that travel from (0,0) to (x,y) is possible.
You will only end up adding each circle to the tree once, but the number of circle intersection checks is on the order of n^2.
I like the idea of an A*-like method for choosing which nodes to explore first, with the estimate being whichever is shorter: the distance from the circle center to the bottom side, or to the right side. This would, however, add the need to sort each node's children by this value to determine the order to explore them in, right? I suspect that there are cases where this would indeed speed up finding an early exit if there is one, but the sorting also adds running time to the worst cases where the tree gets fully built without early exit or there is a connection, but the path is serpentine.
OK great!
For those who are familiar with Java and are scratching their heads wondering why this example is a pass-by-value situation and not pass-by-reference, it comes down to what exactly is being put on the call stack. In the above example, think of "a" and "n" as being integers. "n" is a new variable that gets a copy of the value of "a", hence pass by value. For it to be a pass-by-reference call, you would have to pass the memory address of "a" itself to the function, so that even what "a" points to could be altered. This one level of indirection is the distinction. You cannot do this in Java, but that is what is meant by reference in other languages.
Yes, this is all as expected. As you can see, the Number object is not copied. There are 3 reference variables in play: main::a, increment::n and increment::temp and you are making them all point to the same Number object. It's pass by value because increment::n is a copy of main::a, that is to say, main::a is passed by value. Run the following modification to your program and you will see what I mean:
package com.test;
public class CallByReference
{
public static void main(String[] args)
{
Number a = new Number();
a.x = 3;
System.out.println("Value of a.x before calling increment() is " + a.x);
increment(a);
System.out.println("Value of a.x after calling increment() is " + a.x);
}
public static void increment(Number n)
{
System.out.println("Value of n.x before re-assign is " + n.x);
n = new Number();
n.x = 7;
System.out.println("Value of n.x after re-assign is " + n.x);
}
}
class Number {
int x;
}
Value of a.x before calling increment() is 3
Value of n.x before re-assign is 3
Value of n.x after re-assign is 7
Value of a.x after calling increment() is 3
The program changes what 'n' points to, without affecting 'a', which is possible because 'n' is a copy of 'a', not a reference to 'a'. It doesn't matter so much in Java, because there is no other way to pass the object to the function, but in other languages like C++ you have multiple options that behave differently. It's possible in C++ to actually pass 'a' by reference and change what it points to.
Even in Java, the actual object on the heap is not copied. It behaves as you say, but only because the reference to the object is being copied and passed by value. In your example, there are two variables named "or", both of which reference the same Order object. Inside your orderSubmission() function, you can use the local "or" to access the object, but you could reassign the local copy of "or" to point to a new Order object, without affecting what the calling code's "or" reference points to.
- Adam Smith November 01, 2014This one is pretty straightforward: Do one pass of the matrix O(n) finding all instances of the starting letter ("M" in the example). From each M you find, path outwards (N,S,E,W, optionally NW,NE,SW,SE) terminating the path as soon as you encounter a letter not in the sequence, and continuing the search when you find the next expected letter (e.g. "I"). Repeat recursively. You can do this exhaustively to find all instances of the word, or exit when you find the first complete path, depending on what is asked for.
I'd also ask the interviewer if letters can be used more than once (i.e. path can have loops) or if the visited letter nodes must be marked and not revisited.
In your second paragraph, you meant to say "the actual object is NOT being copied".
- Adam Smith November 01, 2014A virtual function is a member function of a class that can be overridden at runtime in a derived class (dynamic rather than static binding). Calling the function via a base-class pointer will result in a call to the derived class version. The reference is resolved at runtime, using the virtual function table (vtable), which is just a table of function addresses. The base class function need not even be defined, it can be "pure virtual", meant to be defined only in derived classes. This of course makes the base class abstract so it cannot be instantiated, only used as a common ancestor for subclasses.
It's important to make base class destructors virtual, so that the in the event your derived-class object is deleted via a base-class pointer, the derived version of the destructor is called, because your derived class could allocate memory that needs freeing, register for events using a pointer to itself which needs unregistering, etc.
It sounds to me like a problem solvable by circle-circle and circle-line-segment intersection. Consider the rectangle's 4 sides: (L)eft, (T)op, (R)ight, (B)ottom. If you can establish that there is a "chain" of intersecting circles that connects L-B, T-B, T-R or L-R then there is a blockade which prevents travel from the lower left corner to the top right. The chain can be a single circle intersecting two relevant sides, or a long chain of intersecting circles. Chains from L-to-T or B-to-R can't block the path if those are the only sides they touch.
I haven't written an algorithm to solve this, just thought about it for a couple minutes, but I would expect it to be O(n^2) worst case runtime (long chain of all n circles, n^2 circle-circle tests), O(n) best case to prove there is a path if in one pass over all circles you find that none intersect the rectangle, and O(1) best case to find there is no path, since you could discover on your very first inspection a circle that makes a blocking connection between 2 sides.
Clarification question #1: The arrays you were given are sorted. Ask the interviewer if the function will always be operating on already-sorted arrays or not, since that is a very obvious opportunity for optimization.
Clarification #2: Can the arrays have duplicates of the same value? If they do, should the intersection contain unique values? For example, if each array has 3 copies of the number 7, should the intersection array also have 3 copies of 7, or just one 7? I've assumed the latter in my examples, but either case is a valid real-world problem.
I wrote two functions in C# to find the intersections.
The function with Presorted in the name only works if it's given arrays of ints that are already sorted in ascending order. It doesn't validate that they are sorted, because I didn't want to confuse the intersection code with validation code, so this version simply returns incorrect results if given unsorted arrays. This version runs quicker than the other, because it takes advantage of knowing the arrays are sorted, looping only as many times as the length of the longer array. Loop does min(n,m) iterations, for Time complexity: O(n)
In the function with Unsorted in the same, the arrays need not be sorted. The smaller of the two arrays is copied into a HashSet, and the larger array is looped over. Any element in the larger array that is already in the HashSet is pushed into a new HashSet that is the scratch space for the results. I used the HashSet here because the arrays we have are unsorted, so this gives an O(1) way to be sure we're not putting duplicates into the output. if you clarified that duplicate values are not expected in the input arrays, or preservation of duplicates is desired in the output, you could save some memory and use a temp array here just as is done in the Presorted function. At the end of the function, the result HashSet is copied into the return value array. The intersection is not sorted, the values are in the order they are encountered in the larger of the 2 arrays.
static void Main( string[] args )
{
int[] arr1 = { 10, 9, 8, 2, 7, 6, 5, 4, 3, 2, 1 };
int[] arr2 = { 2, 2, 3, 5, 6, 9 };
int[] intersection;
/*
* Test of version that can handle unsorted arrays
*/
ArrayIntersectionUnsorted( arr1, arr2, out intersection );
PrintArray( intersection );
/*
* Test of version optimized for already-sorted arrays
*/
Array.Sort( arr1 );
Array.Sort( arr2 );
ArrayIntersectionPresorted( arr1, arr2, out intersection );
PrintArray( intersection );
}
static void ArrayIntersectionPresorted( int[] arr1, int[] arr2, out int[] intersection )
{
int i = 0;
int j = 0;
int count = 0;
// Make temporary array the size of the smaller input array
int[] tempArray = new int[Math.Min( arr1.Length, arr2.Length )];
while ( i < arr1.Length && j < arr2.Length )
{
if (arr1[i]==arr2[j])
{
// Record the value that is common to both arrays
tempArray[count++] = arr1[i];
++i;
++j;
// Skip over duplicates of the value we just found
while ( i < arr1.Length && arr1[i] == arr1[i - 1] ) ++i;
while ( j < arr2.Length && arr2[j] == arr2[j - 1] ) ++j;
}
else if ( arr1[i] < arr2[j] )
{
++i;
}
else
{
++j;
}
}
// Copy results from temporary array to return value array
// which is only as large as is necessary
intersection = new int[count];
Array.Copy( tempArray, intersection, count );
}
static void ArrayIntersectionUnsorted( int[] arr1, int[] arr2, out int[] intersection )
{
int[] smallerArray = ( arr1.Length <= arr2.Length ) ? arr1 : arr2;
int[] largerArray = ( arr1.Length <= arr2.Length ) ? arr2 : arr1;
HashSet<int> table = new HashSet<int>( smallerArray );
HashSet<int> result = new HashSet<int>();
for ( int i = 0; i < largerArray.Length; ++i )
{
if ( table.Contains( largerArray[i] ) && !result.Contains(largerArray[i]) )
{
result.Add( largerArray[i] );
}
}
intersection = new int[result.Count];
result.CopyTo( intersection );
}
static void PrintArray( int[] array )
{
if ( array.Length > 0 )
{
for ( int i = 0; i < array.Length - 1; ++i )
{
Console.Write( array[i] + "," );
}
Console.WriteLine( array[array.Length - 1] );
}
else
{
Console.WriteLine( "Empty array." );
}
}
Yes, that's what makes it a brain teaser, that facepalm moment when you realize no calculation is necessary; each birth is an independent Bernoulli trial and half of all children born will be boys, no matter what each couple's criterion is for stopping.
- Adam Smith October 31, 2014Just FYI, most interviewers will expect you to do a static test of your code. At very least you will want to pass even and odd length palindromes and non-palindromes, plus various corner cases like empty string and single-character. Doing this, you would spot that this code does a meaningless final comparison for all odd-length palindromes (including single character input)--how can a character not be equal to itself? You should also provide a type for inputStr; You never know if your interviewer might try to type it in verbatim and compile it, or what they consider excusable.
- Adam Smith October 30, 2014While your main() function is technically a function which detects a palindrome, you will be expected to understand that you're being asked for a utility function that takes some manner of string as an argument and returns a boolean or equivalent enum value.
Secondly, the <= in the while loop condition results in one extra iteration of the loop for odd-length strings, wherein you check the middle character against itself unnecessarily.
Lastly, once converted to a utility function there will be no need for the allocation of k, or the if-then after the loop, since you'll exit with a return false where you have the k=0, or return true after the loop. Also, allocating an int where only a bool is needed is poor form, since an int can be much larger than a bool on some systems (memory wasted). Using appropriate types makes for better portability and readability.
You would be correct. Your solution has runtime performance of O(n^2) in the worst case of being given an array of all zeros, and achieves O(n) really only in the best case of an array with no zeroes. The best solutions are O(n) runtime for all input. Also, you are allocating a variable "temp" which is unneeded as it can never have a value other than 0, and you could just do: a[i+1] = 0;
- Adam Smith December 04, 2014On the plus side, your algorithm is stable (preserving order) and O(1) in memory use, and many solutions on this page duplicate the entire array (O(n) memory use).