Google Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
5
of 5 vote

// There are only two patterns when cross can happen, 
        // one involves four moves another involves six moves. 
        // Checking for this patterns is sufficient.  
        // C#
        static void Main(string[] args)
        {
            //double[] n = new double[] { 2, 2, 2, 1 }; // No cross
            //double[] n = new double[] { 2, 2, 2, 2 }; // Cross
            //double[] n = new double[] { 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 3, 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 2, 2, 4, 5, 1, 4 }; // No Cross
            //double[] n = new double[] { 2, 2, 4, 5, 3, 4 }; // Cross
            //double[] n = new double[] { 1, 2, 4, 5, 1, 4 }; // No Cross
            double[] n = new double[] { 0.5, 2, 2, 4, 5, 3, 4, 0.5 }; // Cross

            for (int i = 0; i < n.Length; i++)
            {
                if (i >= 3 && 
                    n[i] >= n[i - 2] &&
                    n[i - 1] <= n[i - 3])
                {
                    Console.WriteLine("Cross Detected, pattern #1");
                    return;
                }
                if (i >= 5 &&
                    n[i] >= n[i - 2] - n[i - 4] &&
                    n[i - 2] >= n[i - 4] &&
                    n[i - 1] >= n[i - 3] - n[i - 5] &&
                    n[i - 3] >= n[i - 5])
                {
                    Console.WriteLine("Cross Detected, pattern #2");
                    return;
                }
            }
            Console.WriteLine("No Cross");
        }

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I came up with the same solution. It took me around 3 hours, no idea how someone can come up with working solution (not just idea) in 45 minutes.
You can start the loop from 3, because cross can happen only starting from 4th move.

- damluar October 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Consider 2,2,3,2,2

- Tewelde November 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 8 vote

there are only 2 possible intersections for an edge e.
1. (e-3)rd edge
2. (e-5)th edge.
if we can test the intersection of edge e with these 2 (boundary cases must be handled where we dont have 3 or 5 edges), we will get the result. Since we have the starting point we only need to maintiain points of last 5 edges to check intersection

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes the intuition behind it is that to avoid crossings, the "spiral" must unfold: the traveller's path is a spiral.

That's why as justaguy wrote below, crossing happens when:
distance of south <= distance of north &&
distance of east >= distance of west

- anonus October 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

wrong solution..I wonder how wrong solutions are getting promoted to top!

- zahidbuet106 October 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

// There are only two patterns when cross can happen, 
        // one involves four moves another involves six moves. 
        // Checking for this patterns is sufficient.  
        // C#
        static void Main(string[] args)
        {
            //double[] n = new double[] { 2, 2, 2, 1 }; // No cross
            //double[] n = new double[] { 2, 2, 2, 2 }; // Cross
            //double[] n = new double[] { 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 3, 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 2, 2, 4, 5, 1, 4 }; // No Cross
            //double[] n = new double[] { 2, 2, 4, 5, 3, 4 }; // Cross
            //double[] n = new double[] { 1, 2, 4, 5, 1, 4 }; // No Cross
            double[] n = new double[] { 0.5, 2, 2, 4, 5, 3, 4, 0.5 }; // Cross

            for (int i = 0; i < n.Length; i++)
            {
                if (i >= 3 && 
                    n[i] >= n[i - 2] &&
                    n[i - 1] <= n[i - 3])
                {
                    Console.WriteLine("Cross Detected, pattern #1");
                    return;
                }
                if (i >= 5 &&
                    n[i] >= n[i - 2] - n[i - 4] &&
                    n[i - 2] >= n[i - 4] &&
                    n[i - 1] >= n[i - 3] - n[i - 5] &&
                    n[i - 3] >= n[i - 5])
                {
                    Console.WriteLine("Cross Detected, pattern #2");
                    return;
                }
            }
            Console.WriteLine("No Cross");
        }

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the x_1 >= x_2 && x_4 >= x_3, then crosses

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let the length of the ith segment be denoted by len(i).
In order for segment i to intersect the path p composed of segments {1, 2, ... i-1} three conditions must be met:
- i >= 4
- len(i-1) <= len(i-3)
- len(i-2) <= (len(i) + len(i-4))
For each segment i, the value len(i) is simply x_i.
We only need to track the last 4 segment lengths and compare them as per the 3 conditions above:

# -*- coding: utf-8 -*-
import unittest


def collision(lst):
    for i in range(3, len(lst)):
        len_4 = lst[i - 4] if i > 3 else 0
        if lst[i - 1] <= lst[i - 3] and lst[i - 2] <= (lst[i] + len_4):
            return True
    return False


class CollisionTest(unittest.TestCase):

    def test_collision(self):
        self.assertTrue(collision([2, 1, 1, 2]))
        self.assertFalse(collision([1, 2, 3, 4]))
        self.assertTrue(collision([1, 1, 2, 2, 1.5, 1.5]))


if __name__ == "__main__":
    unittest.main()

- Dave September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dave, can you consider this sequence please [1, 1, 2, 4, 3, 2, 2, 1, 1, 0.5f, 0.5f]. It should be false. There is a scenario where two spirals can exist without intersecting. The first getting larger and then the second getting smaller.

- AMP September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Dave, I'd say considering only last 5 is not enough.
Consider [1, 1, 2, 5, 3, 3, 2] - this one should pass
while [ 1, 2, 2, 5, 3, 3, 2] should fail.
Both have same last 5 numbers.

