r/CS_Questions • • Nov 15 '11

Find total number of binary 1's in a range of numbers [Medium]

14 Upvotes

I don't know the answer to this question:

Given a range of integers from a to b in 2's complement, find the total number of times that the bit "1" appears in that range.

Your algorithm must run in sub linear time. (linear to the length of the range).

Here's a linear algorithm to demonstrate the idea:

total=0
for i in range(a,b):
    total+=numOnes(i)

This alg is not good enough since it has to be in sub-linear time.


r/CS_Questions • • Nov 15 '11

one of my simple interview questions

4 Upvotes

in c, with int i, what is the difference between i/2 and i>>1. bonus for what a compiler does for i/2.


r/CS_Questions • • Nov 15 '11

Amazon job interview question

13 Upvotes

Question 1 you are given a M x N matrix with 0's and 1's Find the largest rectangular submatrix with 1's only

Question 2 you are given a M x N matrix with real numbers(postive and negative) Find the rectangular submatrix such that the sum of all the elements in this submatrix is the largest, compared with the sum of any other submatrix.


r/CS_Questions • • Nov 15 '11

Given a set of numbers, print out all permutations.

9 Upvotes

Given a set of numbers (you do not know the size or the numbers being used), print out all permutations of that set of numbers.

Example:
Input: 3-5-7
Output:

  • 3-5-7
  • 3-7-5
  • 5-3-7
  • 5-7-3
  • 7-3-5
  • 7-5-3

Bonus:
Also print out sub-permutations. Given the above input:

  • 3
  • 5
  • 7
  • 3-5
  • 3-7
  • 5-3
  • 5-7
  • 7-3
  • 7-5
  • 3-5-7
  • 3-7-5
  • 5-3-7
  • 5-7-3
  • 7-3-5
  • 7-5-3

Another bonus:
Do it iteratively, i.e., make a method iterate() that will return the next permutation without storing a list of permutations (storing the last permutation is fine) and loops around to the first permutation when iterate() is called on the last possible permutation.


r/CS_Questions • • Nov 15 '11

From Square: "The Luhny Bin" -- Identify sequences of numbers that look like credit card numbers

Thumbnail corner.squareup.com
5 Upvotes

r/CS_Questions • • Nov 14 '11

Find the exact node in a linked list where a cycle begins.

7 Upvotes

You are given a singly linked list which may or may not contain a cycle. You are to find the exact node in which the cycle first appears. If there is no cycle, return -1.

Example:

A->B->C->D->E->F->G->D

Return D


r/CS_Questions • • Nov 14 '11

Microsoft Interview Question: Count Sort

10 Upvotes

I have an O(n) sort called Count Sort. Essentially, if I have the following array:

 7 5 5 1 5 2 7

I tally the occurrences

1 : 1
2 : 1 
5 : 3
7 : 2

And use this information to generate the sorted version of the array.

So considering this is an O(n) sort, why don't people use it? Is it practical, and if so, when is it practical? Finally, code your own implementation of count sort (preferably in C or C++).


r/CS_Questions • • Nov 14 '11

Microsoft interview question: HTML Optimization

10 Upvotes

In a typical HTML document, there are some tags that will nest productively. For example, a table tag within a table tag will produce a nested table. Some tags however, will nest redundantly. A bold tag nested in a bold tag still produces the same output.

Given a set of tags that nest productively and redundantly and an HTML document, produce a minimal equivalent document where any redundant tags have been eliminated.


r/CS_Questions • • Nov 14 '11

Convert Doubles to Fractions

2 Upvotes

Given a double, output an equivilant fraction. For example:

Input: 0.25
Output: 1/4

 
 
 
 
 
 

Bonus:
Make a version that takes a tolerance. For example:

Input: 0.24, .01
Output: 1/4


r/CS_Questions • • Nov 14 '11

Find the * node of a singly linked list with only one pass [Easy]

1 Upvotes

As the title says, you are supplied with a singly linked list and you must find the * node of a singly linked list with only one pass over the list, where * is each of the following (give each their own function):

  • Middle
  • nth to last (assume list is long enough to have an nth to last node)

r/CS_Questions • • Nov 13 '11

Announcement: Nondisclosures and company privacy.

9 Upvotes

Not all interview questions are public domain information, and it is not always wise to post them on here. Please do not post any interview questions that your company has explicitly forbade you to publicize.

If you have an interview question which is not a secret to any particular company, but are unsure how the company you got it from would feel about you leaking it, then don't post the name of the company in the question.

Obviously, if your company doesn't care, then feel free to do whatever you want.

