Algorithm problems
Contents
About
On this page I keep a list of interesting little coding problems / questions and the solutions I came up with. The coding problems range in difficulty but represent the type of problems you may be asked in a university exam and are also good practice for job interview too. If you're interested in solving some you should read the questions above in the "table of contents" before scrolling down the the solutions I've written.
DISCLAMER: I've written most of these solutions myself, but have not tested them in code meaning: (a) more efficient solutions may exist and (b) the code may not necessarily compile! To me these solutions make sense, but if you spot any errors free free to start the discussion page or contact me directly (http://www.andrewnoske.com/contact.php).
Child Pages
Related/Child Pages:
- Algorithm problems - prep set 1 - Nice little set of questions including "virtual destructor" style questions.
- Algorithm problems - prep set 2 - Very small set of question questions.
Search Tree Problems
PROBLEM: Determine if a given number exists in a binary search tree (VERY EASY)
Answer: Involves traversing the binary search tree left or right depending on if the value is higher or lower, until you get to the end or find the matching number.
bool searchBinarySearchTree(Node *rootNode, int val) { Node *n = rootNode; while(n != NULL) { if (val == n->value()) return true; else if (val < n->value()) n = n->left(); else n = n->right(); } return false; // Not found. }
PROBLEM: Given a number and a binary search tree, find the closest node to that number (EASY)
Same as above, but you also need to keep track of which number is closest as you go down - for all you know the root node is closest! Here's a solution I wrote down in C++:
int getClosestValInBinaryTree(Node *rootNode, int findVal) { Node *n = rootNode; int closestVal = MAX_INT; int minDiff = MAX_INT; while(n != NULL) { int diff = abs(n->value() - findVal); if(diff < minDiff) { minDiff = diff; closestVal = n->value(); if(nodeDiff==0) return n->value(); } if(findVal < n->value()) n = n->leftNode(); else n = n->rightNode(); } }
Array Problems
PROBLEM: Given an array of integers (positive and negative), work out the largest sum of contiguous numbers (EASY)
This is a problem I was asked once and almost practiced for, but didn't - otherwise I could have figured it out straight away! The trickiest thing about this problem is figuring out the wording... by "largest contiguous sum" means that you have to find which subset of numbers, added together, give the biggest result. If we consider this example:
1,2,-4,3,2,-1,4 -> answer is 8 (3 +2 + -1 + 4)
* * * *
The answer is 8. The trick to figuring it out is to iterate through the numbers and sum them together, but reset the sum to 0 if it ever becomes negative... for instance (1+2+ -4 = -1), so we note that "3" is the largest sum so far, but then reset the sum to 0. The other trick, however is that you may get a sequence of only negative numbers, in which case the answer is the value of the largest negative number:
-80,-43,-1,-123 -> answer is -1
The solution I came up with, in C++ is:
int maxContiguousSum(vector<int> vect) { if(vect==NULL || vect.size()=0) return 0; int sum = vect[0]; // Running total. int maxSum = vect[0]; // Largest total found so far. for(int i=1; i<vect.size(); i++) { if(sum < 0) sum = 0; sum += vect[i]; if(sum > maxSum) maxSum = sum; } return (maxSum); }
PROBLEM: Given two unsorted arrays, find the intersections where 'b' duplicates 'a' (MEDIUM)
This problem is quite easy to solve by brute force: for each element in a, check each element in b... but this is O(n*m) and thus very undesirable. Probably the fastest solution is to turn one array into a hash table in O(n) time and then search for duplicates in O(m * (1 + n/k)) time (where k is the number of unique keys) - assuming a good hash function exists. Has tables can also find self-intersection really easily and both arrays could be concatenated to find all intersections.
If no good hash function exists, one could construct a binary search tree for the second array, and the problem becomes O(m log m) to sort, then O(n log m) to find all duplicates. Yet another options would be to sort both arrays using an algorithm like quicksort (qsort). This would then be O(m log m + n log n) to sort both arrays, then O(m + n) to search for duplicates. In C++ this would look like:
#include <iostream.h> #include <algorithm> #include <vector> void findIntersections(vector<int> a, vector<int> b) { sort(a); // O(n log(n)) time (where n = a.length). sort(b); // O(m log(m)) time (where m = b.length). int aIdx = 0; int bIdx = 0; while (aIdx < a.length && bIdx < b.length) // O(n + m) time. { if (a[aIdx] == b[bIdx]) { cout << a[aIdx] << " is in both a and b" << endl; aIdx++; bIdx++; } else if (a[aIdx] < b[bIdx]) { aIdx++; } else { bIdx++; } } }
PROBLEM: Given two arrays, find the longest common sequence (MEDIUM)
In this problem, we must search through two arrays (a and b) of integers (although could just as easily be characters in a string) and find the longest stretch of adjacent elements which are the same in array a and array b:
* * * * A: 1,2,0,1,2,2,4,0,1 |--> output should be: B: 1,2,2,4,1,3 | 1,2,2,4 (4 elements long) * * * *
The problem of "longest common subsequence" is explained an documented here on algorithmist.com, and it suggests a recursive solution which takes O(n^2). There is, however, a much faster way if you use "suffix arrays". In our two suffix array data structures, one for each array, we make a pointer to each element in the array, but also make sure we add a sentinel value at the end of each array so we know where to stop comparing characters. This is more-or less equivalent to creating a separate array starting at every potion of the array to the end (eg: 122413, 22413, 2413, 2413, 413, 13, 3), except that we don't need to repeat the same values again and again, we just need only need one pointer per starting position. This solution takes up O(n) extra space (where n is the sum of a and b's lengths), but we can sort the two suffix arrays (one for a and one for b) in O(n log n) time, and then process them in parallel in O(n*l) worst time where l is the length of the lowest common denominator. In C++ this looks like this:
#include <vector> #include <algorithm> // for "sort" using namespace std; const int SENTINEL = -9999; // Used to signal the end of the array. int countCommonElements(const int* a, const int* b) { // Used to count the number of common element int i; // in our suffix arrays (not including our sentinel). for(i=0; a[i]!=SENTINEL && a[i]==b[i]; i++); return i; } int compare(const int* a, const int* b) { // Used to find which array is "smaller"... int i; // think "alphabetically first" where: for(i=0; a[i]!=SENTINEL && a[i] == b[i]; i++); // > (0,1,2) is < (2,2) return (a[i]==SENTINEL || a[i] < b[i]) ? 1 : 0; // > (0,1) is < (0,1,1) and } vector <int> findLCS(vector<int> &a, vector<int> &b) { int n = a.size(); int i,j; // |-- Lets store the size of both our arrays int m = b.size(); // | before we add sentinel values to each. a.push_back(SENTINEL); // |-- Add sentinel values so we don't "compare" or b.push_back(SENTINEL); // | count too far when using our suffix arrays. vector<int*> aSuff(n); // |-- Used to store suffix array for a and b vector<int*> bSuff(m); // | respectively. for(i=0; i<n; i++) aSuff[i] = &a[i]; // |-- Setup the suffix array so that we have one for(i=0; i<m; i++) bSuff[i] = &b[i]; // | pointer to each element in the original vectors. sort(aSuff.begin(), aSuff.end(), compare); // |-- Sort both suffix arrays so the sequences sort(bSuff.begin(), bSuff.end(), compare); // | starting with the lowest ints come first. int maxLen = 0; // |-- Keep track of the current "longest common subsequence" found int aSuffIdx = -1; // | using its length (maxLen) and index within the first suffix array for(i=0, j=0; i<n && j<m;) // Progress through both suffix arrays until the end: { int len = countCommonElements(aSuff[i], bSuff[j]); // Counts the number of common elements. if(len > maxLen) { // If this has more: update values maxLen = len; aSuffIdx = i; } compare(aSuff[i], bSuff[j]) ? i++ : j++; // Whichever sequence is smaller, go to the next. } a.pop_back(); b.pop_back(); // Remove the sentinel values we added vector<int> returnVect(maxLen); // |-- Build up then return a new array for(i=0; i<maxLen; i++) // | representing the largest common substring returnVect[i] = aSuff[aSuffIdx][i]; // | we found. return returnVect; }
Linked Lists
PROBLEM: Change a linked list to start from the middle node (EASY)
This problem I thought up myself as an easy example of altering a singly linked list. Its solution involves two parts: (1) counting the number of elements in the linked list to determine which element/idex is in the middle... and (2) altering the node before it to be the new end, that node to be the new head and the last last element to link around. Here's what that might look like in C++:
void reodrerListToStartAtMiddle(Node *hHead) { if(nHead==NULL) return; int mid = (getListLength(nHead) - 1) / 2; if(mid<=0) return; giveListNewStartNode(nHead, mid); } bool giveListNewStartNode(Node *nHead, int newHeadIdx) // Designed to return true if change made. { if(nHead==NULL || newHeadIdx <=0) return (false); Node *oldHead = nHead; Node *prevNode = nHead; // Need to change the node just before idx "newHeadIdx". for(int i=0; i<newHeadIdx-1; i++) { if(prevNode->next == NULL) // Will occur if newHeadIdx is >= the linked list's length. return (false); prevNode = prevNode->next; } Node *n = prevNode->next; nHead = n; // This is now start of the linked list. prevNode->next = NULL; // This is now the end of the list. while(n->next != NULL) n = n->next; n->next = oldHead; // And the old last node points to the old first node. return (true); }
PROBLEM: Take two sorted linked lists and merge them (EASY)
This problem is the "merge" part of a merge sort algorithm. The answer seems simple enough keep taking the smallest value from the front of the list.... but the code seems a bit tricky. Here's what I wrote below, with the big assumption that it's a non-circular, single linked list (meaning the pointer in the last element is NULL) and that there is already an insert(Node *n, int val) function which will add a new node to the end of the list each time... otherwise you'd want another node pointer "combinedEnd" to the last node in "combined" and use this to insert values at the end more efficiently.
Node* mergeSortedLists(Node *leftHead, Node *rightHead) { Node *left = leftHead; Node *right = rightHead; Node *combinedHead; while(left!=NULL && right!=NULL) { if(left->value < right->value) { insert(combinedHead, left->value); // Assumption: this adds a new node with this value to the end. left = left->next; } else { insert(combinedHead, right->value); right = right->next; } } while(left!=NULL) { insert(combinedHead, left->value); left = left->next; } while(right!=NULL) { insert(combinedHead, right->value); right = right->next; } return combinedHead; }
PROBLEM: Reverse a linked list (EASY)
Given a singly linked list, here's some code to reverse it in C++:
void reverseLinkedListInPlace(Node **nHead) // Reverses the order of nodes and changes "nHead" (hence pointer to pointer needed). { // To point to what was the end, but now the start. if(n==NULL) return; Node *prev = NULL; Node *curr = *nHead; Node *next = NULL; while (curr!=NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } (*nHead) = prev; }
If was want to create a copy of a linked list and reverse it in one function call:
Node *reverseLinkedList(Node *aHead) // Creates a copy of a linked list with nodes reversed. { if(aHead==NULL) return NULL; Node *a = aHead; Node *b = NULL; Node *bPrev = NULL; while(a!=NULL) { b = new Node(); b->value = a->value; b->next = bPrev; bPrev = b; a = a->next; } return (bPrev); }
PROBLEM: Find where two single linked lists converge (MEDIUM-EASY)
This is a pretty tricky problem I was asked - tricky because it involves quite a lot of code and multiple functions. If two linked lists "converge" it implies that one or more elements at the end of the arrays match - for instance {a,b,c,d} and {e,f,g,c,d} converge on the letter c. If they don't have the same last element - for instance {a,b,c,d} and {b,b,c,d,e} - then then don't "converge" at all - so this is something you probably want to test first. It is possible to solve this in O(n+m) (linear) time (where n and m are the size of both linked lists) but there may be a few variations. The best solutions I've thought up involves iterating through both lists once to find their length, then calculating the difference (diff=abs(n-m)) and iterating through the longer list by this amount. These lists are now effectively the same length, and the converge point can be found by comparing elements from there:
bool doLinkedListsConvergeAndWhere(Node *aHead, Node *bHead, Node **aConverge, **bConverge) { *aConverge = NULL; *bConverge = NULL; if(aHead==NULL || bHead==NULL) return (false); int aLength = getLengthList(aHead); int bLength = getLengthList(bHead); Node *a = aHead; Node *b = bHead; for(int i=bLength, i<aLength; i++) // If a is longer move a till it is same length. a = a->next; for(int i=aLength, i<bLength; i++) // If b is longer move a till it is same length. b = b->next; while(a!=NULL && b!=NULL) { bool sameValue = (a->value == b->value); // These lines just for readability bool newCandidate = (aConverge == NULL) && (sameValue); // but could be merged below. if(!sameValue) { // If values don't match: *aConverge = NULL; // this will tell us there is no candidate yet found. *aConverge = NULL; } else if(newCandidate) { // If values do match and we don't yet have a candidate *aConverge = a; // update these values. *bConverge = b; } } return (*aConverge!=NULL); } bool getLengthList(Node *nHead) // Returns the number of nodes. { int length = 0; Node *n = nHead; while(n!=NULL) { n = n->next(); length++; } return (length); }
This is the answer I wish I'd given, however I didn't think to make both arrays the same size, so instead I suggested reversing them... it's still O(n+m) time, but definitely less efficient. I'll include the code below anyway:
bool whereLinkedListsConverge(Node *aHead, Node *bHead, int &valueConverge) { if (!doLinkedListsConverge(aHead, bHead)) return false; Node *aRevHead = NULL; Node *bRevHead = NULL; Node reverseLinkedListInPlace(aRevHead); // |-- Lets completely reverse these lists Node reverseLinkedListInPlace(bRevHead); // | knowing we can reverse them back at the end. Node *aRev = aRevHead; Node *bRev = bRevHead; while(aRev!=NULL && bRev!=NULL && aRev->value==bRev->value) { valueConverge = aRev->value; aRev = aRev->next; bRev = bRev->next; } reverseLinkedListInPlace(aRevHead); // |-- Now we must reverse the lists reverseLinkedListInPlace(bRevHead); // | back to their original state return true; } bool doListsHaveSameLastValue(Node *aHead, Node *bHead) // Inputs the start of both lists { // and checks if have same last element. if(aHead==NULL || bHead==NULL) return false; Node *a = aHead; Node *b = bHead; while(a->next!=NULL) a = a->next; while(b->next!=NULL) b = b->next; return (a->value == b->value); } void reverseLinkedListInPlace(Node *nHead); // See function in last problem.
Actually what was sad is that my solution I wrote was worse than this. For some reason I though I should make a reversed copy of the linked list. The first problem is that this takes as it also takes O(n+m) extra space and the next problem is that after finding the convergence point in the reversed list the reverse list needs to be freed (to avoid a memory link) and so suddenly the references to the convergence points become invalid!
String Problems
PROBLEM: Write an atoi function (EASY)
The 'atoi' function is a function to convert a string to an integer. To do this conversion means looking at each character in the string and using its ASCII value to help determine its integer value, and making sure all the digits are summed together by the right amount. If you know the digit's position you could use the "digitValue * pow(10, digitPos)" (eg: if the second digit is 3 then it is worth '30'), but the "pow" function is quiet expensive, so the better solution is to multiply the sum by ten each time you move right a digit. Another thing to consider is there might be a '-' at the front. Here's a solution for C++ string:
#include <string> using namespace std; int atoi(string str) { if(str.length() == 0) return 0; int value = 0; int sign = 1; int i = 0; if(str[0]=='-') { sign = -1; i = 1; } for(; i<str.length(); i++) { // For each digit: int digitVal = (int)str[i] - (int)'0'; // '0' is 48 in ASCII table, but that's easy to forget. value = value * 10 + digitVal; } return (sign * value); }
If instead this had to be solved for a C string, you can determine when you get to the last character when it's NULL. The C string solution below also makes use of some clever bit-shifting to make the (*10) operation less expensive.
unsigned int atoiForCString(const char *string) { unsigned int val; val=0; while(*string) { val=(val<<3) + (val<<1) + (*string - '0'); // Uses bit shift to (val*8)+(val*2). string++; // Dont increment i! } return(val); }
PROBLEM: Find the longest palindrome in a given string (MEDIUM)
The problem is to find the longest palindrome hidden within a string. A palindrome is a sequence that can be read the same way in either direction. A few examples: "121", "abba" and "refer". Palindromes are the same spelt backwards as forwards. My solution below starts the beginning and uses each character as a "center" and searches left and right as far as characters match, before advancing the center. Also note that a palindrome can have an even number of letters, so I have accounted for this too.
#include <string> string findLongestPalindrome(string str) { string longestPalindrome = ""; int longestLength = 1; for(int i=1; i<str.length()*2 - longestLength; i++) { int center = i/2; // Index of the current "center" within "str". int leftIdx = center - 1; // Used to iterate left of the center. int rightIdx = center + 1; // Used to iterate right of the center. if(i%2==0) // To account for palindromes with even number of letters. left = center; while(left>=0 && right < str.length() // While left and right are in limits && str[left] == str[right]) // and left and right are equal: { int length = right - left + 1; if(length > longestLength) // If this is our longest: { longestLength = length; //|-- Update. longestPalindrome = substr(left, length); //| } left--; //|-- Expand left and right out from center. right++; //| } } return (longestPalindrome); }
It's possible there's a way to make this more efficient using data structures, but if so I haven't figured it out yet, so please let me know if that's true! In this section I also have the disclaimer that I haven't tested any of these functions - but am pretty sure they'll work just by looking at them.
Math and Other Problems
PROBLEM: Multiply two integers without using multiply or divide operation (MEDIUM-EASY)
This is the type of hard question you might see on an assignment but would never have to do in real life! To solve it you will need some kind of loop, and the simplest solution would be to add a to itself b times.
int multiplyTheHardWay(int a, int b) // We want to return a*b. { int sum = 0; for(int i=0; i<a; i++) sum += b; for(int i=0; i>a; i--) // In case a is negative. sum -= b; return (sum); }
The second for loop here only gets used if a is negative. It might also be worth adding a few lines up top to check if a or b is 0 (return 0) or 1 (return the opposite value) - but not essential (you could just add 0 or 1 to itself many times). For a recursive version:
int multiplyRecursive(int a, int b) { if(a == 0) return 0; if(a > 0) return (b + multiplyRecursive(a-1, b)); if(a < 0) return -multiplyRecursive(-a, b); }
Recursive or not this is slow O(a). A faster solution might involve the use of a modulus operator (%) and/or bit-wise operators like bit-shift (<<) and bit-wise and (&). I haven't tested it, but I *think* this should work:
int multiplyUsingBitwiseTrick(int a, int b) unsigned int sum = 0; unsigned int bitmask = 1; for(int d=1; d<=32; d++) // Unsigned int is usually 32 bits, so once for each digit/bit. { if(a & bitmask != 0) sum += b << (d-1); bitmask = bitmask << 1; // Or could double using "bitmask += bitmask;". } }
See Also
- Data structures - vectors, linked lists, hash tables and so on - it is important to be able to use most of these
- Sorting algorithms - includes descriptions and code for all the common types of sorts
- Object-oriented languages - highlights differences between C++, C#, Java and other OO languages
Links
- Data structure - Wikipedia
- Google Code Jam - has a list of past problems presented as part of their "code jam" competition.
- ProgrammerInterview.com - contains a huge list of questions about code and also questions like "what is a virtual destructor?".
