Codility Training: Java Solution to TapeEquilibrium


A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
Complexity:
  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
The Solution
The idea is simple: first scan the array to get its sum, then scan again to compute the difference between first part and second part.

We can use add accumulatively to get the sum from a[0] to a[i], to get the difference: diff = Math.abs(2 * prefixSum - sum);

/**
 * O(1) space
 */
public int solution(int[] A) {
  if (A == null)
    throw new IllegalArgumentException("Can't be null");
  if (A.length == 0) {
    return 0;
  }
  if (A.length == 1) {
    return Math.abs(A[0]);
  }

  int sum = 0;
  for (int i = 0; i < A.length; i++) {
    sum += A[i];
  }
  int minRst = Integer.MAX_VALUE;

  // ignore last one, as second array can't be empty
  int prefixSum = 0;
  for (int i = 0; i < A.length - 1; i++) {
    prefixSum += A[i];
    int diff = Math.abs(2 * prefixSum - sum);
    if (diff < minRst) {
      minRst = diff;
    }
  }

  return minRst;
}
This is my first solution, it takes O(n) extra space.
/**
 * O(n) space
 */
public int solution1(int[] A) {
  if (A == null)
    throw new IllegalArgumentException("Can't be null");
  if (A.length == 0) {
    return 0;
  }
  if (A.length == 1) {
    return Math.abs(A[0]);
  }

  int[] prefixSum = new int[A.length];

  prefixSum[0] = A[0];
  for (int i = 1; i < A.length; i++) {
    prefixSum[i] += prefixSum[i - 1] + A[i];
  }
  int sum = prefixSum[A.length - 1];
  int minRst = Integer.MAX_VALUE;

  // ignore last one, as second array can't be empty
  for (int i = 0; i < A.length - 1; i++) {
    int diff = Math.abs(2 * prefixSum[i] - sum);
    if (diff < minRst) {
      minRst = diff;
    }
  }

  return minRst;
}

Test Code
To take a real interview test in codility, it's important to add more test cases and run them in our own IDE before submit the solution.

public static void main(String[] args) {
  TapeEquilibrium instance = new TapeEquilibrium();

  Map<int[], Integer> inAns = new HashMap<int[], Integer>();
  // the input and answer from the origin question
  inAns.put(new int[] { 3, 1, 2, 4, 3 }, 1);

  inAns.put(new int[] { 1 }, 1);
  inAns.put(new int[] { 1, 3 }, 2);
  inAns.put(new int[] { 3, 1 }, 2);
  inAns.put(new int[] { -1 }, 1);
  inAns.put(new int[] { 1, -1 }, -1);

  for (Entry<int[], Integer> entry : inAns.entrySet()) {
    assertEquals(instance.solution(entry.getKey()), entry.getValue()
        .intValue());
  }
 }

Lesson Learned
Notice common bug pattern: < or <=, init value is 0 or 1, A.length - 1 or A.length etc.
Handle and test edge cases.
Analyze time and space complexity, and whether we can improve it.
Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts