Priceline Junior Software Developer Interview Questions and Answers

Round duration - 90 minutes
Round difficulty - Hard

This was an online coding round where we were supposed to solve 2 questions under 90 minutes . Both the questions in my set were related to Graphs and were quite tricky and heavy to implement.

Q1. 
Path Counting in Directed Graph
Given a directed graph with a specified number of vertices V and edges E, your task is to calculate the total number of distinct paths from a given source node S to all ot...read more
Ans. 
Calculate the total number of distinct paths from a given source node to all other nodes in a directed graph.
• Use dynamic programming to keep track of the number of paths from the source node to each node in the graph.

• Consider using modular arithmetic to handle large numbers and prevent overflow.

• Start by initializing the number of paths from the source node to itself as 1.

• Iterate through the edges of the graph and updat...read more
Answered by AI
View 2 more answers
Q2. 
Course Schedule II Problem Statement
You are provided with a number of courses 'N', some of which have prerequisites. There is a matrix named 'PREREQUISITES' of size 'M' x 2. This matrix indicates that fo...read more
Ans. 
Given courses with prerequisites, determine a valid order to complete all courses.
• Use topological sorting to find a valid order of courses.

• Create a graph with courses as nodes and prerequisites as edges.

• Start with courses that have no prerequisites and remove them from the graph.

• Continue this process until all courses are taken or there are no valid courses left.

• If there is a cycle in the graph, it is impossible to com...read more
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This was a Data Structures and Algorithms round with some standard questions . I was expected to come up with an
efficient approach and code it as well .

Q1. 
Merge Intervals Problem Statement
You are provided with 'N' intervals, each containing two integers denoting the start time and end time of the interval.
Your task is to merge all overlapping intervals a...read more
Ans. 
Merge overlapping intervals and return sorted list of merged intervals.
• Sort the intervals based on start times.

• Iterate through intervals and merge overlapping intervals.

• Return the merged intervals in sorted order.
Answered by AI
Add your answer
Q2. 
Longest Route Problem Statement
Given a 2-dimensional binary matrix called Mat of size N x M that consists solely of 0s and 1s, find the length of the longest path from a specified source cell to a destina...read more
Ans. 
Find the length of the longest path from a source cell to a destination cell in a binary matrix.
• Use depth-first search (DFS) to explore all possible paths from source to destination.

• Keep track of visited cells to avoid revisiting them.

• Return the length of the longest path found, or -1 if no path exists.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both
as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Q1. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Ans. 
Find the length of the longest strictly increasing subsequence in an array of integers.
• Use dynamic programming to solve this problem efficiently.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the result.
Answered by AI
Add your answer
Q2. 
Search In Rotated Sorted Array Problem Statement
Given a rotated sorted array ARR of size 'N' and an integer 'K', determine the index at which 'K' is present in the array.
Note:
1. If 'K' is not present...read more
Ans. 
Given a rotated sorted array, find the index of a given integer 'K'.
• Use binary search to find the pivot point where the array is rotated.

• Then perform binary search on the appropriate half of the array to find 'K'.

• Handle cases where 'K' is not present in the array by returning -1.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round with 2 questions of Medium to Hard difficulty . I was expected to follow some clean code and OOPS principles to write the code in this round .

Q1. 
Rank from Stream Problem Statement
Given an array of integers ARR and an integer K, determine the rank of the element ARR[K].
Explanation:
The rank of any element in ARR is defined as the number of elem...read more
Ans. 
Given an array and an index, find the number of elements smaller than the element at that index appearing before it in the array.
• Iterate through the array up to index K and count the number of elements smaller than ARR[K].

• Return the count as the rank of ARR[K].

• Handle edge cases like empty array or invalid index K.
Answered by AI
Add your answer
Q2. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
• Implement a doubly linked list to maintain the order of recently used keys.

• Use a hashmap to store key-value pairs for quick access.

• Update the order of keys in the linked list on get and put operations.

• Evict the least recently used key when the cache reaches its capacity.
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

