Linkedin | SRE | Coding OA and Solutions | Set-16 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

Picking Tickets
Consider an array of n ticket prices, tickets. A number, m, is defined as the size of some subsequences, s, of tickets where each element covers an unbroken raneg of integers. That is to say, if you were to sort the elements in s, the absolute difference between any elements j and j+1 would be either 0 or 1. Determine the maimum length of a subsequence chosen from the tickets array

 

Example
tickets = [8, 5, 4, 8, 4]

 

Valid subsequences, sorted, are {4,4,5} and {8,8}. These subsequences have m values of 3 and 2, respectively. Return 3.

 

Constraints

 

• 1 <= n <= 10^5
• 1 <= tickets[i] <= 10^9

Answer 2

I was thing approach like following not sure if this would work for all test cases

 

pub fn picking_tickets(mut prices: Vec<i32>) -> usize {
    
    prices.sort();
    
    let mut max_size = 0;
    let mut seq = VecDeque::new();

    for i in 0..prices.len() - 1 {
        if (prices[i] - prices[i + 1]).abs() <= 1 {
            if seq.back().is_none() {
                seq.push_back(prices[i]);
                seq.push_back(prices[i + 1]);
            } else {
                seq.push_back(prices[i + 1])
            }
        } else {
            max_size = max(seq.len(), max_size);
            seq.truncate(0);
        }
    }
    return max_size;
}

Answer 3

freq = Counter(tickets)
tmp = []
def dfsFindSeq(cur):
    st= []
    cur_len = 0
    st.append(cur)
    #base case
    if cur not in freq:
        return cur_len
    
    while st:
        k = st.pop()
        if k in freq:
            cur_len+=freq[k]
            freq.pop(k)
        if (k+1) in freq:
            st.append(k+1)
        if (k-1) in freq:
            st.append(k-1)
    
    return cur_len
l= 0
for x in tickets:
    l = max(l, dfsFindSeq(x))
    


print(l)