Google Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
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.
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
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
// 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");
}
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, 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.
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.
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.
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;
}
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
# -*- 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
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;
}
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;
}
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}
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;
}
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
}
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;
}
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;
}
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];
}
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];
}
#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;
}
#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;
}
/*
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
}
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;
}
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;
}
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];
}
}
#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;
}
#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;
}
#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;
}
#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;
}
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.
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]
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)
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)
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)
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;
}
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;
}
}
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;
}
- Anonymous September 05, 2015