This was an online coding, mcq and debugging round round held on Amcat platform, there were 3 sections in the test.
1)20 MCQ questions {10 involving mathematics and the other 10 on programming fundamentals}; duration:20 mins;
you cannot navigate back to a questions after moving further, so have to answer carefully
2)debugging section- it involved 7 questions which were to be completed within 20 mins, 5 of them were very easy, each question only took almost a minute to figure out the problem with the code, last 2 questions were relatively moderate and there were errors at 3-4 sections of the entire code. I was able to solve all the questions in 15 mins
3)2 Coding questions- duration:80 mins, one was moderate on string while the other one involved dynamic programming, I was able to successfully execute all the available test cases.

Q1. 
Smallest Window Problem Statement
Given two strings, S and X, your task is to find the smallest substring in S that contains all the characters present in X.
Example:
Input:
S = "abdd", X = "bd"
Outpu...read more
Ans. 
Find the smallest substring in S that contains all characters in X.
• Use a sliding window approach to find the smallest window in S containing all characters of X.

• Maintain a hashmap to keep track of characters in X and their frequencies.

• Slide the window by moving the right pointer until all characters in X are found, then move the left pointer to minimize the window size.

• Return the smallest window found.

• Example: S = 'abd...read more
Answered by AI
Add your answer
Q2. 
Minimum Sum in Matrix Problem Statement
You are given a 2D matrix 'ARR' of size 'N x 3' with integers, where 'N' is the number of rows. Your task is to compute the smallest sum achievable by selecting one...read more
Ans. 
Find the smallest sum achievable by selecting one element from each row of a 2D matrix, following certain constraints.
• Iterate through each row and find the minimum element that does not violate the constraints.

• Keep track of the minimum sum achieved by selecting elements from each row.

• Avoid selecting elements directly beneath previously selected elements.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Hard

The interview started with introduction, there were two interviewers, they both introduced themselves and then asked me to introduce myself. Then we had a brief description on my projects, and they really appreciated my projects. Then as they were more concerned with DSA part, so we moved towards solving a coding problem. It was a famous rotten oranges problem with some change in language but as I haven't seen it beforehand, I wasn't able to give them an optimal approach and had to ask for some hints, but with a certain amount of help and hints, I was able to solve the problem and successfully coded it in 5 mins. Then the interviewers went for a dry run of the algorithm and tried to run it on each and every corner case, but as my algorithm was kind of bullet proof, it successfully passed all the corner cases.
Then they went for some questions on OOPS concepts involving inheritance and we had a long discussion on virtual function and runtime polymorphism. Then the interview was ended after a Q/A round that lasted for 3-4 minutes.

Q1. 
Rotten Oranges Problem Statement
Given a grid containing oranges in three possible states:
• Value 0 - Empty cell
• Value 1 - Fresh orange
• Value 2 - Rotten orange
Every second, any fresh orange adjac...read more
Ans. 
Given a grid with fresh and rotten oranges, determine the minimum time for all oranges to become rotten.
• Create a queue to store the coordinates of rotten oranges and perform BFS to rot adjacent fresh oranges

• Track the time taken to rot all oranges and return -1 if some fresh oranges remain

• Handle edge cases like empty grid or no fresh oranges present

• Example: For input grid = [[2,1,1],[1,1,0],[0,1,1]], the minimum time to...read more
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

Evening test around 5
Platform :- SHL
Environment was amazing

Q1. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
• Check if the second tree is a subtree of the first tree by comparing their structures and node values.

• Use a recursive approach to traverse both trees and check for equality.

• Handle cases where one tree is null or the values do not match.

• Return true if S is a subtree of T, false otherwise.
Answered by AI
Add your answer
Q2. 
Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the positi...read more
Ans. 
Given a sorted N*N matrix, find the position of a target integer X.
• Iterate over each row and column to find the target integer X

• Utilize the sorted nature of the matrix to optimize the search process

• Return the position of X if found, else return -1 -1
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

1 Hour 
Afternoon

Q1. 
Intersection of Linked List Problem
You are provided with two singly linked lists containing integers, where both lists converge at some node belonging to a third linked list.
Your task is to determine t...read more
Ans. 
Find the node where two linked lists merge, return -1 if no merging occurs.
• Traverse both lists to find their lengths and the difference in lengths

• Move the pointer of the longer list by the difference in lengths