I'd adjust the rules as following:
1) i >= 4
// test lengths from now on, "len" omitted for brevity
2) (i-1) <= (i-3) /* collision possible, we are spiraling inside */
3) if ( (i)+(i-4) >= (i-2) ) /* collision with i-3 */
else /* we can still collide with i-5 as it could be between us and i-3 */
if ((i-2) >= (i-4) /* i-5 lies in front of us */
&& (i-1) + (i-5) >= (i-3) /* part of i-5 is in the way */
&& (i) + (i-4) >= (i-2)) /* we go far enough to collide with i-5 */

Let me know what you think.

- deirh.mana September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:
3) if ( (i) >= (i-2) ) /* simple collision with i-3 */

- deirh.mana September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't see any valid solution, check that array [1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1], path is not crossing, we have two spiral

- Kris September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't see any valid solution, check that array [1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1], path is not crossing, we have two spiral

- Kris September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since two spirals can coexist peacefully (unless we are given infinite number of following steps) we need to compare the last length at least against 5 previous lengths.
So our window size should be 6. My take on this:
Let i be the value of last step. A positive collision should then satisfy all of the following:
1) i >= 4 /* can't collide with previous two */
// test lengths from now on, "len" omitted for brevity
2) (i-1) <= (i-3) /* collision possible, we are spiraling inside */
3) if ( (i)+(i-4) >= (i-2) ) /* simple collision with i-3 */
else /* we can still collide with i-5 as it could be between us and i-3 */
if ((i-2) >= (i-4) /* i-5 lies in front of us */
&& (i-1) + (i-5) >= (i-3) /* part of i-5 is in the way */
&& (i) + (i-4) >= (i-2)) /* we go far enough to collide with i-5 */

Note: If we have less than 6 nodes, assume value of the nonexistent ones to be 0.
Let me know what you think.

- deirh.mana September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:
3) if ( (i) >= (i-2) ) /* simple collision with i-3 */

- deirh.mana September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Loop through checking the following condition:

