## united

BAN USER
Questions (2)

Comments (1)

Reputation 450

- 0of 0 votes

AnswersGiven an arraylist of N integers,

- united in United States

(1) find a non-empty subset whose sum is a multiple of N.

(2) find a non-empty subset whose sum is a multiple of 2N.

Compare the solutions of the two questions.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 4of 4 votes

AnswersGiven the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates.

- united in United States

e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Solution to (1):

- united November 14, 2014Let Fk (1<=k<=N) be the first k elements in the list. Let sk be the sum of elements in Fk.

If there exists k such that sk%N = 0, then return elements in Fk.

Otherwise, every sk%N is between 1 and N-1. So, among s1%N, s2%N, ..., sN%N, there must exist i, j, si%N = sj%N. Return elements in Fj but not in Fi (suppose j > i).

This takes O(N) time. The same solution doesn't apply for question (2). But it seems a BFS approach should still use O(N) time.