• Traverse both lists simultaneously until they meet at the merging point
Answered by AI
Add your answer
Q2. 
Problem: Pair Sum in a Binary Search Tree
Given a Binary Search Tree (BST) and an integer 'S', your task is to find all pairs of nodes within the BST that total to 'S' and return these pairs. If no such p...read more
Ans. 
Find pairs of nodes in a BST that sum up to a given value 'S'.
• Traverse the BST in-order to get a sorted list of nodes.

• Use two pointers approach to find pairs with sum 'S'.

• Keep track of visited nodes to avoid using the same node twice in a pair.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Online Round held on Chime

Q1. 
Is Binary Heap Tree Problem Statement
You are given a binary tree of integers. Your task is to determine if it is a binary heap tree or not.
Input:
The first line of input contains an integer ‘T’ denoti...read more
Ans. 
Determine if a given binary tree is a binary heap tree or not based on certain properties.
• Check if the binary tree is a complete binary tree where every level, except the last level, is completely filled and the last level is as far left as possible.

• Ensure that every parent node is greater than all its children nodes, forming a max-heap.

• If any node does not have a left or right child, it should be represented as -1 in ...read more
Answered by AI
Add your answer
Q2. 
Edit Distance Problem Statement
Given two strings S and T with lengths N and M respectively, your task is to find the "Edit Distance" between these strings.
The Edit Distance is defined as the minimum nu...read more
Ans. 
The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the edit distances between substrings of the two input strings.

• Fill up the array based on the minimum of three possible operations: insert, delete, or replace.

• The final answer will be the value at...read more
Answered by AI
Add your answer

Round duration - 90 Miinutes
Round difficulty - Medium

First round had MCQ + 2 coding questions. It was held in morning around 11 am. It was held on campus.

Q1. 
Robot Delivery Path Problem
You are tasked with directing a robot from the top-left corner of an N*N matrix to a specified point (x, y), delivering a parcel. The robot is restricted to move only on flat a...read more
Ans. 
Determine if a robot can reach a specified destination in a matrix by moving only downwards or rightwards.
• Start at (0,0) and move towards the destination (x, y) only downwards or rightwards.

• Check if the path is clear (1) and avoid obstacles (0) while staying within matrix boundaries.

• Return true if the robot can reach the destination, false otherwise.

• Example: For input matrix [[1, 0, 1], [1, 1, 1], [1, 1, 5]] with desti...read more
Answered by AI
Add your answer
Q2. 
Unique Element in Array
Given an arbitrary array arr consisting of N non-negative integers where every element appears thrice except for one. Your task is to find the element in the array that appears onl...read more
Ans. 
Find the unique element in an array where every element appears thrice except for one.
• Use XOR operation to find the unique element.

• Iterate through the array and XOR each element to find the unique element.

• The XOR operation cancels out elements that appear thrice, leaving only the unique element.

• Example: arr = [2, 2, 3, 2], XOR of all elements = 3.

• Example: arr = [0, 1, 0, 1, 0, 1, 99], XOR of all elements = 99.
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

Second Round was held in morning around 10-11 am. There was one interviewer working on his laptop. Interviewer was really helpful and first offered me water and then for a bit talked about himself.

Q1. 
BST Iterator Problem Statement
You are tasked with implementing a class BSTIterator, which is designed to traverse a Binary Search Tree (BST) in the inorder manner. The class must support the following op...read more
Ans. 
Implement a BSTIterator class to traverse a Binary Search Tree in inorder manner.
• Implement a constructor to initialize the iterator with the root of the BST.

• Implement next() and hasNext() methods to traverse the BST in inorder.

• Implement prev() and hasPrev() methods to access the previous element in the inorder traversal.

• Use level-order traversal format to represent the tree input.

• Output the inorder traversal of the bin...read more
Answered by AI
Add your answer
Q2. 
Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum num...read more
Ans. 
Calculate the distance between two nodes in a binary tree.
• Traverse the tree to find the paths from the root to each node

• Find the lowest common ancestor of the two nodes

• Calculate the distance by adding the distances from the LCA to each node
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

