---
# System prepended metadata

title: Bharat

---

# Bharat | 7+ yrs exp
- Took so much time trying to solve ds problem. Coulnt solve one. Please skip
- Java | Nodejs, Ruby on Rails, ReactJs.
- Psql
- AWS: 

# Question 1: Sort
- 0s , 1s, 2s

- Single iteration O(N) and constant space complexity 
                                                      
ex - [2, 1, 0, 2, 1, 2, 2, 0, 0]    
     i,m                      j
     [0, 1, 0, 2, 1, 2, 2, 0, 2]
     i,m                     j


while(mid < j) {
    if(a[mid] == 0) {
        swap(a[mid], a[i])
        i++
        mid++
    } else if(a[mid] == 2){
        swap(a[mid], a[j])
        j--
    } else if(a[mid] == 1) {
       mid++
    }
}


0..low-1 -> 0
low..mid-1 -> 1
mid..high-1 -> everything jumbled
high..n -> 2


# Question 2: Combination of array of length k using array elements

- array - [1, 2, 3, 4, 5] - distinct values
- k = 3, 0 < k < length-1 

```javascript!
// main function

function combinations(arr, k) {
    const result = [];
      recursiveCombinations(0, [], arr, k, result);
    return result;
}

function recursiveCombinations(start, curr, arr, k, result) {
    if (curr.length === k) {
        result.push([...curr]);
        return;
    }
    
    for (let i = start; i < arr.length; i++) {
        curr.push(arr[i]);
        recursiveCombinations(i + 1, curr, arr, k, result);
        curr.pop();
    }
}
```

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
....