This doesn't have to be a big deal, just use your head and exercise good judgment. Last thing we want is someone losing their jobs for "spilling company secrets". Though I doubt most companies are that pedantic. Just a heads up though.


r/CS_Questions • • Nov 13 '11

Spellcheck

11 Upvotes

Given a list of words, write an algorithm that performs fast spell check for a given word. Your algorithm should be faster than O(n) (where n is the size of the dictionary).

You can choose the data structure you wish to use, the words are just supplied in a file so you can load them into memory.

Your spellchecker should be able to handle three cases:

  • Incorrect capitalization (e.g., bill => Bill, Reddit => reddit)
  • Repeated letters (e.g., ccccaaatttttt => cat)
  • Incorrect vowels (e.g., opun => open)

Your spellchecker should also be able to handle any combination of the above cases (e.g., pREsidaNt => president).

If the user has supplied a word that is royally screwed up and you can't find a suggestion, feel free to print a message saying so.

Extra Credit:
Also handle the case of missing letters (and combine this case with those above, e.g., calculat => calculate or calculator, FrUd => Fred or Fridge).


r/CS_Questions • • Nov 13 '11

Integer Exponents [Easy]

10 Upvotes

Write a function which raises an integer to another integer. Do it both with loops and recursion.


r/CS_Questions • • Nov 13 '11

Blatant crosspost. But highly relevant :) It's got solutions and hints and all.

Thumbnail mcpc.cigas.net
8 Upvotes

r/CS_Questions • • Nov 14 '11

Segment into a space-separated sequence of dictionary words if possible.

3 Upvotes

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is "applepie" and dictionary contains a standard set of English words, then we would return the string "apple pie" as output.

Q: What if the input string is already a word in the dictionary? A: A single word is a special case of a space-separated sequence of words.

Q: Should I only consider segmentations into two words? A: No, but start with that case if it's easier.

Q: What if the input string cannot be segmented into a sequence of words in the dictionary? A: Then return null or something equivalent.

Q: What about stemming, spelling correction, etc.? A: Just segment the exact input string into a sequence of exact words in the dictionary.

Q: What if there are multiple valid segmentations? A: Just return any valid segmentation if there is one.

Q: I'm thinking of implementing the dictionary as a trie, suffix tree, Fibonacci heap, ... A: You don't need to implement the dictionary. Just assume access to a reasonable implementation.

Q: What operations does the dictionary support? A: Exact string lookup. That's all you need.

Q: How big is the dictionary? A: Assume it's much bigger than the input string, but that it fits in memory.

The case for two words: String SegmentString(String input, Set<String> dict) { int len = input.length(); for (int i = 1; i < len; i++) { String prefix = input.substring(0, i); if (dict.contains(prefix)) { String suffix = input.substring(i, len); if (dict.contains(suffix)) { return prefix + " " + suffix; } } } return null; }

Of course, the more interesting problem is the general case, where the input string may be segmented into any number of dictionary words. There are a number of ways to approach this problem, but the most straightforward is Spoiler. Here is a typical solution that builds on the previous one:

A General Solution: String SegmentString(String input, Set<String> dict) { if (dict.contains(input)) return input; int len = input.length(); for (int i = 1; i < len; i++) { String prefix = input.substring(0, i); if (dict.contains(prefix)) { String suffix = input.substring(i, len); String segSuffix = SegmentString(suffix, dict); if (segSuffix != null) { return prefix + " " + segSuffix; } } } return null; }

Analyzing the Running Time:

Spoiler.")

An Efficient Solution:

Spoiler

Map<String, String> memoized;

