CareerCup

Here is a question from the "Cracking The Coding Interview" book with a twist.

Implement a method to perform basic string compression using the counts of repeated characters. (p. 73 5th edition)

The twist: the string can also contain digits. Think of encoding and decode protocol. How the compression can be reversed properly?

For example, ab2ccccd -> ab24cd

Given a matrix, find all its combinations by row. For example,

[a, b, c]
[d, e, f]
[x, y, z]

its combinations are adx, ady, adz, bdx, …. cfy, cfz

Rearrange a LinkedList:

Before : a->x->b->y->c->z
After : a->b->c->z->y->x

Find the first N words with the highest frequency in an array of strings. The result needs to be sorted by frequency.

For example:

An array of String:

Inputs:

{"geeks", "for", "geeks", "a", "portal", "to", "learn", "can", "be", "computer", "science", "zoom", "yup", "fire", "in", "be", "data", "geeks"}

and the first 2 words with the highest frequency.

Outputs: {'geek", "be"}

where "geek" has a frequency of 3 and "be" has a frequency of 2.

Given someone's favorite songs (as a map) and a genre category (as a map as well). Find out this person's most favorite genre. For example,

"David": ["song1", "song2", "song3", "song4", "song8"],
"Emma": ["song5", "song6", "song7"]

and

"Rock": ["song1", "song3"],
"Dubstep": ["song7"],
"Techno": ["song2", "song4"],
"Pop": ["song5", "song6"],
"Jazz": ["song8", "song9"]

Output:

"David": "Rock"
"Emma": "Pop"

Given a list of a string which is a list of words separated by a space. Sort the list in the lexicographical order. For example, given the followings:

[act car]
[air dog]
[act zoo]

Result:

[act car]
[act zoo]
[air dog]

A set of points in the 2D plane. Find the first k number of points with the shortest distance to the point (0, 0), where k is a positive integer.

e.g.
Input
{[-16, 5], [-1, 2], [4, 3], [10, -2], [0, 3], [-5, -9]}
k = 3

Output:
{[-1, 2], [0, 3], [4, 3]}
.

A matrix represents a sequence of travel points. One only can travel either left/right or up/down. Some of those points are dead points which one can't travel any further. There is a destination point in the matrix. Find the shortest path from the top left point (1, 1) to the destination.

e.g.
Input
[
[‘O’, ‘O’, ‘O’, ‘O’],
[‘D’, ‘O’, ‘D’, ‘O’],
[‘O’, ‘O’, ‘O’, ‘O’],
[‘X’, ‘D’, ‘D’, ‘O’],
]

Output
Route is (0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (3, 0) The minimum route takes 5 steps.

Given a positive integer array and a positive integer. Find a pair of integers in the array so that the sum of the pair is the largest one among all pairs not larger than the given integer.

e.g.
Input
{90, 85, 75, 60, 120, 150, 125}
d: 250

Output:
{90, 125}

For a given amount of currency, find the minimum set of bills. The currency set is the following: 0.01, 0.05, 0.1, 0.25, 1, 5, 10, 20, 50, and 100. For example, for 21.28, 1 20 bill, and 1 1 bill, and 1 0.25 bill and 3 0.01 bills.

Design a Twitter-like topic system so that the most popular topics can be retrieved from the system. A post can have one or more topics and these topics can be shared by multiple posts. (hint: thinking of scalability)

Given a bar chart which the heights of bars are notated as an array of positive integers. Rectangles can be formed in areas covered by one or more bars. Find the largest rectangle.

Given two sets of intervals such as {[1, 2], [4, 8]} and {[2, 5]}. Find their union {[1, 8]} for the two intervals.

Design a dictionary which words are grouped by the same characters. For example, dog and god are in the same group. And how to make it scalable to handle a huge number of words?

For a given integer array, find a closet pair of elements in the array with a sum of N. For example, {1, 5, 3, 6, 4, 2} and 8, (5, 3) is the pair, but not (6, 2).

Note: the condition is an array of integers, which can be either positive or negative.

Assuming in a Facebook like social network application, find the shortest friend connection path for a given pair of two people.

Note: for scalability of this problem, she has discuss it in her book "Crashing The Coding Interview".

Find the first N prime numbers where N is a positive integer.

Note: This question is to find all first N prime numbers, but not determinate whether N is prime or not.

Given a linked list, swap each pair of nodes to form a new linked list.

Given two people in a social network application, find the close level of connection between them. A friend relationship is an one level connection, a friend's friend is a two level connection and such.

Design a hotel reservation system. To make it simple, we assume that the hotel has only one building and the building has only one floor. Design your objects so that they work better with a non-sql database, say a document-oriented database.

Given a custom table (id, ...), an order table (id, order_date, custom_fk, ...) and an order item table (id, order_fk, price, sale_price...) where price is "not null" and sale_price isn't, write a SQL query statement to find out customers' total purchasing payment in the past six months.

Given a custom table (id, ...), an order table (id, order_date, custom_fk, ...) and an order item table (id, order_fk, ...), write a SQL query statement to find out all customers who haven't placed any order in the past six months.

Given an array containing both positive and negative integers, return an array of alternating positive integers and negative integers such that each set of integers--e.g all the positive integers and all the negative integers are in the same order as in the input array. For example, input {2, 3, -4, -9, -1, -7, 1, -5, -6} and its output shall be {2, -4, 3, -9, 1, -1, -7, -5, -6}. Can you implement it without using any additional space? Also, provide your test cases.

Given an array of integers, find the closest pair with a sum which equals to a given integer. For example, for {1, 7, 5, 3, 9} and 10. The pair is {7, 3}. Also, provide test cases.

Write a function to print out all permutations of a string.

I rephrase the original question as the following: Let say in Facebook, given two person A and B. Write a function to find out whether A is a friend or a friend of a friend of ... of B.

Write a Java function to find unique integers of a given integer array. (Note: I assume the question won't allow using any Java Data Structures for unique elements. And the question might be for an array of characters instead.)

Here is a Java function API: int [] intersection(int [] a, int [] b). Provide your implementation of this Java function. (Note: it is an easy question. They are looking for code quality.)

Given two binary trees. Write a function to determine whether they are similar or not.

Given a string (an array of characters). Find the longest sub-string with less than 3 repeatable characters. Example: for string "abbc", "abb" is the sub-string.

Can you do it with O(n) on the time constrain?

Given a web site log file, find the most visited URL. Also find the top ten most visited URLs.

Find out whether two strings are the same or not without using the equality operator nor the equals method.

Write a function to convert a decimal data to a binary data.

A web site log file contains user sign in information. What data structure you will use to store the user sign in information so that it is easy to find out whether a user signed in in the previous date? (I asked to clarify the user sign in information data format. The answer is a string (?))

Create a doubly-linked list from the most bottom notes (leafs?) in a binary tree by re-using the left and right pointers. (that is the original text with a spelling error)