Programming Interview Questions 9: Convert Array

Given an array:

[a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]

convert it to:

[a_1, b_1, c_1, a_2, b_2, c_2, ..., a_N, b_N, c_N]

in-place using constant extra space.

Continue reading

VN:F [1.9.10_1130]
Rating: 0.0/10 (0 votes cast)

Posted in Programming Interview | 2 Comments

Programming Interview Questions 8: Transform Word

Given a source word, target word and an English dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all intermediate words being valid English words. Return the transformation chain which has the smallest number of intermediate words.

Continue reading

VN:F [1.9.10_1130]
Rating: 10.0/10 (2 votes cast)

Posted in Programming Interview | 3 Comments

Programming Interview Questions 7: Binary Search Tree Check

This is a very common interview question. Given a binary tree, check whether it’s a binary search tree or not. Simple as that..

Continue reading

VN:F [1.9.10_1130]
Rating: 10.0/10 (1 vote cast)

Posted in Programming Interview | 4 Comments

Programming Interview Questions 6: Combine Two Strings

We are given 3 strings: str1, str2, and str3. Str3 is said to be a shuffle of str1 and str2 if it can be formed by interleaving the characters of str1 and str2 in a way that maintains the left to right ordering of the characters from each string. For example, given str1=”abc” and str2=”def”, str3=”dabecf” is a valid shuffle since it preserves the character ordering of the two strings. So, given these 3 strings write a function that detects whether str3 is a valid shuffle of str1 and str2.

Continue reading

VN:F [1.9.10_1130]
Rating: 9.5/10 (2 votes cast)

Posted in Programming Interview | 6 Comments

Programming Interview Questions 5: Linked List Remove Nodes

This is a very fundamental question and it’s tricky to implement without any bugs. Given a linkedlist of integers and an integer value, delete every node of the linkedlist containing that value.

Continue reading

VN:F [1.9.10_1130]
Rating: 8.3/10 (4 votes cast)

Posted in Programming Interview | 4 Comments

Programming Interview Questions 4: Find Missing Element

This question can be solved efficiently with a very clever trick. There is an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array. Here is an example input, the first array is shuffled and the number 5 is removed to construct the second array.

Continue reading

VN:F [1.9.10_1130]
Rating: 10.0/10 (5 votes cast)

Posted in Programming Interview | 6 Comments

Programming Interview Questions 3: Largest Continuous Sum

This is one of the most common interview practice questions. Given an array of integers (positive and negative) find the largest continuous sum.

Continue reading

VN:F [1.9.10_1130]
Rating: 9.0/10 (1 vote cast)

Posted in Programming Interview | 2 Comments

Programming Interview Questions 2: Matrix Region Sum

This is a very elegant question which seems easy at first but requires some hard thinking to solve it efficiently: Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle. Our program will be called multiple times with different rectangular regions from the same matrix.


Continue reading

VN:F [1.9.10_1130]
Rating: 10.0/10 (8 votes cast)

Posted in Programming Interview | Leave a comment

Programming Interview Questions 1: Array Pair Sum

Once again it’s the college recruiting season of the year and tech companies started the interview process for full time and internship positions. I had many interviews last year these days for a summer internship. Eventually I was an intern at Microsoft Bing, and will be joining there full time next summer. I won’t have any interviews this year, but since most of my friends are actively preparing for them nowadays, I thought it would be useful to share some good quality interview questions and provide my solutions. I come across this particular question pretty often recently: Given an integer array, output all pairs that sum up to a specific value k.

Continue reading

VN:F [1.9.10_1130]
Rating: 10.0/10 (3 votes cast)

Posted in Programming Interview | 6 Comments

How to Implement a Search Engine Part 3: Ranking tf-idf

Overview
We have come to the third part of our implementing a search engine project, ranking. The first part was about creating the index, and the second part was querying the index. We basically have a search engine that can answer search queries on a given corpus, but the results are not ranked. Now, we will include ranking to obtain an ordered list of results, which is one of the most challenging and interesting parts. The first ranking scheme we will implement is tf-idf. In the following articles, we’ll analyze Okapi BM25, which is a variant of tf-idf. We will also implement Google’s PageRank. Then we will explore Machine Learning techniques such as Naive Bayes Classifier, Support Vector Machines (SVM), ClusteringDecision Trees and so forth.

Tf-idf is a weighting scheme that assigns each term in a document a weight based on its term frequency (tf) and inverse document frequency (idf).  The terms with higher weight scores are considered to be more important. It’s one of the most popular weighting schemes in Information Retrieval.

Continue reading

VN:F [1.9.10_1130]
Rating: 9.5/10 (4 votes cast)

Posted in Information Retrieval, Search Engines, Web Search | Leave a comment