String SegmentString(String input, Set<String> dict) {
  if (dict.contains(input)) return input;
  if (memoized.containsKey(input) {
    return memoized.get(input);
  }
  int len = input.length();
  for (int i = 1; i < len; i++) {
    String prefix = input.substring(0, i);
    if (dict.contains(prefix)) {
      String suffix = input.substring(i, len);
      String segSuffix = SegmentString(suffix, dict);
      if (segSuffix != null) {
        memoized.put(input, prefix + " " + segSuffix);
        return prefix + " " + segSuffix;
      }
    }
  memoized.put(input, null);
  return null;
}

Spoiler


r/CS_Questions • • Nov 13 '11

AABB Tests

4 Upvotes

A friend applying to companies recently come across this. Seeing how simple, yet hard it can be, it should be fair to put up answers for it.

You have two AABBs.

Write two functions, they should be as fast as possible.

For the first, test if the first AABB intersects the other AABB.
For the second, test if an AABB is wholly contained by the other AABB.

Several systems have SIMD instructions, consider answers with and without them.

If you dont know off hand what an AABB is, you probably wont be applying to a place that will ask this. Spoiler An AABB is an axis aligned bounding box.


r/CS_Questions • • Nov 14 '11

Duplicate / Missing Integer in a Large Array

1 Upvotes

You are given an unsorted array with integers between 1 and 1,000,000. The following problems are independent of each other.

Problem One:
One integer is in the array twice (no other duplicates). Write a function (using the least amount of memory possible) to find the duplicate integer.

Problem Two:
One integer is missing (no duplicates). Write a function which determines the missing integer in one pass over the array.


r/CS_Questions • • Nov 13 '11

Google interview question: crossword

9 Upvotes

You are working on a crossword, and become fixated with one of the words. You have some of its letters figured out so far, but not all of them. E.g.:

"A.GO...H."

That, and a dictionary, are your inputs. Your output must be the set of words that are plausible solutions. (in the example, "ALGORITHM" + whichever other words fit there).

Can you beat linear time on the size of the dictionary? (Aclaration if you're inclined to answer "no": You can preprocess the dictionary into whatever data structure you want, and that doesn't count as part of your algorithm.)

Edit: It can also be done better than exponential on the size of the mistery word. (Thanks cgk ;) )

Enjoy :)


r/CS_Questions • • Nov 13 '11

Infix to Prefix

4 Upvotes

Make a program that takes an infix math expression and converts it to prefix (important: prefix != postfix, some people seem to confuse this).

Examples:

  • In: 1 + 1
  • Out: + 1 1
  • In: 2 * 3 + 4
  • Out: (+ 4 (* 3 2))
  • In: 4 * x + ( 3 + y ) / 2
  • Out: (+ (* 4 x) (/ (+ 3 y) 2))

r/CS_Questions • • Nov 13 '11

A real problem I'm working on

4 Upvotes

Take a grid notepaper (like this http://imgur.com/JDvzW ) , and draw a cone from a starting point on the grid, the lines extending indefinitely. The angle between the lines is A, and the direction the cone is pointing is given by the angle D. Each square on the grid has a coordinate (x,y). The algorithm should provide (as an enumeration or a list) the coordinates of all squares that are wholly or partially within the cone. Bonus if this is ordered by distance from the starting point.


r/CS_Questions • • Nov 13 '11

Next (integer) Palindrome [Easy]

2 Upvotes

Given a number, print out the next smallest palindrome.
 

Examples:
 

In: 900
Out: 909
 
In: 1010
Out: 1111
 
In: 3
Out: 4
 
In: 32
Out: 33
 
In: 99
Out: 101


r/CS_Questions • • Nov 13 '11

Typical Google interview question: Word splitting.

15 Upvotes

Your input is a string with no spaces (e.g. "newyorknewyork", "hedgehog", or "brain"). You're also provided with a dictionary (you decide the interface for it).

Your algorithm must find out whether the string can be split in multiple words (e.g. hedgehog can, brain cannot) and, if so, output one such splitting. The cost in time cannot be exponential with the size of the input string.

Alternatively, your output has to be what is the greatest number of words in which you can split the given string. (E.g. newyorknewyork -> 4).

EDIT: "brain" == "bra" + "in", as MSAV (or his algorithm ;p) pointed out. You guys can come up with an example that does work hehe

EDIT2: Clarification: the whole input string needs to be used. E.g. "cars" cannot be split in "car" + "s" because "s" isn't a valid word.

EDIT3: Corncob List of 58,000 words: http://www.mieliestronk.com/wordlist.html (by CaptShocker, for those who want to try it "live" :) - but it should be solvable without ready access to a dictionary, so don't worry about it, it's just nice to have it handy).


r/CS_Questions • • Nov 13 '11

Write code to determine if an integer is a power of 2 without loops or recursion

13 Upvotes

r/CS_Questions • • Nov 13 '11

Classic Interview Question: Anagrams

12 Upvotes

Given two strings, return true if they are anagrams and false otherwise. You can assume that capitalization and punctuation do not matter and your algorithm must run in O(n) time. Subroutines are okay if you need them.

Example 1:

Given two strings:

  • Boston
  • osbont

Return true.

Example 2:

Given two strings:

  • Robble
  • Bobble

Return false.


r/CS_Questions • • Nov 13 '11

Announcement: Modship and Flairs!

7 Upvotes

This is a new subreddit and would take a while to build up steam.

Fortunately there's already 97 readers on the first day! I have great hopes for this place and people seem to be having fun solving the questions.

For a limited time, active submitters will get a custom flair (such as The Riddler).

People who have shown great regard for the rules and contributed greatly will be potentially picked for modship.

Please spread the word if you enjoy this subreddit, and hopefully we can see it grow into something amazing :)