1.Given a string, write a function that return if it is Palindrome. This wasn't asked directly but from interviewer example i was need to understand that this function must ignore all spaces and special symbols.
2. Given an array, write a function that return true if any 3 elements of this array can sum to 0. My first solution was the simplest and far from best which result in O(n^3). Then interviewer asked me to improve to improve it to O(n^2). This give me a hint that i can use Hash to reduce complexity.

Question

1.Given a string, write a function that return if it is Palindrome. This wasn't asked directly but from interviewer example i was need to understand that this function must ignore all spaces and special symbols.
2. Given an array, write a function that return true if any 3 elements of this array can sum to 0. My first solution was the simplest and far from best which result in O(n^3). Then interviewer asked me to improve to improve it to O(n^2). This give me a hint that i can use Hash to reduce complexity.

Anónimo · Accepted Answer

As I wrote I used HashSet to store all values so I can for every pair of numbers check if there is negative one in HashSet istead of thrid for so overall complexity will be reduced to n+n^2 which is O(n^2)

Boaz · Answer

How do you know you are not using the same number twice?
for example: {2,-1,0}
you will sum 2+(-1)=1 and search in the hash for (-1) which you will find
but you already used it.

Vlad · Answer

Ignore my previous answer, copy and paste issue.

Time complexity is O(n^2)

   private static boolean hasThreeElementsSumUpToZero(int[] a) {
        HashMap cache = new HashMap();
        for (int i : a) {
            if (cache.containsKey(i)) {
                cache.put(i, cache.get(i) + 1);
            } else
                cache.put(i, 1);
        }

        for (int i = 0; i  1)
                        return true;
                } else if (cache.containsKey(target))
                    return true;
            }
        }
        return false;
    }

Anónimo · Answer

Carlos, In your example you are not taking in account the cases where one number can sum to 0 with 2 negative numbers in ur z Hash.

Example: your first number is 5 and you have a -3 and -2 in your hash.

Vlad · Answer

O(n^2)

    private static boolean hasThreeElementsSumUpToZero(int[] a) {
        HashMap cache = new HashMap();
        for (int i : a) {
            if (cache.containsKey(i)) {
                cache.put(i, cache.get(i) + 1);
            } else
                cache.put(i, 1);
        }

        for (int i = 0; i  1)
                        return true;
                } else if (cache.containsKey(target))
                    return true;
            }
        }
        return false;
    }

Vlad · Answer

Damn glass door. It keeps messing up with my post. Lets try again:

consider x = 1 and y = -2, then target (in this case = 1) must appear at least twice in the cache to satisfy the condition (sum of three values).

O(n^2)
                    

private static boolean hasThreeElementsSumUpToZero(int[] a) {
        HashMap cache = new HashMap();
        for (int i : a) {
            if (cache.containsKey(i)) {
                cache.put(i, cache.get(i) + 1);
            } else
                cache.put(i, 1);
        }

        for (int i = 0; i  1)
                        return true;
                } else if (cache.containsKey(target))
                    return true;
            }
        }
        return false;
    }

Vlad · Answer

Stuff you glass door. I give up :(

hehe · Answer

private static boolean hasThreeSum(int[] array) {
		if(array == null || array.length > map = new HashMap();
		for(int i = 0; i  pairs = new ArrayList();
					pairs.add(array[j]);
					pairs.add(array[i]);
					map.put(array[i]+ array[j], pairs);
				}
			}
		}
		return false;
	}

Tasneem · Answer

Using Binary Search 

class Solution {
  public static void main(String[] args) {
    boolean flag = false;
    int a[] = {1,2,3,4,5,-8,-0, 0};
    Arrays.sort(a);
    // a[] = {-1, -1, 0, 1, 2, 3, 4, 5}
    int length = a.length;
    for (int i = 0; i a[mid]) {
        isValuePresent(a, value, mid + 1, r);
      }
    }
    return false;
  }
}

Tasneem · Answer

Continuing ...

  /**
  * Binary search to find the value
  */
  private static boolean isValuePresent(int a[], int value, int l, int r) {
    if (l  a[mid]) {
        isValuePresent(a, value, mid + 1, r);
      }
    }
    return false;
  }
}

Daniel · Answer

I think it's the right approach to use a hash, but it should be a HashMap instead of a HashSet, as Boaz said, we need to keep track of which elements make up the value in the set to avoid counting the same value twice

Anónimo · Answer

Oh didn't think about trying to use the negative of the value of the sum to look in a hash. 
Thanks for clearing it up!

someone · Answer

I don't think you can improve it to n^2.
Just by the fact that calculating all possible combinations of 3 items is n*(n-1)*(n-2)/(3*2).
And unless you can find a way to "skip" some of these combinations you will always have to do o(n^3) at worse

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo