Coding Interview: Reverse Array in Place - Whiteboard Thursday

Check out the detailed data structures and algorithms course at www.interviewaccelerator.com
Here is the problem I'll cover in next week's Whiteboard Thursday:
You're given an array of integers where each element contains the index to the next element. Determine if the array has a cycle.
Try it out yourself and leave your answers in the comments below. And subscribe to get notified of the solution next week.
For advanced data structures and algorithms practice, visit irfanbaqui.com/coding-intervi...

[@rahul.gupta.96]

It's always nice to see coding problems in an interview environment. Thanks for taking out the time for doing this. It's really helpful and mostly, it's fun to watch. 😄 Eagerly waiting for the next week. 😋

[@IrfanBaqui]

Thanks for the kind words, Rahul!

[@jasonwelsh417]

This Whiteboard Thursday series is amazing. Thank you so much!

[@IrfanBaqui]

I'm so glad you like it :)

[@PadillaJosh]

Awesome vids man. Been watching your vids in prep for my interviews.

[@saurabhmishra8833]

I like the series ,actually the first series of tutorials that I found useful and interesting .Please make more videos

[@travhenry3451]

This was awesome! Keep up the great work!

[@ridhwaans]

this week's question was an easy one

[@anirban_j]

@Irfan Don't you think time complexity should be n/2 becoz you have condition while (front

[@Davidh0330]

The complexity is still linear time so it's o(n)

[@APMathNerd]

O(n/2) is the same as O(n). We ignore constant factors and added lower order terms when talking about time complexity (e.g., O(3n+7) is also the same as O(n)).

[@shrajan28]

can you explain time complexity, how its linear?

[@tannerbarcelos6880]

Loop through the array , swaps are constant. O(n/2) sure, but you actually loop the whole array using two pointers that compress, so, it’s O(n) where n is the number of elements traversed in this array

[@JossinJax]

Why is the back index array.length -1? What if the value of index zero, zero?

[@iliketocode6986]

i saw this in a book and it hurt my brain.

[@pratapdafedar7305]

//Tip#2: Swapping 2 elements in an array without using any temp or extra space. function Swap(Arr, front, back) { Arr[front] = Arr[front] + Arr[back]; Arr[back] = Arr[front] - Arr[back]; Arr[front] = Arr[front] - Arr[back]; }

[@nands4410]

Pratap dafedar Using ^ would be better than this

[@jackxlifer6346]

Sum operation could overflow, or we can loose precision for float numbers, so temp variable is better option.

[@alxjones]

Both add swap and xor swap are strictly worse than temp swap in 99% of applications. Compilers will optimize away the temp variable, which means that temp swap won't use any additional space, but will rather use a built in swap op in the processor instruction set. This is the most efficient way to do it. The add swap and xor swap both are slower because they often won't get optimized away, and each operation requires the results from the last meaning that parallelization is not possible. Also, add swap can have issues with integer overflow, float overflow and precision, while xor swap can create problems with aliasing. Lastly, neither of these two swaps will work for objects in java, since there are no pointers to even use as a work-around, not to mention that they are very unintuitive to people reading that code that aren't familiar with those techniques. In the end, use temp swap. But it doesn't hurt to bring up other methods of swapping (or doing anything) in an interview if you can explain when they are better and when they are worse.

[@rmadhavmca1]

I like your videos, Could you please also explain time complexity of each of your video. thanks in advance

[@misslondonstani]

Can’t you just use a stack?

[@scuba485]

Kindly Request the lady interviewer to increase her volume..many videos her voice is not audible

[@adrianharo6586]

Perv

[@hand__banana]

@@adrianharo6586 are you dense?

[@chetanpalekar9366]

this problem can be implemented with n/2 time complexity. github.com/ChetanPalekar/JAVA-/blob/master/arrayInverseInPlace.java

[@Christopherney]

/** * Reverse an array in place. Time complexity O(n/2), Space complexity O(1) * @param arr Array to reverse * @return Reverse array */ public static int[] reverseArrayInPlace(int[] arr) { int mid = arr.length / 2; for (int leftIndex = 0; leftIndex < mid; leftIndex++) { int rightIndex = arr.length - leftIndex - 1; int leftValue = arr[leftIndex]; int rightValue = arr[rightIndex]; arr[leftIndex] = rightValue; arr[rightIndex] = leftValue; } return arr; }

[@george.5c4]

A bit slower implementation but ok.