Q1. 
Find All Pairs Adding Up to Target
Given an array of integers ARR of length N and an integer Target, your task is to return all pairs of elements such that they add up to the Target.
Input:
The first line ...read more
Ans. 
Given an array of integers and a target, find all pairs of elements that add up to the target.
• Iterate through the array and for each element, check if the target minus the element exists in a hash set.

• If it exists, add the pair to the result. If not, add the element to the hash set.

• Handle cases where the same element is used twice in a pair.

• Return (-1, -1) if no pair is found.
Answered by AI
Add your answer
Q2. 
Clone a Linked List with Random Pointers
Given a linked list where each node contains two pointers: one pointing to the next node and another random pointer that can point to any node within the list (or ...read more
Ans. 
Create a deep copy of a linked list with random pointers.
• Iterate through the original linked list and create a new node for each node in the list.

• Store the mapping of original nodes to new nodes in a hashmap to handle random pointers.

• Update the random pointers of new nodes based on the mapping stored in the hashmap.

• Return the head of the copied linked list.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Unique Element in Array
Given an arbitrary array arr consisting of N non-negative integers where every element appears thrice except for one. Your task is to find the element in the array that appears onl...read more
Ans. 
Find the element that appears only once in an array where every other element appears thrice.
• Use bitwise operations like XOR to find the unique element in linear time complexity.

• XOR all elements in the array, the result will be the unique element.

• Elements that appear thrice will cancel out each other in XOR operation.

• Example: arr = [2, 2, 3, 2], XOR of all elements = 3 which is the unique element.
Answered by AI
Add your answer
Q2. 
Next Greater Element Problem Statement
You are provided with an array or list ARR containing N positive integers. Your task is to determine the Next Greater Element (NGE) for each element in the array.
T...read more
Ans. 
Find the Next Greater Element for each element in an array.
• Iterate through the array from right to left

• Use a stack to keep track of elements with no greater element to the right

• Pop elements from the stack until a greater element is found or stack is empty
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Convert BST to Greater Sum Tree
Given a Binary Search Tree (BST) of integers, your task is to convert it into a greater sum tree. In the greater sum tree, each node's value should be replaced with the sum...read more
Ans. 
Convert a Binary Search Tree into a Greater Sum Tree by replacing each node's value with the sum of all nodes' values greater than the current node's value.
• Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.

• Keep track of the running sum of visited nodes' values and update each node's value with this sum.

• Recursively apply the above steps to all nodes in the BST.

• Example: For input ...read more
Answered by AI
Add your answer
Q2. 
Sort Linked List Problem Statement
You are given a linked list of N nodes where each node contains values 0, 1, and 2 exclusively. Your task is to sort the linked list.
Input:
The first line contains an...read more
Ans. 
Sort a linked list containing values 0, 1, and 2 exclusively.
• Use three pointers to keep track of nodes with values 0, 1, and 2 separately.

• Traverse the linked list and move nodes to their respective positions based on their values.

• Finally, concatenate the three lists in the order 0 -> 1 -> 2 to get the sorted linked list.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider edge cases like when the matrix is empty or when all cells are water (0s).
Answered by AI
Add your answer
Q2. 
Maximum Path Sum in a Matrix
Given an N*M matrix filled with integer numbers, determine the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row...read more
Ans. 
Find the maximum sum that can be obtained from a path in a matrix from the first row to the last row.
• Use dynamic programming to keep track of the maximum sum at each cell.

• Consider moving down, down-left, and down-right to calculate the maximum sum.

• Start from the second row and update the values based on the maximum sum from the row above.

• At the end, find the maximum sum in the last row to get the final result.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This round was held during university hours and consisted of 2 coding questions.

Round duration - 120 minutes
Round difficulty - Easy

Make sure you do no cutting and are clear about the approach you'd be following. 
 

Q1. What is the running median of an input stream?
Ans. 
Running median of an input stream is the median value of the numbers seen so far in a continuous stream of data.
• Maintain two heaps - a max heap for the lower half of the numbers and a min heap for the upper half.

• Keep the number of elements in the two heaps balanced or differ by at most 1.

• If the total number of elements is odd, the median is the root of the max heap. If even, it is the average of the roots of the two he...read more
Answered by AI
Add your answer