Programming Interview Questions 28: Longest Compound Word

This is my last post of the long programming interview questions series. I’m starting my first full-time job next week at Microsoft Bing Relevance team. Wish me luck..

Given a sorted list of words, find the longest compound word in the list that is constructed by concatenating the words in the list. For example, if the input list is: ['cat', 'cats', 'catsdogcats', 'catxdogcatsrat', 'dog', 'dogcatsdog', 'hippopotamuses', 'rat', 'ratcat', 'ratcatdog', 'ratcatdogcat']. Then the longest compound word is ‘ratcatdogcat’ with 12 letters. Note that the longest individual words are ‘catxdogcatsrat’ and ‘hippopotamuses’ with 14 letters, but they’re not fully constructed by other words. Former one has an extra ‘x’ letter, and latter is an individual word by itself not a compound word.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.0/10 (26 votes cast)

Posted in Programming Interview | 18 Comments

Programming Interview Questions 27: Squareroot of a Number

Find the squareroot of a given number rounded down to the nearest integer, without using the sqrt function. For example, squareroot of a number between [9, 15] should return 3, and [16, 24] should be 4.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.3/10 (34 votes cast)

Posted in Programming Interview | 17 Comments

Programming Interview Questions 26: Trim Binary Search Tree

Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree. So, if we get this tree as input:

and we’re given min value as 5 and max value as 13, then the resulting binary search tree should be:

Continue reading

VN:F [1.9.22_1171]
Rating: 8.5/10 (38 votes cast)

Posted in Programming Interview | 10 Comments

Implementing Search Engines

Welcome to my ‘how to implement a search engine’ series. I describe how to implement an actual search engine with working code in python. Here you can find pointers to original detailed articles. I will continue to share in this area.

Continue reading

VN:F [1.9.22_1171]
Rating: 8.1/10 (11 votes cast)

Posted in Search Engines | 4 Comments

Programming Interview Questions

The complete list of all my programming interview question articles with pointers to original posts. There are 28 questions in total, and since 28 is a perfect number (as Donald Knuth also mentioned) I decided that’s a good place to stop.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.9/10 (61 votes cast)

Posted in Programming Interview | 28 Comments

Programming Interview Questions 25: Remove Duplicate Characters in String

Remove duplicate characters in a given string keeping only the first occurrences. For example, if the input is ‘tree traversal’ the output will be ‘tre avsl’.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.1/10 (14 votes cast)

Posted in Programming Interview | 10 Comments

Programming Interview Questions 24: Find Next Higher Number With Same Digits

Given a number, find the next higher number using only the digits in the given number. For example if the given number is 1234, next higher number with same digits is 1243.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.7/10 (31 votes cast)

Posted in Programming Interview | 24 Comments

Programming Interview Questions 23: Find Word Positions in Text

Given a text file and a word, find the positions that the word occurs in the file. We’ll be asked to find the positions of many words in the same file.

Continue reading

VN:F [1.9.22_1171]
Rating: 9.9/10 (20 votes cast)

Posted in Programming Interview | 3 Comments

Programming Interview Questions 22: Find Odd Occurring Element

Given an integer array, one element occurs odd number of times and all others have even occurrences. Find the element with odd occurrences.

Continue reading

VN:F [1.9.22_1171]
Rating: 8.7/10 (11 votes cast)

Posted in Programming Interview | 7 Comments

Programming Interview Questions 21: Tree Reverse Level Order Print

This is very similar to the previous post level order print. We again print the tree in level order, but now starting from bottom level to the root. Using the same tree as before:

The output should be:
4 5 6
2 3
1
Continue reading

VN:F [1.9.22_1171]
Rating: 9.6/10 (13 votes cast)

Posted in Programming Interview | 11 Comments