pirate
BAN USERStrong in DS
Looking for core development job.
- -1of 1 vote
AnswersGiven a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S' (you can use as many coins you want). If it's not possible to sum to 'S', return -1
- pirate in India
Input #01:
Coin denominations: { 5,5,5,5,5 }
Required sum (S): 11
Output #01:
-1| Report Duplicate | Flag | PURGE
Amazon SDE1 - -2of 2 votes
AnswersLongest increasing subsequence:
- pirate in United States
Given n numbers A1..An determine subsequence of maximum length values in the subsequence form a strictly increasing sequence.
ex: input 5,2,6,3,4,1,9,9,8,9,5
output: 2,3,4,8,9| Report Duplicate | Flag | PURGE
Yahoo Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersGiven a sequence of numbers A(1) ..A(n), find the continuous subsequenceA(i)..A(j) for which the sum of elements is maximum.
- pirate in India
condition: we should not select two contiguous numbers| Report Duplicate | Flag | PURGE
Yahoo Facebook Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven infinite array in which the first n cells contain integers in sorted order and rest filled with symbol $. Assume we don't know n value. Give algorithm that takes an integer k as input and finds a position in array in O(logn)
- pirate in India| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersMerge sort is better for linked lists. How and implement ?
- pirate in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersMaximum value Continuous Subsequence:
- pirate in United States
Given array A[n] find continuous subsequence a[i]..a[j] for which sum of elements in the subsequence is maximum.
Ex: {-2, 11, -4, 13, -5, -2} --> 11 - 4 +13 = 20
{1, -3, 4, -2, -1, 6} --> 4 -2 -1 +6 = 7
Time complexity should O(nlogn)| Report Duplicate | Flag | PURGE
Yahoo Microsoft Linkedin Software Engineer / Developer Algorithm Arrays - 0of 0 votes
AnswersWrite a program to get shortest path between two given nodes in a binary tree.
- pirate in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer C - 1of 1 vote
AnswersWhat will be the output of the program ?
- pirate in India
#include< stdio.h >
void fun(void *p);
int i;
int main()
{
void *vptr;
vptr = &i;
fun(vptr);
return 0;
}
void fun(void *p)
{
int **q;
q = (int**)&p;
printf("%d ", **q);
}| Report Duplicate | Flag | PURGE
Samsung Software Engineer / Developer
- 0 Answers Samsung R&D Interview process
First phase is written test 20 questions 45min.
- pirate April 13, 2013
Total 3 test papers that C,C++ and Java we can select any one option.
I selected C most of the questions on pointers. We need to give output values. If compile time error "Compile error" , if runtime error "runtime error" or else value.| Flag | PURGE
Assume M(i) represents maximum sum from 1 to i without selecting two contiguous numbers.
Base conditions
A[1] if i=1
Max{A[1],A[2]} if i=2
if i > 2
Max{ A[i] + M(i-2) , M(i-1)}
On this we can write recessive DP program as:
int maxsum(int A[], int n)
{
int M[n];
M[0]=a[0];
m[1] = (A[0]>A[1] ? A[0] : A[1]);
for(i=2;i<n;i++)
M[i]=(M[i-1]>M[i-2] + A[i] ? M[i-1] : M[i-2]+A[i]);
return M[n-1];
}
Time complexity O(n)
- pirate August 07, 2013For Intersection of two sorted arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.
int printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while(i < m && j < n)
{
if(arr1[i] < arr2[j])
i++;
else if(arr2[j] < arr1[i])
j++;
else /* if arr1[i] == arr2[j] */
{
printf(" %d ", arr2[j++]);
i++;
}
}
}
Time Complexity: O(m+n) for sorted arrarys.
For unsorted arrays Time complexity will be O(mlogm + nlogn)
Note: Sorting phase takes O(nlogn)
Virtual memory is a place on the hard drive (a swap file) to swap programs to if there's not enough physical memory (RAM) to hold them. A program that's swapped out can't run - another program has to be swapped out to make room for that program to be swapped back in. Every time you click on a program that's swapped out, it has to get swapped back in.
- pirate August 02, 2013The major difference between threads and processes is:
1 Threads share the address space of the process that created it; processes have their own address space.
2 Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process.
3 Threads can directly communicate with other threads of its process; processes must use interprocess communication to communicate with sibling processes.
4 Threads have almost no overhead; processes have considerable overhead.
5 New threads are easily created; new processes require duplication of the parent process.
6 Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.
7 Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process; changes to the parent process does not affect child processes.
why can you run multiple threads but not multiple processes?
On a uni-processor system, though true parallelism is not achieved, a process scheduling algorithm is applied and the processor is scheduled to execute each process one at a time yielding an illusion of concurrency.
Do the level order traversal. Print first element after each level change.
int leftMostBinaryTree(struct BinaryTreeNode *root)
{
if(!root) return 0;
struct Queue *Q=CreateQueue();
EnQueue(Q,root);
EnQueue(Q,NULL); //end of first level
while(!IsEmptyQueue(Q)){
root = DeQueue(Q);
if(root == NULL) {
if(!IsEmptyQueue(Q)) //Put another marker for next level
EnQueue(Q,NULL);
if(root->left) //Print left Most element
print("%d",Q->left);
}
else{
if(root->left)
Enqueue(Q,root->left);
if(root->right)
Enqueue(Q,root->right);
}
}
}
@vgeek:
Good try I appreciate, program gives correct solution but problem in time complexity in worst case.
If given input is in descending and last value is greatest then this time complexity is O(n^2) where everytime your j variable goes end.
ex: 10,9,8,7,6,5,4,3,2,1,11
@Ashish: solution always gives O(N)
In python we can write in simple
in pattern * means is repeated zero or more times (allowing a pattern to repeat zero times means it does not need to appear at all to match).
and pattern ? means the pattern appears zero or one time.
import re
def isMatching(a,b):
regexe=re.compile(b)
if regexe.search(a):
return true
else:
return false
Replace all elements using one traversal of the array.
The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element only if it is greater than current element otherwise -1.
input {16, 17, 4, 3, 5, 2},
output {17, -1, 5, 5, -1 -1}
void nearGreater(int arr[], int size)
{
int max_from_right = arr[size-1];
int current;
arr[size-1] = -1;
for(int i = size-2; i >= 0; i--)
{
current = arr[i];
if(max_from_right > current)
arr[i] = max_from_right;
else {
arr[i] = -1;
max_from_right = current;
}
}
O(n)
modified http://www.geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side
Logic is bit-wise and operation between networkaddress and IPaddress gives networkaddress.
1. Convert decimal dotted quad string to long integer
2. Convert a network address to a long integer
3. verify ip & net == net
Python code:
import socket,struct
def addressInNetwork(ip,net):
ipaddr = struct.unpack('L',socket.inet_aton(ip))[0]//long int IPaddr
netaddr,bits = net.split('/') //separate netaddress and mask
netmask = struct.unpack('L',socket.inet_aton(netaddr))[0] & ((2L<<int(bits)-1) - 1)
return ipaddr & netmask == netmask
returns true if it matches.
- pirate July 30, 2013single scan, logic start from end of arrays and compare
int[] top5LargestNumber(int[] A1,int[] A2,int[] A3)
{
int i,j,k,l=0;
int top5[];
if((A1.length + A2.length +A3.length) < 5)
return 0;
i = A1.length -1; // points to end
j = A2.length -1;
k = A3.length -1;
while(top5.length < 5) {
large = Max(A1[i],A2[j],A3[k]) ;
i-- if(large == A1[i]) //decrement large pointer
j-- if(large == A2[j])
k-- if(large == A3[k])
top5[l++] = large;
}
return top5;
}
@vgeek:
In-place means that you should update the original string rather than creating a new one.
In your recursive call every time creating new string "char str[] "
Its simple just swap begin with end chars
void reverse_in_place(char a[],int n) {
for(i=0; i< n/2 ; i ++)
swap(a[i], a[n-i]);
}
@oOZz great Algos
I am giving program for your first Algo.
void search(int A[],int n,int K) {
int i,j,temp;
Sort(A,n);
for(i=0,j=n-1;i<j;) {
temp = A[i] + A[j];
if(temp == K) {
printf("Elements found %d %d", i, j);
return;
}else if(temp < k)
i=i+1;
else
j=j-1;
}
return;
}
Even it works without Sort since we are checking all possibilities.
- pirate July 20, 2013We can solve this in two scans Time complexity: o(n) ans space complexity o(1)
1) In first scan for each of occurrence of an element add the array size to that element.
2) In second scan Divide the element value by n gives frequency of occurrence.
void repetitions(int A[],int n)
{
int i=0;
for(i=0;i<n;i++)
A[A[i] %n] + = n;
for(i=0;i<n;i++) {
frequency = A[i]/n;
element=i;
print("Element= %d , frequency = %d", element, frequency );
}
}
int LongestPath(struct BinaryTreeNode *root,int *ptr)
{
int left,right;
if(!root)
return 0;
left = LongestPath(root->left , ptr);
right = LongestPath(root->right , ptr);
if(left+right > *ptr)
*ptr = left+right;
if(left>right)
return left +1;
else
return right + 1;
}
Q4 Answer)
struct BinaryTreeNode *MirrorOfBinaryTree(struct BinaryTreeNode *root)
{
struct BinaryTreeNode *temp;
if(root) {
MirrorOfBinaryTree(root->left);
MirrorOfBinaryTree(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
return root;
}
Least common Ancestor Tested this code
struct BinaryTreeNode *LCA(struct BinaryTreeNode *root,struct BinaryTreeNode *a,struct BinaryTreeNode *b) {
struct BinaryTreeNode *left,*right;
if (root == NULL) return NULL;
if(root == a || root == b) return root;
left = LCA(root->left,a,b)
right = LCA(root->right,a,b)
if(left && right)
return root;
else
return (left? left:right)
}
Python code:
char MostCommonChar(String str, int num):
char_count = char_count(string) # returns each char to its count dictionary
chars_dict = sorted(char_count.values())
char_dict = chars_dict[num-1]
print char_dict[0]
#Hasing key is char and value is count
def char_count_dict(string):
char_count = {} #Map each char to its count
for char in string
if char in char_count:
char_count[char] = char_count[char] + 1
else:
char_count[char] = 1
return char_count
SwapListNodes(struct *node head)
{
length = LengthOfList(struct *head) // before we need length
if k>length
exception "K is more then length"
middle = length/2
if k == middle # middle node no need to swap
return true
struct *node temp,prev1,prev2,k1,k2
count =1
k1=k2=head
// travelling nodes
while(count == k) {
prev1=k1
k1=k1->next
count ++
}
count=1
while(count == length-k+1) {
prev2=k2
k2=k2->next
count ++
}
//swapping nodes
prev1->next = k2
prev2->next = k1
temp = k1
k1->next=k2->next
k2->next=temp->next
return head
}
it fails in test case {5,11} , s=11
- pirate September 14, 2013