Join Regular Classroom : Visit ClassroomTech

Amazon Interview Questions + Coding Solutions – codewindow.in

Hot Topics

Amazon Solution

Technical Round

Given a string “aaabbbcc”, compress it, = “a3b3c2”. Given that output string’s length is always smaller than input string, you have do it in place. No extra space

#include <iostream>
using namespace std;

void compress(string str) 
{ 
    int len = str.length(); 
    for (int i = 0; i < len; i++) {  
        int count = 1; 
        while (i < len - 1 && str[i] == str[i + 1]) { 
            count++; 
            i++; 
        }
        if (count == 1){
          cout << str[i];
        }
        else{
          cout << str[i] << count;
        }
         
    } 
} 

int main() {
  
  string str = "aaabbbcc"; 
  compress(str); 
}
/*
output:
a3b3c2
*/

Write an algorithm to determine whether a given number is of the form (2^n) +1, where n is an integer.

Here’s one algorithm to determine whether a given number is of the form (2^n) + 1, where n is an integer:
  1. Initialize a variable n to 0.
  2. While 2^n <= number:
    1. If 2^n + 1 = number, return true.
    2. Increment n by 1.
  3. If the while loop terminates, return false.
The algorithm works by iteratively increasing n and checking if 2^n + 1 is equal to the given number. If it is, then the number is of the form (2^n) + 1. If the while loop terminates, then the number is not of that form.

Implement Sum(3)(4)(5)=12 with JavaScript

Here is an implementation of the expression Sum(3)(4)(5) = 12 in JavaScript using closures:
function Sum(num) {
  let result = num;

  function f(x) {
    result += x;
    return f;
  }

  f.toString = function() {
    return result;
  };

  return f;
}

console.log(Sum(3)(4)(5)); // 12
n this implementation, the Sum function returns a closure, f, that adds the passed-in number to a result variable and returns f itself. The closure has a custom toString method that returns the final value of result.
This allows the function to be called multiple times with additional arguments, as in Sum(3)(4)(5), building up the value of result with each call. When the final call is made, the toString method is implicitly called and returns the final value of result, which is 12 in this case.

Write an algorithm to determine if 2 linked lists intersect.

Here’s one algorithm to determine if two linked lists intersect:
  1. Create two pointers, pointer1 and pointer2, both initialized to the head of each linked list.
  2. While pointer1 is not null and pointer2 is not null:
    1. If pointer1 equals pointer2, return true as the linked lists intersect at this point.
    2. If pointer1 is not null, move pointer1 to its next node.
    3. If pointer2 is not null, move pointer2 to its next node.
    4. If pointer1 is null, set it to the head of the other linked list.
    5. If pointer2 is null, set it to the head of the other linked list.
  3. If the while loop terminates, return false as the linked lists do not intersect
The algorithm works by iteratively moving both pointers through each linked list and checking if they ever point to the same node. If they do, then the linked lists intersect at that node. If the while loop terminates, then the linked lists do not intersect.
Note that this algorithm is optimized for linked lists of different lengths and will take linear time in the length of the intersection.

Find the union of two strings.

Here’s one algorithm to find the union of two strings:
  1. Initialize an empty set result to store the unique characters of the union.
  2. Iterate through each character in the first string and add it to result if it doesn’t already exist.
  3. Iterate through each character in the second string and add it to result if it doesn’t already exist.
  4. Convert the set result to a string and return it.
The algorithm works by iterating through each character in both strings, adding it to a set result if it doesn’t already exist in the set. The set automatically ensures uniqueness, so each character will only be added once. Finally, the set is converted to a string and returned.

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i. Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] You must do this in O(N) without using division.

Here’s one algorithm to find the product of all numbers in the array except the number at the current index, in O(N) time complexity:
  1. Initialize two arrays, left and right, both of length nums.length.
  2. Initialize left[0] = 1 and iterate through the array nums from index 1 to nums.length-1, updating left[i] = left[i-1] * nums[i-1].
  3. Initialize right[nums.length-1] = 1 and iterate through the array nums in reverse order from index nums.length-2 to 0, updating right[i] = right[i+1] * nums[i+1].
  4. Initialize an empty array products of length nums.length.
    1. Iterate through the array nums and update products[i] = left[i] * right[i].
    2. Return the array products.
    The algorithm works by precomputing the product of all the numbers to the left and right of each index and then multiplying those values to get the final product of all numbers except the number at the current index. The time complexity of this algorithm is O(N), as we only iterate through the array nums twice.

To find and return the common node of two linked lists merged into a ‘Y’ shape.