boolean isIntersecting(float[] arr, int n) {
	
	if ((arr[n-1] < arr[n - 3]) && (arr[n] > arr[n-2])) {
		return true;
	}

	if (n < 5) {

		return false;
	}

	if ((arr[n-1] < arr[n - 3]) && (arr[n - 5] > arr[n - 1]) && (arr[n] > (arr[n-2] - arr[n-4])) {
		return true;
	}

	return false;
}

- SK September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List all possible crossing situations and solve.

-*- coding: utf-8 -*-
__author__ = 'YUAN'

def solution(lst):
    if len(lst) < 4: return 'not crossed'
    for i in xrange(3, len(lst)):
        if i == 3:
            if lst[2] <= lst[0] and lst[3] >= lst[1]:
                return 'corssed'
        elif i == 4:
            if (lst[3] == lst[1] and lst[4] + lst[0] >= lst[2]) or (lst[3] < lst[1] and lst[4] >= lst[2]):
                return 'corssed'
        elif i > 4:
            # outer spiral
            if lst[i-2]>=lst[i-3]>=lst[i-4] and lst[i-1]<=lst[i-3] and lst[i]+lst[i-4]>=lst[i-2]:
                return 'crossed'
            elif lst[i-3]>=lst[i-4]>=lst[i-5] and lst[i-1]+lst[i-5]<lst[i-3] and lst[i]>=lst[i-2]:
                return 'crossed'
            elif lst[i-3]>=lst[i-4]>=lst[i-5] and lst[i-2]>lst[i-4] and lst[i-3]-lst[i-5]<=lst[i-1]<=lst[i-3] and lst[i]+lst[i-4]>=lst[i-2]:
                return 'crossed'
            elif i>=6 and lst[i-4]>=lst[i-5]>=lst[i-6] and lst[i-3]>lst[i-5] and lst[i-1]+lst[i-5]<lst[i-3] and lst[i]>=lst[i-2]:
                return 'corssed'
            # inner spiral
            elif lst[i-1]<=lst[i-2]<=lst[i-3] and lst[i]>=lst[i-2]:
                return 'corssed'

    return 'not corssed'

if __name__ == "__main__":
    print solution([ 1, 2, 2, 5, 3, 3, 2])   # crossed
    print solution([1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1])   # not crossed
    print solution([1, 1, 2, 5, 3, 3, 2])   # not crossed

- Yuan September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# -*- coding: utf-8 -*-
__author__ = 'YUAN'

def solution(lst):
    if len(lst) < 4: return 'not crossed'
    for i in xrange(3, len(lst)):
        if i == 3:
            if lst[2] <= lst[0] and lst[3] >= lst[1]:
                return 'corssed'
        elif i == 4:
            if (lst[3] == lst[1] and lst[4] + lst[0] >= lst[2]) or (lst[3] < lst[1] and lst[4] >= lst[2]):
                return 'corssed'
        elif i > 4:
            # outer spiral
            if lst[i-2]>=lst[i-4] and lst[i-3]>=lst[i-5]:
                if lst[i-3] - lst[i-5] <= lst[i-1] <= lst[i-3] and lst[i]>=lst[i-2]-lst[i-4]:
                    return 'crossed'
                elif lst[i-1]<lst[i-3]-lst[i-5] and lst[i]>=lst[i-2]:
                    return 'crossed'
            # inner spiral
            elif lst[i-1]<=lst[i-3] and lst[i-2]<=lst[i-4] and lst[i]>=lst[i-2]:
                return 'corssed'

    return 'not corssed'

if __name__ == "__main__":
    print solution([ 1, 2, 2, 5, 3, 3, 2])   # crossed
    print solution([1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1])   # not crossed
    print solution([1, 1, 2, 5, 3, 3, 2])   # not crossed

- akak18183 September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static boolean isCrossed(double[]  s){
		//base case 
		if(s.length < 4){
			return false;
		}
		if(s[0] >= s[2] && s[3] >= s[1]){
			return true;
		}
		
		//test if the moves are on outward increasing spiral
		int i = 3;
		while(i < s.length){
			if(s[i] > s[i-2] && s[i-1] > s[i-3])
				i++;
			else break;
		}
		
		//if we visited all the moves then there is no intersection
		if(i == s.length){
			return false;
		}
		
		//otherwise moves are on a decreasing inward spiral starting from i
		//we first need check if the two spirals are crossing each other which can only possible
		//when edge i+1 crosses edge (i-4) if its there
		
		if(i < s.length && i > 3 && s[i+1] >= (s[i-1]-s[i-3])){
                        if (s[i] >= (s[i - 2] - s[i - 4]) || s[i + 1] >= s[i - 1])
			         return true;
		}
		
		//if two spiral didn't intersect then check for decreasing s
		while(i+3 < s.length){
			if(s[i] > s[i+2] && s[i+1] > s[i+3]){
				i++;
			}
			else break;
		}
		
		//if we visited all the moves then there is no intersection
		if(i+3 == s.length){
			return false;
		}
		
		return false;
	}

- zahidbuet106 September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is perfect solution

- dhs.du.08 September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just a small correction: it should be s.length-1

//if we visited all the moves then there is no intersection
if(i == s.length-1){
return false;
}

- justaguy September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works most of the time. Definitely a good solution, but it does not work for following:
{1.0,2.0,2.0,4.0,3.0,3.0,0.5}

- justaguy September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Almost correct, doesn't seem to handle the case [1, 1, 2, 3, 4, 1, 3.5f].

I have updated my previous solution...

public static boolean doesSpiralIntersect(float[] s) {

        // need 4 or more to intersect
        if (s == null || s.length < 4) {
            return false;
        }

        // does it intersect straight away?
        if (s[0] >= s[2] && s[3] >= s[1]) {
            return true;
        }

        int index = 3;
        // is the spiral increasing?, options are to change to decreasing or exhaust the list
        while (index < s.length && s[index] > s[index - 2] && s[index - 1] > s[index - 3]) {
            index++;
        }

        // handle the change over from increasing to decreasing. Need to check 4
        // back in order to see if the right boundary of the increasing is going
        // to intersect with this line against the line 1 forward
        if (index < s.length && index > 3) {
            if (s[index] >= s[index - 2] - s[index - 4]) {
                // handle case where i+1 may hit i-4
                if (s[index + 1] + s[index - 3] >= s[index - 1]) {
                    return true;
                }
            } else {
                // handle the case where i + 1 may hit i - 2
                if (s[index + 1] >= s[index - 1]) {
                    return true;
                }
            }
            // change over is ok, inc index
            index++;
        }

        // otherwise, decreasing if we made it here
        while (index < s.length) {
            if (s[index] >= s[index - 2]) {
                return true;
            }
            index++;
        }

        return false;
    }

- AMP September 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Good solution. You are missing this case though, s = [1,2,4,4,2,3] this spiral is not intersected and your code will return that is a crossed path because of this check

if(i < s.length && i > 3 && s[i+1] >= (s[i-1]-s[i-3])){
			return true;
		}

I added one more check inside, so the entire check goes like this:

if (i < s.Length && i > 3 && s[i + 1] >= (s[i - 1] - s[i - 3])
	{
        	if (s[i] >= (s[i - 2] - s[i - 4]) || s[i + 1] >= s[i - 1])
            		return True
	}

- rchg1988 September 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

there was a typo bug in the my final return. It should return false instead of true. Also, appreciate @rchg1988 for the fixing of missing case. Including these 2 fix the solution works for all cases now

public static boolean isCrossed(double[]  s){
	//base case 
	if(s.length < 4){
		return false;
	}
	if(s[0] >= s[2] && s[3] >= s[1]){
		return true;
	}
	
	//test if the moves are on outward increasing spiral
	int i = 3;
	while(i < s.length){
		if(s[i] > s[i-2] && s[i-1] > s[i-3])
			i++;
		else break;
	}
	
	//if we visited all the moves then there is no intersection
	if(i == s.length){
		return false;
	}
	
	//otherwise moves are on a decreasing inward spiral starting from i
	//we first need check if the two spirals are crossing each other which can only possible
	//when edge i+1 crosses edge (i-4)  or edge i+1 crosses edge i-2 (if exists)
	
	if(i < s.length && i > 3 && s[i + 1] >= (s[i - 1] - s[i - 3])){
		if (s[i] >= (s[i - 2] - s[i - 4]) || s[i + 1] >= s[i - 1])
    		return true;
	}
	
	//if two spiral didn't intersect then check for decreasing s
	while(i+3 < s.length){
		if(s[i] > s[i+2] && s[i+1] > s[i+3]){
			i++;
		}
		else break;
	}
	
	//if we visited all the moves then there is no intersection
	if(i+3 == s.length){
		return false;
	}
	
	return false;
}

- zahidbuet106 September 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this will work too:

bool isCross(const vector<float> &nums) {
  float bound[2]{0}; // used in inner spiral, only need two bounds
  float pre[4]{0};
  bool isbound = false; // if isbound, then enter inner spiral
  int j, n = nums.size();
  for (int i = 0; i < n; ++i) {
    j = i % 4;
    if (isbound) {
      if (nums[i] >= bound[j % 2]) return true;
      bound[j % 2] = nums[i];
    } else if (nums[i] > pre[(j + 2) % 4]) {
      pre[j] = nums[i];
    } else {
      isbound = true;
      bound[j % 2] = nums[i];
      bound[(j + 1) % 2] = nums[i] + pre[j] < pre[(j + 2) % 4] ? nums[i - 1] : nums[i - 3];
    }
  }
  return false;
}

- Eidolon.C September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this. Intersection has to happen within the previous 6 steps:

public static boolean isSelfIntersecting(double[] steps) {
        double[] bufx = new double[7];
        double[] bufy = new double[7];
        int bi = 0;

        for(int i = 0; i < steps.length; i++) {

            int newBi = (bi + 1) % 7;
            int d = i % 4;
            if(d == 0 || d == 2) {
                bufx[newBi] = bufx[bi];
                bufy[newBi] = bufy[bi] + (d == 0 ? steps[i] : -steps[i]);

            } else {
                bufy[newBi] = bufy[bi];
                bufx[newBi] = bufx[bi] + (d == 3 ? steps[i] : -steps[i]);
            }



            // check intersection
            if(i >= 3) {
                int a = (bi + 4) % 7;
                int b = (newBi + 4) % 7;

                if(intersects(bufx, bufy, bi, newBi, d, a, b)) {
                    return true;
                }
            }

            if(i >= 5) {

                int a = (bi + 1) % 7;
                int b = (newBi + 1) % 7;

                if(intersects(bufx, bufy, bi, newBi, d, a, b)) {
                    return true;
                }
            }

            bi = newBi;
        }

        return false;
    }

    private static boolean intersects(double[] bufx, double[] bufy, int bi, int newBi, int d, int a, int b) {
        int s1, s2, t1, t2;

        if(d == 0) {
            s1 = b;s2 = a;
            t1 = bi;t2 = newBi;
        } else if(d == 3) {
            s1 = bi;s2 = newBi;
            t1 = a; t2 = b;
        } else if(d == 1) {
            s1 = newBi; s2 = bi;
            t1 = b; t2 = a;
        } else {
            s1 = a; s2 = b;
            t1 = newBi; t2 = bi;
        }

        return bufy[s1] >= bufy[t1] && bufy[s1] <= bufy[t2] &&
                bufx[t1] <= bufx[s2] && bufx[t1] >= bufx[s1];
    }

- learner21 September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isSelfIntersecting(double[] steps) {
        double[] bufx = new double[7];
        double[] bufy = new double[7];
        int bi = 0;

        for(int i = 0; i < steps.length; i++) {

            int newBi = (bi + 1) % 7;
            int d = i % 4;
            if(d == 0 || d == 2) {
                bufx[newBi] = bufx[bi];
                bufy[newBi] = bufy[bi] + (d == 0 ? steps[i] : -steps[i]);

            } else {
                bufy[newBi] = bufy[bi];
                bufx[newBi] = bufx[bi] + (d == 3 ? steps[i] : -steps[i]);
            }



            // check intersection
            if(i >= 3) {
                int a = (bi + 4) % 7;
                int b = (newBi + 4) % 7;

                if(intersects(bufx, bufy, bi, newBi, d, a, b)) {
                    return true;
                }
            }

            if(i >= 5) {

                int a = (bi + 1) % 7;
                int b = (newBi + 1) % 7;

                if(intersects(bufx, bufy, bi, newBi, d, a, b)) {
                    return true;
                }
            }

            bi = newBi;
        }

        return false;
    }

    private static boolean intersects(double[] bufx, double[] bufy, int bi, int newBi, int d, int a, int b) {
        int s1, s2, t1, t2;

        if(d == 0) {
            s1 = b;s2 = a;
            t1 = bi;t2 = newBi;
        } else if(d == 3) {
            s1 = bi;s2 = newBi;
            t1 = a; t2 = b;
        } else if(d == 1) {
            s1 = newBi; s2 = bi;
            t1 = b; t2 = a;
        } else {
            s1 = a; s2 = b;
            t1 = newBi; t2 = bi;
        }

        return bufy[s1] >= bufy[t1] && bufy[s1] <= bufy[t2] &&
                bufx[t1] <= bufx[s2] && bufx[t1] >= bufx[s1];
    }

- learner21 September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

#include <stdlib.h>
#include <stdio.h>

bool isCrossing(int* a, int size) {
if(size < 4)
return false;

int i = 3;
while(i < size) {
if(a[i] > a[i-2] || a[i-1] > a[i-3])
break;
i++;
}

while(i < size) {
if(a[i] < a[i-2] || a[i-1] < a[i-3])
break;
i++;
}

while(i < size) {
if(a[i] > a[i-2] || a[i-1] > a[i-3])
break;
i++;
}

if(i < size)
return true;
return false;
}

int main(int argc, char** argv) {
int size = argc -1;
int *input = new int[size];

for(int i = 0; i < size; i++)
input[i] = atoi(argv[i+1]);

if(isCrossing(input, size))
cout << "Intersects" << endl;
else
cout << "Non Intersecting" << endl;


return 1;
}

- looper September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

#include <stdlib.h>
#include <stdio.h>

bool isCrossing(int* a, int size) {
        if(size < 4)
                return false;

        int i = 3;
        while(i < size) {
                if(a[i] > a[i-2] || a[i-1] > a[i-3])
                        break;
                i++;
        }

        while(i < size) {
                if(a[i] < a[i-2] || a[i-1] < a[i-3])
                        break;
                i++;
        }

        while(i < size) {
                if(a[i] > a[i-2] || a[i-1] > a[i-3])
                        break;
                i++;
        }

        if(i < size)
                return true;
        return false;
}

int main(int argc, char** argv) {
        int size = argc -1;
        int *input = new int[size];

        for(int i = 0; i < size; i++)
                input[i] = atoi(argv[i+1]);

        if(isCrossing(input, size))
                cout << "Intersects" << endl;
        else
                cout << "Non Intersecting" << endl;


        return 1;
}

- looper September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
	Takes array of numbers
	returns if there is a path intersection
*/

function intersectPath(A) {
	
	if (A.length < 4) {	
		// path cannot intersect with only 3 moves
		return false		
	}

	else if (A[2] <= A[0]) {
		// we must have an inward spiral, or a collision
		var testCondition = function(x) { return A[x] >= A[x-2] }
	}

	else {
		// we must have an outward spiral, or a collision
		var testCondition = function(x) { return A[x] <= A[x-2] }
	}

	for (var i = 2; i < A.length; i++) {
		// test all Numbers for collision in O(n)
		if ( testCondition(i) ) {
			return true
		}
	}

	return false
}

- shahar.zimmerman.usa September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Passes all of the cases from the comments tested against.

int prev(int curr) {
  return (curr + 3) % 4;
}

int opp(int curr) {
  return (curr + 2) % 4;
}

bool crossesPath(const vector<double>& steps) {
  
  if (steps.size() < 4) {
    return false;
  }
  
  vector<double> bounds = {steps[0], steps[1], 0, 0};
  bool decreased = false;
  
  for (int i = 2, j = 2; i < steps.size(); ++i, j = i % 4) {
    
    if (steps[i] < bounds[opp(j)] || (steps[i] == bounds[opp(j)] && !decreased)) {
      
      if (!decreased && steps[i] >= bounds[opp(j)] - bounds[j]) {
        bounds[prev(j)] -= bounds[opp(prev(j))];
      }
      if (!decreased) {
        decreased = true;
      }
    }
    else if (decreased) {
      return true;
    }
    
    bounds[j] = steps[i];
  }
  
  return false;
}

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static final int SMALLER = 0x10;
public static final int BIGGER = 0x20;
public static boolean crossesItself(List<Double> distances){
	if(distances.size() < 4){
		return false;
	}		
	Double prevY = distances.get(0);
	Double prevX = distances.get(1);
	//need these two so that we know when we have both set
	int xOrientation = 0;
	int yOrientation = 0;		
	for(int i = 2; i < distances.size(); i++){
		int direction = i % 2;			
		if(direction == 0){				
			Double y = distances.get(i);
			int newYOrientation = y.compareTo(prevY) > 0 ? BIGGER : SMALLER;
			if(yOrientation == 0){
				yOrientation = newYOrientation;
				xOrientation = newYOrientation;
			} else if(yOrientation == BIGGER && newYOrientation == SMALLER){
				yOrientation = newYOrientation;
				xOrientation = newYOrientation;
				System.out.println("Y coordinate changed from BIGGER -> SMALLER");
			} else if(newYOrientation != yOrientation){
				return true;
			}
			prevY = y;
		} else {				
			Double x = distances.get(i);
			int newXOrientation = x.compareTo(prevX) > 0 ? BIGGER: SMALLER;
			if(xOrientation == 0){
				xOrientation = newXOrientation;
				yOrientation = newXOrientation;
			} else if(xOrientation == BIGGER && newXOrientation == SMALLER){
				xOrientation = newXOrientation;
				yOrientation = newXOrientation;
				System.out.println("X coordinate changed from BIGGER -> SMALLER");
			} else if(newXOrientation != xOrientation){
				return true;
			}
			prevX = x;
		}			
	}
	return false;
}

- ABCD September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below might work, even though a little bit long. Anyone checks?

public static boolean self(float[] nums){
float[] r = {0,0};
Edge north = new Edge(0, r);
Edge west = new Edge(0, r);
Edge south = new Edge(0, r);
Edge east = new Edge(0, r);
float[] original = {0,0};
for(int i=0;i<nums.length;i++){
if(i%4==0){
if(i!=0){
float[] top = north.range;
float p = north.index;
if(original[0]>=top[0]&&original[0]<=top[1]&&original[1]<=p&&original[1]+nums[i]>=p){
return true;
}
}
east.index = original[0];
east.range[0] = original[1];
east.range[1] = original[1]+nums[i];
original[1] = original[1] + nums[i];
}else if(i%4==1){
if(i!=1){
float[] left = west.range;
float p = west.index;
if(original[1]>=left[0]&&original[1]<=left[1]&&original[0]>=p&&original[0]-nums[i]<=p){
return true;
}
}
north.index = original[1];
north.range[0] = original[0]-nums[i];
north.range[1] = original[0];
original[0] = original[0]-nums[i];
}else if(i%4==2){
if(i!=2){
float[] bottom = south.range;
float p = south.index;
if(original[0]>=bottom[0]&&original[0]<=bottom[1]&&original[1]>=p&&original[1]-nums[i]<=p){
return true;
}
}
west.index = original[0];
west.range[0] = original[1]-nums[i];
west.range[1] = original[1];
original[1] = original[1]-nums[i];
}else{
float[] right = east.range;
float p = east.index;
if(original[1]>=right[0]&&original[1]<=right[1]&&original[0]<=p&&original[0]+nums[i]>=p){
return true;
}
south.index = original[1];
south.range[0] = original[0];
south.range[1] = original[0]+nums[i];
original[0] = original[0]+nums[i];
}
}
return false;
}

public static class Edge{
float index;
float[] range = new float[2];
public Edge(float index, float[] range){
this.index = index;
this.range[0] = range[0];
this.range[1] = range[1];
}
}

- ddll October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <vector>
using namespace std;

struct walk {
    double x;
    double y;
    walk(double x, double y): x(x), y(y) {}
    walk() {}
   
};


walk operator+(walk w1, walk w2) {
    walk result;
    result.x = w1.x + w2.x;
    result.y = w1.y + w2.y;
    return result;
}

walk operator*(double d, walk w1) {
    walk result;
    result.x = d * w1.x ;
    result.y = d * w1.y;
    return result;
}


bool crossPaths(vector<double> & path) {
    walk arr[] = {walk(0,1), walk(-1,0), walk(0,-1), walk(1,0)};
    
    walk position = walk(0,0);
    
    for(int i=0; i<path.size(); ++i) {
        int iMod = i%4;
        position = position + path[i]* arr[iMod];
    }
    
    if(position.x ==0 && position.y==0) {
        return true;
    }
    return false;
}

- Lilian September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are only considering ingoing spiral or outgoing spiral. Won't work for move containing both. For example, 2, 1, 4, 4, 3, 3, 2, 1, 1.

- zahidbuet106 September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <vector>
using namespace std;

struct walk {
    double x;
    double y;
    walk(double x, double y): x(x), y(y) {}
    walk() {}
   
};


walk operator+(walk w1, walk w2) {
    walk result;
    result.x = w1.x + w2.x;
    result.y = w1.y + w2.y;
    return result;
}

walk operator*(double d, walk w1) {
    walk result;
    result.x = d * w1.x ;
    result.y = d * w1.y;
    return result;
}


bool crossPaths(vector<double> & path) {
    walk arr[] = {walk(0,1), walk(-1,0), walk(0,-1), walk(1,0)};
    
    walk position = walk(0,0);
    
    for(int i=0; i<path.size(); ++i) {
        int iMod = i%4;
        position = position + path[i]* arr[iMod];
    }
    
    if(position.x ==0 && position.y==0) {
        return true;
    }
    return false;
}

- Lilian September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <vector>
using namespace std;

struct walk {
double x;
double y;
walk(double x, double y): x(x), y(y) {}
walk() {}

};


walk operator+(walk w1, walk w2) {
walk result;
result.x = w1.x + w2.x;
result.y = w1.y + w2.y;
return result;
}

walk operator*(double d, walk w1) {
walk result;
result.x = d * w1.x ;
result.y = d * w1.y;
return result;
}


bool crossPaths(vector<double> & path) {
walk arr[] = {walk(0,1), walk(-1,0), walk(0,-1), walk(1,0)};

walk position = walk(0,0);

for(int i=0; i<path.size(); ++i) {
int iMod = i%4;
position = position + path[i]* arr[iMod];
}

if(position.x ==0 && position.y==0) {
return true;
}
return false;
}

- Anonymous September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are only considering ingoing spiral or outgoing spiral. Won't work for move containing both. For example, 2, 1, 4, 4, 3, 3, 2, 1, 1.

- zahidbuet106 September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <vector>
using namespace std;

struct walk {
    double x;
    double y;
    walk(double x, double y): x(x), y(y) {}
    walk() {}
   
};


walk operator+(walk w1, walk w2) {
    walk result;
    result.x = w1.x + w2.x;
    result.y = w1.y + w2.y;
    return result;
}

walk operator*(double d, walk w1) {
    walk result;
    result.x = d * w1.x ;
    result.y = d * w1.y;
    return result;
}


bool crossPaths(vector<double> & path) {
    walk arr[] = {walk(0,1), walk(-1,0), walk(0,-1), walk(1,0)};
    
    walk position = walk(0,0);
    
    for(int i=0; i<path.size(); ++i) {
        int iMod = i%4;
        position = position + path[i]* arr[iMod];
    }
    
    if(position.x ==0 && position.y==0) {
        return true;
    }
    return false;
}

- Anonymous September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are only considering ingoing spiral or outgoing spiral. Won't work for move containing both. For example, 2, 1, 4, 4, 3, 3, 2, 1, 1.

- zahidbuet106 September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def does_self_intersect(steps):
    for i in range(3, len(steps)):
        if steps[i - 3] >= steps[i - 1] and steps[i - 2] <= steps[i]:
            return True
    return False

Single pass, O(1) memory.

- YOLOSWAG September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Close but I think it should be:

def does_self_intersect(steps):
    for i in range(3, len(steps)):
        len_4 = steps[i - 4] if i > 3 else 0
        if steps[i - 1] <= steps[i - 3] and steps[i - 2] <= (steps[i] + len_4):
            return True
    return False

I don't think there is any escaping the need to track at least one value outside the input list because a collision can occur with only 4 steps, but for > 4 steps your collision condition becomes steps[i - 3] >= steps[i - 1] and steps[i - 2] <= (steps[i] + steps[i - 4]).

For example test [1, 1, 2, 2, 1.5, 1.5]

- Dave September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how does it work? it doesn't work for these cases -

[2, 1, 4, 4, 3, 2, 2, 1, 1] --> should be non-crossing
[2, 1, 4, 4, 3, 3, 2, 1, 1] --> should be crossing

both cases failed in your code.

- zahidbuet106 September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Figure out all possible paths to a depth of 6, and then you have the solution.

data St s a = St { collision :: Bool, st :: s, next :: a -> St s a }                                                                                                                                         
                                                                                                                                                                                                             
f :: [Int] -> Bool                                                                                                                                                                                           
f n = any collision . driveSt (stMachine initSt) $ n'                                                                                                                                                        
  where                                                                                                                                                                                                      
    (initSt, n') = case n of                                                                                                                                                                                 
                     (x:y:z:rs) -> if z > x                                                                                                                                                                  
                                   then case rs of                                                                                                                                                           
                                         (a:rs') -> (S1 a z y x, rs')                                                                                                                                        
                                         _ -> (S1 0 0 0 0, [])                                                                                                                                               
                                   else (S2 z x y, rs)                                                                                                                                                       
                     _ -> (S1 0 0 0 0, [])                                                                                                                                                                   
                                                                                                                                                                                                             
driveSt :: St a -> [a] -> [St a]                                                                                                                                                                             
driveSt = scanl next                                                                                                                                                                                         
                                                                                                                                                                                                             
data MSt = S1 { s13 :: Int, s12 :: Int, s11 :: Int, s10 :: Int }                                                                                                                                             
        | S2 { s22 :: Int, s21 :: Int, s20 :: Int }  deriving (Eq, Ord, Show, Read)                                                                                                                          
                                                                                                                                                                                                             
                                                                                                                                                                                                             
stMachine :: MSt -> St MSt Int                                                                                                                                                                               
stMachine initSt = St False initSt (f initSt)                                                                                                                                                                
  where                                                                                                                                                                                                      
    f (S1 a3 a2 a1 a0) x = St False newSt (f newSt)                                                                                                                                                          
      where                                                                                                                                                                                                  
       newSt | x < a2 - a0 = S2 x a3 x                                                                                                                                                                       
             | x < a2 = S2 x (a3 - a1) x                                                                                                                                                                     
             | otherwise = S1 x a3 a2 a1                                                                                                                                                                     
    f (S2 a2 a1 a0) x = St b newSt (f newSt)                                                                                                                                                                 
      where                                                                                                                                                                                                  
       (b, newSt) | x < a1 = (False, S2 x a2 a1)                                                                                                                                                             
                  | otherwise = (True, S2 x a2 a1)

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

data St s a = St { collision :: Bool, st :: s, next :: a -> St s a }                                                                                                                                         
                                                                                                                                                                                                             
f :: [Int] -> Bool                                                                                                                                                                                           
f n = any collision . driveSt (stMachine initSt) $ n'                                                                                                                                                        
  where                                                                                                                                                                                                      
    (initSt, n') = case n of                                                                                                                                                                                 
                     (x:y:z:rs) -> if z > x                                                                                                                                                                  
                                   then case rs of                                                                                                                                                           
                                         (a:rs') -> (S1 a z y x, rs')                                                                                                                                        
                                         _ -> (S1 0 0 0 0, [])                                                                                                                                               
                                   else (S2 z x y, rs)                                                                                                                                                       
                     _ -> (S1 0 0 0 0, [])                                                                                                                                                                   
                                                                                                                                                                                                             
driveSt :: St a -> [a] -> [St a]                                                                                                                                                                             
driveSt = scanl next                                                                                                                                                                                         
                                                                                                                                                                                                             
data MSt = S1 { s13 :: Int, s12 :: Int, s11 :: Int, s10 :: Int }                                                                                                                                             
        | S2 { s22 :: Int, s21 :: Int, s20 :: Int }  deriving (Eq, Ord, Show, Read)                                                                                                                          
                                                                                                                                                                                                             
                                                                                                                                                                                                             
stMachine :: MSt -> St MSt Int                                                                                                                                                                               
stMachine initSt = St False initSt (f initSt)                                                                                                                                                                
  where                                                                                                                                                                                                      
    f (S1 a3 a2 a1 a0) x = St False newSt (f newSt)                                                                                                                                                          
      where                                                                                                                                                                                                  
       newSt | x < a2 - a0 = S2 x a3 x                                                                                                                                                                       
             | x < a2 = S2 x (a3 - a1) x                                                                                                                                                                     
             | otherwise = S1 x a3 a2 a1                                                                                                                                                                     
    f (S2 a2 a1 a0) x = St b newSt (f newSt)                                                                                                                                                                 
      where                                                                                                                                                                                                  
       (b, newSt) | x < a1 = (False, S2 x a2 a1)                                                                                                                                                             
                  | otherwise = (True, S2 x a2 a1)

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Haskell Solution:

data St s a = St { collision :: Bool, st :: s, next :: a -> St s a }                                                                                                                                         
                                                                                                                                                                                                             
f :: [Int] -> Bool                                                                                                                                                                                           
f n = any collision . driveSt (stMachine initSt) $ n'                                                                                                                                                        
  where                                                                                                                                                                                                      
    (initSt, n') = case n of                                                                                                                                                                                 
                     (x:y:z:rs) -> if z > x                                                                                                                                                                  
                                   then case rs of                                                                                                                                                           
                                         (a:rs') -> (S1 a z y x, rs')                                                                                                                                        
                                         _ -> (S1 0 0 0 0, [])                                                                                                                                               
                                   else (S2 z x y, rs)                                                                                                                                                       
                     _ -> (S1 0 0 0 0, [])                                                                                                                                                                   
                                                                                                                                                                                                             
driveSt :: St a -> [a] -> [St a]                                                                                                                                                                             
driveSt = scanl next                                                                                                                                                                                         
                                                                                                                                                                                                             
data MSt = S1 { s13 :: Int, s12 :: Int, s11 :: Int, s10 :: Int }                                                                                                                                             
        | S2 { s22 :: Int, s21 :: Int, s20 :: Int }  deriving (Eq, Ord, Show, Read)                                                                                                                          
                                                                                                                                                                                                             
                                                                                                                                                                                                             
stMachine :: MSt -> St MSt Int                                                                                                                                                                               
stMachine initSt = St False initSt (f initSt)                                                                                                                                                                
  where                                                                                                                                                                                                      
    f (S1 a3 a2 a1 a0) x = St False newSt (f newSt)                                                                                                                                                          
      where                                                                                                                                                                                                  
       newSt | x < a2 - a0 = S2 x a3 x                                                                                                                                                                       
             | x < a2 = S2 x (a3 - a1) x                                                                                                                                                                     
             | otherwise = S1 x a3 a2 a1                                                                                                                                                                     
    f (S2 a2 a1 a0) x = St b newSt (f newSt)                                                                                                                                                                 
      where                                                                                                                                                                                                  
       (b, newSt) | x < a1 = (False, S2 x a2 a1)                                                                                                                                                             
                  | otherwise = (True, S2 x a2 a1)

- Roger September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public bool IsCrossing(List<float> nums)
{
    if(nums.Count < 4) return false;
    float x1, x2, y1, y2;
    
    x1 = 0;
    y1 = nums[0];
    x2 = 0- nums[1];
    y2 = y1 - nums[2];
    
    for(int i = 3; i < nums.Count; i++)
   {
        switch(i%4)
        {
              case 0: // north
                   if((y2+ nums[i]) <= y1) return false;
                   y1 = y2+ nums[i];
                   break;
              case 1: // west
                   if(x1-nums[i] >= x2) return false;
                   x2 = x1-nums[i];
                   break;
              case 2: // south
                   if(y1 - nums[i] >= y2) return false;
                   y2 = y1 - nums[i];
                   break;
               case 3: // east
                   if(x2 + nums[i] <= x1) return false;
                   x1 = x2 + nums[i]; break;
        }
        
    }
    return true;
}

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain how does it work for these cases

[2, 1, 4, 4, 3, 2, 2, 1, 1] --> should be non-crossing
[2, 1, 4, 4, 3, 3, 2, 1, 1] --> should be crossing

I can see this code is failing for both of the above cases (returning false at i=4).

- zahidbuet106 September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

distance of south <= distance of north &&
distance of east >= distance of west

- justaguy September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

distance(South)<=distance(North) &&
distance(East)>=distance(West)

- justaguy September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

wrong

- hanks October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My solution:

public class Spiral {

    public static void main(String[] args) {
        // increasing without intersection
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{1, 2, 3, 4, 5, 6, 7, 8}));
        // decreasing without intersection
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{8, 7, 6, 5, 4, 3, 2, 1}));
        // intersection
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{2, 1, 1, 2}));
        // expanding and then decreasing with intersection
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{1, 1, 2, 4, 1, 3, 0.9f, 2.5f, 0.5f, 2}));
        // expanding and then decreasing without intersection
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{1, 1, 2, 4, 1, 2.9f, 0.9f, 2.5f, 0.5f, 2}));
        System.out.println("intersects: " + doesSpiralIntersect(new float[]{1, 1, 2, 4, 0.95f, 3.5f, 0.9f, 2.5f, 0.5f, 2}));
    }

    /**
     * Checks to see if the input array of floats intersect given that after each
     * number the direction changes counter clockwise by 90 degrees.
     * Timing: O(n)
     * Space: O(1)
     * @param s An array of positive floats
     * @return true if intersects otherwise false.
     */
    public static boolean doesSpiralIntersect(float[] s) {
        // need 4 or more to intersect
        if (s == null || s.length < 4) {
            return false;
        }

        // does it intersect straight away?
        if (s[0] >= s[2] && s[3] >= s[1]) {
            return true;
        }

        int index = 3;
        // is the spiral increasing?, options are to change to decreasing or exhaust the list
        while (index < s.length && s[index] > s[index - 2] && s[index - 1] > s[index - 3]) {
            index++;
        }

        // handle the change over from increasing to decreasing. Need to check 4
        // back in order to see if the right boundary of the increasing is going
        // to intersect with this line against the line 1 forward
        if (index < s.length && index > 3
                && (s[index] + s[index - 4]) >= s[index - 2]
                && (s[index + 1] + s[index - 3]) >= s[index - 1]) {
            return true;
        }

        // otherwise, decreasing if we made it here
        while (index < s.length) {
            if (s[index] >= s[index - 2]) {
                return true;
            }
            index++;
        }

        return false;
    }
}

- AMP September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

close, but fail to work for [1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1]

- Anonymous September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

on each axis independently (North-South, East-West) every new value must be greater than the previous registered in such axe.

float last_ns{}, last_we{};
bool we{false}; // next value is in NS axis.
while(true) {
	int cur{}; //current value
	cin >> cur;
	if (we) {
		if (last_we<=cur) {
			cout << "crossing WE" << endl;
			break;
		}
		last_we=cur;
	}
	else {
		if (last_ns<=cur) {
			cout << "crossing NS" << endl;
			break;
		}
		last_ns=cur;
	} 
	we=!we;	
}

- Marcos Mayorga September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your collision conditions need a rethink. Consider the sequence [5, 4, 3, 2, 1, 1]

- Dave September 05, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More