Please enable JavaScript.
Coggle requires JavaScript to display documents.
SDE questions - Coggle Diagram
SDE questions
1.Arrays
- using sorting
If the numbers are sorted, then any duplicate numbers will be at adjacent index in the sorted array.
-
-
- using hashing
If we store each element as we iterate over the array, we can simply check each element as we iterate over the array.
-
- Floyd's Tortoise and Hare (Cycle Detection)
-
-
- sort the array in O(nlogn)
- count number of 0, 1 and 2 then make array ; takes two pass so O(2N) time
- using Dutch national flag algo; takes O(n) time and O(1) space
three pointers - low, mid and high
Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers.
- sort and iterate ; takes Onlogn for sorting and On for iterating
- Improve this by using hashing; takes O(2n) time and On space
-
- There is another approach of negating the values but interviewer can tell not to change the array
-