To find and return the common node of two linked lists merged into a ‘Y’ shape.
Here is the code in Python:
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
def getIntersectionNode(headA, headB):
    lenA = lenB = 0
    currA, currB = headA, headB
    
    # Get the length of both linked lists
    while currA:
        lenA += 1
        currA = currA.next
    while currB:
        lenB += 1
        currB = currB.next
        
    # Set two pointers, one at the head of each linked list
    currA, currB = headA, headB
    
    # Advance the pointer in the longer linked list by the difference in lengths
    if lenA > lenB:
        for _ in range(lenA - lenB):
            currA = currA.next
    else:
        for _ in range(lenB - lenA):
            currB = currB.next
            
    # Move both pointers one step at a time until they are pointing at the same node
    while currA != currB:
        currA = currA.next
        currB = currB.next
    
    return currA
This algorithm has a time complexity of O(max(m, n)), where m and n are the lengths of the linked lists.

Given a string find the first non-repeated character

Here is one approach to find the first non-repeated character in a string:
  1. Create a dictionary to store the count of each character in the string.
  2. Iterate through the string again, and return the first character with count 1 in the dictionary.
Here is the code in Python:
def first_non_repeated_char(s):
    char_count = {}
    
    # Create a dictionary to store the count of each character in the string
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
            
    # Iterate through the string again, and return the first character with count 1 in the dictionary
    for char in s:
        if char_count[char] == 1:
            return char
        
    return None
This algorithm has a time complexity of O(n), where n is the length of the string.

Write a function in any language that will print “AN” if a number is divisible by 8, “ANIM” if divisible by 16 and “ANIMAL” if divisible by 32.

Here is an example implementation of the function in Python:
def divisible_by_8(n):
    if n % 32 == 0:
        print("ANIMAL")
    elif n % 16 == 0:
        print("ANIM")
    elif n % 8 == 0:
        print("AN")

List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god — output dog, god, act, cat

Here is an example implementation in Python to list all anagrams in a file:
from collections import defaultdict

def list_anagrams(file_path):
    anagrams = defaultdict(list)
    
    with open(file_path, 'r') as f:
        for line in f:
            word = line.strip().lower()
            sorted_word = ''.join(sorted(word))
            anagrams[sorted_word].append(word)
            
    return [group for group in anagrams.values() if len(group) > 1]
The above code uses a defaultdict from the collections module to store all the anagrams, where the keys are the sorted form of the words, and the values are lists of words that are anagrams of each other. After reading each word from the file and storing it in the anagrams dictionary, it returns a list of groups of words that are anagrams of each other.

Find the largest sum of consecutive integers in an array.

#include <bits/stdc++.h>
using namespace std;

void print(vector<int> &arr){
    for(int num:arr){
        cout<<num<<" ";
    }
}

void findUnion(int arr1[],int arr2[],int m,int n){
    int i=0,j=0;
    vector<int> arr;
    
    while(i<m && j<n){
        if(arr1[i]<arr2[j]){
            if(arr.size()==0 || arr.back()!=arr1[i]){
                arr.push_back(arr1[i]);
            }
            i++;
        }
        else{
            if(arr.size()==0 || arr.back()!=arr2[j]){
                arr.push_back(arr2[j]);
            }
            j++;
        }
    }
    
    while(i<m){
        if(arr.size()==0){
            arr.push_back(arr1[i]);
        }
        i++;
    }
    
    while(j<n){
        if(arr.size()==0){
            arr.push_back(arr2[j]);
        }
        j++;
    }
    print(arr);
}

