Computer Networks Questions & Answers – #1: Transport layer aggregates data from different applications into a single stream before passing it to a) network layer b) data link layer c) application layer d) physical layer Show Answer Answer: a Explanation: None #2: Which one of the following is a transport layer protocol used in internet? … Read More →
Merging 2 Arrays without using Extra Space
Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B’s elements. Solution: Suppose we want to merge two arrays a1 and a2. a1 has n elements and has space for … Read More →
Largest Difference in an Array
You have an array of integers: int[] A = { 10, 3, 6, 8, 9, 4, 3 }; My goal is to find the largest difference between A[Q] and A[P] such that Q > P. If P = 1 and Q = 4 diff = A[Q] – A[P] diff = 9 – 3 diff = … Read More →
Check if Any Anagram of a String is Palindrome or Not
Examples: Input: str = “aaaad” Output: 1 // “aaaad” is a anagram of a palindrome “aadaa” Input: str = “abcd” Output: 0 // “abcd” is not a anagram of any palindrome. A Simple Solution is to take the input string, try every possible rotation of it and return true if a anagram is a palindrome. … Read More →
Remove Duplicates from a Linked List
Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list. Implemntation: Complexity: O(n^2) If you can sort the list in O(nlogn) then it will take O(nlogn). Post your solution in comments.
Largest subarray with equal number of 0s and 1s
Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array) Implementation: In this method,use two nested loops. The outer loop … Read More →
Recursive Spiral Order Traversal of Tree
This is also called zig-zag order traversal of a binary tree. Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to … Read More →
Recursive Level Order Traversal of a tree
Level order traversal is also called breadth first traversal for the tree. Non-Recursive solution of the problem is – Non-recursive Level Order Traversal Approach: There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes. … Read More →
DE Shaw Interview Questions – Set 2
Company: DE Shaw Off campus (Bangalore) (0-1 yr experience) Role : Software Developer Round 1: (Written Test) 20 Aptitude – Basic Quantitative Apt questions 20 Technical – C,C++ & JAVA related, Finding output, Basic Concepts Round 2: Q1. find maximum length BST in a given binary tree? Q2. Write an algorithm to find the absolute … Read More →
Print BST elements in range K1 and K2
Problem: Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1
Reverse a Linked List using Recursion
Problem: To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion”. Solution: In recursive approach, we need to move to the end of the node. But must stop just before the end of the node, and we should have … Read More →
Populate each next pointer to point to its next right node
Problem: Given a binary tree populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. You may assume that it is a perfect binary tree (i.e. all leaves are at the … Read More →
What’s going on ?