This is the fifth in a
series of answers to
100 Interview Questions for Software Developers.
The list is not intended to be a "one-size-fits-all" list.
Instead, "the key is to ask challenging questions that enable you to distinguish the smart software
developers from the moronic mandrills." Even still, "for most of the questions in this list there are no
right and wrong answers!"
Keeping that in mind, I thought it would be fun for me to provide my off-the-top-of-my-head answers,
as if I had not prepared for the interview at all. Here's that attempt.
Though I hope otherwise, I may fall flat on my face. Be nice, and enjoy (and help out where you can!).
This week's answers are on a topic I've been wanting to explore more in depth here lately: algorithms (though it doesn't go into as much detail). I'll
wait until the end to give reference information because all of this post relies on experience, but there
are two sources where I'd start learning the information for every question. Trying to keep the post
DRY and all.
- How do you find out if a number is a power of 2? And how do you know if it is an odd number?
To find out if a number is a power of two, you can divide by two until the number is 1 or odd. If the number is odd
at any point before you reach one, the number is not a power of two. To find out if a number is odd, I'd normally
take number mod 2 and see if the result is 1 or not (1 would mean the number is odd). If performance
is a concern and the compiler or runtime doesn't optimize for mod 2, you could use a bit mask that
checks if the smallest bit is set or not. If so, the number is odd. If not, the number is even.
Here's an example with the bit mask:
def even? n
n == n & 0b11111111_11111111_11111111_11111110
end
n = 512
while even?(n) && n > 1 do
n = n >> 1
end
puts n==1
Note you'll need a large enough bit mask to cover the size of the number in bits.
- How do you find the middle item in a linked list?
If it's important to be able to find the middle element, I'd keep a pointer to it. If it's implemented using an
array and it's important, we can store the array length and divide by two. If it's implemented using pointers to
elements, we can iterate over the list while counting its length, then iterate from the beginning until we get
halfway there. We could also take the size of the structure in memory and divide by two, going straight to that
element by adding 1/2 the size to the pointer, but that'd be a mighty WTF to most programmers when trying
to understand it.
- How would you change the format of all the phone numbers in 10,000 static html web pages?
Not by hand if I could avoid it. I'd write a regex that matches any of the known formats in the set of pages
and use a language with a function that replaces based on a regular expression find.
- Can you name an example of a recursive solution that you created?
I was creating a pattern enumeration algorithm in an effort to statistically identify potentially important
subsequences in a given genome. The more immediate goal was to identify Rho sites
in a set of bacterial genomes. Since we wanted to identify any potential pattern, the form needed to be general,
so a variable depth was required and we used recursion to achieve this. (This is a job interview, so I tried to
think of the most impressive sounding example from the last year I could think of.)
- Which is faster: finding an item in a hashtable or in a sorted list?
Item retrieval is basically O(1) in a hash table, while O(log n) in a sorted list, so the hash table is faster on
average.
- What is the last thing you learned about algorithms from a book, magazine or web site?
I guess it depends on what you'd consider learning. For instance, I recently looked up
merge sort to use as reference in writing a sorting
algorithm for a custom data structure, but I wouldn't say I "learned" it there. If you take "learning" as
being introduced to, it was in a course at school or via a book.
- How would you write a function to reverse a string? And can you do that without a temporary string?
In most instances I'd be working with a language that already implements a reverse method for strings.
If not working in such a language, and I'm using a temporary string, the problem boils down to iterating backwards
over the given string, and assigning tempstring[realstring_length - i] = realstring[i]. If we restrict
the usage of a temporary string, then we can just use a variable to store the current character for swapping:
for(i=0; i<len; i++) {
lowerchar = realstring[i];
realstring[i] = realstring[len-i-1]; // -1 for 0 based arrays
realstring[len-1] = lowerchar;
}
- What type of language do you prefer for writing complex algorithms?
I prefer very super extremely high level languages (to distinguish from VHLL)
that tend to be dynamic. The reason is that, in using them, I don't have to worry about low level details
that might otherwise get in the way of understanding the algorithm. After that, I'll normally have to implement
the same algorithm in a lower level language and take care of the details I could otherwise ignore, because
normally performance is going to matter when developing that complex algorithm.
- In an array with integers between 1 and 1,000,000 one value is in the array twice. How do you determine which one?
I'd insert each value as a key in a hash and when the key already exists, I know we've hit the duplicate. This
gives us O(n) time complexity, which I'm sure could be proven to be the lower bound.
- Do you know about the Traveling Salesman Problem?
Yes, it's famous. The problem asks us to find the shortest path that visits every node in a graph.
I promised you reading material, so here it is:
- The Art of Computer Programming series by Donald Knuth
- Wikipedia's list of algorithms is another good place to start.
What advice would you give?
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
How do you find the middle item in a linked list?
There is one more solution to this problem. The technique is to use 2 pointers and one increments by one step and the other increments in two steps. the two step counter can reach the end of the list by then the other comes to the middle. of course you should be careful in handling edge cases when the length of the list is odd. This can return the middle element in one iteration instead of two iterations.
Posted by kishore
on Jan 04, 2010 at 11:13 AM UTC - 6 hrs
When you are trying to find out if a number is a power of 2, there is a better solution. Any number which is a power of 2 has only one of its bit set to 1. So you can just count the number of bits set in the number. There is an even simpler solution which can be written in one line. For that solution, please check out <a href='
http://www.mytechinterviews.com/power-of-2'>My Tech Interviews</a>.
Posted by
Aswinkumar Rajendiran
on Jan 05, 2010 at 09:39 PM UTC - 6 hrs
Powers of two have the feature that when you subtract 1, it clears the most significant bit leaving all less significant bits set.
And a thoughtful person may consider that there is no solution to 2^x == 0, so zero is properly not a power of two.
bool IsPowerOfTwo( unsigned int n ) {
return n && (n & n-1) == 0;
}
Posted by chad
on Jan 12, 2010 at 08:38 PM UTC - 6 hrs
For finding the middle of a linked list... how about using two iterators, A and B. Each iteration through the loop increment A once, and B twice. Since B moves through the list twice as fast as A, when B reaches the end, A will be in the middle.
Posted by chad
on Jan 12, 2010 at 08:41 PM UTC - 6 hrs
You may be surprised to find that your string reversing algorithm will actually do nothing at all to your string.
To do what you intended, you should probably stop half-way through the string. Continuing to the end will actually undo all the reversing you had done while processing the first half of the string.
const int n = strlen( s );
for( int i=0; i<n/2; i++ ) {
char t = s[i];
s[i] = s[n-i-1];
s[n-i-1] = t;
}
Posted by chad
on Jan 12, 2010 at 08:49 PM UTC - 6 hrs
For your list of integers between 1 and 1,000,000 your hash table will use a lot of memory. If resources are scarce, you could simply keep a single radix accumulator. You exclusive-or the accumulator with both the index and the value at that index. The implementation below is crafted to account for the zero-based indexing of C/C++.
The fact that x ^ C ^ x == C is useful here, since each number will be xor'd twice, except the one that's in there twice, which will appear 3 times. (x ^ x ^ x == x) And the final index, which will appear once. So if we seed the accumulator with the final index, the accumulator's final value will be the number that is in the list twice.
int val[] = {4,1,3,5,3,2}; // answer will be '3'
int n = sizeof(val)/sizeof(val[0]);
int a = n;
for( int i=0; i<n; i++ ) {
a ^= (i+1);
a ^= val[i];
}
// a==3 now
Posted by chad
on Jan 12, 2010 at 09:05 PM UTC - 6 hrs
@kishore, Aswin, and chad:
Thanks for all the thoughtful comments. In fact, as I wrote this I was determined to think of a way to find the power of two via bit manipulation, but the solution never occurred to me. Since the idea was to do it without prep, I didn't look it up either.
However, I have thought about it since then, mostly with regards to an algorithm I've been playing around with in my head for some bioinformatics work I was doing a while back. Thanks for sharing the solution I was looking for! I may actually go back to thinking about that now that it's on my mind again.
Also, chad, thanks for pointing out about the string. You are totally right - thanks for finding my oversight and correcting it for future visitors!
(update: sorry about mispelling Aswin's name the first time)
Posted by
Sammy Larbi
on Jan 19, 2010 at 08:12 AM UTC - 6 hrs
Hi Chad,
Your algorithm will leave 6^3 in a instead of 3. I thought it was great, otherwise. The repetition means, there will be atleast one number that will not be in the list that the algorithm is including in the XOR sequence.
Posted by navi
on Jul 09, 2010 at 02:52 PM UTC - 6 hrs
Dear.. if we sort array of digits(if they are positive) with counting sort in O(n), then just run a loop like..
for(int i = 0, i<n-1;i++){
if(arr[i]==arr[i+1])
return a[i];
}
it works...
Posted by Adnan
on May 03, 2011 at 02:00 AM UTC - 6 hrs
Adnan,
Wouldn't you just check where arr[i] > 1, since you said it was counting sort (
http://en.wikipedia.org/wiki/Counting_sort )
That would work, and it's basically the same idea as using a hash, but you could potentially be reserving a ton of unused memory (if the ints you are counting are sparse).
Posted by
Sammy Larbi
on Jun 12, 2011 at 12:49 PM UTC - 6 hrs
for hashtable vs sorted list, it depends on the number of elements. for 10 elements the hashtable may be slower due to the hash function overhead
Posted by sopolis
on Jun 26, 2011 at 09:44 AM UTC - 6 hrs
I strongly disagree with your solution an the linked list. The point of a linked list is, that it is not one block of memory as an array (or vector in c++), but that each entry has a pointer to the next and previous entry.
Also I would not loop over the whole list to count, and then go the the middle item, as this takes 1.5*N steps. I would get a pointer to the first and last entry, and then do something like
for (;;){
first++;
if (first==last return) first;
last--;
if (first==last return) first;
}
Posted by Thomas
on Jul 09, 2011 at 07:28 AM UTC - 6 hrs
Thomas,
You are right. I hadn't considered that we may have added elements to the list that could be in any random chunk of memory.
So, that limits our available solutions. If you keep a count of elements in the list, you need to iterate over the items until you meet 1/2 the count.
If you keep a pointer to both the first and last elements, and it is a doubly linked list, you can use your solution.
If there is no extra information outside of the first node, then I guess we still have to iterate over the entire list to get a count, then go 1/2 way again. I was thinking of only a singly linked list when I offered that as a solution.
Another way you could do it with a singly linked list is to remember the node in the middle of the start node and where your current node is at. Something like this:
int counter = 0;
this_node = list.first;
mid_node = list.first;
for(;;){
if (this_node.last?) return mid_node;
counter++;
if (counter % 2 == 0) mid_node = mid_node.next;
this_node = this_node.next;
}
So a strategy like that will go over the list once, but keep a count so that we can only visit the next node 1/2 as many times, and it works on a singly linked list.
What do you think?
Posted by
Sammy Larbi
on Jul 09, 2011 at 12:04 PM UTC - 6 hrs
thnx chad for thoughtful comment .I never thought about it.
reverse of string can be done in o(n/2).
Posted by shailendra saxena
on Mar 21, 2012 at 03:11 PM UTC - 6 hrs
Regarding O(n/2), typically you'll leave off the constant in O notation. In this case, the constant is 1/2. The reason being is that we're focusing on how fast the time (in this case, but you could look at storage, for example) grows as a function of n, and the constant factors don't affect it much. n^2, for example, grows a ton faster than n, whereas 1/2 or 100 n is not much different than just n, for large enough values of n.
Posted by
Sammy Larbi
on Mar 21, 2012 at 04:18 PM UTC - 6 hrs
Regarding TSP: it is more accurate to say "closed" path instead of just path. The problem asks us to find the shortest closed path that visits every node in a graph.
Posted by Y. Lan
on Sep 17, 2012 at 09:21 AM UTC - 6 hrs
Good point -- we need to remember we have to visit the starting node at the end as well, right?
Posted by
Sammy Larbi
on Sep 17, 2012 at 01:51 PM UTC - 6 hrs
-4 down vote favorite
While preparing for Google onsite interviews, I was advised as:
Apart from CLR and Skiena's algorithms book, the following books are focussed on real coding interviews questions which contains great details(real questions with real answers as expected by the google/amazon interviewer):
Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach By Dr Lin Quan
Elements of Programming Interviews: 300 Questions and Solutions By Adnan et al.
Programming Pearls By Dr Bentley
More Programming Pearls By Dr Bentley
These books helped many google/amazon's aspirants greatly in their onsite interviews. Practicing TopCoder questions can be an additional help if it suits individual interest.
Any other resource I should be aware of?
Posted by Doug
on Mar 28, 2013 at 05:55 PM UTC - 6 hrs
Nothing off the top of my head, but I suppose if you go through all of that you ought to have enough of a background that you should feel comfortable in any interview.
Posted by
Sammy Larbi
on Mar 28, 2013 at 07:48 PM UTC - 6 hrs
//to reverse the string
main(){
int i, l;
char str[] = "abcdef";
l = strlen(str);
for( i = 0; i<l/2; i++){
str[i]^=str[l-i-1];
str[l-i-1]^=str[i];
str[i]^=str[l-i-1];
}
printf("%s", str);
}
Posted by sizins
on Jul 12, 2013 at 12:11 PM UTC - 6 hrs
@sizins: That's incredible. I would never have though to try something like that. Where'd you learn / think of it?
Posted by
Sammy Larbi
on Jul 13, 2013 at 05:54 PM UTC - 6 hrs
thanksssssss
Posted by anonymus
on Jan 16, 2014 at 12:23 PM UTC - 6 hrs
This also works, and is a little easier to talk through. Basically, you are storing both numbers (temporarily) in the first as an addition of the two. To get it back, take the difference of the numbers.
for (i = 0; i<l/2; i++)
{
str[i] += str[l-i-1];
str[l-i-1] = str[i] - str[l-i-1];
str[i] -= str[l-i-1];
}
printf("%s\n", str);
Posted by aarons
on Jul 20, 2014 at 06:48 PM UTC - 6 hrs
Leave a comment