int main() {
    
    int arr1[5]={1, 3, 4, 5, 7};
    int arr2[4]={2, 3, 5, 6};
    
    findUnion(arr1,arr2,5,4);
    
    return 0;
}
/*output:

If you have a file containing millions of integers, how would you sort the data in the file using extremely limited resources, such a s 1GB of memory?

When sorting a large amount of data with limited memory, a common approach is to use an external sorting algorithm. One such algorithm is called the “External Merge Sort”.
Here’s how the External Merge Sort algorithm works:
  1. Divide the data into smaller chunks, each small enough to fit in memory.
  2. Sort each chunk individually, using an in-memory sorting algorithm like QuickSort or MergeSort.
  3. Write each sorted chunk to a temporary file.
  4. Merge the sorted chunks, two at a time, into a single larger chunk.
  5. Repeat step 4 until all chunks have been merged into a single file.
The key idea behind External Merge Sort is to keep the memory usage low by only processing small chunks at a time. This allows you to sort a large amount of data using limited memory.
This algorithm has a time complexity of O(n log n), where n is the total number of elements in the data. The space complexity is proportional to the size of the data chunks, so you can adjust the chunk size to fit within the memory constraints.

Vertically and horizontally center an element on the screen using css.

Here’s how you can vertically and horizontally center an element on the screen using CSS:
.center {
  position: absolute;
  top: 50%;
  left: 50%;
  transform: translate(-50%, -50%);
}
In the above code, we set the position of the element to absolute, which allows us to position it relative to the nearest positioned ancestor. Then, we set the top and left properties to 50%, which positions the element in the center of the screen.
Finally, we use the transform property with the translate function to adjust the position of the element. The translate function takes two arguments, the first for the horizontal axis (-50%) and the second for the vertical axis (-50%). These values move the element up and to the left by half of its own height and width, effectively centering it on the screen.
Note: Make sure to apply the style to a parent element with a fixed size or with position: relative, otherwise, the absolute positioning will be relative to the body element and the element won’t be centered.

Find the last element of a linked list.

Here’s an example in Python to find the last element of a linked list:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def last_element(head):
    if head is None:
        return None
    current = head
    while current.next:
        current = current.next
    return current.val
In this example, we use a while loop to traverse the linked list until we reach the end, where current.next is None. At that point, we return the value of the last node, current.val.
The time complexity of this solution is O(n), where n is the number of elements in the linked list. The space complexity is O(1), as we only use a single variable to keep track of the current node.

In an array provide pairs of numbers that add to a particular value 2. In Fibonacci series provide sum of all even numbers

Here is an example solution in Python to find pairs of numbers that add up to a given value target in an array:
def find_pairs_with_sum(arr, target):
    seen = set()
    pairs = []
    for num in arr:
        complement = target - num
        if complement in seen:
            pairs.append((num, complement))
        seen.add(num)
    return pairs
n this example, we use a set seen to keep track of the numbers we have seen so far. For each number in the array, we calculate its complement (i.e., the number that adds up to target) and check if it is in the set. If it is, we add the pair (num, complement) to the list of pairs. If not, we add the current number to the set.
The time complexity of this solution is O(n), where n is the length of the array. The space complexity is O(n), as we use a set to store the numbers we have seen so far.
def sum_of_even_fibonacci_numbers(max_value):
    fib = [1, 2]
    while fib[-1] <= max_value:
        fib.append(fib[-1] + fib[-2])
    return sum(num for num in fib if num % 2 == 0)
In this example, we use a list fib to keep track of the Fibonacci numbers. We use a while loop to generate the next number in the series until we reach a number greater than max_value. Then, we use a list comprehension to find the sum of all even numbers in the fib list.
The time complexity of this solution is O(n), where n is the number of Fibonacci numbers we need to generate. The space complexity is O(n), as we use a list to store all the Fibonacci numbers.

code a function that takes 2 parameters and an algorithm, print out all the numbers between the 2 parameters that completes the algorithm

Here’s an example solution in Python to print all the numbers between two parameters start and end that complete a given algorithm:
def print_numbers_that_complete_algorithm(start, end, algorithm):
    for i in range(start, end + 1):
        if algorithm(i):
            print(i)
In this example, we use a for loop to iterate over the numbers between start and end, inclusive. For each number i, we pass it as an argument to the algorithm function. If the function returns True, we print the number.
The time complexity of this solution is O(n), where n is the number of numbers between start and end. The space complexity is O(1), as we only use a few variables in the loop.
You would call the function by passing in the desired start and end values, as well as a reference to the desired algorithm to use. The algorithm function should take a single number as an argument and return a boolean value indicating whether the number completes the algorithm or not.

How would you find the pairs of numbers that added to some specific number in an array?

Here is an example solution in Python to find pairs of numbers that add up to a given value target in an array:
def find_pairs_with_sum(arr, target):
    seen = set()
    pairs = []
    for num in arr:
        complement = target - num
        if complement in seen:
            pairs.append((num, complement))
        seen.add(num)
    return pairs
In this example, we use a set seen to keep track of the numbers we have seen so far. For each number in the array, we calculate its complement (i.e., the number that adds up to target) and check if it is in the set. If it is, we add the pair (num, complement) to the list of pairs. If not, we add the current number to the set.
The time complexity of this solution is O(n), where n is the length of the array. The space complexity is O(n), as we use a set to store the numbers we have seen so far.

In python code, given a json object with nested objects, write a function that flattens all the objects to a single key value dictionary. Do not use the lib that actually performs this function. { a:{b:c,d:e} } becomes {a_b:c, a_d:e} ( not, a:”b:c,d:e” }

Here is an example solution in Python to flatten a nested JSON object into a single key-value dictionary:
def flatten_json(data, parent_key='', sep='_'):
    result = {}
    for k, v in data.items():
        new_key = parent_key + sep + k if parent_key else k
        if isinstance(v, dict):
            result.update(flatten_json(v, new_key, sep))
        else:
            result[new_key] = v
    return result
In this example, we use a recursive function flatten_json that takes a JSON object data and two optional parameters, parent_key and sep, to keep track of the current key and separator. For each key-value pair (k, v) in the data, we construct a new key by concatenating the parent_key with the sep and the current key k. If the value v is another dictionary, we call flatten_json recursively with v as the new data and the new key as the parent_key. If v is not a dictionary, we add the key-value pair (new_key, v) to the result dictionary. Finally, we return the result dictionary.
The time complexity of this solution is O(n), where n is the number of keys in the JSON object, as we visit each key once. The space complexity is O(n), as we need to store the result dictionary.

Nagarro Solved

Automata Fixing

      

We Love to Support you

Go through our study material. Your Job is awaiting.

Recent Posts
Categories