## Google Interview Question for Software Developers

• 8

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");
}``````

Comment hidden because of low score. Click to expand.
0

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.

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

Consider 2,2,3,2,2

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

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

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!

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");
}``````

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

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()``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

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

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.

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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 <= lst and lst >= lst:
elif i == 4:
if (lst == lst and lst + lst >= lst) or (lst < lst and lst >= lst):
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]:
# inner spiral
elif lst[i-1]<=lst[i-2]<=lst[i-3] and lst[i]>=lst[i-2]:

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``````

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 <= lst and lst >= lst:
elif i == 4:
if (lst == lst and lst + lst >= lst) or (lst < lst and lst >= lst):
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]:

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``````

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 >= s && s >= s){
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;
}``````

Comment hidden because of low score. Click to expand.
0

this is perfect solution

Comment hidden because of low score. Click to expand.
0

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;
}

Comment hidden because of low score. Click to expand.
0

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}

Comment hidden because of low score. Click to expand.
0

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 >= s && s >= s) {
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;
}``````

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
}``````

Comment hidden because of low score. Click to expand.
0

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 >= s && s >= s){
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;
}``````

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{0}; // used in inner spiral, only need two bounds
float pre{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;
}``````

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

``````public static boolean isSelfIntersecting(double[] steps) {
double[] bufx = new double;
double[] bufy = new double;
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];
}``````

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

``````public static boolean isSelfIntersecting(double[] steps) {
double[] bufx = new double;
double[] bufy = new double;
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];
}``````

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;
}

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;
}``````

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 <= A) {
// 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
}``````

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, steps, 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;
}``````

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;
}``````

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>=top&&original<=top&&original<=p&&original+nums[i]>=p){
return true;
}
}
east.index = original;
east.range = original;
east.range = original+nums[i];
original = original + nums[i];
}else if(i%4==1){
if(i!=1){
float[] left = west.range;
float p = west.index;
if(original>=left&&original<=left&&original>=p&&original-nums[i]<=p){
return true;
}
}
north.index = original;
north.range = original-nums[i];
north.range = original;
original = original-nums[i];
}else if(i%4==2){
if(i!=2){
float[] bottom = south.range;
float p = south.index;
if(original>=bottom&&original<=bottom&&original>=p&&original-nums[i]<=p){
return true;
}
}
west.index = original;
west.range = original-nums[i];
west.range = original;
original = original-nums[i];
}else{
float[] right = east.range;
float p = east.index;
if(original>=right&&original<=right&&original<=p&&original+nums[i]>=p){
return true;
}
south.index = original;
south.range = original;
south.range = original+nums[i];
original = original+nums[i];
}
}
return false;
}

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

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;
}

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

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]

Comment hidden because of low score. Click to expand.
0

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.

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)``````

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)``````

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)``````

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;
x2 = 0- nums;
y2 = y1 - nums;

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;
}``````

Comment hidden because of low score. Click to expand.
0

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).

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

wrong

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 >= s && s >= s) {
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;
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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.

### 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.